我不相信标准库提供任何东西来计算两个字符串之间的距离，我似乎在Boost StringAlgo中找不到任何东西。还有别的图书馆可以用吗?
我对算法不太挑剔。Jaro-Winkler很好，Levenshtein也是，我愿意接受建议，我不想写别人已经写过的东西。
你没有用实际的距离度量来定义你的问题，所以我认为它只需要满足"度量(数学)"中的条件:
集X上的度规是一个函数(称为距离函数或简称距离)d: X × X→R(R是实数的集合)。对于x中的所有x, y, z，该函数需要满足以下条件:
- d(x, y)≥0(非负性，或分离公理)
- d(x, y) = 0当且仅当x = y(不可分辨的恒等式，或重合公理)
- d(x, y) = d(y, x)(对称)
- d(x, z)≤d(x, y) + d(y, z)(次可加性/三角不等式)。
假设我们这样定义d:
{ 0 if x = y
d(x, y) = {
{ 1 otherwise
所以满足前三个条件:
-
d(x, y) ≥ 0 -
d(x, y) = 0 iff x = y -
d(x, y) = d(y, x) = 0 for x = y和d(x, y) = d(y, x) = 1 for x ≠ y
对于最后一个条件，有两种情况:
-
d(x, z) = 0。右边唯一可能的值是0、1和2，它们中的任何一个都满足条件。 -
d(x, z) = 1。假设右边不大于等于1。这意味着它一定是零。那么右边的两项都必须是0，这意味着x = y和y = z。第二个条件表示x = z，这又表示d(x, z) = 0。这是一个矛盾，所以右边必须大于等于1。
那么我们可以将度规定义为:
int d(std::string x, std::string y) {
if (x == y) {
return 0;
} else {
return 1;
}
}
你可以试试SimString。
SimString是一个简单的库，用于快速近似字符串检索。近似字符串检索在数据库中查找符合以下条件的字符串与查询字符串的相似度不小于阈值。发现不仅相同，而且相似的字符串，近似字符串检索包括拼写纠正在内的各种应用程序是否灵活字典匹配、重复检测和记录链接。
SimString支持余弦、Jaccard、dice和重叠系数相似的措施。SimString使用字母n-gram作为特征计算字符串相似度。
或SimMetric库。
SimMetrics是一个相似度度量库，例如从编辑距离(Levenshtein, Gotoh, Jaro等)到其他参数(例如Soundex，查普曼)。工作由英国谢菲尔德大学提供，由(AKT)和IRC由EPSRC资助，授权号GR/N15764/01。
或者libdistance库，它实现了Levenshtein、Dameru、Needleman-Wunsch、Hamming、Bloom Filter、Jaccard和Minkowski距离。
语音算法也可能很有趣。
这个相关的问题包含一个演示Levenshtein距离的代码片段。