我使用Levenshtein算法来找到两个字符串之间的相似性。 这是我在做节目的一个非常重要的一部分，所以它需要是有效的。 问题是，该算法没有找到下面的例子类似：
CONAIR
空调
该算法将给出6.距离所以对于6个字母（你看与字母最高量的字），所不同的是100％=>的相似性为0％这个词。
我需要找到一种方法来找到两个字符串之间的相似性，同时也考虑到案件像我之前提出。
有没有更好的算法，我可以使用吗？ 或者，你们怎么推荐我吗？
编辑：我也进去看了“Damerau - 莱文斯坦”算法，它增加了换位。 的问题是，这种换位仅用于相邻字符（而不是一个数量的字符）。
我会分裂术语为对unigram，二元语法和卦，然后计算余弦相似度。
我认为这可以通过采用在弦上的一个最长公共子串/后算法（例如“Conair公司”），并追加到自身，一旦其他字符串可以轻松解决（如“空调” - >“airconaircon”）。
在C样品代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Returns the length of the longest common substring (LCS)
// between two given strings.
//
// This recursive implementation can be replaced by a
// more performant dynamic programming implementation.
size_t llcs(const char* s1, const char* s2)
{
size_t len[3];
if (*s1 == '\0' || *s2 == '\0') return 0;
len[0] = (*s1 == *s2) + llcs(s1 + 1, s2 + 1);
len[1] = llcs(s1 + 1, s2);
len[2] = llcs(s1, s2 + 1);
if (len[0] < len[1]) len[0] = len[1];
if (len[0] < len[2]) len[0] = len[2];
return len[0];
}
// Returns similarity of two given strings in the range
// from 0.0 to 1.0 (1.0 for equal strings).
double similarity(const char* s1, const char* s2)
{
size_t s1len = strlen(s1);
size_t s2len = strlen(s2);
double sim;
if (s1len == 0 && s2len == 0)
{
// Two empty strings are equal
sim = 1;
}
else
{
size_t len;
// Append s1 to itself in s1s1 (e.g. "aircon" -> "airconaircon")
char* s1s1 = malloc(s1len * 2 + 1);
strcpy(s1s1, s1);
strcpy(s1s1 + s1len, s1);
// Find the length of the LCS between s1s1 and s2
// (e.g. between "airconaircon" and "conair")
len = llcs(s1s1, s2);
// We need it not longer than s1 (e.g. "aircon")
// since we're actually comparing s1 and s2
if (len > s1len) len = s1len;
len *= 2;
// Prevent 100% similarity between a string and its
// cyclically shifted version (e.g. "aircon" and "conair")
if (len == s1len + s2len && strcmp(s1, s2) != 0) len--;
// Get the final measure of the similarity
sim = (double)len / (s1len + s2len);
free(s1s1);
}
return sim;
}
int main(int argc, char** argv)
{
if (argc == 3)
printf("Similarity of \"%s\" and \"%s\" is %.2f%%\n",
argv[1], argv[2], 100 * similarity(argv[1], argv[2]));
else
printf("Usage:\n %s string1 string2\n",
argv[0]);
return 0;
}
输出示例：
Similarity of "123" and "123" is 100.00%
Similarity of "123" and "1234" is 85.71%
Similarity of "0123" and "123" is 85.71%
Similarity of "a" and "aa" is 66.67%
Similarity of "aa" and "a" is 66.67%
Similarity of "aaaaaaa" and "aaaaaa" is 92.31%
Similarity of "aaaaaa" and "aaaaaaa" is 92.31%
Similarity of "aircon" and "conair" is 91.67%
Similarity of "spit" and "pits" is 87.50%
Similarity of "pits" and "spit" is 87.50%
Similarity of "spits" and "pits" is 88.89%
Similarity of "pits" and "spits" is 88.89%
这听起来像你可能想尝试使用音节或音素的不是字母做Levenshtein距离。
从理论上讲，你正在使用的方法是，你正在试图解决的问题是正确的。 但是，莱文施泰因将只考虑单个字符的两套。
串相似度也可以使用发现最长公共子序列的方法，然后你可以看到无与伦比的休息莱文施泰因。
如果你想做一个集群的方式， 下面的回答似乎有一些细节，但显然是更难以实现。
排序的话，寻找莱文斯坦会给您例如100％的比赛，但它也给了100％匹配如
CONAIR
RCIAON
这可能不是你想要的。
另一种方法来定义相似性会找出共同子串2串。 您可以创建一个后缀树 ，找出所有常见字符串，并试图确定他们是多么相似。 因此，对于你如后缀树会给普通子为CON和AIR覆盖整个字（您2串），因此他们的结论相似。
尝试使用其他类似措施，如索伦森，捷卡和jaro_winkler
我个人是哈罗温克勒的忠实粉丝，因为它曾我的目的了很多次。
from Levenshtein import jaro_winkler
In [2]: jaro_winkler("conair","aircon")
Out[2]: 0.8333333333333334
看看以尼德曼 - 翁施，或史密斯 - 沃特曼算法。 它们被用来通过适于编辑距离处理字符串匹配用于DNA序列，其中任何形式的插入，倒转，转座子可以发生任何长度，在任何地方。 话说到此，我需要补充的是，一个足够长的字符串没有最优解。 而且不要忘记，编辑成本取决于算法（一种语义问题）的使用情境中，而任何算法始终是一个语法机。
