Javascript minhash функция для генерации характерного хеш-ключа для строкового текста - PullRequest
Новая
       24

Javascript minhash функция для генерации характерного хеш-ключа для строкового текста

0 голосов
/ 20 марта 2019

В настоящее время я испытываю алгоритм функции minhash для проверки сходства между двумя текстами (или документами) на основе этого модуля: https://github.com/sjhorn/node-minhash/blob/master/lib/minhash.js.

В этой функции я разделяю свой текст на токены (или k-shingles), а затем вычисляю число хеш-функций для каждого из токенов / shingles: 

crc32.str(token) & 0xffffffff

поэтому я возвращаю массив чисел для разных частей моего токена. Пример: 

The quick brown fox jumps over the lazy dog.  ==  -3677935418
The quick brown fox jumps over the lazy dog.  ==  -3191969143
The quick brown fox jumps over the lazy dog.  ==  -2264094193
The quick brown fox jumps over the lazy dog.  ==  -4003895775
The quick brown fox jumps over the lazy dog.  ==  -4077650760
The quick brown fox jumps over the lazy dog.  ==  -3917776217
The quick brown fox jumps over the lazy.  ==  -3677935418
The quick brown fox jumps over the lazy.  ==  -3191969143
The quick brown fox jumps over the lazy.  ==  -2264094193
The quick brown fox jumps over the lazy.  ==  -4003895775
The quick brown fox jumps over the lazy.  ==  -4077650760
The quick brown fox jumps over the lazy.  ==  -2302592728
M1 length: 6
M2 length: 6
Minhash1: -3677935418  Minhash2: -3677935418
Minhash1: -3191969143  Minhash2: -3191969143
Minhash1: -2264094193  Minhash2: -2264094193
Minhash1: -4003895775  Minhash2: -4003895775
Minhash1: -4077650760  Minhash2: -4077650760
shared: 5 total: 6
Shared/Total: 0.8333333333333334

По сравнению друг с другом совпадающие хэш-числа очень похожи. В этом примере число перестановок равно 6.

Теперь мой вопрос, я хотел бы знать, как создать единственную характеристическую строку хеш-функции для этого текста, потому что все модули сравнивают только тексты напрямую друг с другом и выводят коэффициент подобия. Для похожих текстов / документов хеш-строки также должны быть одинаковыми. Пример (примерно так): 

The quick brown fox jumps over the lazy dog

Hash: KV5rsUfZpcZdVojpG8mHLA==

The quick brown fox jumps over the lazy

Hash: KV5rsUfZpcZdVojpG8hTPS==

Возможно ли как-то создать идентификационную хеш-строку из одиночных токенов-хешей? И закодировать их в шестнадцатеричную строку или что-то подобное?

РЕДАКТИРОВАТЬ: я знаю, что есть что-то вроде MongoDB Object_ID, который представляет собой уникальную шестнадцатеричную строку, которая создается из 3 полей: 

a 4-byte value representing the seconds since the Unix epoch,
a 5-byte random value, and
a 3-byte counter, starting with a random value.

https://docs.mongodb.com/manual/reference/method/ObjectId/

Было бы неплохо сделать что-то похожее с Token-Array ... но я понятия не имею, как: (

РЕДАКТИРОВАТЬ: я создал из числа токенов шестнадцатеричный токен строки и соединил их вместе: 

function convertToHex(numberArray) {
    if (Array.isArray(numberArray)) {
        return numberArray.map((number) => {
            if (number < 0)
            {
              number = 0xFFFFFFFF + number + 1;
            }

            return number.toString(16).toUpperCase();
            // number = number >>> 0;
            // return pa
        });
    } else {
        return null;
    }        
}

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

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

...