algorithm - 基于非文字比较的快速搜索方法

Question

基于非文字比较的快速搜索方法

我正在对相当大的数据集(基本上是所有字符串)进行小型搜索。表字段之间的关系很简单，尽管比较不能是字面的。即它应该能够关联“filippo”、“philippo”、“filipo”等等。

我已经找到了一些可以完成的方法，但经常会遇到 Levinstein 距离(this、here 和 here)，尽管我不确定它是否适用于我的具体情况。

简而言之，我有两个表，一个带有“搜索键”的小表和一个更大的表，应该在其中执行搜索。两个表都有相同的字段，并且它们都具有相同的“含义”。例如

KEYS_TABLE
# | NAME  | MIDNAME | SURNAME | ADDRESS         | PHONE
1 | John  | Fake    | Doe     | Sesame St.      | 333-12-32
2 | Ralph | Stue    | Michel  | Bart. Ghost St. | 778-13000
...

和

SEARCH_TABLE
#   | NAME     | MIDNAME | SURNAME | ADDRESS         | PHONE
...
532 | Jhon     | F.      | Doe     | Sesame Street   | 3331232
...
999 | Richard  | Dalas   | Doe     | Sesame St.      | 333-12-32

我想做的就是获取某种指标，或者对 KEYS_TABLE 上的每条给定记录进行排名，报告 SEARCH_TABLE 中高于特定相关性(定义通过度量或简单地通过一些“KNN”之类的方法)。

我说 Levinstein 距离可能不实用，因为它需要计算 KEYS_TABLE x SEARCH_TABLE 中每一行的每个字段。考虑到 SEARCH_TABLE 有大约 4 亿条记录，而 KEYS_TABLE 从 10 万到 100 万不等，得出的数字太大了。

我希望有一些方法可以丰富这两个表，或者一些更简单(更便宜)的方法来执行搜索。

值得一提的是，我可以随意转换数据。例如将 St. 规范化为 st，将 Street 规范化为 st，删除特殊字符等。

我的选择是什么？

Answer 1

我能想到的一种方法(启发式!)是:

除了表中的原始字段外，对于每个字段还存储其通过一些stemming获得的规范化形式算法。如果您使用的是 java，lucene 的 EnglishAnalyzer可能会帮助您完成这一步。

使用标准方法进行精确比较，为 table1 中的每个条目查找候选列表。 table2 中的条目 e2 将成为 table1 中条目 e1 的候选者，如果它们有一些公共(public)字段规范化形式与常规形式匹配。这可以使用一些允许快速字符串搜索的数据结构有效地完成——有很多这样的数据结构。

对于 e1 中的每个条目 - 使用您选择的确切度量(例如您建议的 leneshtein 距离)在列表中找到“最佳”候选者

如果这是一个问题，您可能需要进行一些后处理以确保 table1 中没有两个元素映射到 table2 中的相同元素.