Реализация алгоритма шинглов на Node.JS. Поиск нечетких дубликатов для английских текстов

Часть проекта по парсингу реализована на Node.JS, поэтому и алгоритм нужно было реализовать на нем. Реализаций на javascript или npm-пакетов я не нашел — пришлось писать свою.

Вся работа по коду основана на статье выше, поэтому все пункты алгоритма будет из нее, но с некоторыми поправками.

Для определения схожести 2-х документов необходимо:

1. канонизация текста;
2. разбиение на шинглы;
3. вычисление хешей шинглов с помощью 84х статических функций;
4. случайная выборка 84 значений контрольных сумм;
5. сравнение, определение результата.

Пункты 3,4 для меня оказались довольно проблематичными. 1-е — необходимо найти 84 статических функции для хеширования, а 2-е – случайная выборка 84-х значений контрольных сумм. Если для 1й проблемы – решения найти можно, то второе мне не ясно. Если массив шинглов для текста мы хешируем 84-мя функциями то выходит что на выходе получится 2-х мерный массив размерностью 84xN(кол-во шинглов в документе). Теперь необходимо обойти этот 84-х элементный массив для каждого текста и сравнить случайные хеши шинглов. Можно сравнивать случайные элементы, но такой вариант может не дать совпадений. Если брать минимальные хеши по длинне, то для md5 все хеши равны по длине, а рассчитывать длину по кодам символов – дополнительная нагрузка. Поэтому я решил пункты 3 и 4 заменить на простое хеширование шинглов с помощью crc32 и последовательное сравнение.
Конечный алгоритм:

1. канонизация текста;
2. разбиение на шинглы;
3. вычисление хешей шинглов с помощью crc32;
4. последовательное сравнение, определение результата.

1. Канонизация текста

В моем случае канонизация состоит из:

1. очистка от html сущностей;
2. очистка от лишних пробелов по бокам(trim);
3. очистка от таких спец символов ‘”’, ‘“’, "\n", ‘\r’, ‘,’, ‘.’, ‘:’, ‘$’, ‘#’, ‘"’, ‘(‘, ‘)’;
4. очистка от ненужных частей речи в предложении

Для начала необходимо подготовить методы для обработки текста.

var strWordRemove = function(entry) {     var regex = new RegExp('(^|\\s)'  + entry + '(?=\\s|$)', 'g');     text = text.replace(regex, '');   };    var strCharacterRemove = function(entry) {     var escapeRegExp = function (str) {       return str.replace(/[\-\[\]\/\{\}\(\)\*\+\?\.\\\^\$\|]/g, "\\$&");     };      var regex = new RegExp(escapeRegExp(entry), 'g');     text = text.replace(regex, '');   }; 

Первый нужен для замено слов в тексте, а второй для замены спец. символов. Далее идет сама обработка:

  var withoutTagsRegex = /(<([^>]+)>)/ig;    text = text.replace(withoutTagsRegex, "");    text = text.trim();    ['”', '“', "\n", '\r'].forEach(strCharacterRemove); 

Для Node.JS есть npm-пакет “pos”, который позволяет находить в тексте части речи. Работает довольно неплохо.

var words = new pos.Lexer().lex(text);   var taggedWords = new pos.Tagger().tag(words);    var removeWords = [];   var nounWords = [];    for (var i in taggedWords) {     var taggedWord = taggedWords[i];     var word = taggedWord[0];     var tag = taggedWord[1];      //Adjective      /*      JJ Adjective                big      JJR Adj., comparative       bigger      JJS Adj., superlative       biggest      CC Coord Conjuncn           and,but,or      IN Preposition              of,in,by      TO ÒtoÓ                     to      UH Interjection             oh, oops      DT Determiner               the,some      */      //console.log(word + " /" + tag);     if(tag === 'NNS') {       nounWords.push(word);     }      if(['JJ', 'JJR', 'JJS', 'CC', 'IN', 'TO', 'UH', 'DT'].indexOf(tag) !== -1) {       removeWords.push(word);     }   }    removeWords.forEach(strWordRemove); 

Все остальные спец. символы я решил убрать после обработки частей речи.

[',', '.', ':', '$', '#', '"', '(', ')'].forEach(strCharacterRemove); 

Далее осталось привести все существительные к единственному виду и блок канонизации можно считать готовым. Стоить заметить, что pos заносит к множественным существительным такие слова как Command’s. Их я решил пропускать.

// replace all plural nouns to single ones   nounWords.forEach(function(entry) {     //parent’s || Apple’s || Smurf’s     if(entry.length > 2 && entry.slice(-2) === "’s") {       // now skip it. in future we can test to remove it       return ;     }      var newOne = '';      if(entry.length > 3 && entry.slice(-3) === "ies") {       newOne = entry.slice(0, -3) + 'y';     } else if(entry.length > 2 && entry.slice(-1) === "s") {       newOne = entry.slice(0,-1);     } else {       return ;     }      var rexp = new RegExp('(^|\\s)' + entry + '(?=\\s|$)','g')     text = text.replace(rexp, "$1" + newOne );   }); 

Убираем все множественные пробелы и передаем текст на следующий уровень.

text = text.replace(/ +(?= )/g,''); callback(text); 

2. Разбиение на шинглы

С этим пунктом все просто. Делим текст по пробелам и создаем массивы.

var makeShingles = function(text, callback) {   var words = text.split(' ');   var shingles = [];   var wordsLength = words.length;   while(shingles.length !== (wordsLength - shingleLength + 1)) {    shingles.push(words.slice(0, shingleLength).join(' '));    words = words.slice(1);   }    callback(shingles) }; 

3. Вычисление хешей шинглов с помощью crc32

В этом пункте мы обходим массив шинглов и хешируем строки. Первый цикл от 0 до 1 остался от попытки хешировать с помощью 84-х функций. Решил не убирать(вдруг вернусь к этой идее).

var hashingShingles = function(shingles, callback) {   var hashes = [];   for(var i = 0, n = 1; i < n; i++) {     var hashedArr = [];     for(var j = 0, k = shingles.length; j < k; j++) {         hashedArr.push(crc.crc32(shingles[j]));     }     hashes.push(hashedArr);   }    callback(hashes); }; 

4. Последовательное сравнение, определение результата

Для примера я взял 2 новости из google news которые тот показал как похожие. Сохранил их в json файле и далее, для более высокой скорости, обрабатывал параллельно с помощью Async utilities. После чего нашел количество совпавших шинглов и рассчитал результат.

var fileJSON = require('./article1.json'); var content1 = fileJSON.content;  var fileJSON2 = require('./article2.json'); var content2 = fileJSON2.content;  var async = require('async');  async.parallel([   function(callback){     textCanonization(content1, function(text) {       makeShingles(text, function(shingles) {         hashingShingles(shingles, function(hashes) {           callback(null, hashes);         });       })     });   },   function(callback){     textCanonization(content2, function(text) {       makeShingles(text, function(shingles) {         hashingShingles(shingles, function(hashes) {           callback(null, hashes);         });       })     });   } ], function(err, results){     var firstHashes = results[0];     var secondHashes = results[1];       var compareShingles = function(arr1, arr2) {       var count = 0;        arr1[0].forEach(function(item) {         if(arr2[0].indexOf(item) !== -1) {           count++;         }       });        return count*2/(arr1[0].length + arr2[0].length)*100;     };      var c = compareShingles(firstHashes, secondHashes);      console.log(c);   }); 

Формула count*2/(arr1[0].length + arr2[0].length)*100 находит процентное соотношение для 2х текстов.

Тексты для сравнения: FTC says Apple will pay at least $32.5 million over in-app purchases и Apple will pay $32.5m to settle app complaints. При количестве слов в шингле, равном 10 — тексты были похожи на 2.16% что очень неплохо.
Из вопросов не ясно, чем вариант использования 84х функций лучше. А также хотелось бы знать какой-то алгоритм для высчитывания оптимального количества слов в шингле(в текущем указано 10).
Весь исходный код алгоритма и пример работы можно посмотреть на github.com