相似字符串算法

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)  

(注意所有翻转包括范围内的所有元素,并且我使用的范围是X-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)) 你会得到高分,如果他们完全不同, Lon(COMP)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序列的算法,因为它们必须处理许多相同的事情(区块可能丢失,或插入,或只是移动到字符串中的不同位置)。

这个 Smith-Waterman 算法可能是一个很好地工作的例子,尽管对于您的使用来说它可能太慢了。不过,可能会给你一个起点。

我有一个类似的问题,我需要得到字符串中相似字符的百分比。它需要精确的序列,例如“hello sir”和“sir hello”,当比较时,需要给我五个相同的字符,在这种情况下,它们将是两个“hello”。然后,它将取两个字符串中最长的长度,并给出它们相似程度的百分比。这就是我想出的密码

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的一个实现来测试他的理论,它被证明是一个很好的解决方案。在我最初的问题中,我正在寻找一种短字符串(2到200个字符)的方法,在这种方法中,Levenshtein距离算法将起作用。但是,问题中没有提到需要比较两个(较大的)字符串(在本例中,是中等大小的文本文件),并执行快速检查以查看这两个字符串有多相似。我相信这种压缩技术会很好地工作,但是我还没有研究它,以发现在哪一点上,从样本数据的大小和所讨论的操作的速度/成本来看,一个比另一个更好。我认为这个问题的很多答案都很有价值,值得一提的是,对于任何一个想解决类似的弦乐考验的人来说,就像我在这里做的一样。谢谢大家的回答,我希望他们也能很好地为他人服务。

还有另一种方法。使用卷积的模式识别。图像A通过傅立叶变换运行。图像B也。现在将f(a)叠加在f(b)上,然后将其转化为带有几个白点的黑色图像。这些点表示a与b强匹配的位置。点的总和表示总体相似性。不知道你是如何在弦上进行快速傅立叶变换的,但我很确定它会起作用。

困难是要在语义上匹配字符串。

可以根据字符串的词汇属性生成某种值。例如,他们有蓝色,天空,他们在同一句话,等等…但它不能处理“sky's jean is blue”或其他一些使用相同单词的奇怪的ball-english结构的情况,但您需要解析英语语法…

要做任何超出词汇相似度的事情,你需要看自然语言处理,而且不会有一个单一的算法可以解决你的问题。

可能的方法:

为中的所有单词组合构造一个字符串键为“word1 word2”的字典。 参考 字符串。单个组合可能多次发生,因此字典的值应为 列表 个数,每个代表 距离 在引用字符串中的单词之间。

当您这样做时,这里会有重复:对于每个“word1 word2”字典条目,都会有一个“word2 word1”条目,具有相同的距离值列表,但会被否定。

对于中的每个单词组合 比较 字符串(单词1和2、单词1和3、单词2和3等),检查引用字符串中的两个键(单词1单词2和单词2_单词1),找到 最近的 值到当前字符串中的距离。将当前距离与计数器最近距离之差的绝对值相加。

如果两个词之间的最近引用距离与比较字符串方向相反(word2 word1),则可能希望将其权重小于两个字符串中的最近值方向相同时的权重。

完成后,将和除以比较字符串中单词数的平方。

这应该提供一些十进制值,表示每个单词/短语与原始字符串中某些单词/短语的匹配程度。

当然,如果原始字符串较长,就不能解释这一点,因此可能需要计算这两个方向(使用一个作为参考,然后使用另一个)并平均它们。

我完全没有这方面的代码,我可能只是重新发明了一个非常粗糙的轮子。YMMV。