大きな文字列とベクトルを扱うことができるLevenshteinの実装

Question

stringdistという名前のは、Levenshtein文字列距離を計算するための関数を含んでいます。私はこのパッケージには二つの問題があります。

第一をそれは例えば、大きな文字列を使用していますしない：ベクトルで

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 

第二距離はむしろ全体のベクトルあたりよりベクトル要素の文字ごとに計算されています

a.vec <- c(1, 2, 3, 4, 5, 666) 
b.vec <- c(1, 2, 4, 3, 6, 777) 
stringdist(a.vec, b.vec, method = "lv") 
# [1] 0 0 1 1 1 3 

4つの置換が必要である（対応する位置の4つのベクトル要素が異なるため）、最後のコマンド4から結果を得たいと考えています。この場合、0ではない値を取得し、例えばr <- stringdist(a.vec, b.vec, method = "lv"); length(r[r!=0])とカウントできます。しかし、それは、たとえば次の作品はありません：

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 

は私が最後のコマンド1（第一のベクトルで第一位に2を挿入）からの結果を持っていると思います。

PSあり、実装に内蔵されているが、それはまた、大規模な文字列を使用していますしない（と私はそれが出力だ理解していないので、私はそれがベクターで働いているか分からない正直に言うと）：

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) 

私の要件を満たす実装（できればpython、perl、またはR）がありますか？どうもありがとうございました。

PPS私は、各行に1〜500の数字が含まれている複数のファイルを持っています（これは、347を1要素として扱う必要があるためです。別の別の番号です）。これらのファイルには〜250000行があります。そして私は、それらのファイルが互いにどれほど類似しているかを知りたい。私は10k * 10kサイズが問題だと思います。しかし、hereは、2 * 10kサイズのみを使用するLevenshteinアルゴリズム（両方の文字列が10kの長さの場合）に言及されています。私はトリックは、結果を計算し、結果が計算された方法を忘れるということだと思いますが、これは私にとっては問題ありません。私は考慮に入れて挿入、削除、置換を考慮する必要があるので、ハミング距離は十分ではありません。1234567890は完全に異なっていますが、Levenshteinでは似ています。ここで

Answer 1

は、メモリの問題を解決する：

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 

はまだそれは自動的にパッケージが想定されていないようpasteを使用して文字列にベクトルを変換する必要があります。ほとんどのユースケースでは、ベクトル化された操作が必要です。

彼らは代わりに文字列として扱われることを得るための方法については、以下を参照してください：

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