Node.js / javascript модуль minhash, который выводит похожую хеш-строку для похожего текста

Question

Я ищу модуль node.js / Javascript, который применяет алгоритм minhash к строке или большему тексту и возвращает мне «идентифицирующую» или «характеристическую» строку байтов или строку Hexstring для этого текста.Если я применяю алгоритм к другой подобной текстовой строке, строка хеша также должна быть похожей.Такой модуль уже существует?

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

По сути, я ищу этот код здесь (Java): в Javascript: https://github.com/codelibs/elasticsearch-minhash

например, для строки типа: "The quick brown fox jumps over the lazy dog" и "The quick brown fox jumps over the lazy d" это создаст хэш для первого предложения, например:

"KV5rsUfZpcZdVojpG8mHLA=="

, а для второй строки что-то вроде:

KV5rsSfZpcGdVojpG8mGLA==

обе хеш-строки не очень сильно отличаются ... в этом суть алгоритма minhash, однако я не знаю, как создать подобную хеш-строку ... и все библиотеки, которые я нашел, толькосравнивайте непосредственно 2 документа и создавайте коэффициент сходства, но они не создают хеш-строку, характерную для документа ... Сходство со всеми алгоритмамиявляется то, что они создают хеш-значение crc32 (или аналогичное) для своего массива слов токенов (или shingles).Но я до сих пор не знаю, как они сравнивают эти хэши друг с другом ...

Answer 1

Если вы намереваетесь сравнивать только два документа за раз (насколько сходен документ A с документом B?), То сохранение мини-хэшей каждого документа в виде объединенной строки - это нормально. Вы бы сравнили два документа, разбив строки каждого документа обратно на составляющие их мини-хэши и посчитав, сколько мини-хэшей было разделено (идентично).

Но если вы хотите спросить «какие другие документы похожи на документ А», это плохое решение, поскольку вам придется сравнивать документ А по отдельности с любым другим документом, который вы ранее видели. Хуже того, если вы хотите найти все сходства между документами в корпусе, вы должны сравнить каждый документ с любым другим документом. В группе из 1000 документов это потребует 499 500 сравнений. С миллионами документов это почти 500 миллиардов сравнений. Это проблема O (n ² ).

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

Скорее всего, вас интересуют только сходства, когда, по крайней мере, скажем, половина minhashes разделена (примерно 50% сходство с jaccard), но для их поиска все еще может потребоваться много вычислений, поскольку могут быть миллионы документы, которые разделяют по крайней мере один minhash с входящим документом, и вам нужно подсчитать количество общих хэшей для каждого. Хеширование с учетом локальных условий может существенно сократить количество обращений (и необходимое хранилище).

Answer 2

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

const str1 = "The quick brown fox jumps over the lazy dog";
const str2 = "The quick brown fox jumps over the lazy d";
console.log(str1);
console.log(str2);
var s1 = str1.split(' ');
var s2 = str2.split(' ');

// create a hash for each set of words to compare
// default numPerm is 128 but that gives very long hash
// below 8, almost similar string will give exactly the same hash
var m1 = new Minhash({numPerm: 8});
var m2 = new Minhash({numPerm: 8});

// update each hash
s1.map(function(w) { m1.update(w) });
s2.map(function(w) { m2.update(w) });


// estimate the jaccard similarity between two minhashes
console.log('jaccard similarity:', m1.jaccard(m2));

// Now to convert hashvalues to a string we use a kind of base64
// encode but since hasvalues is an array of 32bits integer we
// have to explode it into a array of 8bits integers first

// for a given int32 returns 4 bytes
function int32ToBytes(num) {
    // the hexadecimal representation of the largest 32bits unsigned integer is 0xFFFFFFFF
    // the hexadecimal representation of the largest unsigned integer (8bits === a byte) is 0xFF
    // so it is possible to think a 32bits uint (unsigned integer) as the concatenation of 4 8bits uint.
    // the bitwise & operator is the bitwise AND
    // its table of truth is 0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0 and 1 & 1 = 1
    // for instance 8 & 1 <=> 0b111 & 0b001 <=> 0b001 <=> 1

    // the same is possible with hex representation:
    // 65535 & 255 <=> 0xFFFF & 0x00FF <=> 0x0FF <=> 255
    // 65535 & 65280 <=> 0xFFFF & 0xFF00 <=> 0xFF00 <=> 65280
    // 255 + 65535 = 65535

    // now about the bitwise >> shift operator
    // a >> n shift the number a by n bits to the right
    // in hex FF is 8bits so `0xFF00 >> 8 = 0xFF`
    // this operation is reversible `0xFF << 8 = 0xFF00`

    // 0xFFFF needs 16 bits to be represented, as 0xFF00
    // but 0xFF only needs 8 bits
    // so its possible to split a 16 bits integer into two 8 bits integer this way:
    // int16 = (int16 & 0xFF00) >> 8 + (int16 & 0x00FF) >> 0
    // no information was lost because we're able to do the reverse operation

    // the same principle is used below to encode a 32 bits integer into 4 bytes (8bits integers)
   // max uint32 = 0xFFFFFFFF =
   // 0xFF << 24 + 0xFF << 16 + 0xFF << 8 + 0xFF << 0
    

  
    const arr = [
        (num & 0xff000000) >> 24,
        (num & 0x00ff0000) >> 16,
        (num & 0x0000ff00) >> 8,
        (num & 0x000000ff)
    ];
    return arr;
}

// tolerant base64 encode of 4 bytes
function Uint8ToString(u8a){
  var CHUNK_SZ = 0x8000;
  var c = [];
  for (var i=0; i < u8a.length; i+=CHUNK_SZ) {
    c.push(String.fromCharCode.apply(null, u8a.subarray(i, i+CHUNK_SZ)));
  }
  return c.join("");
}

// tolerant base64 encode of int32 array
function base64EncodeInt32Array(intArray) {
    let str = '';
    intArray.forEach((i) => {
        var u8 = new Uint8Array(int32ToBytes(i));
        var b64encoded = btoa(Uint8ToString(u8));
        str += b64encoded;
    });
    
    return str;
    
}

// replace non significant '==' to shorten hash
console.log(base64EncodeInt32Array(m1.hashvalues).replace(/==/g, ''));
console.log(base64EncodeInt32Array(m2.hashvalues).replace(/==/g, ''));

<script src='https://rawgit.com/duhaime/minhash/master/minhash.min.js'></script>