34

我需要比较 2 个字符串并计算它们的相似性，以过滤出最相似的字符串列表。

例如。搜索“狗”会返回

  1. 狗
  2. 多戈内
  3. 沼泽
  4. 多雾路段
  5. 有雾的

例如。搜索“crack”会返回

  1. 裂缝
  2. 俏皮话
  3. 架子
  4. 杰克
  5. 嘎嘎

我遇到过：

你知道更多的字符串相似度算法吗？

4

5 回答 5

31

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

于 2010-08-26T14:47:37.357 回答
20

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

于 2010-08-26T15:24:28.710 回答
9

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

请先关注上面的维基百科链接。Tries是最快的单词排序方法（n 个单词，搜索s，O( n ) 来创建特里树，O(1) 来搜索s（或者如果你愿意，如果a是平均长度，O( an ) 来创建特里树和O( s ) 用于搜索))。

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

  • 使用单词列表进行尝试，将所有字母索引前后（参见下面的示例）
  • 要搜索s ，从s [0]迭代以查找 trie 中的单词，然后s [1] 等...
  • 在 trie 中，如果找到的字母数是 len( s ) -k，则显示单词，其中k是容差（1 个字母缺失，2...）。
  • 该算法可以扩展到列表中的单词（见下文）

例如，用词car, vars。

构建特里树（大写字母表示一个词在这里结束，而另一个可能继续）。是>后索引（前进）和<前索引（后退）。在另一个例子中，我们可能还必须指出起始字母，为了清楚起见，这里没有给出。例如，C++ 中
的<and是，意思是 from ，你可以直接从to ，反过来，也可以 from to 。>Mystruct *previous,*nexta > c < racaR

  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

严格寻找car特里树可以让您从 1. 访问，然后您会找到car（您还会发现以 car 开头的所有内容，以及内部有 car 的所有内容 - 它不在示例中 - 但是会找到vicar例如从c > i > v < a < R)。

要在允许 1 个字母的错误/缺失容差的同时进行搜索，您可以从 s 的每个字母进行迭代，并计算从s中获得的连续字母的数量 - 或跳过 1 个字母。

寻找car，

  • c: 在 trie 中搜索c < aand （ sc < r中缺少的字母）。要接受单词w中的错误字母，请尝试在每次迭代时跳到错误字母以查看是否在后面，这是 O( w )。有两个字母，O（w²）等......但是可以将另一个级别的索引添加到特里以考虑跳过字母 - 使特里变得复杂，并且对内存很贪婪。ar
  • a, then r: 同上，但也向后搜索

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

于 2010-08-26T17:00:19.553 回答
1

你可以这样做：

 haystack中的foreach字符串 做偏移：= -1；
    匹配字符：= 0；
    Foreach char in needle Do offset := PositionInString( string , char , offset +1);
        如果offset = -1 Then Break ;
        结束；
        匹配字符:=匹配字符+ 1;
    结束；
    如果matchedCharacters > 0那么  
        
         
             
       //（部分）匹配找到
    结束；
结束；

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

于 2010-08-26T14:59:19.967 回答
0 
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();
    }
}
于 2017-07-24T21:16:18.313 回答