R - längste gemeinsame Substring

Question

Kennt jemand ein R -Paket, das löst? Das am längsten häufige Substringproblem? Ich suche etwas schnelles, das an Vektoren funktionieren könnte.

Answer 1

Schauen Sie sich das "rlibstree" -Paket auf Omegahat an: http://www.omegahat.org/rlibstree/.

Dies verwendet http://www.icir.org/christian/libstree/.

Answer 2

Sie sollten sich das ansehen LCS Die Funktion von qualV Paket. Es ist c-implementiert und daher ziemlich effizient.

Answer 3

Die Frage hier ist nicht ganz klar, ob die beabsichtigte Anwendung der Lösung auf das am längsten gemeinsame Substringproblem. Eine gemeinsame Anwendung, auf die ich begegnet ist, stimmt zwischen den Namen in verschiedenen Datensätzen überein. Das stringdist Paket hat eine nützliche Funktion amatch() was ich für diese Aufgabe geeignet finde.

In Kürze, amatch() wird als Eingabe zwei Vektoren annehmen, der erste ist x Der Vektor der Zeichenfolgen, aus denen Sie Übereinstimmungen finden möchten (dies kann auch nur eine einzelne Zeichenfolge sein), der zweite ist table, Das ist der Vektor der Zeichenfolgen, die Sie mit dem längsten gemeinsamen Substring vergleiche und die Übereinstimmung wählen möchten. amatch() wird dann einen Vektor zurückgeben, dessen Länge der von entspricht x - Jedes Element dieses Ergebnisses ist ein Index in table Das enthält die beste Übereinstimmung.

Einzelheiten: amatch() nimmt ein method Argument, das Sie angeben lcs Wenn Sie das längste gemeinsame Substring übereinstimmen möchten. Es gibt viele andere Optionen für verschiedene String -Matching -Techniken (z. B. Levenshtein -Distanz). Es gibt auch eine obligatorische maxDist Streit. Wenn alle Saiten in table sind größere "Entfernungen" von einer bestimmten Zeichenfolge in x, dann amatch() wird zurückkehren NA für dieses Element seiner Ausgabe. "Distanz" wird je nach dem von Ihnen gewählten String -Matching -Algorithmus unterschiedlich definiert. Für LCs bedeutet es (mehr oder weniger) nur, wie viele verschiedene (nicht passende) Zeichen es gibt. Weitere Informationen finden Sie unter Dokumentation.

Parallelisierung: Ein weiteres schönes Merkmal von amatch() ist, dass es den Vorgang automatisch für Sie parallelisieren und angemessene Vermutungen zu den zu verwendenden Systemressourcen vorliegt. Wenn Sie mehr Kontrolle darüber haben möchten, können Sie die umschalten nthread Streit.

Beispielanwendung:

library(stringdist)

Names1 = c(
"SILVER EAGLE REFINING, INC. (SW)",
"ANTELOPE REFINING",
"ANTELOPE REFINING (DOUGLAS FACILITY)"
)

Names2 = c(
"Mobile Concrete, Inc.",
"Antelope Refining, LLC. ",
"Silver Eagle Refining Inc."
)

Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)
Match_Idx
# [1] 3 2 2

Matches = data.frame(Names1, Names2[Match_Idx])
Matches

#                                 Names1          Names2.Match_Idx.
# 1     silver eagle refining, inc. (sw) silver eagle refining inc.
# 2                    antelope refining   antelope refining, llc. 
# 3 antelope refining (douglas facility)   antelope refining, llc. 

### Compare Matches:

Matches$Distance = stringdist(Matches$Names1, Matches$Match, method = 'lcs')

Auch im Gegensatz zu Funktionen wie LCS aus qualV, Dies wird nicht "Subsequence" -Aghte berücksichtigt, bei denen Zwischenzeichen ignoriert werden, um eine Übereinstimmung zu bilden (wie diskutiert hier). Zum Beispiel sehen Sie Folgendes:

Names1 = c(
"hello"
)

Names2 = c(
"hel123l5678o",
"hell"
)

Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)

Matches = data.frame(Names1, Match = Names2[Match_Idx])
Matches

# 1  hello  hell

Answer 4

Ich weiß nicht R, aber ich habe Hirschbergs Algorithmus implementiert, der schnell ist und nicht zu viel Platz verbraucht.

Wie ich mich erinnere, sind es nur 2 oder 3 rekursiv als kurze Funktionen bezeichnet.

Hier ist ein Link:http://wordaligned.org/articles/longest-common-subsequence

Zögern Sie also nicht, es in R zu implementieren, es lohnt sich, es ist ein sehr interessanter Algorithmus.