类似的String算法

我正在寻找一种算法,或者至少是关于如何在两个或多个不同的字符串中找到类似文本的操作理论......

就像这里提出的问题一样:查找具有相似文本的文章的算法,区别在于我的文本字符串只会是少数单词.

就像说我有一个字符串:"进入清澈的蓝天",我正在与以下两个字符串进行比较:"颜色是天蓝色"和"在蓝色的晴空中"

我正在寻找一种可用于匹配两者中文本的算法,并决定它们的匹配程度.在我的情况下,拼写和标点符号将是重要的.我不希望它们影响发现真实文本的能力.在上面的例子中,如果颜色参考被存储为"'天蓝色'",我希望它仍然能够匹配.但是,列出的第3个字符串应该比第二个字符串更好,等等.

我敢肯定谷歌这样的地方可能会使用类似于"你是不是的意思:"的功能......

*编辑*
在与朋友交谈时,他与一位撰写有关此主题的论文的人合作.我想我可能会与阅读此内容的所有人分享,因为其中描述了一些非常好的方法和流程......

这是他的论文的链接,我希望它对阅读这个问题的人以及类似的字符串算法的主题有所帮助.

Levenshtein距离不会完全起作用,因为你想允许重新排列.我认为你最好的选择是找到levenstein距离的最佳重排作为每个单词的成本.

要找到重新排列的成本,有点像煎饼排序问题.因此,您可以使用其他字符串的每个组合来置换每个单词组合(过滤掉完全匹配),尝试最小化每个单词对上的置换距离和Levenshtein距离的组合.

编辑: 现在我有一个我可以发布一个快速示例(所有'最佳'猜测都在检查,而不是实际运行算法):

original strings             | best rearrangement w/ lev distance per word
Into the clear blue sky      |    Into the c_lear blue sky 
The color is sky blue        |    is__ the colo_r blue sky

R_dist = dist( 3 1 2 5 4 ) --> 3 1 2 *4 5* --> *2 1 3* 4 5 --> *1 2* 3 4 5 = 3  
L_dist = (2D+S) + (I+D+S) (Total Subsitutions: 2, deletions: 3, insertion: 1)  

(注意所有翻转包括范围内的所有元素,并且我使用Xi-Xj = +/- 1的范围)

其他例子

original strings             | best rearrangement w/ lev distance per word
Into the clear blue sky      |   Into the clear blue sky 
In the blue clear sky        |   In__ the clear blue sky

R_dist = dist( 1 2 4 3 5 ) -->  1 2 *3 4* 5  = 1
L_dist = (2D) (Total Subsitutions: 0, deletions: 2, insertion: 0)

并显示三者的所有可能组合......

The color is sky blue         |    The colo_r is sky blue
In the blue clear sky         |    the c_lear in sky blue

R_dist = dist( 2 4 1 3 5 ) --> *2 3 1 4* 5 --> *1 3 2* 4 5 --> 1 *2 3* 4 5 = 3
L_dist = (D+I+S) + (S) (Total Subsitutions: 2, deletions: 1, insertion: 1)

无论如何你做成本函数第二选择将是最低成本,这是你所期望的!

确定"不依赖于秩序的总体相似性"度量的一种方法是使用某种基于压缩的距离.基本上,大多数压缩算法(例如gzip)工作的方式是沿着字符串扫描以查找之前出现的字符串片段 - 无论何时找到这样的片段,它都会被标识早期片段的(偏移,长度)对替换.使用.您可以使用两个字符串压缩的度量来检测它们之间的相似性.

假设您有一个string comp(string s)返回压缩版本的函数s.然后,您可以使用下面的表达式作为两个字符串之间的"相似性得分" s和t:

len(comp(s)) + len(comp(t)) - len(comp(s . t))

在哪里.被连接.我们的想法是,通过先查看,您可以测量您可以进一步压缩t的程度s.如果s == t,那么len(comp(s . t))几乎不会超过len(comp(s))并且你会获得高分,而如果它们完全不同,len(comp(s . t))将非常接近len(comp(s) + comp(t))并且你将获得接近零的分数.中间相似性水平产生中间分数.

实际上下面的公式甚至更好,因为它是对称的(即分数不会根据哪个字符串而变化,而且是s哪个t):

2 * (len(comp(s)) + len(comp(t))) - len(comp(s . t)) - len(comp(t . s))

这种技术源于信息理论.

优点:良好的压缩算法已经可用,因此您不需要进行太多编码,并且它们以线性时间(或几乎如此)运行,因此它们很快.相比之下,涉及所有单词排列的解决方案在单词数量上呈超指数增长(尽管在你的情况下可能不会出现问题,因为你说你知道只有少数几个单词).

一种方法(尽管这可能更适合拼写检查类型算法)是"编辑距离",即计算将一个字符串转换为另一个字符串所需的编辑量.这里有一个常见的技术:

http://en.wikipedia.org/wiki/Levenshtein_distance

您可能希望研究生物学家用来比较DNA序列的算法,因为它们必须处理许多相同的事情(块可能丢失,或者已经插入,或者只是移动到字符串中的不同位置.

在史密斯-沃特曼算法将是一个例子很可能工作得相当好,尽管它可能是你使用过慢.不过,可能会给你一个起点.