字串相似算法？

Question

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

例如.寻找"狗"会回来

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

例如.寻找"破解"将返回

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

我遇到过:

• 水银
• 的Liquidmetal

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

Answer 1

在莱文斯坦距离算法,我会建议.它计算将1个字符串更改为另一个字符串必须执行的最小操作数.变化越少意味着字符串更相似......

Answer 2

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

Answer 3

如果重点是性能,我会实现一个基于trie结构的算法
(适用于在文本中查找单词,或帮助纠正单词,但在您的情况下,您可以快速找到包含给定单词或所有单词的所有单词例如,一封信).

请先按照上面的维基百科链接进行操作.Tries是最快的单词排序方法(n个单词,搜索s,O(n)创建trie,O(1)来搜索s(或者如果你喜欢,如果a是平均长度,O(an)为trie和O(s)搜索)).

快速简便地实现(优化)您的问题(类似的单词)包括

• 使用单词列表制作trie,将所有字母编入正面和背面(参见下面的示例)
• 要搜索s,从s [0] 迭代以找到trie中的单词,然后s [1]等...
• 在trie中,如果找到的字母数是len(s) - k,则显示单词,其中k是容差(缺少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

严格看车,trie让你从1.进入,你找到了汽车(你也可以找到所有从车开始的东西,但也有车内的任何东西 - 它不在例子中 - 但是例如教区牧师会被发现来自c > i > v < a < R).

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

寻找car,

• c:搜索trie c < a和c < r(s中缺少字母).要接受单词w中的错误字母,请尝试在每次迭代时跳转错误的字母以查看是否ar落后,这是O(w).以两个字母,O(w ^ ²)等...但另一指数水平可以被添加到线索来考虑跳了字母-使得线索复杂,贪婪有关的记忆.
• a,然后r:同上,但也向后搜索

这只是为了提供一个关于原理的想法 - 上面的例子可能有一些小问题(明天我会再次检查).