Levenshtein Implementierung fähig mit großen Strings und Vektoren zu arbeiten

Question

Es gibt package namens stringdist in R, die Funktionen zur Berechnung Levenshtein Zeichenfolge Entfernung enthält. Ich habe zwei Probleme mit diesem Paket:

1. Es ist nicht mit großen Strings zB nicht funktioniert:

set.seed(1) 
a.str <- paste(sample(0:9, 100000, replace = T), collapse="") 

set.seed(2) 
b.str <- paste(sample(0:9, 100000, replace = T), collapse="") 

stringdist(a.str, b.str, method = "lv") 
# THE LAST COMMAND RESTARTS R SESSION 

2.e Entfernungen in Vektoren berechnet werden pro Zeichen der Vektor-Elements anstatt pro ganzem Vektor:

Ich hätte gerne das Ergebnis von letzten Befehl 4: weil 4 Substitutionen benötigt werden (4 Vektorelemente auf entsprechenden Positionen sind unterschiedlich). In diesem Fall kann ich Werte abrufen, die nicht 0 sind, und sie z. B. zählen: r <- stringdist(a.vec, b.vec, method = "lv"); length(r[r!=0]). Aber es hat nicht funktioniert in folgendem Beispiel:

a.vec <- c(1, 2, 3) 
b.vec <- c(1, 2, 2, 3) 
stringdist(a.vec, b.vec, method = "lv") 
# [1] 0 0 1 1 
# Warning message: 
# In stringdist(a.vec, b.vec, method = "lv") : 
# longer object length is not a multiple of shorter object length 

Ich mag würde das Ergebnis von den letzten Befehl haben 1 (Einsatz 2 in der 1. Position im ersten Vektor).

PS gibt es auch bei der Umsetzung gebaut aber es funktioniert auch nicht mit großen Strings (und um ehrlich zu sein, ich habe keine Ahnung, wie es mit Vektoren arbeitet, weil ich es Ausgabe nicht verstehen):

adist(a.str,b.str, counts = T) 
# Error in adist(a.str, b.str, counts = T) : 
# 'Calloc' could not allocate memory (1410265409 of 8 bytes) 

Gibt es eine Implementierung (vorzugsweise in Python, Perl oder R), die meine Anforderungen erfüllt? Vielen Dank.

PPS Ich habe mehrere Dateien, in denen jede Zeile Zahlen von 1 ~ 500 enthält (deshalb muss ich zB 347 als ein Element behandeln und nicht als eine Folge von 3,4,7, weil 3,4,7 sind andere separate Zahlen). Diese Dateien haben ~ 250000 Zeilen. Und ich möchte wissen, wie ähnlich diese Dateien zueinander sind. Ich denke, dass 10k * 10k Größe das Problem ist. Aber here erwähnt Levenshtein Algorithmus, der nur 2 * 10k Größe verwendet (wenn beide Zeichenfolgen 10k lang sind). Ich denke, der Trick ist, dass es nur das Ergebnis berechnet und vergisst, wie das Ergebnis berechnet wurde, aber das ist in Ordnung für mich. Die Hammingdistanz ist für mich nicht ausreichend, da ich Einfügungen, Löschungen, Ersetzungen berücksichtigen muss, in Hamming sind diese beiden Strings 1234567890 völlig anders, aber in Levenshtein sind sie ähnlich.

Answer 1

Hier ist eine Lösung für Speicherproblem:

library(RecordLinkage) 

set.seed(1) 
a.str <- paste(sample(0:9, 100000, replace = T), collapse="") 
set.seed(2) 
b.str <- paste(sample(0:9, 100000, replace = T), collapse="") 
levenshteinDist(a.str, b.str) 
[1] 73969 

Noch müssen Vektoren in Strings konvertieren, indem Sie paste als dass nicht automatisch durch das Paket angenommen wird. Die meisten Anwendungsfälle möchten eine vektorisierte Operation.

Siehe unten für eine Art und Weise, sie zu behandeln als Strings statt zu bekommen:

a.vec <- c(1, 2, 3, 4, 5, 666) 
b.vec <- c(1, 2, 4, 3, 6, 777) 
levenshteinDist(paste(a.vec, collapse = ''), paste(b.vec, collapse = '')) 
[1] 5