Diskussion:Gestalt Pattern Matching
Letzter Kommentar: vor 5 Jahren von Xqt in Abschnitt Beschreibung des Algorithmus
Beschreibung des Algorithmus
BearbeitenDer Abschnitt „Algorithmus“ schreibt bisher nichts zum Algorithmus, sondern nur zur Definition des Ähnlichkeitsmaßes.—Godung Gwahag (Diskussion) 09:01, 12. Mär. 2019 (CET)
- 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)
- Ein Algorithmus ist bekanntlich ein Berechnungsverfahren.—Godung Gwahag (Diskussion) 08:11, 16. Mär. 2019 (CET)
- 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)
- Ein Algorithmus ist bekanntlich ein Berechnungsverfahren.—Godung Gwahag (Diskussion) 08:11, 16. Mär. 2019 (CET)
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)
- 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)
- 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)
- 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)
- Die dargestellte Funktion ist nur ein cut-off, nicht der komplette Algorithmus. @xqt 10:47, 2. Jun. 2019 (CEST)
- Sollte man das nicht erwähnen? Oder das Stückchen ganz weglassen? --Berthold Werner (Diskussion) 10:40, 3. Jun. 2019 (CEST)
- 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)
- Ähm, steht ja schon da :) @xqt 12:21, 21. Jun. 2019 (CEST)
- Die dargestellte Funktion ist nur ein cut-off, nicht der komplette Algorithmus. @xqt 10:47, 2. Jun. 2019 (CEST)
- 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)