使用LSH的近似字符串匹配

Question

我希望使用对位置敏感的散列近似匹配字符串。我有许多字符串>；10M可能包含拼写错误。对于每个字符串，我想与所有其他字符串进行比较，并根据某个阈值选择具有编辑距离的字符串。

也就是说，朴素的解决方案需要O（n^2）比较。为了避免这个问题，我正在考虑使用对位置敏感的散列。然后接近相似的字符串将导致相同的桶，我只需要做桶内搜索。所以是O（n*C），其中C是桶的大小。

但是，我不知道如何表示字符串。如果是文本，我会用向量空间来表示。我的主要问题是使用LSH和字符串的适当向量表示是否可以处理这个问题。

我是否可以使用已实现的库来执行此任务？还是取决于我的问题，所以我必须自己实施？有什么python包可以做到这一点吗？

Answer 1

我在这方面找到的最好的学术资源是Chapter 3海量数据集的挖掘，它提供了对局部敏感的散列和minhashing的极好概述。

简单地说，其思想是取几个字符串，对这些字符串进行矢量化，然后在生成的向量上传递一个滑动窗口。如果两个向量在同一窗口位置具有相同的值，则将它们标记为更细粒度相似性分析的候选向量。

Python数据集库中有一个很好的实现（pip install datasketch）。下面是一个示例，显示您可以捕获模糊字符串相似性：

from datasketch import MinHash, MinHashLSH
from nltk import ngrams

data = ['minhash is a probabilistic data structure for estimating the similarity between datasets',
  'finhash dis fa frobabilistic fata ftructure for festimating the fimilarity fetween fatasets',
  'weights controls the relative importance between minizing false positive',
  'wfights cfntrols the rflative ifportance befween minizing fflse posftive',
]

# Create an MinHashLSH index optimized for Jaccard threshold 0.5,
# that accepts MinHash objects with 128 permutations functions
lsh = MinHashLSH(threshold=0.4, num_perm=128)

# Create MinHash objects
minhashes = {}
for c, i in enumerate(data):
  minhash = MinHash(num_perm=128)
  for d in ngrams(i, 3):
    minhash.update("".join(d).encode('utf-8'))
  lsh.insert(c, minhash)
  minhashes[c] = minhash

for i in xrange(len(minhashes.keys())):
  result = lsh.query(minhashes[i])
  print "Candidates with Jaccard similarity > 0.5 for input", i, ":", result

这将返回：

Candidates with Jaccard similarity > 0.5 for input 0 : [0, 1]
Candidates with Jaccard similarity > 0.5 for input 1 : [0, 1]
Candidates with Jaccard similarity > 0.5 for input 2 : [2, 3]
Candidates with Jaccard similarity > 0.5 for input 3 : [2, 3]