使用LSH的近似字符串匹配

Question

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

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

然而，我不明白如何表示字符串。如果它是文本，我会在向量空间中表示。我的主要问题是，如果使用LSH，然后使用适当的字符串向量表示，这是否可以处理。

我能使用一个已经实现的库来完成这个任务吗?还是取决于我的问题，所以我必须自己实现?有什么python包能做到这一点吗?

Answer 1

我找到的关于这个主题的最好的学术资源是《海量数据集挖掘》的第3章，它给出了对位置敏感哈希和最小哈希的一个很棒的概述。

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

在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]