Recherches textuelles dans des bases documentaires (Première partie)

Gazette Linux n°149 — Avril 2008

René PFEIFFER

Adaptation française : Gérard Baylard

Relecture de la version française : Deny

Article paru dans le n°149 de la Gazette Linux d'Avril 2008.

Article publié sous Open Publication License. La Linux Gazette n'est ni produite, ni sponsorisée, ni avalisée par notre hébergeur principal, SSC, Inc.


Table des matières

Documents et transactions avec du texte
Recherche en texte intégral et en langage naturel avec MySQL
Recherche en texte intégral avec PostgreSQL
Conclusion
Références utiles
L'auteur

Lecture et écriture de données sous forme de texte sont-elles votre lot quotidien ? Utilisez‐vous fréquemment des outils de recherche ? Possédez‐vous des paquets de données empilées dans des serveurs de fichiers ou web ? Bon nombre d'entre nous sommes dans ce cas. Comment organisez‐vous votre collection de textes ? Utilisez‐vous un classement par répertoires, par indexation ou dans une base de données ? Si vous n'êtes pas encore décidé, laissez-moi vous suggérer quelques pistes.

Documents et transactions avec du texte

Je me limiterai à l'organisation, l'indexation et la recherche de données textuelles. C'est raisonnable, car la plupart des recherches peuvent être ramenées à des recherches textuelles. J'ajouterai que manipuler du texte n'est pas aussi facile qu'il paraît ; une mise au point n'est donc pas inutile. Peut‐être avez‐vous noté que je différencie documents et données sous forme de texte ; la diversité vertigineuse des formats de documents justifie cette distinction. Certains formats sont bien définis, d'autres pas : une spécification ouverte est immédiatement accessible aux développeurs, un format propriétaire fait toujours obstacle au traitement des données. Malheureusement on ne peut pas éviter ces derniers.

La première chose à faire est d'organiser les données d'une certaine façon. Peu importe que ce soit en créant dans le serveur de fichiers une arborescence structurée de répertoires dans lesquels vous incorporerez les données, ou bien que ce soit en tenant à jour une liste de marque-pages dans le navigateur. L'essentiel est que chaque document ait un identifiant ou une référence unique. Les URL (Uniform Resource Locator : adresse universelle ou adresse réticulaire) fonctionnent bien ; un chemin complété par le nom du fichier est également parfait. Si vous regroupez vos documents par catégories, cela sera encore mieux. Il faut aussi prendre en considération le format du document. La plupart des outils d'indexation ou de recherche ne sait manipuler que le texte, donc si le format de votre document autorise une conversion, un tel traitement sera utile. Voici quelques exemples de scripts de conversion pour programmation shell :

  1. PDF : pdftotext -q -eol unix -enc UTF-8 $IN - > $OUT
  2. Postscript : pstotext $IN | iconv -f ISO-8859-1 -t UTF-8 -o $OUT -
  3. MS Word : antiword $IN > $OUT
  4. HTML : html2text -nobs -o $OUT $IN
  5. RTF : unrtf --nopict --text $IN > $OUT
  6. MS Excel : py_xls2txt $IN > $OUT
  7. tout document OpenOffice : ooo_as_text $IN > $OUT

La variable $IN désigne le document source ; $OUT représente le nom et la localisation du contenu converti en texte brut. Dans l'optique de couvrir l'ensemble des codages possibles de caractères, il est toujours utile d'opérer une conversion dans le codage Unicode approprié. J'utilise généralement le codage UTF-8. Une conversion de tout autre codage vers l'UTF-8 fonctionne bien ; une conversion d'UTF-8 vers un codage ayant une définition de caractères plus pauvre est sujette à des « pertes » et, habituellement, n'est pas assez précise pour être utile.

N'oublions pas que les formats de documents MS Office™ ne sont pas les meilleurs pour emmagasiner l'information, même si quelques convertisseurs savent les traiter. Ils sont encore « propriétaires » : vous n'êtes pas autorisé à utiliser une spécification dite « libre » de Microsoft© en toutes circonstances, puisque l'usage à des fins commerciales est explicitement interdit. Stocker l'information dans ces formats peut être source de nombreux ennuis —en particulier si le promoteur de ces formats abandonne des anciennes versions à l'occasion d'une mise à jour logicielle (c'est déjà arrivé). Vous voilà prévenus de façon claire et nette : vous pouvez éviter de multiples déconvenues dès le départ, si vous avez quelques lumières sur la façon d'organiser vos collections de documents.

Après avoir réfléchi à l'organisation des données, examinons maintenant comment les indexer au mieux. Ce n'est pas que vous en ayez fini de refléchir à l'organisation —mais l'indexation est vraiment l'étape essentielle.

Recherche en texte intégral et en langage naturel avec MySQL

MySQL offre la possibilité de créer des index sur du texte intégral ; la section « Natural Language Full-Text Searches » (Recherche en texte intégral et en langage naturel) du manuel décrit cette action. C'est un moyen facile pour indexer des données sous forme de texte. Soit la table suivante :


CREATE DATABASE textsearch;
USE textsearch;
CREATE TABLE documents (
   	id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
   	filename VARCHAR(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
   	path VARCHAR(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
   	type VARCHAR(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
   	mtime TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
   	content TEXT CHARACTER SET utf8 COLLATE utf8_unicode_ci NOT NULL,
   	FULLTEXT (filename),
   	FULLTEXT (content)
);

On incorpore dans la table le nom du fichier, le chemin pour y accéder, le type de fichier ainsi que son contenu converti. La taille des données du type VARCHAR peut se révéler trop petite si vous avez une arborescence de répertoires importante, mais elle suffit pour ce simple exemple. Chaque document possède un numéro d'identification unique avec le champ id. L'option FULLTEXT() demande à MySQL de créer une indexation pour des recherches en texte intégral dans les colonnes filename et content. Vous pouvez demander l'indexation d'autres champs si vous le souhaitez, mais il faut être attentif à ne pas indexer n'importe quoi. Ajouter le champ type à la liste des champs à indexer peut se révéler judicieux aussi.

Maintenant nous avons besoin d'un peu de contenu dans la base —ajoutons quelques enregistrements pour un test.


INSERT INTO documents ( filename, path, type, content )
   VALUES ( 'gpl.txt', '/home/pfeiffer', 'Text', 'This program is free software; 
   you can redistribute it and/or modify it under the terms of the GNU General 
   Public License as published by the Free Software Foundation;' );
INSERT INTO documents ( filename, path, type, content )
   VALUES ( 'fortune.txt', '/home/pfeiffer', 'Text', 'It was all so different 
   before everything changed.' );
INSERT INTO documents ( filename, path, type, content )
   VALUES ( 'lorem.txt', '/home/pfeiffer', 'Text', 'Lorem ipsum dolor sit amet,
   consectetuer adipiscin...' );

Maintenant on peut faire une recherche texte intégral.

mysql> SELECT id,filename FROM documents WHERE MATCH(content) AGAINST('lorem');

+----+----------+
| id | filename |
+----+----------+
|  6 | test.txt |
+----+----------+
1 row in set (0.01 sec)

mysql>

La construction MATCH() AGAINST() effectue la recherche en texte intégral pour vous. MySQL se sert d'un nombre pour indiquer la pertinence de l'enregistrement dans la table. Vous pouvez voir tous les classements en faisant une requête sur MATCH() AGAINST().

mysql>
 SELECT id, filename, MATCH(content) AGAINST('lorem') FROM documents;

+----+-------------+---------------------------------+
| id | filename    | MATCH(content) AGAINST('lorem') |
+----+-------------+---------------------------------+
|  1 | gpl.txt     |                               0 |
|  2 | fortune.txt |                               0 |
|  3 | s3.txt      |                               0 |
|  4 | s4.txt      |                               0 |
|  5 | miranda.txt |                               0 |
|  6 | test.txt    |                0.75862580537796 |
+----+-------------+---------------------------------+
6 rows in set (0.00 sec)

mysql>

Manifestement j'avais placé quelques enregistrements supplémentaires dans la description initiale de la table. La colonne de droite indique le classement. Seul l'enregistrement 6 affiche un nombre supérieur à zéro parce qu'aucun autre contenu ne comporte le mot lorem. Vous pouvez maintenant ajouter d'autres lignes dans la table et voir ce à quoi leur classement correspond. Il faut noter que MySQL utilise une stratégie spécifique lors de l'indexation d'un texte intégral :

  • les mots de moins de quatre caractères ne sont pas indexés.
  • tout mot apparaissant dans plus de la moitié des lignes de texte est ignoré.
  • les mots avec un trait d'union sont considérés comme deux mots distincts.
  • les parties de mot sont ignorées.
  • le moteur de la base de données tient une liste de mots courants en anglais (stop words : mots non significatifs)  ils sont également ignorés.

Faites attention : si votre recherche ne porte uniquement que sur des mots non significatifs, vous n'obtiendrez aucun résultat. Si vous avez besoin de faire une recherche texte intégral dans des langues autres que l'anglais vous pouvez fournir votre propre liste de mots non significatifs. La documentation vous expliquera comment faire.

Il est également possible de faire des recherches portant sur plusieurs mots, en plaçant une virgule entre les mots de la liste de recherche.

SELECT id, filename, MATCH(content) AGAINST('lorem,ipsum') FROM documents;

Recherche en texte intégral avec PostgreSQL

Bien entendu PostgreSQL prend également en charge la recherche en texte intégral ‐ si votre numéro de version est inférieur à 8.3.0, vous devrez installer un greffon appelé Tsearch2 (ce moteur est intégré dans la version 8.3.0). Tout comme pour MySQL, vous pourrez accorder finement les fonctions selon le vernaculaire de vos textes. Leur contenu doit être soumis à analyse lexicale, et PostgresSQL possède toutes les nouvelles classes d'objets pour ces opérations. Le moteur Tsearch2 dispose d'analyseurs pour le découpage, de dictionnaires pour la normalisation des termes (et de listes de mots non significatifs), de modèles pour basculer entre divers analyseurs ou dictionnaires, et de configurations à utiliser selon les besoins du langage (NdT : de programmation). La création de nouveaux objets pour bases de données requiert la connaissance de la programmation en C.

Recréons une table identique à celle de l'exemple précédent avec PostgreSQL (j'utilise la version 8.3.0 ; si vous avez une version plus ancienne, vous devez installer Tsearch2).


CREATE TABLE documents (
	id_documents serial,
	filename character varying(254),
	path character varying(254),
	type character varying(254),
	mtime timestamp with time zone,
	content text );
CREATE INDEX documents_idx ON documents USING gin(to_tsvector('english',content));

Une fois la table créée, nous allons générer les index GIN (Generalized Inverted Index : index génériques inverses) sur les textes ; ce type d'index se bâtit avec les divers lexèmes. La fonction to_tsvector() opére la conversion dans ces termes normalisés du texte contenu dans la colonne content. Pour ce faire, elle utilisera l'analyseur et le dictionnaire anglais. Une requête en recherche ressemble à quelque chose comme cela :

lynx=>
 SELECT filename,mtime FROM documents WHERE to_tsvector(content) @@ to_tsquery('lorem');

 filename  |            mtime             
-----------+------------------------------
 lorem.txt | 2008-02-26 12:15:16.34584+01
(1 row)

lynx=>

NdT: Lorsque vous nourrirez la table de ses enregistrements, n'oubliez pas de fixer les valeurs de la colonne mtime avec la fonction now().

On utilise une commande SELECT classique avec l'opérateur @@ de recherche d'équivalence textuelle. Cet opérateur compare l'argument et la chaîne recherchée convertis en lexèmes en utilisant les fonctions to_tsvector() et to_tsquery(). Le résultat est renvoyé par l'assertion SELECT. Vous pouvez aussi demander le classement pour trier les résultats.

lynx=>
 SELECT filename,mtime,ts_rank(to_tsvector(content),to_tsquery('lorem'))
          FROM documents WHERE to_tsvector(content) @@ to_tsquery('lorem');

 filename  |            mtime             |  ts_rank  
-----------+------------------------------+-----------
 lorem.txt | 2008-02-26 12:15:16.34584+01 | 0.0607927
(1 row)

lynx=>

L'analyse lexicale est l'une des étapes cruciales dans la recherche d'un texte ; il faut comprendre l'algorithme que Postgres utilise pour décomposer une chaîne. Voyez l'exemple ci-après :

lynx=>
 SELECT alias, description, token FROM ts_debug('copy a complete database');

   alias   |   description   |  token   
-----------+-----------------+----------
 asciiword | Word, all ASCII | copy
 blank     | Space symbols   |  
 asciiword | Word, all ASCII | a
 blank     | Space symbols   |  
 asciiword | Word, all ASCII | complete
 blank     | Space symbols   |  
 asciiword | Word, all ASCII | database
(7 rows)

lynx=>

Cet exemple utilise la fonction ts_debug() et affiche chaque terme avec sa classification. Le module de recherche du texte maîtrise la compréhension de la plupart des constructions textuelles courantes ; il sait également décoder les URL.

lynx=>
 SELECT alias, description, token FROM ts_debug('http://linuxgazette.net/145/lg_tips.html');

  alias   |  description  |               token               
----------+---------------+-----------------------------------
 protocol | Protocol head | http://
 url      | URL           | linuxgazette.net/145/lg_tips.html
 host     | Host          | linuxgazette.net
 url_path | URL path      | /145/lg_tips.html
(4 rows)

lynx=>

L'analyseur lexical affiche les termes constitutifs de l'URL et les identifie. Ce découpage permet un meilleur traitement de la requête, et c'est pourquoi vous devez filtrer la chaîne recherchée. Une recherche se fait en comparant les lexèmes et non les chaînes elles-mêmes.

Conclusion

Je n'ai présenté que deux méthodes d'indexation de données textuelles. À dire vrai, ce n'est que la partie émergée de l'iceberg— il y a encore beaucoup à dire sur les recherches en texte intégral. MySQL et PostgreSQL possèdent tous deux des algorithmes prêts à l'emploi pour faciliter la recherche de documents. Vous pouvez utiliser un simple script Perl avec l'un de ces deux moteurs, le nourrir avec vos marque-pages et construire un tableau d'index des pages web correspondantes prêt pour des recherches. Il y a beaucoup d'autres outils disponibles, et je vous présenterai un autre moyen d'indexer dans la deuxième partie de cette série. Si vous faites quelque chose de différent ou d'intéressant pour effectuer ces mêmes opérations, écrivez et faites les connaître !

Références utiles

L'auteur

René est né pendant l'année de la fondation d'Atari© et la sortie du jeu Pong. Depuis sa prime jeunesse, il a commencé à démonter des objets pour savoir comment ils fonctionnent. Il ne pouvait pas même passer devant des chantiers en construction sans rechercher les fils électriques qui pourraient sembler intéressants. Sa passion pour l'informatique débute quand son grand-père lui achéte un 64-bit micro contrôleur avec 256 octets de mémoire vive et un système d'exploitation de 4096 octets, le poussant à apprendre l'assembleur avant tout autre langage.

Après avoir fini l'école, il est allé à l'université afin d'apprendre la physique. Il a alors collecté des expèriences avec un C64©, un C128©, deux Amigas©, un Ultrix© de DEC©, un OpenVMS et finalement un GNULinux sur un PC en 1997. Il emploie Linux depuis ce temps et il aime toujours démonter des choses pour les ré-assembler. Sa soif de découverte le rend proche du mouvement Free Software©, où il s'évertue à comprendre comment les choses fonctionnent. Il est aussi impliqué dans des groupes de liberté civile axés sur les droits numériques.

Depuis 1999, il propose ses compétences en tant qu'indépendant. Ses principales activités comprennent l'administration système et réseau, la programmation et des conseils. En 2001, il a commencé à donner des conférences sur la sécurité informatique à Technikum Wien. Quand il n'est pas vissé devant les écrans d'ordinateur, n'examine pas du matériel et ne disserte pas d'équipement réseau, il se passionne pour la plongée sous-marine, l'écriture ou la photographie avec sa caméra numérique. Il aimerait à nouveau s'essayer à l'écriture de roman et au jeu de rôle dès qu'il trouvera un peu plus de temps libre pour s'organiser

Adaptation française de la Gazette Linux

L'adaptation française de ce document a été réalisée dans le cadre du Projet de traduction de la Gazette Linux.

Vous pourrez lire d'autres articles traduits et en apprendre plus sur ce projet en visitant notre site : http://wiki.traduc.org/Gazette_Linux.

Si vous souhaitez apporter votre contribution, n'hésitez pas à nous rejoindre, nous serons heureux de vous accueillir.