🎅🏼 🎄 🥃 Node.JS पर शिंगल एल्गोरिथ्म का कार्यान्वयन। अंग्रेजी ग्रंथों के लिए फजी डुप्लिकेट की खोज करें 💇🏾 📯 🧖🏼

जानकारी के साथ काम करते समय, वेब पेजों को पार्स करना अक्सर होता है। इसके साथ समस्याओं में से एक समान पृष्ठों की पहचान कर रहा है। इस तरह के एक एल्गोरिथ्म का एक अच्छा उदाहरण "शिंगल्स अल्गोरिथम फॉर वेब डॉक्यूमेंट्स" है ।

पार्सिंग परियोजना का एक हिस्सा नोड.जेएस पर लागू किया गया था, इसलिए उस पर लागू करने के लिए एल्गोरिथ्म की आवश्यकता थी। मुझे जावास्क्रिप्ट या एनपीएम पैकेज में कार्यान्वयन नहीं मिला - मुझे अपना खुद का लिखना था।

कोड पर सभी काम ऊपर दिए गए लेख पर आधारित है, इसलिए एल्गोरिथम के सभी बिंदु इसके साथ होंगे, लेकिन कुछ संशोधनों के साथ।

2 दस्तावेजों की समानता निर्धारित करने के लिए, आपको निम्न करना चाहिए:

पाठ को रद्द करना;
दाद में विभाजित;
84x स्थिर कार्यों का उपयोग करते हुए दाद के कंप्यूटिंग हैश;
84 चेकसम मूल्यों का यादृच्छिक नमूना;
तुलना, परिणाम का निर्धारण।

अंक 3.4 मेरे लिए काफी समस्याग्रस्त थे। 1 - आपको हैशिंग के लिए 84 स्टैटिक फ़ंक्शंस और 2 की ज़रूरत है - चेकसम के 84 मूल्यों का एक यादृच्छिक नमूना। यदि 1 समस्या के लिए - समाधान पाया जा सकता है, तो दूसरा मेरे लिए स्पष्ट नहीं है। यदि हमारे पास 84 कार्यों के साथ पाठ के लिए दाद की एक सरणी है, तो यह पता चलता है कि आउटपुट 84xN (दस्तावेज़ में दाद की संख्या) के आयाम के साथ एक 2-आयामी सरणी होगा। अब आपको प्रत्येक पाठ के लिए इस 84-तत्व सरणी के चारों ओर जाने की आवश्यकता है और यादृच्छिक दाद हैश की तुलना करें। आप यादृच्छिक तत्वों की तुलना कर सकते हैं, लेकिन यह विकल्प संयोग नहीं दे सकता है। यदि हम न्यूनतम हैश को लंबाई में लेते हैं, तो md5 के लिए सभी हैश लंबाई में बराबर हैं, और चरित्र कोड द्वारा लंबाई की गणना करना एक अतिरिक्त बोझ है। इसलिए, मैंने crc32 और अनुक्रमिक तुलना का उपयोग करके एक साधारण हैशिंग के साथ आइटम 3 और 4 को बदलने का फैसला किया।
अंतिम एल्गोरिथ्म:

पाठ को रद्द करना;
दाद में विभाजित;
crc32 का उपयोग करके शिंगल हैश की गणना करना;
अनुक्रमिक तुलना, परिणाम का निर्धारण।

1. पाठ का कैननाइजेशन

मेरे मामले में, विहितीकरण में निम्नलिखित शामिल हैं:

HTML संस्थाओं की समाशोधन;
पक्षों पर अतिरिक्त रिक्त स्थान की सफाई (ट्रिम);
ऐसे विशेष वर्णों ",", "\", "\ 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 पैकेज "पॉस" है, जो आपको पाठ में भाषण के कुछ हिस्सों को खोजने की अनुमति देता है। यह बहुत अच्छी तरह से काम करता है।

पॉस के साथ भाषण के प्रसंस्करण भागों

 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);

फिर यह सभी संज्ञाओं को एक ही रूप में लाने के लिए बनी हुई है और कैनोनेज़ेशन ब्लॉक को तैयार माना जा सकता है। यह ध्यान देने योग्य है कि पॉज़ कमांड का बहुवचन संज्ञा जैसे शब्दों का परिचय देता है। मैंने उन्हें छोड़ने का फैसला किया।

एकवचन संज्ञा

 // 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. अनुक्रमिक तुलना, परिणाम का निर्धारण

उदाहरण के लिए, मैंने Google समाचार से 2 समाचार लिए जो उसने इसी तरह दिखाए। मैंने उन्हें एक जसन फ़ाइल में सहेजा और फिर, उच्च गति के लिए, उन्हें Async उपयोगिताओं के समानांतर समानांतर में संसाधित किया। फिर उन्होंने मिलान वाले दादों की संख्या को पाया और परिणाम की गणना की।

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 इन-ऐप खरीदारी पर कम से कम $ 32.5 मिलियन का भुगतान करेगा और ऐप शिकायतों का निपटान करने के लिए Apple 32.5 मिलियन डॉलर का भुगतान करेगा । 10 के बराबर शिंगल में शब्दों की संख्या के साथ - ग्रंथ 2.16% के समान थे जो बहुत अच्छा है।
प्रश्नों से यह स्पष्ट नहीं है कि 84x कार्यों का उपयोग करने का विकल्प बेहतर क्यों है। और साथ ही मैं कुछ एल्गोरिथ्म को एक शिंगल में शब्दों की इष्टतम संख्या की गणना करने के लिए जानना चाहूंगा (10 को वर्तमान में इंगित किया गया है)।
एल्गोरिथ्म का पूरा स्रोत कोड और काम का एक उदाहरण github.com पर देखा जा सकता है

Node.JS पर शिंगल एल्गोरिथ्म का कार्यान्वयन। अंग्रेजी ग्रंथों के लिए फजी डुप्लिकेट की खोज करें

1. पाठ का कैननाइजेशन

2. दाद में विभाजित होना

3. crc32 का उपयोग करके शिंगल हैश की गणना करना

4. अनुक्रमिक तुलना, परिणाम का निर्धारण

More articles: