L'implantation et l'utilisation de SMART
On donne certains détails sur l'implantation de SMART afin de vous donner une idée sur comment un système de RI peut être réalisé. Nous abordons les questions suivantes:
1. Structures de données
Structures de données produites durant l'indexation
Durant l'indexation des documents, SMART produit principalement les ficxhiers suivants:
La structure de données utilisée dans dict est la suivante (http://www.iro.umontreal.ca/~nie/IFT6255/h_smart/dict.h )
typedef struct {
unsigned char *token; /* actual string */
long info; /* Usage dependent field */
long con; /* unique index for this token */
} DICT_ENTRY;
où token est le mot (ou le terme), info caractérise le token (un nom propre, un mot normal, etc.), et con est le numéro assigné à ce token.
Les structures suivantes sont utilisées pour stocker les vecteurs dans doc.nnn et doc.nnn.var (http://www.iro.umontreal.ca/~nie/IFT6255/h_smart/vector.h )
typedef struct {
long con; /* Actual concept number */
float wt; /* and its weight */
} CON_WT;
/* a single vector, sorted on: ctypes,cons */
typedef struct {
long id_num; /* unique number for this vector within */
/* collection */
long num_ctype; /* number of ctypes for this vector */
long num_conwt; /* no. of tuples in the vector */
long *ctype_len; /* length of subvector for each ctype */
CON_WT *con_wtp; /* pointer to concepts, weights for vector*/
} VEC;
Ces structures peuvent être vues comme suit:
Le champ id_num stocke le numéro d'identification du vecteur, num_ctype le nombre de ctypes (ou sous-vecteurs) que le vecteur contient, *ctype_len est un pointeur qui mène à une suite de valeurs correspondant à la longueur de chaque ctype, *con_wtp est un autre pointeur menant à la suite de doublets (con, wt) - numéro de concept et son poids.
La structure du fichier inversé:
typedef struct {
long list;
float wt;
} LISTWT;
/* a single node visible to the user */
typedef struct {
long id_num; /* key to access this inverted list with*/
long num_listwt; /* Number of elements in this list */
LISTWT *listwt; /* Pointer to actual list */
} INV;
où id_num est le numéro de mot (ou de concept), list est le numéro du document contenant le terme, et wt son poids.
Structures de données produites durant la recherche
Durant la recherche, SMART produit un ou deux fichiers suivants: tr et rr. tr stocke les n documents classés en têtes (n étant le nombre demandé par l'usager). rr stocke le rang de tous les documents pertinents de la base. rr peut être obtenu seulement pour des corpus de test. Ces deux fichiers utilisent les structures suivantes:
typedef struct {
long qid; /* query id */
long did; /* document id */
unsigned char rank;/* Rank of this document */
char rel; /* whether doc judged relevant(1) or not(0) */
char action; /* what action a user has taken with doc */
char iter; /* Number of feedback runs for this query */
float sim; /* similarity of did to qid */
} TR;
typedef struct {
long qid; /* query id */
long did; /* document id */
long rank; /* rank of document */
float sim; /* similarity of did to qid */
} RR;
À part ces structures principales, il y en a beaucoup d'autres. Toutes les structures définies sont dans le répertoire h de SMART: http://www.iro.umontreal.ca/~nie/IFT6255/h_smart/
2. Accès aux données
SMART utilise ses propres structures pour stocker les données plutôt que d'utiliser une base de données commerciale. La raison est l'efficacité. Dans un système de base de données commerciale, on essaie d'implanter des opérations de façon générale de sorte qu'elles peuvent être utilisées dans de diverses situations. Notamment, il y a beaucoup de copies de données qui se transfèrent et qui se remodélisent. Ces opérations sont très coûteuses. Dans la RI, on n'a pas besoin de faire des manipulations variées sur les données. Les opérations de base sont fort simples. Ainsi, SMART choisit utiliser une organisation propre à lui pour accélérer les accès aux données.
On remarque, dans les structures de données, que les ensembles de données (e.g. les doublets con-wt) sont stockées dans un même bloc. Ainsi, une fois qu'on identifie le début de ce bloc ainsi que sa longueur, l'opération d'identification est terminée. Au lieu de retourner toutes les données, SMART retourne simplement un pointeur à ce bloc. Ainsi, on économise beaucoup dans le transfert de données.
Les opérations de base sur les fichiers dans SMART sont les suivantes:
Durant l'indexation, une série d'écritures permettent de créer au fur et à mesure les fichiers d'index. Durant la recherche, ce sont plutôt des lectures qu'on effectue.
3. Organisation des traitements
SMART organise les traitements en un arbre. Voici une partie de cet arbre.
Au plus haut niveau, on retrouve les opérations: inter (pour interactive), index (pour indexation), convert (pour convertir des vecteurs en fichier inversé, ou pour convertir le poids en tf*idf), retrieve (pour la recherche), eval (pour l'évaluation de la performance), feedback (pour la rétroaction de pertinence). Les codes sources de SMART est organisés dans des répertoires selon cette même structure. Par exemple, dans Smart/src/libindexing/, on met tous les programmes concernant l'indexation.
Dans chaque opérations, il y a beaucoup d'autres opérations plus petites. Une plus grande opération utilise des petites opérations dans certain ordre. Mais on peut choisir entre différentes possibilités pour ces petites opérations. Ce choix est déterminé par un fichier de spécification (spec) que SMART se réfère pour toute opération.
Au niveau de l'implantation, chaque opération est constituée de trois procédures:
On peut voir un exemple (un des plus simples) pour la lemmatisation qui enlève -s à la fin du mot dans http://www.iro.umontreal.ca/~nie/IFT6255/src_smart/libindexing/remove_s.c
Ce programme contient d'abord un ensemble de constantes. Par exemple:
static SPEC_PARAM spec_args[] = {
TRACE_PARAM ("index.stem.trace")
};
Cela spécifie les paramètres à chercher dans spec.
Ensuite, on a la procédure d'initialisation:
int
init_remove_s (spec, unused)
SPEC *spec;
char *unused;
{
...
}
La lemmatisation:
int
remove_s (word, output_word, inst)
char *word; /* word to be stemmed */
char **output_word; /* the stemmed word (with remove_s, always
the same as word ) */
int inst;
{
...
}
et la fermeture:
int
close_remove_s (inst)
int inst;
{
...
}
Une fois qu'on écrit les programmes pour toutes les opérations, on les met en hiérarchie en utilisant des programmes dans le répertoire libproc. Vous pouvez éventuellement regarder un de ces fichiers pour avoir un aperçu.
4. Utilisation de SMART
On présente l'utilisation de SMART par un exemple.
Indexation d'une collection - CACM
Dans le répertoire ~nie/Smart/colls/cacm/, il y a une collection de test (CACM) qui regroupe un ensemble de titres et de résumés de Communications of the ACM. Ces documents sont stockés dans le fichier cacm.all. Chaque document commence par ".I" qui annonce un nouveau document. Ce marqueur est suivi d'un numéro. On a ensuite les champs suivants:
Il y a aussi un ensemble de requêtes stockées dans query.text. Finalement, les jugements de pertinence sont stockés dans qrels.text. Ces jugements sont ceux qui sont corrects. On compare le résultat du système avec ces jugements pour évaluer la performance du système.
Pour notre exercice, on va d'abord indexer les documents et les requêtes. On convertit ensuite la fréquence en tf*idf. On évalue les requête. Et finalement on évalue la performance du système.
Pour simplifier, on utilise un script déjà créé. Ce script est ~nie/Smart/Sample/make_cacm
set database = $root/indexed_colls/cacm_test
en
set database = ~<votre_login>/cacm_test
C'est-à-dire un répertoire dans votre compte. Le répertoire cacm_test (ou un autre nom que vous donnez) sera créé automatiquement par le script (et le contenu dans ce répertoire sera aussi effacé).
chmod u+x make_cacm
Creating new database at Fri Oct 8 21:20:50 EDT 1999
Indexing docs,queries,qrels at Fri Oct 8 21:20:50 EDT 1999
3.0u 2.0s 0:12 38% 0+0k 0+0io 0pf+0w
All done at Fri Oct 8 21:20:58 EDT 1999
Si à cette étape, vous voyez un message d'erreur (comme "resource temporarily inavailable…"), c'est que l'indexation n'est pas réussi. Il faut relancer.
common_words doc_loc q_textloc.var query.nnn.var textloc.var
dict inv.nnn qrels query_loc
doc.nnn inv.nnn.var qrels.var spec
doc.nnn.var q_textloc query.nnn textloc
doc_loc est le fichier qui indique où se trouve les documents à indexer. query_loc fait la même chose pour les requêtes. doc.nnn et doc.nnn.var stockent les index des documents. query.nnn et query.nnn.var stockent les index pour les requêtes. Textloc et q_textloc stockent respectivement les documents et requêtes originaux (pour permettre de les afficher en mode interactif). dict est le dictionnaire des index. common_words stocke les mots vides. Finalement, spec définit le comportement du système qu'on veut. C'est le fichier le plus important quand on utilise SMART. Tout est défini dans ce fichier.
Le format de définition est "attribut valeur" qui occupe une ligne. Par exemple, les deux premières lignes:
database /u/nie/Smart/indexed_colls/cacm_test
include_file /u/nie/Smart/lib/spec.expcoll
spécifient où le résultat d'indexation est stocké (normalement, vous devez avoir un endroit différent que celui montré) et le fichier de spécification par défaut à inclure.
Dans un spec, on peut définit seulement les choses changées par rapport à la spécification par défaut (voir http://www.iro.umontreal.ca/~nie/IFT6255/src_smart/lib/spec.default ) en incluant cette dernière. Pour mieux comprendre la spécification, aller voir http://www.iro.umontreal.ca/IFT6255/Doc_smart/howto/defaults ).
Pour ceux qui sont à l'aise avec le script, vous pouvez regardez le script make_cacm pour comprendre ce qu'il a fait. En gros, ce script définit où est la collection à indexer, où mettre le résultat, créer un fichier "spec" dans la base de données (le répertoire où on met le résultat), et lancer l'indexation. Vous pouvez remarquer que spec créé définit comment chaque champs du document est reconnu, et comment le traiter.
Vous avez maintenant une collection de test totalement indexée dans cacm_test.
Examen du résultat de l'indexation
Allez dans le répertoire cacm_test. Vous verrez les fichiers suivants:
common_words doc_loc q_textloc.var query.nnn.var textloc.var
dict inv.nnn qrels query_loc
doc.nnn inv.nnn.var qrels.var spec
doc.nnn.var q_textloc query.nnn textloc
Le fichier dict contient tous les mots (ou concepts) rencontrés. À chaque mot, un numéro d'identification a été assigné. Pour pouvez visualiser le contenu par
smprint dict dict | more
L'affichage est comme suit:
0 -1 NOT-a-TOKEN
1 1 written
2 2 derivable
3 3 conveying
4 0 dow, j
5 5 inv
6 6 avint
où chaque ligne contient: numéro de mot, nature du mot, et le mot.
Le fichier common_words est le dictionnaire pour les mots vides. Vous pouvez le visualiser comme dict.
Le fichier doc.nnn (et doc.nnn.var) contient le résultat d'indexation de documents. Vous pouvez le visualiser par
smprint -s spec vec_dict doc.nnn | more
L'affichage est comme suit:
1 0 4691 1.00000 samelson, k
1 0 4975 1.00000 report
1 0 9280 1.00000 algebraic
1 0 10955 1.00000 international
1 0 13644 1.00000 preliminary
1 0 15587 1.00000 language
1 0 15679 1.00000 perlis, a
où chaque ligne contient: numéro de document, ctype, no_mot, fréquence, le mot.
Le fichiers(et inv.nnn.var) est le fichier inversé. La commande suivante permet de le visualiser:
smprint -s spec inv inv.nnn | more
L'affichage est similaire que dans le cas de doc.nnn, mais c'est trié dans l'ordre de no_mot.
Les fichier textloc (et textloc.var) et q_textloc (q_textloc.var) stockent les données qui permettent l'affichage du résultat d'interrogation dans une interface utilisateur (par exemple, le début et la fin de chaque champs dans un document). Pour pouvez les visualiser par:
smprint -s spec textloc textloc | more
smprint -s spec textloc q_textloc | more
Les fichiers doc_loc et query_loc stockent les adresses des documents et des requêtes à indexer.
Le fichier qrels (qrels.var) stockent les jugements de pertinence standard. Ces jugements ont été indexés par SMART pour les transformer en format interne. Vous pouvez le visualiser comme suit:
smprint -s spec rr_vec qrels | more
L'affichage est comme suit:
1 1410 0 0.0000
1 1572 0 0.0000
1 1605 0 0.0000
1 2020 0 0.0000
1 2358 0 0.0000
ce qui donne tous les documents pertinents (2ième colonne) pour chaque requête (1ère colonne). Les deux autres colonnes ne sont pas utilisées.
Le comportement de SMART est définie par le fichier de spécification spec. Vous pouvez voir dans spec que chaque ligne contient un attribut et une valeur. Par exemple:
database /u/nie/Smart/indexed_colls/cacm_test
...
stemmer index.stem.remove_s
...
La ligne de stemmer définit la procédure de lemmatisation à utiliser pendant l'indexation.
Le fichier spec dans cacm_test contient les informations suivantes:
Conversion des poids
Lancer les commandes suivantes pour convertir le poids de terme (fréquence d'occurrence) en un poids tf*idf (spécifié par ltc):
smart convert spec proc convert.obj.weight_query in query.nnn out query.ltc query_weight ltc
smart convert spec proc convert.obj.weight_doc in doc.nnn out doc.ltc doc_weight ltc
smart convert spec proc convert.obj.vec_aux in doc.ltc out inv.ltc
Ces commandes convertissent respectivement les requêtes, le résultat d'indexation et le fichier inversé en poids tf*idf.
Vous pouvez visualiser les résultats de conversion (dans les fichiers query.ltc, doc.ltc et inv.ltc) comme avant. Vous verrez que les poids ont changés.
Recherche (ou évaluation de requêtes)
Lancer la commande de recherche:
smart retrieve spec
Cela produit deux résultats: tr (top-ranked documents) et rr (rank of relevant documents). Visualisez par les commandes suivantes:
smprint -s spec tr_vec tr | more
smprint -s spec rr_vec rr | more
Dans tr, vous verrez:
1 1591 4 0 0 0 32.0000
1 1680 2 0 0 0 34.0000
qui donne pour chaque requête (1ère colonne), les n (n étant spécifié dans spec par num_wanted) documents retrouvés en tête (2ième colonne), son rang (3ième colonne), et sa similarité (dernière colonne). Les autres colonnes sont utilisées pour des fonctions internes.
Dans rr, vous aurez:
1 1410 83 15.0000
1 1572 19 23.0000
qui donne pour chaque requête (1ère colonne), tous les documents pertinents (2ième colonne), son rang (3ième colonne), et sa similarité (4ième colonne).
Dans cette recherche, on utilise les résultat d'indexation par défaut, soit doc.nnn et query.nnn (ou autrement dit, utiliser la fréquence d'occurrence). On peut changer les fichiers utilisés aux *.ltc. Pour cela, créez un autre fichier de spécification spec.ltc contenant les lignes suivantes:
include_file ./spec
doc_file ./doc.ltc
query_file ./query.ltc
tr_file ./tr.ltc
rr_file ./rr.ltc
Relancez la recherche: smart retrieve spec.ltc
Vous aurez d'autres résultats utilisant le poids tf*idf stockés dans tr.ltc et rr.ltc.
Évaluation du système
SMART contient des outils pour évaluer la performance d'un système en comparant les résultats de recherche avec les réponses standard stockées dans qrels. Les deux commandes suivantes:
smprint tr_eval spec
smprint tr_eval spec.ltc
donnent une évaluation des résultats qui utilisent la fréquence d'occurrence et le poids tf*idf.
Vous pouvez les comparer en mettant les fichiers spec ensemble:
smprint tr_eval "spec spec.ltc"
L'option tr_eval peut être changée en rr_eval. Dans ce cas, on enlève la limite sur la taille de réponses. Toutes les réponses sont considérées. Cependant, les documents qui apparaissent après la taille limite seront ordonnés seulement dans l'ordre décroissant de leur numéro d'identification.
En mode interactive
Vous pouvez interagir avec SMART en faisant:
smart inter spec
ou
smart inter spec.ltc
Vous aurez un menu que vous pouvez choisir. Jouez avec ce mode pour voir la fonction feedback en choisissant un document comme pertinent, et réévalue la nouvelle requête. La nouvelle requête est créée en utilisant les paramètres alpha, beta et gamma spécifiés dans spec. Changez ces paramètres à des valeurs raisonnables. Les valeurs dans spec ne sont pas bons. Vous pouvez par exemple définir alpha=1, beta=0.5 et gamma=0.