Реализация алгоритма шинглов на 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”, который позволяет находить в тексте части речи. Работает довольно неплохо.

Обработка частей речи с помощью 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. Их я решил пропускать.

Cуществительные к единственному виду

// 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. После чего нашел количество совпавших шинглов и рассчитал результат.

Определение результатов для 2-х текстов

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