При работе с информацией часто возникают задачи парсинга веб-страниц. Одной из проблем в этом деле является определение похожих страниц. Хороший пример такого алгоритма — «Алгоритм шинглов для веб-документов».
Часть проекта по парсингу реализована на Node.JS, поэтому и алгоритм нужно было реализовать на нем. Реализаций на javascript или npm-пакетов я не нашел — пришлось писать свою.
Вся работа по коду основана на статье выше, поэтому все пункты алгоритма будет из нее, но с некоторыми поправками.
Для определения схожести 2-х документов необходимо:
- канонизация текста;
- разбиение на шинглы;
- вычисление хешей шинглов с помощью 84х статических функций;
- случайная выборка 84 значений контрольных сумм;
- сравнение, определение результата.
Пункты 3,4 для меня оказались довольно проблематичными. 1-е — необходимо найти 84 статических функции для хеширования, а 2-е – случайная выборка 84-х значений контрольных сумм. Если для 1й проблемы – решения найти можно, то второе мне не ясно. Если массив шинглов для текста мы хешируем 84-мя функциями то выходит что на выходе получится 2-х мерный массив размерностью 84xN(кол-во шинглов в документе). Теперь необходимо обойти этот 84-х элементный массив для каждого текста и сравнить случайные хеши шинглов. Можно сравнивать случайные элементы, но такой вариант может не дать совпадений. Если брать минимальные хеши по длинне, то для md5 все хеши равны по длине, а рассчитывать длину по кодам символов – дополнительная нагрузка. Поэтому я решил пункты 3 и 4 заменить на простое хеширование шинглов с помощью crc32 и последовательное сравнение.
Конечный алгоритм:
- канонизация текста;
- разбиение на шинглы;
- вычисление хешей шинглов с помощью crc32;
- последовательное сравнение, определение результата.
1. Канонизация текста
В моем случае канонизация состоит из:
- очистка от html сущностей;
- очистка от лишних пробелов по бокам(trim);
- очистка от таких спец символов '”', '“', "n", 'r', ',', '.', ':', '$', '#', '"', '(', ')';
- очистка от ненужных частей речи в предложении
Для начала необходимо подготовить методы для обработки текста.
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
Автор: aslikeyou
