4

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

我对算法不太挑剔。Jaro-Winkler 很好，Levenshtein 也很好，我愿意接受建议，我不想编写已经有人编写过的代码。

4

3 回答 3

8

您没有用实际的距离度量来定义您的问题，所以我认为它只需要满足“度量（数学） ”中的条件：

集合 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. 假设右手边不大于或等于一。这意味着它必须为零。那么右边的两个术语都必须是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;
    }
}
于 2013-02-28T14:13:03.077 回答
6

你可以试试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 距离。

语音算法也可能很有趣。

于 2013-02-28T15:19:54.297 回答
0

此相关问题包含演示 Levenshtein 距离的代码片段。它也已在此 C 代码中为 MySQL 实现。

于 2013-02-28T15:18:54.877 回答