Приблизительное сопоставление строк с использованием LSH

Question

Я хотел бы приблизительно сопоставить строки с использованием хеширования, чувствительного к локальности. У меня есть много строк>10M, которые могут содержать опечатки. Для каждой строки я хотел бы сравнить все остальные строки и выбрать те, у которых расстояние редактирования соответствует некоторому порогу.

То есть наивное решение требует O(n^2) сравнений. Чтобы избежать этой проблемы, я подумал об использовании хеширования с учетом локальных особенностей. Тогда почти одинаковые строки приведут к одним и тем же сегментам, и мне нужно будет выполнять только поиск по сегментам. Так что это O(n*C), где C - размер корзины.

Тем не менее, я не понимаю, как представлять строки. Если бы это был текст, я бы представлял в векторном пространстве. Мой главный вопрос заключается в том, можно ли это использовать с помощью LSH, а затем с помощью соответствующего векторного представления строки.

Могу ли я использовать уже реализованную библиотеку для этой задачи? или это зависит от моей проблемы, поэтому я должен реализовать это сам? Есть ли пакет Python, который делает это?

Answer 1

Лучшим академическим ресурсом, который я нашел по этому вопросу, является Глава 3 "Mining of Massive Datasets", которая дает потрясающий обзор хеширования и минхэширования с учетом локальных особенностей.

Вкратце, идея состоит в том, чтобы взять несколько строк, векторизовать эти строки, а затем пропустить скользящее окно над результирующими векторами. Если два вектора имеют одинаковое значение в одной и той же позиции окна, отметьте их как кандидатов для более детального анализа сходства.

В библиотеке 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.5, 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]