使用LSH进行近似字符串匹配

Question

我想用局部敏感哈希来大致匹配字符串。我有超过1000万个字符串，里面可能有拼写错误。对于每个字符串，我想和其他所有字符串进行比较，找出那些编辑距离在某个阈值内的字符串。

简单的方法需要进行O(n^2)的比较，这样会很慢。为了避免这个问题，我在考虑使用局部敏感哈希。这样，相似的字符串会被放到同一个桶里，我只需要在这个桶里进行搜索。所以复杂度变成了O(n*C)，其中C是桶的大小。

不过，我不太明白该如何表示这些字符串。如果是文本，我会用向量空间来表示。我的主要问题是，使用局部敏感哈希和合适的字符串向量表示，这样做是否可行。

我能否使用已经实现的库来完成这个任务？还是说这要根据我的具体问题，所以我必须自己实现？有没有什么Python包可以做到这一点？

Answer 1

我找到的关于这个主题最好的学术资源是《大数据挖掘》第三章，里面对局部敏感哈希和最小哈希做了很好的概述。

简单来说，这个想法是先拿几串字符串，把它们转成向量，然后在这些向量上滑动一个窗口。如果两个向量在同一个窗口位置的值相同，就把它们标记为可以进行更细致的相似性分析的候选者。

在Python的datasketch库中有一个很棒的实现（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.4 for input", i, ":", result

这个会返回：

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