类似的String算法
我正在寻找一种算法，或者至少是关于如何在两个或多个不同的字符串中找到类似文本的操作理论……
就像这里提出的问题一样： 查找具有相似文本的文章的算法 ，区别在于我的文本字符串只会是少数单词。
就像说我有一个字符串：“进入清澈的蓝天”，我正在与以下两个字符串进行比较：“颜色是azure色”和“在蓝色晴朗的天空”
我正在寻找一种可用于匹配两者中文本的算法，并决定它们的匹配程度。 在我的情况下，拼写和标点符号将是重要的。 我不希望它们影响发现真实文本的能力。 在上面的例子中，如果颜色参考存储为“’azure色’”，我希望它仍然能够匹配。 但是，列出的第3个字符串应该比第二个字符串更好，等等。
我敢肯定谷歌这样的地方可能会使用类似于“你是不是的意思：”的function……
*编辑*
在与朋友交谈时，他与一位撰写有关该主题的论文的人一起工作。 我想我可能会与阅读此内容的所有人分享，因为其中描述了一些非常好的方法和流程……
这是他的论文的链接 ，我希望它对那些阅读这个问题的人以及类似字符串算法的主题有所帮助。
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) ，它返回string comp(string s)的压缩版本。 然后，您可以使用以下表达式作为两个字符串s和t之间的“相似性得分”：
len(comp(s)) + len(comp(t)) - len(comp(s . t))
在哪里 被认为是连接。 这个想法是你通过先看s来测量你可以进一步压缩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))
这种技术源于信息理论。
优点：良好的压缩算法已经可用，因此您不需要进行太多编码，并且它们以线性时间（或几乎如此）运行，因此它们很快。 相比之下，涉及所有单词排列的解决方案在单词数量上呈超指数增长（尽管在你的情况下可能不是一个问题，因为你说你知道只会有少数几个单词）。
一种方法（尽管这可能更适合拼写检查类型算法）是“编辑距离”，即计算将一个字符串转换为另一个字符串所需的编辑量。 这里有一个常见的技术：
您可能希望研究生物学家用来比较DNA序列的算法，因为它们必须处理许多相同的事情（块可能丢失，或者已插入，或者只是移动到字符串中的不同位置。
史密斯 – 沃特曼算法将是一个可能相当好的例子，尽管它可能对你的使用来说太慢了。 不过，可能会给你一个起点。
我有一个类似的问题，我需要得到一个相似的字符串中的字符百分比。 它需要精确的序列，所以例如“你好先生”和“先生你好”，比较需要给我五个相同的字符，在这种情况下，它们将是两个“你好”。 然后它将花费两个字符串中最长的字符串的长度，并给出一个它们有多相似的百分比。 这是我提出的代码
int compare(string a, string b){ return(a.size() > b.size() ? bigger(a,b) : bigger(b,a)); } int bigger(string a, string b){ int maxcount = 0, currentcount = 0;//used to see which set of concurrent characters were biggest for(int i = 0; i < a.size(); ++i){ for(int j = 0; j < b.size(); ++j){ if(a[i+j] == b[j]){ ++currentcount; } else{ if(currentcount > maxcount){ maxcount = currentcount; }//end if currentcount = 0; }//end else }//end inner for loop }//end outer for loop return ((int)(((float)maxcount/((float)a.size()))*100)); }
我不能在这里标记两个答案，所以我要回答并标记我自己的答案。 在大多数情况下，Levenshtein距离似乎是正确的方法。 但是，值得一提的是j_random_hackers回答。 我使用了LZMA的实现来测试他的理论，它被certificate是一个合理的解决方案。 在我最初的问题中，我正在寻找一种短字符串（2到200个字符）的方法，其中Levenshtein距离算法将起作用。 但是，问题中没有提到需要比较两个（更大的）字符串（在这种情况下，中等大小的文本文件）并执行快速检查以查看两者的相似程度。 我相信这种压缩技术会运行良好，但我还没有研究它，以便在样本数据的大小和所讨论的操作的速度/成本方面找到一个比另一个更好的点。 我认为这个问题的很多答案都是有价值的，值得一提的是，对于任何想要解决类似字符串考验的人来说，就像我在这里做的那样。 谢谢大家的好答案，我希望他们也可以用来为他人服务。
还有另一种方式。 使用卷积进行模式识别。 图像A通过傅里叶变换运行。 图B也。 现在将F（A）叠加到F（B）上然后将其转换回来会给你一个带有几个白点的黑色图像。 那些斑点表明A强烈匹配B的位置。 斑点的总和将表示总体相似性。 不知道你如何在字符串上运行FFT，但我很确定它会起作用。
困难在于语义匹配字符串。
您可以根据字符串的词法属性生成某种值。 例如，他们的机器人有蓝色和天空，他们在同一个句子等等……但它不会处理“天空的牛仔裤是蓝色的”，或者其他一些使用相同单词的奇怪的英语结构，但是你需要解析英语语法……
要做除词汇相似性以外的任何事情，您需要查看自然语言处理，并且不会有单一的算法可以解决您的问题。
可能的方法：
为参考字符串中的所有单词组合构造一个字符串键为“word1 | word2”的Dictionary。 单个组合可能会多次发生，因此Dictionary的值应该是一个数字列表 ，每个数字代表参考字符串中单词之间的距离 。
执行此操作时，此处将存在重复：对于每个“word1 | word2”字典条目，将有一个“word2 | word1”条目具有相同的距离值列表，但是否定。
对于比较字符串中的每个单词组合（单词1和2，单词1和3，单词2和3等），检查参考字符串中的两个键（word1 | word2和word2 | word1）并找到最接近的值到当前字符串中的距离。 添加当前距离与计数器最近距离之差的绝对值。
如果单词之间的最近参考距离是与比较字符串相反的方向（word2 | word1），则可能需要将其加权小于两个字符串中最接近的值在同一方向上的情况。
完成后，将总和除以比较字符串中单词数的平方。
这应该提供一些十进制值，表示每个单词/短语与原始字符串中的某些单词/短语的匹配程度。
当然，如果原始字符串较长，则不会考虑到这一点，因此可能需要计算这两个方向（使用一个作为参考，然后使用另一个）并对它们求平均值。
我绝对没有这个代码，我可能只是重新发明了一个非常粗糙的轮子。 因人而异。