Как сравнить сходство документов с алгоритмом Симхаша?

Question

В настоящее время я создаю программу, которая может вычислить почти одинаковую оценку в совокупности текстовых документов (+5000 документов). Я использую Simhash для создания уникального документа (благодаря этому репозиторию github)

мои данные:

data = {
    1: u'Im testing simhash algorithm.',
    2: u'test of simhash algorithm',
    3: u'This is simhash test.',
}

и это дает мне 3 хеша, как это:

00100110101110100011111000100010010101011001000001110000111001011100110101001101111010100010001011001011000110000100110101100110

00001001110010000000011000001000110010001010000101010000001100000100100011100100110010100000010000000110001001010110000010000100

10001110101100000100101010000010010001011010001000000000101000101100001100100000110011000000011001000000000110000000100110000000

А теперь, как сравнить эти 3 хэша? Я знаю, что я должен разделить их на блоки, но у меня нет точного метода?

Что я хочу сделать, так это вывести все дублированные документы (>70%) с их идентификаторами и идентификаторами дубликатов документов.

Может кто-нибудь помочь?

Answer 1

Прежде чем ответить на ваш вопрос, важно иметь в виду две вещи:

1. Simhash обнаруживает близкие дубликаты, а не точные дубликаты. Это означает, что почти дубликаты будут иметь одинаковый хеш.
2. Примеры, которые вы вставили здесь, слишком малы и, учитывая их размер, их различия значительны. Алгоритм предназначен для работы с большими веб-документами, а не с небольшими предложениями.

Теперь я ответил на ваш вопрос о проблеме Github, который вы подняли здесь.

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

# assuming that you have a dictionary with document id as the key and the document as the value: 
# documents = { doc_id: doc } you can do:

from simhash import simhash

def split_hash(str, num):
    return [ str[start:start+num] for start in range(0, len(str), num) ]

hashes = {}
for doc_id, doc in documents.items():
    hash = simhash(doc)

    # you can either use the whole hash for higher precision or split into chunks for higher recall
    hash_chunks = split_hash(hash, 4)

    for chunk in hash_chunks:
        if chunk not in hashes:
            hashes[chunk] = []
        hashes[chunk].append(doc_id)

# now you can print the duplicate documents:
for hash, doc_list in hashes:
    if doc_list > 1:
        print("Duplicates documents: ", doc_list)

Пожалуйста, дайте мне знать, если что-то не понятно.

Answer 2

В дополнение к ответу Memos, если вы хотите обнаружить сходство>=70%, вы не можете использовать simhash. Simhash позволяет обнаруживать достаточно малые расстояния Хэмминга, с разницей примерно в 6 или 7 битов, в зависимости от размера вашего корпуса. Для сходства в 70% вы должны допустить разницу в 19 бит, что невозможно в любом обычном сценарии. Вы должны вместо этого заглянуть в minhash.

Если вам интересно, вот обширное объяснение simhash.