在大量字符串中查找相似字符串的组

Z时代
2024-01-10
分类：问答

我有一组相当大的字符串（例如100个），其中包含许多以相似性为特征的子组。我试图找到/设计一种算法，可以合理有效地找到这些小组。

例如，假设输入列表在下面的左侧，而输出组在右边。

Input Output ----------------- ----------------- Jane Doe Mr Philip Roberts Mr Philip Roberts Phil Roberts Foo McBar Philip Roberts David Jones Phil Roberts Foo McBar Davey Jones => John Smith David Jones Philip Roberts Dave Jones Dave Jones Davey Jones Jonny Smith Jane Doe John Smith Jonny Smith

有人知道有什么方法可以合理有效地解决这个问题吗？

查找相似字符串的标准方法似乎是Levenshtein距离，但是我看不到如何在无需将列表中的每个字符串与其他字符串进行比较，然后以某种方式决定差异的情况下如何充分利用该距离。确定两个字符串是否在同一组中的阈值。

另一种选择是将字符串哈希化为整数的算法，其中类似的字符串哈希为在数字线上靠在一起的整数。我什至不知道会是什么算法，即使存在

有人有什么想法/指针吗？

更新：@Will A：也许名字并不像我最初想到的那样好。首先，我想我可以假设在要使用的数据中，字符串的微小变化不会使它从一组跳到另一组。