两个字符串之间的距离

Question

4

我不相信标准库提供了计算两个字符串之间距离的任何东西，而且我似乎在Boost StringAlgo中找不到任何内容。那么，还有其他库可以使用吗？

我对算法不是太挑剔。Jaro-Winkler可以，Levenshtein也可以，我也愿意听取建议，我不想编写已经有人编写过的代码。

- qdii

7

“distance between two strings” 的意思是“两个字符串之间的距离”。 - Graham Borland

1

汉明距离怎么样？这个很容易编码。 - John Dvorak

2

好的，那么它们在内存中不仅仅是相隔多远。 :) - Graham Borland

1

这个看起来不错：http://rosettacode.org/wiki/Levenshtein_distance#C.2B.2B （在谷歌上搜索“c++ levenshtein distance”排名第三） - John Dvorak

2

请复制粘贴以下链接以获取与Levenshtein距离相关的编程内容：http://rosettacode.org/wiki/Levenshtein_distance？ - user1773602

显示剩余6条评论

3个回答

6

你可以尝试使用SimString。

SimString是一个简单的库，用于快速的近似字符串检索。近似字符串检索可以在数据库中查找与查询字符串相似度不小于阈值的字符串。除了查找相同的字符串外，近似字符串检索还具有各种应用，包括拼写纠正、灵活的字典匹配、重复检测和记录链接。

SimString支持余弦、Jaccard、dice和重叠系数作为相似度度量。SimString使用字母n-gram作为特征来计算字符串相似度。

或者使用SimMetric库。

SimMetrics是一个相似性度量库，例如从编辑距离（Levenshtein、Gotoh、Jaro等）到其他度量（例如Soundex、Chapman）。这项工作由英国谢菲尔德大学提供，由EPSRC赞助的IRC（AKT），资助编号为GR/N15764/01。

或者使用libdistance库，该库实现了Levenshtein、Dameru、Needleman-Wunsch、Hamming、Bloom Filter、Jaccard和Minkowski距离。

语音算法也可能会引起兴趣。

- Richard

请参见此问题。 - Richard

而这个问题：https://dev59.com/SUfRa4cB1Zd3GeqP_roM。 - Richard

另外，还可以查看 https://github.com/Martinsos/edlib 获取 Levenshtein 距离的 C/C++ 实现！ - Martinsos

0

- Paul Lammertsma

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Waleed Khan · Accepted Answer

您的问题中没有定义实际距离度量，因此我假设它只需要满足“度量（数学）”中的条件：

引理块：对于集合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,z)=0。右侧唯一可行的值为0、1和2，其中任何一个都满足条件。
d(x,z)=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;
    }
}