Bazele algoritmului motorului de cautare

Adevarat SAU Fals Motoarele de cautare au evoluat enorm in ultimii ani, dar la inceput puteau sa se ocupe doar de operatori booleeni. In termeni simpli, un termen a fost inclus intr-un document sau nu. Ceva a fost adevarat sau fals, 1 sau 0. In plus, puteti utiliza operatorii ca AND, OR si NOT pentru a cauta documente care contin mai multi termeni sau pentru a exclude termeni.

Acest lucru suna destul de simplu, dar are unele probleme cu el. Sa presupunem ca avem doua documente, care constau din urmatoarele texte:

Doc1: „Si restaurantul nostru din New York serveste crochete si bitterballen.”

Doc2: „In Tarile de Jos recuperati crochete si frikandellen de pe zid.”  

Hopa, aproape ca am uitat sa-ti arat frikandellenul 😉

Daca ar fi sa construim un motor de cautare, primul pas este tokenizarea textului. Dorim sa putem determina rapid ce documente contin un termen. Acest lucru este mai usor daca punem token-uri intr-o baza de date. Un token este un singur termen dintr-un text, deci cate simboluri contine Doc1?

In momentul in care ai inceput sa raspunzi singur la aceasta intrebare, probabil te-ai gandit la definitia unui „termen”. De fapt, in exemplu, „New York” ar trebui recunoscut ca un singur termen. Modul in care putem determina ca cele doua cuvinte individuale sunt de fapt un singur cuvant este in afara domeniului de aplicare al acestui articol, asa ca in acest moment amenintam fiecare cuvant separat ca un simbol separat. Deci avem 10 jetoane in Doc1 si 11 jetoane in Doc2. Pentru a evita duplicarea informatiilor din baza noastra de date, vom stoca tipuri si nu jetoane.

Tipurile sunt simbolurile unice dintr-un text. In exemplu, Doc1 contine de doua ori simbolul „si”. In acest exemplu ignor faptul ca „si” apare o data cu si o data fara a fi scris cu majuscule. Ca si in cazul stabilirii unui termen, exista tehnici pentru a determina daca ceva trebuie de fapt capitalizat. In acest caz, presupunem ca il putem stoca fara majuscule si ca „Si” si „si” sunt de acelasi tip.

Stocand toate tipurile in baza de date cu documentele unde le putem gasi, putem cauta in baza de date cu ajutorul booleanilor. Cautarea „crochete” va avea ca rezultat atat Doc1, cat si Doc2. Cautarea pentru „crochete AND bitterballen” va returna doar Doc1 ca rezultat. Problema cu aceasta metoda este ca este posibil sa obtineti prea multe sau prea putine rezultate. In plus, ii lipseste capacitatea de a organiza rezultatele. Daca vrem sa ne imbunatatim metoda, trebuie sa stabilim ce putem folosi in afara de prezenta/absenta unui termen intr-un document. Ce factori de pe pagina ati folosi pentru a organiza rezultatele daca ati fi Google?

Indici de zona

O metoda relativ simpla este utilizarea indicilor de zona. O pagina web poate fi impartita in diferite zone. Ganditi-va la un titlu, descriere, autor si corp. Adaugand o greutate fiecarei zone dintr-un document, putem calcula un scor simplu pentru fiecare document. Aceasta este una dintre primele metode pe pagina utilizate de motoarele de cautare pentru a determina subiectul unei pagini. Functionarea scorurilor pe indici de zona este urmatoarea:

Sa presupunem ca adaugam urmatoarele greutati in fiecare zona:

Greutatea zonei titlu 0,4 descriere 0,1 continut 0,5

Efectuam urmatoarea interogare de cautare: „crochete AND bitterballen”

Si avem un document cu urmatoarele zone:

Zona Continut Boolean Titlul punctajului New York Cafe 0 0 descriere Cafenea cu crochete delicioase si bitterballen 1 0,1 continut Restaurantul nostru din New York serveste crochete si bitterballen 1 0,5 Total 0,6    

Deoarece la un moment dat toata lumea a inceput sa abuzeze de greutatile atribuite, de exemplu, descrierii, a devenit mai important ca Google sa imparta corpul in zone diferite si sa atribuie o greutate diferita fiecarei zone individuale a corpului.

Acest lucru este destul de dificil deoarece web-ul contine o varietate de documente cu structuri diferite. Interpretarea unui document XML de catre o astfel de masina este destul de simpla. Cand interpretati un document HTML, devine mai greu pentru o masina. Structura si etichetele sunt mult mai limitate, ceea ce face analiza mai dificila. Bineinteles ca va exista HTML5 in viitorul apropiat si Google accepta microformate, dar inca are limitarile sale. De exemplu, daca stiti ca Google acorda mai multa pondere continutului dineticheta si mai putin la continutul din eticheta, nu veti folosi niciodata eticheta.

Pentru a determina contextul unei pagini, Google va trebui sa imparta o pagina web in blocuri. In acest fel, Google poate judeca care blocuri dintr-o pagina sunt importante si care nu. Una dintre metodele care poate fi folosita este raportul text/cod. Un bloc pe o pagina care contine mult mai mult text decat codul HTML contine probabil continutul principal al paginii. Un bloc care contine multe link-uri / cod HTML si putin continut este probabil meniul. Acesta este motivul pentru care alegerea editorului WYSIWYG potrivit este foarte importanta. Unii dintre acesti editori folosesc o multime de cod HTML inutil.

Utilizarea raportului text/cod este doar una dintre metodele pe care un motor de cautare le poate folosi pentru a imparti o pagina in blocuri. Bill Slawski a vorbit despre identificarea blocurilor la inceputul acestui an.

Avantajul metodei indexurilor de zona este ca puteti calcula destul de simplu un scor pentru fiecare document. Desigur, un dezavantaj este ca multe documente pot obtine acelasi punctaj.

Frecventa termenilor

Cand v-am rugat sa va ganditi la factorii de pe pagina pe care i-ati folosi pentru a determina relevanta unui document, probabil v-ati gandit la frecventa termenilor de interogare. Este un pas logic sa cresti greutatea fiecarui document folosind termenii de cautare mai des.

Unele agentii SEO tin de povestea utilizarii cuvintelor cheie pe un anumit procent din text. Stim cu totii ca nu este adevarat, dar permiteti-mi sa va arat de ce. Voi incerca sa explic pe baza urmatoarelor exemple. Iata cateva formule care trebuie sa apara, dar, asa cum am spus, conteaza conturul povestii.

Documentul 2 este in acest caz mai strans legat de interogare. In acest exemplu, termenul „si” castiga cel mai mult in greutate, dar este corect? Este un cuvant stop si ne place sa ii acordam doar o mica valoare. Putem realiza acest lucru utilizand frecventa inversa a documentului (tf-idf), care este opusul frecventei documentului (df). Frecventa documentelor este numarul de documente in care apare un termen. Frecventa inversa a documentelor este, ei bine, opusul. Pe masura ce numarul de documente in care un termen creste, idf se va micsora.

Model vectorial

Putem rezolva acest lucru analizand asemanarea cosinusului unui document. O explicatie exacta a teoriei din spatele acestei metode este in afara domeniului acestui articol, dar va puteti gandi la ea ca la un fel de medie armonica intre termenii de interogare din document. Am facut un fisier excel, ca sa te poti juca singur cu el.

Exista o explicatie in fisierul in sine. Aveti nevoie de urmatoarele valori:

• Termeni de interogare – fiecare termen separat din interogare.
• Frecventa documentelor – cate documente stie Google care contin termenul respectiv?
• Frecventa termenului – frecventa pentru fiecare termen de interogare separat din document.

O explicatie a tabelului:

• tf = frecventa termenului
• df = frecventa documentului
• idf = frecventa inversa a documentului
• Wt,q = greutatea termenului din interogare
• Wt,d = greutatea pentru termenul din document
• Produs = Wt,q * Wt,d
• Scor = Suma produselor

Pagina principala, care a fost clasat

Document de interogare la termen TF DF IDF WT , Q TF WF WT , D FIETS 1 25.500.000 3.610493159 3.610493159 21 441 0.70711 2.55302 KOPEN 1 118.000.000 2.945151332 2.9452 21 441 0.70711 2.082258                  

Pagina pe care am vrut sa o clasific

Document de interogare la termen TF DF IDF WT , Q TF WF WT , D FIETS 1 25.500.000 3.610493159 3.610493159 22 484 0.61782 2.23063 KOPEN 1 118.000.000 2.945151332 2.945151332 28 784 0.786331 2.31584                  

Desi al doilea document contine termenii de interogare mai des, scorul documentului pentru interogare a fost mai mic (mai mare este mai bine). Acest lucru se datoreaza lipsei de echilibru intre termenii de interogare. In urma acestui calcul, am schimbat textul de pe pagina si am crescut utilizarea termenului „fietsen” si am redus utilizarea „kopen” care este un termen mai generic in motorul de cautare si are o greutate mai mica. Acest lucru a schimbat scorul dupa cum urmeaza:

Document de interogare la termen TF DF IDF WT , Q TF WF WT , D FIETS 1 25.500.000 3.610493159 3.610493159 28 784 0.78631 2.83897 KOPEN 1 118.000.000 2.945151332 2.945151332 22 484 0.61782 1.81960                  

Dupa cateva zile, Google a accesat cu crawlere pagina si documentul pe care l-am schimbat a inceput sa se claseze pentru termen. Putem concluziona ca numarul de ori in care folositi un termen nu este neaparat important. Este important sa gasiti echilibrul potrivit pentru termenii pe care doriti sa ii clasati.

Accelerarea procesului

Pentru a efectua acest calcul pentru fiecare document care corespunde interogarii de cautare, a costat o mare putere de procesare. Puteti remedia acest lucru adaugand niste valori statice pentru a determina pentru ce documente doriti sa calculati scorul. De exemplu, PageRank este o valoare statica buna. Cand calculati pentru prima data scorul pentru paginile care se potrivesc cu interogarea si care au un PageRank ridicat, aveti o schimbare buna pentru a gasi cateva documente care ar ajunge oricum in primele 10 rezultate.

Utilizarea listelor de campioni

Pentru fiecare termen luati numai primele N documente cu cel mai bun punctaj pentru acel termen. Daca aveti apoi o interogare cu mai multi termeni, puteti intersecta acele liste pentru a gasi documente care contin toti termenii de interogare si probabil au un scor mare. Numai daca exista prea putine documente care contin toti termenii, puteti cauta in toate documentele. Deci nu o sa va clasati doar gasind cel mai bun scor vector, aveti si scorurile dvs. de statice corecte.

Feedback de relevanta

Feedback-ul de relevanta este alocarea mai mult sau mai putina valoare unui termen dintr-o interogare, pe baza relevantei unui document. Folosind feedback-ul de relevanta, un motor de cautare poate schimba interogarea utilizatorului fara a-i spune utilizatorului.

Primul pas aici este sa determinati daca un document este relevant sau nu. Desi exista motoare de cautare in care poti specifica daca un rezultat sau un document este sau nu relevant, Google nu mai are de mult o asemenea functie. Prima lor incercare a fost prin adaugarea vedetei preferate la rezultatele cautarii. Acum o incearca cu butonul Google+. Daca destui oameni incep sa apese butonul la un anumit rezultat, Google va incepe sa ia in considerare documentul relevant pentru acea interogare.

O alta metoda este sa te uiti la paginile curente care se claseaza bine. Acestea vor fi considerate relevante. Pericolul acestei metode este derivarea subiectului. Daca sunteti in cautarea de bitterballen si crochete, iar cele mai bune pagini de clasare sunt toate snack-bar-urile din Amsterdam, pericolul este ca veti atribui valoare Amsterdamului si veti ajunge doar cu snack-baruri in Amsterdam in rezultate.

 Minariea de date

O alta modalitate de utilizare a Google este prin simpla utilizare a minarii de date. Ei se pot uita, de asemenea, la CTR-ul diferitelor pagini. Paginile in care CTR-ul este mai mare si au o rata de respingere mai mica decat media pot fi considerate relevante. Paginile cu o rata de respingere foarte mare vor fi pur si simplu irelevante.

Un exemplu de modul in care putem folosi aceste date pentru ajustarea ponderilor termenilor de interogare este formula de feedback a lui Rochio. Se rezuma la ajustarea valorii fiecarui termen din interogare si, eventual, adaugarea unor termeni suplimentari de interogare. 

Valoarea fiecarui termen este ponderea pe care o primeste in interogarea dvs. Putem folosi acele greutati in calculele noastre vectoriale. Desi termenului Amsterdam a primit un scor de -0,5, ajusteaza valorile negative inapoi la 0. In acest fel, nu excludem termeni din rezultatele cautarii. Si desi cafeneaua nu a aparut in interogarea initiala, a fost adaugata si a primit o pondere in noua interogare.