Motorul din spate: Structura Trie

Solutia se numeste Trie (sau arbore de prefixe). Imagineaza-ti un copac intors. Radacina este goala. Din ea pleaca ramuri pentru fiecare litera a alfabetului.

Cand tastezi litera “C”, algoritmul coboara pe ramura respectiva. Din nodul “C” pleaca alte ramuri, dar in secunda in care apesi “U”, sistemul taie instant tot ce nu incepe cu “CU”. Frumusetea acestei structuri este ca timpul de cautare nu depinde de dimensiunea bazei de date. Depinde strict de lungimea cuvantului tau. Matematic, vorbim de o complexitate $O(L)$, unde $L$ este numarul de litere tastate. Ai scris 3 litere? Algoritmul face fix 3 pasi ca sa gaseasca nodul, indiferent ca in baza de date ai 100 de cuvinte sau 10 miliarde.

Cum alege ce sa afiseze primul?

Arborele asta nu tine doar litere. Fiecare nod final stocheaza si o “greutate” (un scor de frecventa). Cand ai ajuns la nodul “M” din “CUM”, algoritmul se uita in jos pe ramuri si iti trage instant sufixele cu cel mai mare scor.

Aici intervine Machine Learning-ul si strica matematica pura. Scorurile alea nu sunt deloc statice. Ele se reevalueaza dinamic pe baza contextului tau. Sistemul nu iti da pur si simplu cele mai cautate cuvinte din lume. Se uita la locatia ta, ora din zi si istoricul tau personal.

Daca stai pe un IP de Politehnica, esti student la Automatica si scrii “cum se face un”, algoritmul creste artificial greutatea ramurilor care duc spre “compilator in C” sau “makefile”. Daca tastezi exact aceeasi secventa dintr-o bucatarie de restaurant, ramurile care duc spre “aluat de pizza” primesc un boost de scor.

Algoritmul reajusteaza in milisecunde graful de probabilitati, bazandu-se pe ce au cautat alte milioane de oameni din zona ta, cu un istoric web similar cu al tau, fix dupa ce au apasat aceleasi trei taste.