Шингл алгоритмі – тақ қайталанатын мәтінді іздеу

Python: Шингл алгоритмі – тақ қайталанатын мәтінді іздеу

VitaliyRodnenko, 19.01.2009

Бұл мақалада «Шинглдар алгоритмі» деп  аталатын тақ  көшірмелерді табу алгоритмі туралы әңгіме қозғаймыз. Сондай-ақ, мен бұл алгоритмді Python-те іске асырамын.

Неге бұл алгоритмді зерттеуді шештім? Мен SEO-shnikмін, веб-сайттарды насихаттаумен және тағы да сол сияқты әрекеттермен айналысамын. Тиісінше, менің қызметім- белгілі бір сұранысқа  сай іздеу  жүйесін ауыстыру болып табылады. Бірақ мен бір жылдан астам уақыт бойы осы бағытта жұмыс істеген соң іздеу жүйелерінің ішкі бөлігіне қызығушылық таныттым. Олап қалай іздеу спамымен жұмыс істейді, құжаттарды қалай бағалайды және т.б. Тақ көшірмелерді іздестіру іздеу жүйесіндегі клондарды немесе ішінара байланысты беттерді шығаруға мүмкіндік береді(ішінара сөзі белгілі бір мәнді білдіреді, онда белгілі бір іздеу жүйесінде екі құжат бірдей дерлік анықталатын болады).

Мұндай алгоритмдердің бірі - «Шингл алгоритмі» (ағылшын тілінде шингл шөгінді дегенді білдіреді).

Біраз теория

Белгісіз көшірмелерді іздеу екі нысанды ішінара бірдей немесе жоқ деп болжауға мүмкіндік береді. Нысан ретінде мәтіндік файлдар және деректердің басқа түрлері түсіндірілуі мүмкін.

Біз мәтінмен жұмыс істейтін боламыз, алайда алгоритм қалай жұмыс істейтінін түсінген сон менің іске асырғанымды өзіңізге қажет объектілерге беру сізге ешқандай да қиындық туғызбайтын болады.

Назар аударыңыз, объектілердің ұқсастығының абсолютті мәнін, сондай-ақ ұқсас бөліктердің әрқайсысында таңдауды анықтау қажет емес. Біз тек объектілер көшірмелер болып табылама немесе жоқ екендігін білуіміз керек.

Бұл алгоритмді қайда қолдануға болады?

Жоғарыда жазғанымдай, ол іздеу жүйесінде іздеу нәтижесін тазарту үшін қолданылады. Сондай-ақ, бұл алгоритм құжаттарды олардың ұқсастығына қарай топтастыру үшін пайдаланылуы мүмкін.

Шамамен бірдей мәтін

Мәтін түріндегі алгоритмнің міндетін қарастырайық. Мысалы, бізде 8 параграфы бар мәтіндік файл бар. Біз оның толық көшірмесін жасаймыз, содан кейін тек соңғы абзацты қайта жазамыз. Екінші файлдың 7-8 тармағы түпнұсқаның толық көшірмесі болып табылады.

Тағы бір қиындау мысал. Егер біз әрбір 5-6-шы сөзді түпнұсқа мәтіннің көшірмесіне қайта жазсақ, онда мәтін бәрібір көшірме болады.

Елестетіп көріңіз, пайдаланушылардың контентін жасайтын үлкен форум немесе портал бар. Бақылаулар көрсеткендей, пайдаланушылар көшірме-паста жасауды және мазмұнды ұрлауды әдетке айналдырады, оны сәл ғана өзгертеді. Біздің сайтта іздеу механизмі бар. Пайдаланушы сұрауды енгізеді және бірінші позицияларда бір немесе екі сөйлеммен ғана ерекшеленетін оннан астам мәтінге ие болады. Әрине, ол бәрін көруге қызығушылық танытпайды және ол іздеу жүйесінің дұрыс жұмыс істемейтінін түсінеді.

Мұны логикалық түрде жасайық. Іздеу нәтижелерінде ондаған нақты бірдей құжаттардың орнына, біз олардың біреуін көрсетеміз, мысалы, сұранысқа ең сәйкес келетінін, ал төменде ұқсас беттердің тізіміне сілтеме жасаймыз.

Мәселен, егер бірдей мәтін бар болса, барлығын бір жерге жинаудың орнына, оны топтарға бөліп, пайдаланушыға осы топтарға сілтеме береміз.

Шингл алгоритмі қалай жұмыс істейді?

Мәселен, бізде 2 мәтін бар және біз олардың көшірме немесе жоқ екендігін болжауымыз керек. Алгоритмді енгізу бірнеше кезеңдерді қамтиды:

• мәтіндерді канонизациялау;

• мәтінді шинглдарға бөлу;

• тексеру сомасы;

• бірдей ізденістерді іздеу.

Енді нақтырақ. Шинглдардың алгоритмінде мәтіндерді салыстыру жүзеге асырылады. Мен өз ізденісімде CRC32 пайдаланамын, бірақ басқалары қолданылады, мысалы SHA1 немесе MD5 және т.б. Өздеріңіз білетіндей, статикалық функциялардың жинақталымдары өзгерістерге өте сезімтал. Мысалы, келесі екі мәтінге арналған сомалар түбегейлі өзгеше болады: