我正在做一个应用程序来计算大量品牌/域并检测预先确定的关键字的变体。
例子：
facebook vs facebo0k.com
linkedIn vs linkedln.com
stackoverflow vs stckoverflow
我想知道是否出于比较两个字符串和检测细微变化的简单目的，两种算法都符合目的，因此除非是为了提高性能，否则选择一个而不是另一个没有附加价值？
问问题
1516 次
3 回答
2
Smith-Waterman 算法可能更适合您的任务，因为它允许您定义一个分数函数，该函数将反映您认为字符之间的“相似性”（例如与等O非常相似0）。
我认为它的优点是允许您定义自己的评分函数，而您提供的其他算法的香草版本不一定是这种情况。
该算法广泛用于生物信息学，生物学家试图检测可能不同但具有相同或非常相似功能的 DNA 序列（例如，AGC编码相同的蛋白质GTA）。
该算法使用动态规划在二次时间中运行，并且相当容易实现。
于 2020-08-28T19:36:04.417 回答
2
我会使用 Damerau–Levenshtein 并增加一个转折点，即替换常见拼写错误（'I' vs 'l'、'0' vs 'O'）或拼写错误（'Q' vs 'W' etc.）的成本将是降低。
于 2020-08-27T13:55:06.540 回答
1
如果您只考虑 Levenshtein 或 Jaro-Winkler 距离，那么您可能希望使用 Jaro-Winkler，因为它只考虑匹配字符和任何所需的换位（字符交换），并且是一个介于 0 和 1 之间的值，并且将如果没有紧密匹配的字符，则等于 1（无相似性）（便于过滤掉任何明显的不匹配）。
Levenshtein 距离将为任意距离的一对字符串提供一个值，无论它们有多么不同，这要求您选择要考虑的截止阈值。
但是，Jaro-Winkler 对前缀相似性（匹配字符串开头附近的字符）给予了额外的重视。如果这不是您想要的，那么您可能想要的是常规的 Jaro 距离。
于 2020-08-30T06:15:54.377 回答