Diskussion:Gestalt Pattern Matching

Letzter Kommentar: vor 5 Jahren von Xqt in Abschnitt Beschreibung des Algorithmus

Beschreibung des Algorithmus

Bearbeiten

Der Abschnitt „Algorithmus“ schreibt bisher nichts zum Algorithmus, sondern nur zur Definition des Ähnlichkeitsmaßes.—Godung Gwahag (Diskussion) 09:01, 12. Mär. 2019 (CET)Beantworten

Wo siehst Du den Unterschied? Meinst Du die Implementierung? Da gäbe es noch Ergänzungsmöglichkeiten.  @xqt 01:52, 16. Mär. 2019 (CET)Beantworten
Ein Algorithmus ist bekanntlich ein Berechnungsverfahren.—Godung Gwahag (Diskussion) 08:11, 16. Mär. 2019 (CET)Beantworten
Ja und diese ist in Prosa für Km auch beschrieben wird und für das Ähnlickeitsmaß darauf aufbauend auch formal. Will mal versuchen, das deutlicher herauszuarbeiten, ohne die Quellenlage verlassen zu müssen.  @xqt 08:36, 16. Mär. 2019 (CET)Beantworten

Also erstmal ist die Formulierung im Artikel irreführend, weil erst von übereinstimmenden Zeichen und dann von der längsten übereinstimmenden Sequenz die Rede ist. Gemeint ist - wie man am Beispiel erkennt - offensichtlich Letzteres. Und dann wird eben nicht gesagt, mit welchem Verfahren diese längste Sequenz gefunden wird. Einfaches Druchprobieren aller Möglichkeiten führt jedenfalls nicht zu den angegebenen Laufzeiten.—Godung Gwahag (Diskussion) 09:01, 16. Mär. 2019 (CET)Beantworten

Vielen Dank für die Anregung. Hier ist die Quellenlage auch etwas dünn. Da kann man dann nur auf mögliche Implementierungen zurückgreifen.  @xqt 10:37, 16. Mär. 2019 (CET)Beantworten
Ich habe einige Änderungen an der verbalen Bespreibung vorgenommen. In Verbindung mit dem nachfolgenden Beispiel sollte nun eigentlich alles klar sein.--FerdiBf (Diskussion) 11:19, 18. Mär. 2019 (CET)Beantworten
Unter https://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/DDJ/1988/8807/8807c/8807c.htm gibt es eine Beschreibung an der John W. Ratcliff mitgearbeitet hat. So wie ich das verstehe, sucht das ursprüngliche Verfahren zunächst die längste Übereinstimmung und arbeitet sich dann rekursiv durch den jeweils verbleibenden linken und rechten Teil. Außerdem stellt sich für mich bei dem Python Beispiel die Frage, wieso die Laufzeit maximal O(n^2) sein soll. Dort wird doch nur die doppelte Länge des kürzeren Strings zur Summe der Längen ins Verhältnis gesetzt. --Berthold Werner (Diskussion) 08:28, 6. Mai 2019 (CEST)Beantworten
Die dargestellte Funktion ist nur ein cut-off, nicht der komplette Algorithmus.  @xqt 10:47, 2. Jun. 2019 (CEST)Beantworten
Sollte man das nicht erwähnen? Oder das Stückchen ganz weglassen? --Berthold Werner (Diskussion) 10:40, 3. Jun. 2019 (CEST)Beantworten
Es ist eine Obere Schranke. Ich werde das zusammen mit einer weiteren noch gelegentlich ergänzen bei Gelegenheit.  @xqt 12:20, 21. Jun. 2019 (CEST)Beantworten
Ähm, steht ja schon da :)  @xqt 12:21, 21. Jun. 2019 (CEST)Beantworten