Реализация Levenshtein, способная работать с большими струнами и векторами

Question

В R есть package, который содержит функции для вычисления длины строки Левенштейна. У меня есть две проблемы, связанные с этим пакетом:

первого Он не работает с большими строками, например:

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-й Расстояния в векторах вычисляются на символы элемента вектора, а не на весь вектор:

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 на 1-й позиции в 1-й вектор).

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 как один элемент, а не как строку, состоящую из 3,4,7, потому что 3,4,7 представляют собой другие отдельные номера). Эти файлы имеют ~ 250000 строк. И я хочу знать, насколько похожи эти файлы друг другу. Я думаю, что проблема 10k * 10k. Но упоминается here алгоритм Левенштейна, который использует только размер 2 * 10k (если обе строки имеют длину 10k). Я думаю, трюк в том, что он только вычисляет результат и забывает, КАК результат был вычислен, но для меня это нормально. Расстояние Хэмминга недостаточно для меня, потому что мне нужно учитывать вставки, удаления, замены, в Хэмминге эти две строки 1234567890 совершенно разные, но в Левенштейне они похожи.

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