usor off topic, despre indexare

Unul din obiectivele avute in vedere in realizarea unei interfete este crearea unui timp de raspuns cat mai bun. Usor off topic pentru ca nu e "ce se vede", indirect relevant insa.

Indexarea e modalitatea de a stoca informatie intr-un mod organizat, principalul obiectiv fiind extragerea informatiilor din index intr-un timp optimal. Unde se foloseste ? Peste tot ! Google news de ex. De bun simt e ca daca ai multe cautari de stiri, nu stai sa crawlezi tot netul pentru fiecare cautare, e mai "cinstit" sa faci asta o singura data, informatiile sa le pastrezi cumva structurat, diminuand extrem de mult timpul de cautare.

Cum ar trebui sa arate un index ? Depinde extrem de mult de modalitatea de cautare a informatiei. Exista mai multe tipuri de cautare (de ex keywords, fraza, cautare booleana, cautare cu expresii regulate, etc), stabilirea modului de cautare influentand structura indexului. In general indexul ca structura de date e un Hashtable, key fiind cuvantul, value fiind un obiect ce ar trebui sa descrie dependintele intre acel cuvant si toate documentele in care apare, pozitiile in care apare in fiecare doc, etc. Acest value e influentat de modalitatea de cautare.

In general intr-un index nu sunt tinute valori de tip text. Pentru optimizare la comparare, se folosesc hashcode-uri, cautarea pe int-uri fiind mult mai eficienta. Cuvintele care sunt indexate sufera o serie de prelucrari. Se aplica algoritmi de eliminare caractere nerelevante(".", ",", ";", etc.), eliminare de stop words, stemming, lemmatisation, etc. Stringul rezultat va fi codificat la int si retinut in index. Algoritmii prezentati reduc dimensiunea textului ce trebuie indexat la ceva considerat "relevant". De exemplu, regula celor 30 spune ca din 30% din cuvintele cu cele mai multe aparitii dintr-un document, 30% sunt cuvinte cheie (stop words), cuvinte cu relevanta mica la cautare.

De asemeni, pe partea de value in hashtable pot fi mai multe abordari. Documente sunt tinute fie sub forma de liste, obligatoriu sortate, pentru ca la cautarea a 2 cuvinte de ex, rezultatul ar trebui sa fie intersectia listelor de documente in care apare fiecare cuvant, intersectia pe 2 liste sortate facandu-se in O(m+n) fata de O(m*n) pentru liste nesortate. Tradeoff pentru listele sortate e dificultatea la adaugare si stergere, listele trebuie resortate dupa fiecare operatie de acest fel. O alta varianta ar fi folosirea unor arbori (binari de cautare, rosu-negru, etc.), adaugarea si eliminarea unei intrari rebalansand arborele, iar cautarea facandu-se rapid. Mai greu de implementat si cu mai multe resurse in memorie.

usor off topic, dar sper interesant :)