我正在寻找一种算法，或者至少是关于如何在两个或多个不同字符串中找到相似文本的操作理论...
很像这里提出的问题:Algorithm to find articles with similar text ，不同之处在于我的文本字符串只会是几个单词。
就像说我有一个字符串: “进入湛蓝的天空” 我正在与以下两个字符串进行比较: “颜色是天蓝色”和 “在蔚蓝晴朗的天空中”
我正在寻找一种算法，可以用来匹配两者中的文本，并决定它们匹配的接近程度。就我而言，拼写和标点符号将很重要。我不希望它们影响发现真实文本的能力。在上面的示例中，如果颜色引用存储为“'sky-blue'”，我希望它仍然能够匹配。但是，列出的第三个字符串应该比第二个更好，等等。
我确信像 Google 这样的地方可能会使用与“您的意思是:”功能类似的东西...
* 编辑 *
在与一位 friend 交谈时，他与一位撰写有关该主题的论文的人一起工作。我想我可以与所有阅读本文的人分享，因为其中描述了一些非常好的方法和过程......
这里是 link to his paper ，希望对阅读这个问题的人以及类似字符串算法的话题有所帮助。
最佳答案
Levenshtein 距离不会完全起作用，因为您希望允许重新排列。我认为您最好的选择是找到以列文斯坦距离作为每个单词成本的最佳重新排列。
要找到重新排列的成本，有点像 pancake sorting problem .因此，您可以置换每个单词组合(过滤掉完全匹配)，以及其他字符串的每个组合，尽量减少每个单词对上置换距离和 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)
无论如何，您将成本函数设为第二选择，成本最低，这正是您的预期!
关于c++ - 类似的字符串算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/451884/