Ответ 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.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]