Levenshtein距离算法优于O(n*m)？
Jas*_*son 40 algorithm big-o ios levenshtein-distance
我一直在寻找一种先进的levenshtein距离算法,到目前为止我发现的最好的是O(n*m),其中n和m是两个弦的长度.算法处于这种规模的原因是因为空间而不是时间,创建了两个字符串的矩阵,例如:
是否有一个公开的levenshtein算法,它比O(n*m)更好？我并不反对看高级计算机科学论文和研究,但却找不到任何东西.我找到了一家名为Exorbyte的公司,该公司据称已经建立了超级先进且超快的Levenshtein算法,但当然这是商业秘密.我正在构建一个iPhone应用程序,我想使用Levenshtein距离计算.有一个Objective-c实现可用,但由于iPod和iPhone上的内存有限,我想找到一个更好的算法,如果可能的话.
sre*_*ean 42
您是否有兴趣减少时间复杂度或空间复杂度？平均时间复杂度可以降低O(n + d ^ 2),其中n是较长字符串的长度,d是编辑距离.如果您只对编辑距离感兴趣并且对重建编辑序列不感兴趣,则只需要将矩阵的最后两行保留在内存中,这样就是order(n).
如果您能够进行近似,则存在多对数近似.
对于O(n + d ^ 2)算法,寻找Ukkonen的优化或其增强型Ukkonen.我所知道的最好的近似是 Andoni,Krauthgamer,Onak
- Ukkonen近似字符串匹配算法的原始论文是http://www.cs.helsinki.fi/u/ukkonen/InfCont85.PDF. (3认同)
- 我用它来进行 DNA 比对；我们首先检查序列的长度，因为更新 Ukkonen 屏障的逻辑比计算整个数组更重。另外，请查看“时间扭曲、字符串编辑和大分子：序列比较的理论与实践”以了解更多详细信息。 (2认同)
Nic*_*son 10
如果您只想要阈值函数 - 例如,测试距离是否低于某个阈值 - 您可以通过仅计算阵列中主对角线两侧的n值来减少时间和空间复杂度.您还可以使用Levenshtein Automata在O(n)时间内针对单个基本单词评估多个单词 - 并且自动机的构造也可以在O(m)时间内完成.