Al giorno d'oggi, Microsoft e Google indicizzeranno i file sul disco rigido in modo da poter cercare rapidamente i loro contenuti.Come si indicizzano i file per le ricerche veloci?
Quello che voglio sapere è come lo fanno? Puoi descrivere l'algoritmo?
Il caso semplice è un indice invertito.
L'algoritmo di base è semplice:
I dettagli sono dove le cose si complicano, ma i fondamentali sono gli stessi.
Per "normalizzare e filtrare" le parole, voglio dire cose come convertire tutto in minuscolo, rimuovere le "parole di arresto" comuni (il, if, in, un ecc.), Possibilmente "arginare" (rimuovere i suffissi comuni per i verbi e plurali e simili).
Dopodiché, hai un elenco univoco di parole per il file e puoi creare il tuo indice da questo.
Esistono ottimizzazioni per ridurre lo spazio di archiviazione, tecniche per il controllo della localizzazione delle parole (è "questo" vicino a "quello" nel documento, ad esempio).
Ma, questo è il modo fondamentale in cui è fatto.
Si potrebbe sempre guardare in qualcosa come Apache Lucene.
Apache Lucene è una libreria di ricerca testuale completa e ad alte prestazioni, interamente scritta in Java. È una tecnologia adatta a quasi tutte le applicazioni che richiedono la ricerca full-text, in particolare cross-platform.
Ecco una descrizione molto semplice; per maggiori dettagli, puoi leggere questo libro di testo (gratuito online): http://informationretrieval.org/ ¹
1). Per tutti i file, crea un indice. L'indice è costituito da tutte le parole univoche che si verificano nel set di dati (chiamato "corpus"). Ad ogni parola è associata una lista di ID documento; ogni documento ID si riferisce a un documento che contiene la parola.
Variazioni: a volte quando si genera l'indice si desidera ignorare le parole di arresto ("a", "il", ecc.). Devi stare attento, però ("essere o non essere" è una vera query composta da stopword).
A volte si arginano anche le parole. Ciò ha un impatto maggiore sulla qualità della ricerca in lingue diverse dall'inglese che utilizzano suffissi e prefissi in misura maggiore.
2) Quando un utente inserisce una query, cerca gli elenchi corrispondenti e uniscili. Se si tratta di una query booleana stretta, il processo è piuttosto semplice - per AND, un docid deve comparire in tutte le liste di parole, per OR, in almeno un elenco di parole, ecc.
3) Se si desidera classificare i risultati, ci sono diversi modi per farlo, ma l'idea di base è quella di utilizzare la frequenza con cui si verifica una parola in un documento, rispetto alla frequenza che ci si aspetta verificarsi in qualsiasi documento nel corpus, come segnale che il documento è più o meno rilevante. Vedi il libro di testo.
4) È possibile anche posizioni negozio di parole per inferire frasi, ecc
La maggior parte di ciò è irrilevante per la ricerca desktop, come siete più interessati a richiamo (tutti i documenti che includono il termine) che la classifica.
¹ precedenza su http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html, raggiungibile attraverso una macchina Wayback
Il link che hai fornito è rotto. – kta