___ qstnhdr ___ Wie ermittle ich den längsten ähnlichen Teil mehrerer Strings?
___ answer500005 ___
Mein erster Instinkt besteht darin, eine Schleife auszuführen, wobei ich das nächste Zeichen aus jeder Zeichenfolge nehme, bis die Zeichen nicht mehr übereinstimmen. Zählen Sie, an welcher Position in der Zeichenfolge Sie sich befinden, und nehmen Sie dann eine Teilzeichenfolge (von jeder der drei Zeichenfolgen) von 0 bis zu der Position, bevor die Zeichen nicht gleich sind.
In Perl müssen Sie die Zeichenfolge zuerst in Zeichen aufteilen, indem Sie etwas wie
verwenden
my
(Teilen auf ein leeres Zeichen setzt jedes Zeichen in ein eigenes Element des Arrays)
Dann mache eine Schleife, vielleicht insgesamt:
%Vor%
Oder zumindest etwas in dieser Richtung. Verzeihen Sie, wenn das nicht funktioniert, ist meine Perl ein wenig eingerostet.
___ antwort500518 ___
Bearbeiten: Es tut mir leid für einen Fehler. Mein Mitleid, dass ich übersehen habe, dass die Verwendung von countit(x, q{}) variable in substr ein großer Fehler ist. Diese Zeichenfolge wird im Benchmark-Modul ausgewertet und @str war dort leer. Diese Lösung ist nicht so schnell wie ich sie vorgestellt habe. Siehe Korrektur unten. Es tut mir wieder leid.
Perl kann schnell sein:
%Vor%
Testsuite:
%Vor%
Testergebnis:
%Vor%
Das bedeutet, dass reine Perl-Lösung mit %code% etwa 20% schneller ist als Roy's Lösung bei Ihrem Testfall und eine Präfix-Suche dauert ca. 50us. Es ist nicht notwendig, XS zu verwenden, es sei denn, Ihre Daten oder Leistungserwartungen sind größer.
___ qstntxt ___
Wie im Titel beschrieben, versuche ich einen Weg zu finden, um den längsten Teil der Ähnlichkeit zwischen mehreren Strings programmatisch zu bestimmen.
Beispiel:
Im Idealfall würde ich %code% zurückbekommen, weil das der längste Teil ist, der für alle 3 Strings gemeinsam ist.
Insbesondere suche ich nach einer Perl-Lösung, aber eine Lösung in jeder Sprache (oder sogar Pseudo-Sprache) würde ausreichen.
Aus den Kommentaren: ja, nur zu Beginn; aber es gibt die Möglichkeit, einen anderen Eintrag in der Liste zu haben, der für diese Frage ignoriert würde.
___ answer499988 ___
Es klingt, als ob Sie den k-common-Teilzeichenalgorithmus möchten. Es ist außergewöhnlich einfach zu programmieren und ein gutes Beispiel für dynamische Programmierung.
___ answer9489829 ___
Schneller als oben, verwendet die native binary xor-Funktion von Perl, die aus perlmongers-Lösung (die $ + [0] funktioniert nicht für mich):
%Vor%
___ answer500685 ___
___ answer499990 ___
Wenn Sie nach "längster gemeinsamer Teilstring" suchen, erhalten Sie einige gute Hinweise für den allgemeinen Fall, dass die Sequenzen nicht am Anfang der Strings beginnen müssen.
ZB Ссылка .
Mathematica hat dafür eine Funktion eingebaut:
Ссылка (Beachten Sie, dass sie zusammenhängende Untersequenz bedeuten, dh Teilzeichenfolge, die was du willst.)
Wenn Sie nur am längsten gemeinsamen Präfix interessiert, dann sollte es viel schneller sein, nur für i von 0 bis die ith Zeichen nicht übereinstimmen und substr (s, 0, i-1) zurückgeben.
___ tag123perl ___ Perl ist eine prozedurale, allgemeine Programmiersprache für allgemeine Zwecke, die für ihre native Unterstützung von regulären Ausdrücken und String-Parsing-Funktionen bekannt ist. Bitte verwenden Sie diesen Tag für Fragen zu Perl im Allgemeinen. Für Dinge, die mit der neuen (aber verwandten) Sprache "Perl 6" zu tun haben, verwenden Sie bitte das perl6-Tag. Verwenden Sie für reguläre Ausdrücke nach Perl-Art in anderen Sprachen das Regex-Tag oder, falls sie auf der PCRE-Bibliothek basieren, das PCRE-Tag.
___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht.
___ tag123string ___ Eine Zeichenfolge ist eine endliche Abfolge von Symbolen, die üblicherweise für Text verwendet wird, manchmal jedoch auch für beliebige Daten.
___ tag123ähnlichkeit ___ Ähnlichkeitsmaße quantifizieren, wie viel gleichartige Objekte (z. B. Dokumente, Merkmalsvektoren) sind.
___ answer500100 ___
Die bereits von Brett Daniel gegebene Referenz für den Wikipedia-Eintrag auf " Longest common substring problem " ist eine sehr gute allgemeine Referenz (mit Pseudocode) für Ihre Frage wie angegeben. Der Algorithmus kann jedoch exponentiell sein. Und es sieht so aus, als ob Sie tatsächlich einen Algorithmus für den längsten gemeinsamen Präfix wünschen, der ein viel einfacherer Algorithmus ist.
Hier ist der, den ich für den längsten gemeinsamen Präfix (und einen Verweis auf die ursprüngliche URL) verwende:
%Vor%
Wenn Sie wirklich eine LCSS-Implementierung wünschen, lesen Sie diese Diskussionen ( Längste gemeinsame Teilzeichenfolge und Längste gemeinsame Subsequenz ) auf PerlMonks.org. Tree :: Suffix wäre wahrscheinlich die beste allgemeine Lösung für Sie und implementiert nach meinem Wissen den besten Algorithmus. Leider sind die letzten Builds kaputt. Aber eine funktionierende Subroutine existiert innerhalb der Diskussionen, die auf PerlMonks in diesem Beitrag von Limbic ~ Region referenziert werden (hier mit Ihrem Daten).
%Vor%
___