Implementation of the shingle algorithm on Node.JS. Search for fuzzy duplicates for English texts

When working with information, parsing web pages often arises. One of the problems with this is identifying similar pages. A good example of such an algorithm is the “Shingles Algorithm for Web Documents” .

Part of the parsing project was implemented on Node.JS, so the algorithm needed to be implemented on it. I did not find implementations in javascript or npm packages - I had to write my own.

All work on the code is based on the article above, so all points of the algorithm will be from it, but with some amendments.

To determine the similarity of 2 documents, you must:

1. canonization of the text;
2. splitting into shingles;
3. computing hashs of shingles using 84x static functions;
4. random sample of 84 checksum values;
5. comparison, determination of the result.

Points 3.4 were quite problematic for me. 1st — you need to find 84 static functions for hashing, and 2nd — a random sample of 84 checksum values. If for the 1st problem - solutions can be found, then the second is not clear to me. If we hash an array of shingles for text with 84 functions, it turns out that the output will be a 2-dimensional array with a dimension of 84xN (number of shingles in the document). Now you need to go around this 84-element array for each text and compare random shingles hashes. You can compare random elements, but this option may not give a match. If we take the minimum hashes in length, then for md5 all the hashes are equal in length, and calculating the length by character codes is an additional burden. Therefore, I decided to replace items 3 and 4 with a simple hashing of shingles using crc32 and a sequential comparison.
The final algorithm:

1. canonization of the text;
2. splitting into shingles;
3. calculating shingle hashes using crc32;
4. sequential comparison, determination of the result.

1. Canonization of the text

In my case, canonization consists of:

1. purification from html entities;
2. clearing of extra spaces on the sides (trim);
3. clearing of such special characters '”', '“', "\ n", '\ r', ',', '.', ':', '$', '#', '"', '(' , ')';
4. cleaning out unnecessary parts of speech in a sentence

First you need to prepare methods for processing text.

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, '');
  };

The first is needed to replace words in the text, and the second to replace specials. characters. Next is the processing itself:

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

There is an npm package “pos” for Node.JS, which allows you to find parts of speech in the text. It works pretty well.

All other specials. I decided to remove the characters after processing parts of speech.

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

Then it remains to bring all nouns to a single form and the canonization block can be considered ready. It is worth noting that pos brings words such as Command's to plural nouns. I decided to skip them.

We remove all multiple spaces and pass the text to the next level.

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

2. Splitting into shingles

With this item, everything is simple. Divide the text by spaces and create arrays.

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. Calculating shingle hashes using crc32

At this point, we go around the array of shingles and hash the lines. The first cycle from 0 to 1 was left from trying to hash using 84 functions. I decided not to clean (suddenly I will return to this idea).

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. Sequential comparison, determination of the result

For example, I took 2 news from google news which he showed as similar. I saved them in a json file and then, for a higher speed, processed them in parallel using Async utilities. Then he found the number of matching shingles and calculated the result.


The formula count*2/(arr1[0].length + arr2[0].length)*100finds the percentage for 2 texts.

Texts for comparison: FTC says Apple will pay at least $ 32.5 million over in-app purchases and Apple will pay $ 32.5m to settle app complaints . With the number of words in the shingle equal to 10 - the texts were similar to 2.16% which is very good.
From the questions it is not clear why the option of using 84x functions is better. And I would also like to know some algorithm for calculating the optimal number of words in a shingle (10 is indicated in the current one).
The entire source code of the algorithm and an example of work can be viewed on github.com