Lar*_*ryF 20 c c++ string algorithm
我正在寻找一种算法,或者至少是关于如何在两个或多个不同的字符串中找到类似文本的操作理论......
就像这里提出的问题一样:查找具有相似文本的文章的算法,区别在于我的文本字符串只会是少数单词.
就像说我有一个字符串:"进入清澈的蓝天",我正在与以下两个字符串进行比较:"颜色是天蓝色"和"在蓝色的晴空中"
我正在寻找一种可用于匹配两者中文本的算法,并决定它们的匹配程度.在我的情况下,拼写和标点符号将是重要的.我不希望它们影响发现真实文本的能力.在上面的例子中,如果颜色参考被存储为"'天蓝色'",我希望它仍然能够匹配.但是,列出的第3个字符串应该比第二个字符串更好,等等.
我敢肯定谷歌这样的地方可能会使用类似于"你是不是的意思:"的功能......
*编辑*
在与朋友交谈时,他与一位撰写有关此主题的论文的人合作.我想我可能会与阅读此内容的所有人分享,因为其中描述了一些非常好的方法和流程......
nlu*_*oni 16
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)
无论如何你做成本函数第二选择将是最低成本,这是你所期望的!
j_r*_*ker 14
确定"不依赖于秩序的总体相似性"度量的一种方法是使用某种基于压缩的距离.基本上,大多数压缩算法(例如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
我无法在这里标记两个答案，所以我将回答并标记我自己的答案。在大多数情况下，编辑距离似乎是正确的方法。但是，也值得一提的j_random_hackers答案。我使用了 LZMA 的实现来测试他的理论，结果证明这是一个很好的解决方案。在我最初的问题中，我正在寻找一种短字符串（2 到 200 个字符）的方法，其中编辑距离算法将起作用。但是，问题中没有提到需要比较两个（较大的）字符串（在本例中为中等大小的文本文件）并执行快速检查以查看两者的相似程度。我相信这种压缩技术会很好地发挥作用，但我还没有对其进行研究，以找出在样本数据的大小和相关操作的速度/成本方面，哪种压缩技术比另一种更好。我认为这个问题的很多答案都很有价值，并且值得一提，对于任何想要解决像我在这里所做的类似字符串考验的人来说。感谢大家的精彩回答，我希望它们也可以用来为他人提供良好的服务。