Clever Geek Handbook

Node.JSでのシングルアルゴリズムの実装。 英語テキストのあいまいな重複を検索する

情報を扱うとき、Webページの解析が頻繁に発生します。 これに関する問題の1つは、同様のページを識別することです。 そのようなアルゴリズムの良い例は、 「Webドキュメントの帯状疱疹アルゴリズム」です。



解析プロジェクトの一部はNode.JSに実装されていたため、アルゴリズムを実装する必要がありました。 javascriptまたはnpmパッケージに実装が見つかりませんでした-自分で作成する必要がありました。



コードに関するすべての作業は上記の記事に基づいているため、アルゴリズムのすべてのポイントはそこからですが、いくつかの修正が加えられています。



2つのドキュメントの類似性を判断するには、以下を行う必要があります。

  1. テキストの正規化;
  2. 帯状疱疹への分割;
  3. 84x静的関数を使用して帯状疱疹のハッシュを計算。
  4. 84個のチェックサム値のランダムサンプル。
  5. 比較、結果の決定。


ポイント3.4は私にとって非常に問題がありました。 1番目—ハッシュ用に84個の静的関数を見つける必要があり、2番目—チェックサムの84個の値のランダムサンプルを見つけます。 最初の問題-解決策が見つかる場合、2番目の問題は私には明らかではありません。 84個の関数でテキスト用の帯状疱疹の配列をハッシュすると、出力は84xN（ドキュメント内の帯状疱疹の数）の次元を持つ2次元配列になることがわかります。 次に、各テキストについてこの84要素の配列を回避し、ランダムなシングルハッシュを比較する必要があります。 ランダムな要素を比較できますが、このオプションは一致しない場合があります。 長さの最小ハッシュを取得する場合、md5ではすべてのハッシュの長さが等しくなり、文字コードによる長さの計算は追加の負担になります。 そのため、crc32と順次比較を使用して、項目3と4を単一の単純なハッシュに置き換えることにしました。

最終的なアルゴリズム：

  1. テキストの正規化;
  2. 帯状疱疹への分割;
  3. crc32を使用してシングルハッシュを計算します。
  4. 逐次比較、結果の決定。


1.テキストの正規化


私の場合、正規化は以下で構成されます。

  1. htmlエンティティのクリア。
  2. 両側の余分なスペースのクリア（トリム）;
  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, ''); };




最初はテキスト内の単語を置き換えるために必要であり、2番目はスペシャルを置き換えるために必要です。 文字。 次は処理自体です。 



  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のような単語を複数の名詞に導入することは注目に値します。 私はそれらをスキップすることにしました。

単数名詞 
 // 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つのニュースを取り上げたが、彼はそれを同じように見せた。 それらをjsonファイルに保存してから、高速化するために、非同期ユーティリティを使用して並列に処理しました。 その後、彼は一致する帯状疱疹の数を見つけ、結果を計算しました。



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によると、Appleはアプリ内購入に対して少なくとも3,250万 ドルを支払い 、 Appleはアプリの苦情を解決するために 3,250万 ドルを支払います。 シングルに含まれる単語の数が10に等しい場合、テキストは2.16％に近く、非常に良好です。

質問から、84x関数を使用するオプションが優れている理由は明らかではありません。 また、シングルの単語の最適な数を計算するためのアルゴリズム（現在の例では10が示されています）も知りたいです。

アルゴリズムのソースコード全体と作業例は、 github.comで表示できます。


More articles:


All Articles