string相似度algorithm

我需要比较两个string并计算它们的相似性，以筛选最相似string的列表。

例如。 search“狗”会返回

1. 狗
2. 该死
3. 沼泽
4. 多雾路段
5. 有雾

例如。 寻找“裂缝”将返回

1. 裂纹
2. 俏皮话
3. 架
4. 插口
5. 嘎嘎

我遇到过：

• 水银
• 的Liquidmetal

你知道更多的string相似度algorithm吗？

Answer 1

看来你需要某种模糊匹配。 下面是一些相似性度量的实现http://www.dcs.shef.ac.uk/~sam/stringmetrics.html 。 下面是对string指标的更详细的解释http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf它取决于你的实现必须多么模糊和多快。;

Answer 2

Levenshtein距离是我会推荐的algorithm。 它会计算您将1个string更改为另一个string所需的最less操作次数。 变化越less意味着string越相似

Answer 3

如果重点是性能，我会实现一个基于trie结构的algorithm
（在文本中查找单词或帮助纠正一个单词的作用很好，但是在你的情况下，你可以迅速find包含给定单词或所有单词的所有单词）。

请首先按照上面的维基百科链接。 Tries是最快的单词sorting方法（ n个单词，searchs ，O（ n ）来创buildtrie，O（1）来searchs （或者如果您更喜欢，如果a是平均长度O（ an ）和O（ s ）进行search））。

你的问题（类似的话）的一个快速和容易的实现（被优化）包括

• 使用单词列表来创build单词列表，将所有字母的前后索引（请参阅下面的示例）
• 为了searchs ，从s [0]迭代findtrie中的单词，然后s [1]等等。
• 如果find的字母数是len（ s ） -k ，则显示单词，其中k是容差（1个字母缺失，2 …）。
• 该algorithm可以扩展到列表中的单词（见下文）

例如，用car ， car的话。

build立特里（大字母意味着一个字在这里结束，而另一个可能会继续）。 >是后索引（前进）， <前索引（后退）。 在另一个例子中，我们可能不得不指出起始字母，为了清晰起见，这里没有给出。
在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 

仔细观察汽车 ，你可以从1号出发，find汽车 （你也可以find所有从汽车开始的东西，也可以find任何有汽车的东西 – 这不是例子 – 但是可以find代理人从c > i > v < a < R ）。

要在允许单字母错误/丢失宽容的情况下进行search，请从s的每个字母开始迭代，然后计算从trie中的s中获得的连续字符数或跳过1个字母的字母数。

寻找car ，

• c ：searchc < a和c < r （ s中缺less的字母）。 要接受一个单词w中的错误字母，试着在每次迭代时跳过错误的字母，看看ar是否在后面，这是O（ w ）。 有两个字母，O（W²）等等，但是另外一个索引级别可以被添加到字典中，以考虑到字母的跳跃 – 使字词变得复杂，并且对于记忆是贪婪的。
• a ，则r ：与上面相同，但也向后search

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

Answer 4

你可以这样做：

 在 草垛干草 string 做
     偏移量 ：= -1;
     matchedCharacters ：= 0;
     在 针的 字符 做
         offset ：= PositionInString（ string ， char ， offset +1）;
         如果 offset = -1 那么
             打破 ;
         结束
         matchedCharacters ：= matchedCharacters + 1;
     结束
     如果 matchedCharacters > 0 那么
        / /（部分）匹配find
     结束
 结束

用matchedCharacters可以确定匹配的“度数”。 如果与针的长度相等，则针中的所有字符也都是string 。 如果还存储第一个匹配字符的偏移量，则还可以通过从最后一个匹配字符偏移量的偏移量中减去第一个匹配字符的偏移量，将结果按照匹配字符的“密度”sorting; 差异越小，比赛越密集。

Answer 5

 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(); } }