两个弦之间的距离

Question

我不相信标准库提供了任何计算两个字符串之间距离的东西,我似乎无法在Boost StringAlgo中找到任何东西.那么,我可以使用其他任何库吗？

我对这个算法不太挑剔.Jaro-Winkler也很好,Levenshtein也是如此,我愿意接受建议,我不想编写某人已编码的内容.

Answer 1

你没有用实际距离度量来定义你的问题,所以我认为它必须满足" 度量(数学) "中的条件:

集合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.这是一个矛盾,因此右侧必须大于或等于一.

然后我们可以将度量定义为:

int d(std::string x, std::string y) {
    if (x == y) {
        return 0;
    } else {
        return 1;
    }
}

Answer 2

你可以试试SimString.

SimString是一个用于快速近似字符串检索的简单库.近似字符串检索在数据库中查找与查询字符串的相似性不小于阈值的字符串.查找不仅相同但相似的字符串,近似字符串检索具有各种应用,包括拼写校正,灵活字典匹配,重复检测和记录链接.

SimString支持余弦,Jaccard,骰子和重叠系数作为相似性度量.SimString使用字母n-gram作为计算字符串相似性的功能.

或SimMetric库.

SimMetrics是一个相似度量库,例如从编辑距离(Levenshtein,Gotoh,Jaro等)到其他指标(例如Soundex,Chapman).英国谢菲尔德大学提供的工作由(AKT)资助,由EPSRC赞助的IRC,资助号GR/N15764/01.

或者是libdistance库,它具有Levenshtein,Dameru,Needleman-Wunsch,Hamming,Bloom Filter,Jaccard和Minkowski距离的实现.

语音算法也可能是有意义的.