string - 有效地计算一个字符串和一大组其他字符串之间的编辑距离？

Question

用例是自动完成选项，我想根据它们与固定字符串的相似程度对一大组其他字符串进行排名。

是否有任何类似 DFA RegEx 的 SCSS 可以比每个选项解决方案的重新开始做得更好？

问的人this question似乎知道解决方案，但未列出任何来源。

(附注:欢迎“阅读此链接”输入答案。)

Answer 1

我最近做了这样的事情。不幸的是，它是闭源的。

解决方案是写一个levenshtein automaton .剧透:这是一个 NFA。

虽然很多人会试图让您相信模拟 NFA 是指数级的，但事实并非如此。从 NFA 创建 DFA 是指数级的。模拟只是多项式。 Many regex engines are writen with sub-optimal algorithms based on this .

对于 n 大小的字符串和 m 个状态，NFA 模拟的复杂度为 O(n*m)。或者，如果您延迟将其转换为 DFA(并缓存它)，则 O(n) 摊销。

恐怕您要么必须处理复杂的自动机库，要么必须编写大量代码(我所做的)。