💾 Archived View for it.omarpolo.com › articoli › esperimenti-con-fts.gmi captured on 2022-04-29 at 12:18:54. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2022-04-28)
-=-=-=-=-=-=-
Di recente ho voluto approfondire come gli engine di "full text search" funzionassero. "Full text search" significa all'incirca cercare del testo arbitrario in una collezione di documenti possibilmente molto, molto vasta.
Ho usato e sto usando tutt'ora elasticsearch per alcune cose, e giochicchiato con solr, ma nulla batte lo scrivere le cose a mano da zero per capire come funzionino.
Per tenere il progetto semplice ho deciso di indicizzare solo un piccolo insieme di documenti -- i pacchetti di OpenBSD e l'abstract delle pagine di Wikipedia in inglese -- in un database personalizzato. Questo database verrà poi usato da un'altra utility per fare le query. A sottolineare la semplicità del progetto, il database è read-only e va ricostruito se i documenti cambiano.
Il codice è disponibile su codeberg o sul mirror github
https://codeberg.org/op/ftsearch
https://github.com/omar-polo/ftsearch
ed è stato ispirato da un post che ho letto qualche tempo fa:
Let's build a Full-Text Search engine
La cosa principale che ho imparato è che non c'è alcuna magia nella FTS, ovviamente, ma ci sono talmente tante cose che si possono personalizzare quando si costruisce un sistema che rischia di essere XYZ.
L'idea generale un indice del testo in qualche modo e poi usarlo (o usarli) per trovare il testo cercato.
Quello che la maggior parte degli engine fanno -- o che credo facciano -- è innanzitutto separare il testo in token (parole), poi farci delle trasformazioni e infine salvarli in un indice dove mappano ogni parola in quale documento compare. Più tardi, molte di queste trasformazioni verranno fatte anche sulla query dell'utente e l'indice consultato per trovare i documenti. QUesta almeno è l'idea generale; nella pratica engine seri usano più di un solo indice.
Alcune delle trasformazioni più comuni fatte dopo la tokenizzazione sono:
Non tutti questi step sono obbligatori e altri probabilmente possono essere aggiunti. Ad esempio, io mi limiterò alla "minuscolazione".
La rimozione delle stop word è solo un workaround per evitare indici enormi ma limita il tipo di query che un utente può fare (si pensi a query come "to be or not to be" o "The Who".)
Lo stemming è un'idea interessante però. Viene usato per mappare le variazioni della stessa parola ad una comune sequenza di caratteri, non necessariamente una parola valida. Ad esempio, l'algoritmo di Porter mappa "argue", "argued", "argues" e "arguing" ad "argu". In questo modo documenti che contengono solo "argued" verranno selezionati anche per una query contenenent "arguing".
Engine decenti hanno anche delle funzioni di ranking dei documenti. Il ranking significa cercare di indovinare quanto un documento sia rilevante rispetto alla query dell'utente e ordinare i risultati in accordo con questo valore. Spoiler: il mio non è un engine decente quindi il ranking non è trattato, ma spero comunque di riuscire a parlarne in un post futuro.
#define WDELIMS "..." /* everything but a-zA-Z */
char **
tokenize(const char *s)
{
char *d, *dup, *t, **tok = NULL;
void *newtok;
size_t cap = 0, len = 0, newcap;
if ((dup = strdup(s)) == NULL)
return NULL;
d = dup;
for (t = d; *t; ++t)
*t = tolower(*t);
while ((t = strsep(&d, WDELIMS)) != NULL) {
if (*t == '\0')
continue;
/* keep the space for a NULL terminator */
if (len+1 >= cap) {
newcap = cap * 1.5;
if (newcap == 0)
newcap = 8;
newtok = recallocarray(tok, cap, newcap,
sizeof(char *));
if (newtok == NULL)
goto err;
tok = newtok;
cap = newcap;
}
if ((tok[len++] = strdup(t)) == NULL)
goto err;
}
free(dup);
if (tok == NULL)
return calloc(1, sizeof(char *));
return tok;
err:
freetoks(tok);
free(dup);
return NULL;
}
Il tokenizer è davvero semplice: trasforma il testo in minuscolo e spezza le parole. La frase "X11 Window Manager" diventa quindi "x", "window", "manager". Come bonus, assumendo che il testo sia UTF-8, le altre lingue Europee dovrebbe funzionare senza alcuna modifica. (tranne che per il lowercase.)
Nonostante questo tokenizer sembri semplice, non è il caso generalmente parlando. Separare programmaticamente le parole in lingue come il cinese o il giapponese è una mezza sfida!
L'indexer usa un dizionario in memoria di parole e documenti dove compaiono, che poi viene usato per generare il database.
Il design è, di nuovo, piuttosto semplice:
struct dict_entry {
char *word;
int *ids;
size_t len;
size_t cap;
};
struct dictionary {
size_t len;
size_t cap;
struct dict_entry *entries;
};
Un dizionario è semplicemente un arry ordinato di struct dict_entry: una parola e la rispettiva lista di id dei documenti dove compare.
Inserire una parola nel dizionario è piuttosto semplice: uso una ricerca binaria per trovare la parola nel dizionario oppure il posto dove inserirla se non è già presente.
Quando ogni documento è stato processato e le sue parole aggiunte al dizionario, è il turno di generare il database: in questo modo non c'è bisogno di re-indicizzare tutti i documenti prima di ogni ricerca.
Non sono sicuro di come engine FTS del calibro di Lucene gestiscano l'archiviazione su disco, ma ho scelto di provare con qualcosa di molto semplice: un singolo file binario. All'inizio c'è un indice con 32 byte per ogni parola e l'offset del file nel quale si trova la lista di documenti: in questo modo è possibile mappare in memoria il file e fare una ricerca binaria per trovare la lista di id dei documenti associati a quella parola.
Poi segue la lista degli id dei documenti, uno per ogni parola. Queste liste sono a dimensione variabile, per questo non li sto tenendo nell'indice centrale.
Alla fine del file c'è un'altra lista con i nomi dei documenti e una descrizione. È inclusa in modo che il programma che effettua le query possa guardare lì per generare risultati più interessanti di una lista di numeri.
,______.________. | word | offset | | word | offset | | ... | ... | `------'--------' [ids for document #1] [ids for document #2] [ids for document #3] [ids for document #4] ... [document #1 name and description] [document #2 name and description] ...
Rispondere alla query "file manager" significa andare nell'indice e cercare la lista di documenti nel quale compare "file" e fare l'intersezione con quella di "manager".
Non è l'unico tipo di query possibili, "phrase query" e query booleane sono anche molto interessanti, ma per il momento mi sto limitando a queste semplici query AND.
Ecco l'intera routine `fts':
struct doclist {
uint32_t *ids;
size_t len;
};
int
fts(struct db *db, const char *query, db_hit_cb cb, void *data)
{
struct doclist *xs = NULL;
size_t i, len;
char **toks, **t;
int ret = 0;
if ((toks = tokenize(query)) == NULL)
return -1;
len = 0;
for (t = toks; *t != NULL; ++t)
len++;
if (len == 0)
goto done;
if ((xs = calloc(len, sizeof(*xs))) == NULL) {
freetoks(toks);
return -1;
}
for (i = 0; i < len; ++i) {
xs[i].ids = db_word_docs(db, toks[i], &xs[i].len);
if (xs[i].ids == NULL || xs[i].len == 0)
goto done;
}
for (;;) {
struct db_entry e;
uint32_t mdoc;
mdoc = xs[0].ids[0];
for (i = 1; i < len; ++i) {
if (xs[i].ids[0] > mdoc)
goto next;
while (xs[i].ids[0] < mdoc) {
if (--xs[i].len == 0)
goto done;
xs[i].ids++;
}
if (xs[i].ids[0] != mdoc)
goto next;
}
if (db_doc_by_id(db, mdoc, &e) == -1) {
ret = -1;
goto done;
}
if (cb(db, &e, data) == -1) {
ret = -1;
goto done;
}
next:
if (--xs[0].len == 0)
goto done;
xs[0].ids++;
}
done:
free(xs);
freetoks(toks);
return ret;
}
L'unica (?) parte interessante potrebbe essere il loop centrale. Può puzzare come magia nera, ma credo sia una soluzione carina per calcolare l'intersezione di un numero variabile di array numerici senza usare memoria addizionale.
L'idea è di prendere il primo elemento del primo array e di attraversare la lista di array seguenti:
Il tutto funziona perchè la lista di id è garantita essere già ordinata.
Una possibile ottimizzazione potrebbe essere quella di ordinare le parole per frequenza in modo che la meno comune sia per prima: dovrebbe ridurre il numero di iterazioni per computare l'intersezione in alcuni casi.
Il repository contiene due utility da linea di comando:
Anche se l'implementazione è incredibilmente naïve i risultati non sono così male:
% ls -lah db.wiki
-rw-r--r-- 1 op op 92.9M Apr 14 11:19 db.wiki
% time ./obj/ftsearch -d db.wiki 'small wild cat'
https://en.wikipedia.org/wiki/Wildcat Wildcat
https://en.wikipedia.org/wiki/Catopuma Catopuma
0m00.02s real 0m00.00s user 0m00.06s system
Ci sono voluti 0.02 secondi per consultare il database da 90M; per confronto grep ci sta 0.21, dieci volte tanto.
% time grep cat db.wiki > /dev/null
0m00.21s real 0m00.21s user 0m00.15s system
I documenti che seleziona sono anche pertinenti, ad esempio ecco la lista di giochi strategici a turni presenti nel port tree:
% time ./obj/ftsearch 'turn-based strategy game'
1oom game engine recreation of Master of Orion 1
freeciv-server Civilization clone for X11; multiplayer; game server
freecol free Colonization clone
lgeneral turn-based strategy engine
ufoai squad-based tactical strategy game
wesnoth fantasy turn-based strategy game
0m00.00s real 0m00.00s user 0m00.01s system
OK, probabilmente non sono gli unici, ma senza cose elaborate come lo stemming non si riesce fare molto e può cercare solo parole esatte tra nei commenti e descrizione di ogni pacchetto.
Purtroppo il database non è particolarmente veloce da generare: mkftsidx impiega piu di tre minuti per indicizzare i 947M di enwiki-latest-abstract1.xml.
La profilazione mostra che il 67% del tempo viene sprecato in memmove(3): mantenere un dizionario come array ordinato forse non è stata una buona idea dopo tutto. Qualche altra struttura dati, magari un'hash table o un qualche tipo di albero potrebbero avere performance migliori. Inoltre, con grandi collezioni da data potrebbe non essere possibile mappare l'indice in memoria.
Altri possibili miglioramenti includono:
In un psot futuro vorei estendere questo piccolo framework per includere anche qualche semplice meccanismo di ranking, e magari anche qualche tipologia di stemming.
$BlogIt: esperimenti-con-fts.gmi,v 1.2 2022/04/15 19:50:26 op Exp $