gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-28 18:31:25 37 4
gpt4 key购买 nike

R 中有一个名为stringdistpackage,它包含计算Levenshtein 字符串距离的函数。这个包有两个问题:

1st 它不适用于大字符串,例如:

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 视为一个元素而不是由 3,4,7 组成的字符串,因为 3 ,4,7 是另一个单独的数字)。这些文件有大约 250000 行。我想知道这些文件彼此之间有多相似。我猜 10k*10k 大小是问题所在。但是提到了 here Levenshtein 算法,它只使用 2*10k 大小(如果两个字符串都是 10k 长)。我想诀窍是它只计算结果而忘记了结果是如何计算的,但这对我来说没问题。汉明距离对我来说不够,因为我需要考虑插入、删除、替换,在汉明中,这两个字符串 1234567890 0123456789 是完全不同的,但在 Levenshtein 中它们是相似的。

最佳答案

这里是内存问题的解决方案:

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

关于python - Levenshtein 实现能够处理大字符串和向量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36863750/

37 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com