你可能会发现这个图书馆很有用! http://code.google.com/p/google-diff-match-patch/

目前可以在Java, JavaScript, Dart, c++， c#， Objective C, Lua和Python中使用

它也运行得很好。我在我的几个Lua项目中使用了它。

而且我认为将其移植到其他语言并不困难!

如果您在搜索引擎上下文中执行此操作，或者在数据库前端执行此操作，则可以考虑使用类似Apache Solr的工具，并使用ComplexPhraseQueryParser插件。这种组合允许您搜索字符串索引，并根据相关性(由Levenshtein距离确定)对结果进行排序。

当传入的查询可能有一个或多个拼写错误时，我们一直在对大量艺术家和歌曲标题的集合使用它，并且它工作得非常好(考虑到集合包含数百万个字符串，它的速度非常快)。

此外，使用Solr，您可以根据需要通过JSON根据索引进行搜索，因此不必在不同的语言之间重新设计解决方案。

我怀疑选项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

类似地，我们为用户查询中的其他关键字计算它。

最后，总分将表示用户查询与给定文档之间的相似程度。

要以有效的方式查询大量文本，可以使用编辑距离/前缀编辑距离的概念。

编辑距离ED(x,y):从项x到项y的最小变换数

但是计算每个术语和查询文本之间的ED是资源和时间密集型的。因此，我们可以使用一种称为Qgram Index的技术提取可能匹配的项，而不是首先计算每个项的ED。然后对这些选定的项进行ED计算。

Qgram索引技术的优点是支持模糊搜索。

采用QGram索引的一种可能的方法是使用QGram构建倒排索引。在那里，我们存储了所有与特定Qgram组成的单词，在那个Qgram之下。(而不是存储完整的字符串，您可以为每个字符串使用唯一的ID)。为此，您可以使用Java中的Tree Map数据结构。 下面是存储术语的一个小示例

科尔姆比亚，科伦坡，甘科拉，塔科拉马

然后，在查询时，我们计算查询文本和可用术语之间的公共Qgrams的数量。

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

共有q-gram数= 4。

对于具有大量常见Qgrams的术语，我们根据查询术语计算ED/PED，然后向最终用户建议该术语。

你可以在下面的项目中找到这个理论的实现(参见“QGramIndex.java”)。请随意提问。https://github.com/Bhashitha-Gamage/City_Search

要了解更多关于编辑距离，前缀编辑距离Qgram索引，请观看Hannah Bast教授的视频https://www.youtube.com/embed/6pUg2wmGJRo(课程从20:06开始)