1

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

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

我找到了一些可以做到的方法，经常绊倒莱文斯坦距离（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”之类的方法定义）。

我说莱文斯坦距离可能不实用，因为它需要计算KEYS_TABLEx中每一行中的每个字段SEARCH_TABLE。考虑到它SEARCH_TABLE有大约 4 亿条记录并且KEYS_TABLE从 100k 到 100 万不等，结果数字太大了。

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

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

我的选择是什么？

4

2 回答 2

0

根据可能的拼写错误，您可以使用 Soundex 或 Metaphone 进行搜索。

于 2012-12-06T01:04:03.540 回答
0

我能想到的一种方法（启发式！）是：

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

使用标准方法进行精确比较table1，以查找候选人列表中的每个条目。如果一个条目有一些通用字段，其中规范化形式与常规形式相匹配，则e2该条目table2将是一个候选条目e1。table1这可以使用一些允许快速字符串搜索的数据结构有效地完成 - 有很多这样的。

对于每个条目e1- 使用您选择的确切指标（例如您建议的 leneshtein 距离）在列表中找到它的“最佳”候选者

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

于 2012-12-05T18:29:16.657 回答