能够处理大字符串和向量的Levenshtein实现

Question

能够处理大字符串和向量的Levenshtein实现

pythonrperllevenshtein-distancestringdist

3

在R语言中有一个名为stringdist的package，其中包含用于计算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 个向量元素不同）。在这种情况下，我可以获取非零值并计数，例如：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）？非常感谢。

PS 我有多个文件，每行包含1~500之间的数字（这就是为什么我需要将例如347视为一个元素而不是由3、4、7组成的字符串，因为3、4、7是另一个单独的数字）。这些文件大约有250000行。我想知道这些文件彼此之间有多相似。我猜10k*10k的大小是问题所在。但here提到了Levenshtein算法，它只使用2*10k的大小（如果两个字符串都是10k长）。我想诀窍在于它只计算结果并忘记了结果是如何计算的，但这对我来说没问题。汉明距离对我来说不够，因为我需要考虑插入、删除、替换，在汉明中，这两个字符串1234567890 0123456789是完全不同的，但在Levenshtein中它们是相似的。

- Wakan Tanka

100000 * 100000 是10GB。不确定你的目标是什么。为什么要计算如此大的字符串上的 stringdist？ - Gopala

例如，在stringdist中对于相同的两个字符串，使用method=JW会产生一个结果。算法不同，不需要平方数量的内存。 - Gopala

这可能会有所帮助：https://dev59.com/oW855IYBdhLWcg3w-JQr - Gopala

@Gopala 我可以在所有元素前加上零，得到 007 和 455，但问题是这会使已经很大的字符串变得更大，所以我想避免这种情况，改用向量。 - Wakan Tanka

我为你找到了解决方案！ :) 在R中尝试使用RecordLinkage包中的levenshteinDist。它使用了内存高效的版本。您仍然需要使用paste将您的向量转换为字符串以进行输入。 - Gopala

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gopala · Accepted Answer

这是一个解决内存问题的方案：

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