基于非文字比较的快速搜索方法
我正在对相当大的数据集(基本上是所有字符串)进行小型搜索。表字段之间的关系很简单,尽管比较不能是字面的。即它应该能够关联“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
,删除特殊字符等。
我的选择是什么?
最佳答案
我能想到的一种方法(启发式!)是:
除了表中的原始字段外,对于每个字段还存储其通过一些stemming获得的规范化形式算法。如果您使用的是 java,lucene 的 EnglishAnalyzer
可能会帮助您完成这一步。
使用标准方法进行精确比较,为 table1
中的每个条目查找候选列表。 table2
中的条目 e2
将成为 table1
中条目 e1
的候选者,如果它们有一些公共(public)字段规范化形式与常规形式匹配。这可以使用一些允许快速字符串搜索的数据结构有效地完成——有很多这样的数据结构。
对于 e1
中的每个条目 - 使用您选择的确切度量(例如您建议的 leneshtein 距离)在列表中找到“最佳”候选者
如果这是一个问题,您可能需要进行一些后处理以确保 table1
中没有两个元素映射到 table2
中的相同元素.
关于algorithm - 基于非文字比较的快速搜索方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13729553/