1

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

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

我找到了一些可以做到的方法,经常绊倒莱文斯坦距离(thisherehere),尽管我不确定它在我的具体情况下是否实用。

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

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.stStreetst,删除特殊字符等等。

我的选择是什么?

4

2 回答 2

0

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

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

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

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

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

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

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

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