Mig*_*uel 4 c c++ algorithm performance levenshtein-distance
晚安,
我一直在使用模糊字符串匹配已经有一段时间了,并且使用带有一些指针的C,我可以写一个非常快的(根据我的需要)实现两个字符串之间的Levenshtein距离.我试图使用不安全的代码和fixed关键字将代码移植到C#,但性能却慢了.所以我选择构建一个C++ DLL并使用[DllImport]来自C#,自动编组每个字符串.问题是,在分析之后,这仍然是我的程序中最耗时的部分,占用程序总运行时间的50-57%.由于我认为我需要做一些繁重的工作,包含大量来自300万个数据库记录的文本字段的子字符串,我认为Levenshtein距离所采用的时间几乎是不可接受的.那就是,我想知道您是否对下面的代码有任何建议,包括算法或编程相关,或者您是否知道有任何更好的算法来计算这个距离？
#define Inicio1 (*(BufferVar))
#define Inicio2 (*(BufferVar+1))
#define Fim1 (*(BufferVar+2))
#define Fim2 (*(BufferVar+3))
#define IndLinha (*(BufferVar+4))
#define IndCol (*(BufferVar+5))
#define CompLinha (*(BufferVar+6))
#define TamTmp (*(BufferVar+7))
int __DistanciaEdicao (char * Termo1, char * Termo2, int TamTermo1, int TamTermo2, int * BufferTab, int * BufferVar)
{
*(BufferVar) = *(BufferVar + 1) = 0;
*(BufferVar + 2) = TamTermo1 - 1;
*(BufferVar + 3) = TamTermo2 - 1;
while ((Inicio1 <= *(BufferVar + 2)) && (Inicio2 <= *(BufferVar + 3)) && *(Termo1 + Inicio1) == *(Termo2 + Inicio2))
Inicio1 = ++Inicio2;
if (Inicio2 > Fim2) return (Fim1 - Inicio1 + 1);
while ((Fim1 >= 0) && (Fim2 >= 0) && *(Termo1 + Fim1) == *(Termo2 + Fim2))
{ Fim1--; Fim2--;}
if (Inicio2 > Fim2) return (Fim1 - Inicio1 + 1);
TamTermo1 = Fim1 - Inicio1 + 1;
TamTermo2 = Fim2 - Inicio2 + 1;
CompLinha = ((TamTermo1 > TamTermo2) ? TamTermo1 : TamTermo2) + 1;
for (IndLinha = 0; IndLinha <= TamTermo2; *(BufferTab + CompLinha * IndLinha) = IndLinha++);
for (IndCol = 0; IndCol <= TamTermo1; *(BufferTab + IndCol) = IndCol++);
for (IndCol = 1; IndCol <= TamTermo1; IndCol++)
for (IndLinha = 1; IndLinha <= TamTermo2; IndLinha++)
*(BufferTab + CompLinha * IndLinha + IndCol) = ((*(Termo1 + (IndCol + Inicio1 - 1)) == *(Termo2 + (IndLinha + Inicio2 - 1))) ? *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)) : ((*(BufferTab + CompLinha * (IndLinha - 1) + IndCol) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) : ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)))) + 1);
return *(BufferTab + CompLinha * TamTermo2 + TamTermo1);
}
请注意,BufferVar和BufferTab是两个外部int *(在这种情况下,int[]变量是从C#编组的),我没有在每个函数调用中实例化,以使整个过程更快.尽管如此,这段代码对我的需求来说还是很慢的.任何人都可以给我一些建议,或者,如果可能的话,提供一些更好的代码？
编辑:距离不能限制,我需要实际距离.
非常感谢你,
1.蛮力
这是Python中Levenshtein距离的实现.
def levenshtein_matrix(lhs, rhs):
def move(index): return (index+1)%2
m = len(lhs)
n = len(rhs)
states = [range(n+1), [0,]*(n+1)]
previous = 0
current = 1
for i in range(1, m+1):
states[current][0] = i
for j in range(1,n+1):
add = states[current][j-1] + 1
sub = states[previous][j] + 1
repl = states[previous][j-1] + abs(cmp(lhs[i-1], rhs[j-1]))
states[current][j] = min( repl, min(add,sub) )
previous = move(previous)
current = move(current)
return states[previous][n]
这是典型的动态编程算法,只是利用了因为只需要最后一行,所以一次只保留两行就足够了.
对于C++实现,您可以查看LLVM的一个(第70-130行),注意使用固定大小的堆栈分配数组,仅在必要时由动态分配的数组替换.
我只是无法跟进你的代码来尝试和诊断它...所以让我们改变攻击角度.我们将完全改变算法,而不是微距离优化距离.
2.做得更好:使用字典
你面临的一个问题是你可以做得更好.
第一个注意事项是距离是对称的,虽然它不会改变总体复杂性,但它会将所需时间减半.
第二个是因为你实际上有一个已知单词的字典,你可以建立在它上面:"actor"和"actual"共享一个共同的前缀("act"),因此你不需要重新计算第一阶段.
这可以使用Trie(或任何其他排序结构)来利用来存储您的单词.接下来,您将使用一个单词,并利用前缀计算其相对于存储在字典中的所有单词的距离.
让我们举一个例子dic = ["actor", "actual", "addict", "atchoum"],我们想计算距离word = "atchoum"(我们在此时将其从字典中删除)
matrix = [[0, 1, 2, 3, 4, 5, 6, 7]][[0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 1, 2, 3, 4, 5, 6]][[0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 1, 2, 3, 4, 5, 6], [2, 1, 1, 2, 3, 4, 5, 6]][[..], [..], [..], [..]][[..], [..], [..], [..], [..]]这里重要的是倒带步骤,通过保留为前一个单词完成的计算,您可以与之共享一个长度良好的前缀,从而有效地节省了大量工作.
请注意,这通过简单的堆栈实现,并且不需要任何递归调用.