我需要一种方法来比较多个字符串到一个测试字符串，并返回与它非常相似的字符串:
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。此时，伪代码是可以接受的。如果你能提供一个特定语言的例子，这也是非常感谢的!
当前回答
我怀疑选项B更接近测试字符串，因为它距离原始字符串只有4个字符(和2个删除)。而C更接近，因为它同时包含棕色和红色。但是，它有一个更大的编辑距离。
有一种叫做Levenshtein Distance的算法可以测量两个输入之间的编辑距离。
这里有一个算法工具。
选择A的距离是15。 选择B的距离是6。 选择C的距离为9。
编辑:对不起，我一直在levenshtein工具混合字符串。更新到正确的答案。
其他回答
关于这类算法，一个非常非常好的资源是Simmetrics: http://sourceforge.net/projects/simmetrics/
不幸的是，包含大量文档的很棒的网站已经消失了:( 以防它再次出现，它之前的地址是这样的: http://www.dcs.shef.ac.uk/~sam/simmetrics.html
瞧(由“时光倒流机”提供):http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html
你可以研究一下源代码，有几十种算法可以进行这种比较，每一种都有不同的权衡。这些实现是用Java实现的。
你可能会对这篇博客感兴趣。
http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python
Fuzzywuzzy是一个Python库，它提供了简单的距离度量，例如用于字符串匹配的Levenshtein距离。它构建在标准库中的difflib之上，并将使用Python-levenshtein(如果可用的话)的C实现。
http://pypi.python.org/pypi/python-Levenshtein/
我怀疑选项B更接近测试字符串，因为它距离原始字符串只有4个字符(和2个删除)。而C更接近，因为它同时包含棕色和红色。但是，它有一个更大的编辑距离。
有一种叫做Levenshtein Distance的算法可以测量两个输入之间的编辑距离。
这里有一个算法工具。
选择A的距离是15。 选择B的距离是6。 选择C的距离为9。
编辑:对不起，我一直在levenshtein工具混合字符串。更新到正确的答案。
下面是一个不依赖于任何库的快速解决方案，并且可以很好地处理自动完成表单之类的事情:
function compare_strings(str1, str2) {
arr1 = str1.split("");
arr2 = str2.split("");
res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
return(res)
}
可以像这样在自动完成输入中使用:
HTML:
<div id="wrapper">
<input id="tag_input" placeholder="add tags..."></input>
<div id="hold_tags"></div>
</div>
CSS:
body {
background: #2c2c54;
display: flex;
justify-content: center;
align-items: center;
}
input {
height: 40px;
width: 400px;
border-radius: 4px;
outline: 0;
border: none;
padding-left: 5px;
font-size: 18px;
}
#wrapper {
height: auto;
background: #40407a;
}
.tag {
background: #ffda79;
margin: 4px;
padding: 5px;
border-radius: 4px;
box-shadow: 2px 2px 2px black;
font-size: 18px;
font-family: arial;
cursor: pointer;
}
JS:
const input = document.getElementById("tag_input");
const wrapper = document.getElementById("wrapper");
const hold_tags = document.getElementById("hold_tags");
const words = [
"machine",
"data",
"platform",
"garbage",
"twitter",
"knowledge"
];
input.addEventListener("input", function (e) {
const value = document.getElementById(e.target.id).value;
hold_tags.replaceChildren();
if (value !== "") {
words.forEach(function (word) {
if (compare_strings(word, value) > value.length - 1) {
const tag = document.createElement("div");
tag.className = "tag";
tag.innerText = word;
hold_tags.append(tag);
}
});
}
});
function compare_strings(str1, str2) {
arr1 = str1.split("");
arr2 = str2.split("");
res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
return res;
}
结果:
还有一个相似度测量，我曾经在我们的系统中实施，并给出了令人满意的结果:-
用例
有一个用户查询需要与一组文档进行匹配。
算法
从用户查询中提取关键字(相关POS TAGS -名词，专有名词)。 现在根据下面的公式计算分数，用于测量用户查询和给定文档之间的相似性。
对于从用户查询中提取的每个关键字:-
开始在文档中搜索给定的单词，并在文档中每出现一次该单词就减少奖励点数。
从本质上讲，如果第一个关键字在文档中出现了4次，则得分将计算为:-
第一次出现将获取'1'点。 第二次出现将在计算分数上加1/2 第三次会增加总数的1/3 第四次得到1/4
总相似度= 1 + 1/2 + 1/3 + 1/4 = 2.083
类似地，我们为用户查询中的其他关键字计算它。
最后，总分将表示用户查询与给定文档之间的相似程度。
