是否有一种算法可以采用两个字段名称并告诉我它们有多相似？ [复制]

TheLevenshteindistance 是我推荐的算法。它计算将一个字符串更改为另一个字符串所必须执行的最小操作数。更少的变化意味着字符串更相似……

看来你需要某种模糊匹配。这里是一些相似性度量的java实现http://www.dcs.shef.ac.uk/~sam/stringmetrics.html。这里是字符串度量的更详细解释http： //www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf这取决于你的实现必须有多模糊和多快。

如果重点是性能，我会实现一个基于trie结构的算法
（可以很好地在文本中查找单词，或帮助纠正单词，但在您的情况下，您可以快速找到包含给定单词或除一个字母之外的所有单词的所有单词）。

请首先按照上面的维基百科链接。Tries是最快的单词排序方法（nwords, searchs, O(n) 创建trie, O(1) to searchs（或者如果你愿意，如果是平均长度，O(an)对于 trie 和 O(s) 进行搜索））。

您的问题（相似词）的快速简便的实现（待优化）包括

• 使
  特里
  带有单词列表，所有字母都被前后索引（参见下面的示例）
• 搜索
  s
  ，从
  s
  [0] 在 trie 中查找单词，然后
  s
  [1] 等等…
• 在 trie 中，如果找到的字母数是 len(
  s
  )-
  ķ
  显示单词，其中
  ķ
  是公差（1 个字母缺失，2…）。
• 该算法可以扩展到列表中的单词（见下文）

例，用car，vars字。

构建特里树（大写字母意味着一个词在这里结束，而另一个可能继续）。 >是后索引（前进），<是前索引（后退）。在另一个例子中，我们可能还必须指出起始字母，为了清楚起见，这里没有给出。
比如C++中的<和>就是Mystruct *previous,*next，意思是从a > c < r，可以直接从a到c，反之，也可以从a到R。

  1.  c < a < R
  2.  a > c < R
  3.    > v < r < S
  4.  R > a > c
  5.        > v < S
  6.  v < a < r < S
  7.  S > r > a > v

严格查找 carthe trie 可以让您从 1. 访问，然后您会找到汽车（您会发现所有以 car 开头的东西，还有任何内部有汽车的东西 – 它不在示例中 – 但 vicar 例如会从c > i > v < a < R找到）。

要在允许 1 个字母的错误/缺失容差的情况下进行搜索，请从每个字母中迭代，并计算从 trie 中获得的连续字母的数量（或跳过 1 个字母）。

寻找car，

• c ：在 trie 中搜索 c < a 和 c < r（缺少字母
  s
  ）。接受单词中的错误字母
  w
  , 尝试在每次迭代时跳错字母以查看 ar 是否落后，这是 O(
  w
  ）。用两个字母，O(
  w
  ²) 等等…但是可以在 trie 中添加另一个级别的索引以考虑
  跳
  超过字母 – 使特里树变得复杂，并且对记忆很贪婪。
• a ，然后 r ：与上面相同，但也向后搜索

这只是为了提供一个关于原理的想法——上面的例子可能有一些小故障（我明天再检查一次）。

你可以这样做：

Foreach string in haystack Do
    offset := -1;
    matchedCharacters := 0;
    Foreach char in needle Do
        offset := PositionInString(string, char, offset+1);
        If offset = -1 Then
            Break;
        End;
        matchedCharacters := matchedCharacters + 1;
    End;
    If matchedCharacters > 0 Then
       // (partial) match found
    End;
End;

使用matchedCharacters，您可以确定匹配的“程度”。如果它等于needle 的长度，则所有inneedle 的字符也都是instring。如果还存储了第一个匹配字符的偏移量，还可以通过最后一个匹配字符offset的偏移量减去第一个匹配字符的偏移量，按照匹配字符的“密度”对结果进行排序；差异越小，匹配越密集。

class Program { 
    static int ComputeLevenshteinDistance(string source, string target) {
        if ((source == null) || (target == null)) return 0;
        if ((source.Length == 0) || (target.Length == 0)) return 0;
        if (source == target) return source.Length;

        int sourceWordCount = source.Length;
        int targetWordCount = target.Length;

        int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];

        // Step 2
        for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++);
        for (int j = 0; j <= targetWordCount; distance[0, j] = j++);

        for (int i = 1; i <= sourceWordCount; i++) {
            for (int j = 1; j <= targetWordCount; j++) {
                // Step 3
                int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

                // Step 4
                distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
            }
        }

        return distance[sourceWordCount, targetWordCount]; 
    }

    static void Main(string[] args){ 
       Console.WriteLine(ComputeLevenshteinDistance ("Stackoverflow","StuckOverflow"));
       Console.ReadKey();
    }
}