[ Cum? ] Offline Search cu Damerau-Levenshtein, Bayes, weights și filtre 03/08/2018

Ce e aia „Offline Search” și hă?

TL;DR

„Offline Search” e un fel de OnPage Search, doar că extins pe tot site-ul și rulează pe client (JavaScript). Presupune să ai un dicționar și un hashmap din conținut, dând posibilitatea unei pagini statice să fie searchable. Ca să nu fie banal pui un Damerau-Levenstein pentru avion și pentru rachetă mai bagi un Bayes și niste weights. Dacă mai punem și niște filtre… navă spațială.

Plecăm de la premisa: „Site-ul meu, e o carte„.

Dacă stai să compari e cam același lucru, dar diferența e că site-ul e on-line și cartea e fizică. Ca și esență:

  • O carte are n pagini;
  • O carte are m cuvinte;
  • Un cuvânt îl pot găsi în mai multe pagini sau deloc.

Deci, convertim site-ul la o carte… ceva de genul. Printer ON! (glumesc…).

Ca și pași pentru setup, ar fii următorii, dar nu musai:

  1. Extragem textele din site într-un singur obiect JSON, unde cheia e URI-ul și valoarea e conținutul paginii pe care l-am curățat (strip, trim, encode… etc).
    var site_content = {
    "/some/url/to/page/1" : "Bla bla bla",
    "/some/url/to/page/2" : "More bla bla bla",
    "/some/url/to/page/3" : "Even more bla bla bla"
    }
  2. Mai creem un JSON cu ocurența fiecărui cuvânt. În română, numărăm, pentru fiecare cuvânt, de câte ori apare în site-ul nostru. Cheia e cuvântul în sine si valoarea e de câte ori l-am găsit.
    var cuvinte = {
    "cuvânt1" : "10",
    "cuvânt2" : "3",
    "cuvânt3" : "26"
    }

SetUp-ul e cam gata, o să descriu procesul în sine, în linii mari.

Vine ninja pe pagina ta, scrie ceva în search și-i dă submit. Prima dată o să cauți cuvântul/cuvintele în obiectul cu ocurență și dacă există, îl/le cauți apoi în colecția mare. Nimic special aici.

Dacă nu există, aici devine interesant. Poți presupune că ninja e alfabetist și încerci să-i corectezi cuvintele și le cauți în colecția mare. „Aha… le corectez…”, ai zice tu. Cum știi ce a vrut să zică poietul?… păi nu știi :), dar poți în schimb să cauți un alt cuvânt din colecția ta cu distanța Levenshtein cea mai mică. „Ce-i aia?”, men, ai răbdare că ajungem și acolo.

Am făcut la început analogia că site-ul nostru e o carte… right? Deci, search-ul tău e restrans doar la ce e în ea și ce caută poietul nostru ar trebui să fie acolo. Sunt sigur ca nu ai căuta „avion” într-o carte cu bucate, gen. Bun…

Nenea ăsta, Levenshtein, a publicat o teoremă prin 65 și a zis că distanța între 2 cuvinte, a și b, este egală cu numărul de operații (inserare, ștergere și înlocuire) pe care le aplicăm pe cuvîntul a să devină b.

Ca și-un exemplu simplu, presupunem că poietul a scris „cvant1” și calculăm distanța pe cuvintele din exemplu cu ocurența și am avea

a b dist
cvant1 cuvânt1 2; inserare + înlocuire
cvant1 cuvânt2 3; inserare + înlocuire x 2
cvant1 cuvânt3 3; inserare + înlocuire x 2

 

Distanța cea mai mică e la „cuvânt1”, deci probabil, asta a vrut să scrie.

Ok, dar în titlu e și-un nene Damerau. Păi nenea asta, Damerau, s-a uitat la ce-o facut nenea ălălalt și a zis că mai este o operație care a omis-o. Aia e inversarea a 2 litere și btw, toate 4 operațiile enumerate de aștia 2 s-au demonstrat a fii 80% din totalul cauzelor pentru care poietul a scris altceva. Tot aici, ai mai putea calcula și distanța dintre taste pe-un anumit layout și ai folosi-o ca și penalty pentru o mai bună predicție, asta ca și îmbunătățire la ce au zis aștia 2. Ca și hint, ai putea folosi distața euclidiană, dacă maparea tastelor e carteziană.

Ca și recap, avem:

  • textele;
  • map cu cuvinte și ocurența lor;
  • o metodă să ghicim ce a vrut să zică ninja.

Treaba cu distanța e nice, doar că ne mai trebuie ceva dacă există mai multe cuvinte cu aceeași distanță. Dacă ar fi să căutăm „cvant”, folosind exemplu de mai sus, am avea:

a b dist
cvant cuvânt1 3; inserare x2 + înlocuire
cvant cuvânt2 3; inserare x2 + înlocuire
cvant cuvânt3 3; inserare x2 + înlocuire

Oare, care e? Hmm… Aici îl introducem pe Bayes (tip pe care l-am urât în facultate…). Are și el o teoremă cu care ai putea determina probabilistic care ar putea fi cuvântul căutat. Nu are rost să explic formula, sunt mii de exemple pe net. Dacă am aplica teorema pe exemplul de mai sus, am avea:

a b dist Bayes P
cvant cuvânt1 3; inserare x2 + înlocuire 0.1xxxx
cvant cuvânt2 3; inserare x2 + înlocuire 0.0xxxx
cvant cuvânt3 3; inserare x2 + înlocuire 0.6xxxx

Rezultă că, cuvânt3 ar fii cel mai probabil, deoarece ocurența lui este cea mai mare. Acum în lumea reală, tu o să-i afișezi rezultatele pentru cuvânt3, dar o să o arzi „Did you mean”, gen google, și o să-i arăți și restul rezultatelor care au o probabilitate >= cu-n threshold.

Mai zice în titlu de weights și filtre.

Weights 1st

Pentru un search cu exact match, teoretic nu ai nevoie de weights. Ai găsit ceva bine, altfel îi dai un mesaj frumos cu mai încearcă 🙂 Dar dacă omulețul care a căutat ceva a folosit tehnica numită inversiune pentru că-și exersează stilul poetic… și ar exista rezultate, doar că în altă formă. No aici, ai putea face tot felul de morfisme de genu permutări, aranjamente și combinări, dar cred că mai simplu ai putea folosi some weights. Spre ex:

  • lungimea cuvântului;
  • ocurența lui în fragmentul căutat;
  • poziția lui față de cuvintele cu care a fost căutat împreună;

Când zic filtre mă refer mai mult la procesul prin care o să ne construim colecția de cuvinte, dar o poți aplica și în timpul procesului de căutare. Nimic fancy aici și ca exemple:

  • am putea exclude toate cuvintele care au o lungime mai mică sau egală cu 2. Gen: „și”, „în”, etc
  • am putea converti diacriticile, pentru că nu toată lumea le folosește;

O să adaug si-un demo într-o zi, când o să am timp liber… Spor!