相关疑难解决方法(0)

我需要一种方法来将多个字符串与测试字符串进行比较,并返回与其非常相似的字符串:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(如果我这样做的话)最接近"TEST STRING"的字符串应该是"CHOICE C".最简单的方法是什么？

我计划将其实现为多种语言,包括VB.net,Lua和JavaScript.此时,伪代码是可以接受的.如果您可以提供特定语言的示例,这也是值得赞赏的!

我发现了Levenshtein distancePython的一些实现。

我想知道如何有效地修改这些算法，以便在编辑距离大于n（例如 3）时它们会中断，而不是运行到最后？

因此，如果我只是想知道距离是否大于阈值，那么本质上我不想让算法运行太长时间来计算最终距离。

我在这里找到了一些相关的帖子：

1. 修改 Levenshtein Distance 算法以不计算所有距离
2. 莱文斯坦距离限制
3. 计算编辑距离的最有效方法
4. Levenshtein 距离算法比 O(n*m) 更好？

但是，我仍然没有看到任何 Python 代码执行我上面描述的操作（这或多或少也是这些帖子所描述的）。

PS：下面@amirouche提供的解决方案基于我通过一些基准测试测试过的最快实现（来自此处： https : //en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python，https :// stackoverflow.com/a/32558749/9024698）及其有界版本是我的测试中最快的版本（不排除可能有更快的版本）。