Discussion :

[caspertn]

Bonjour
Je désire créer une application qui permet de permet d'afficher des articles ou même des livres et faire des recherche dans les textes.
L'idée générale est qu'on peut ajouter des articles ou des livres sous format .txt.
Afin d'aclerer la recherche l'application fait l'indexation de chaque nouveau fichier.
Je cherche des algorithmes d'indexation pour faciliter et accelérer la recherche.

[djo.mos]

Pourqoui ne pas utiliser une Base de données ? ce sera beacoup plus performant, beaucoup plus simple, ...

[vmolines]

http://sqlpro.developpez.com/cours/indextextuelle/

[camboui]

A chaque fois que je passe du temps à réfléchir sur le problème de l'indexation textuelle de données, il y a toujours un pro de SQL Server pour me rabrouer ... "passe donc en indexation 'full text', c'est une fonction de base du SGBD !".
Je dois sans doute être profondément réfractaire à Microsoft, mais au vu de mon expérience, enrichie d'ailleurs par celle des autres, je préfère une solution en qui j'ai toute confiance, dont je maîtrise le paramétrage et la montée en charge, plutôt que de m'en remettre à Saint Isidore de Séville, patron d'Internet...

L'indexation et la recherche sont des points cruciaux des sites Web. En matière de recherches textuelles, les études montrent qu'en dessous d'un taux de 50% de réponses pertinentes, l'utilisateur abandonne l'outil de recherche. Une explication certaine au fait que les internautes qui naviguent sur des sites marchands ne sont que 1 à 2% à passer commande !

Intéressant, je vais lire la suite de l'article

Mais je voudrais partager ma petite expérience.
Pendant près de 4 ans on a utilisé SQL Server pour indexer plusieurs milliers de livres de référence informatique.
Au début il fallait développer "vite" afin de présenter un produit flatteur au client (c'est idiot ce que je dis, il faut toujours aller vite ). SQL Server s'est avéré efficace et fiable malgré le coté obscur de son fonctionnement et ses réponses laconiques, du genre "oui/non" avec une pondération de 1 à 1000 en cas de "oui". Avec un peu d'imagination on a réussi à maitriser le paramétrage en détail jusqu'à, par exemple, pondérer plus lourdement les titres ou permettre des recherches ciblées dans des portions déterminées de texte (comme le code, les titres des images/figures ou de tableau, les footnotes, etc). On a même réussi à faire du highlight des termes recherchés alors que SQL Server semble incapable de nous dire où sont situés exactement ces termes dans le texte qu'on lui a donné à indexer.

Mais, le succès du produit aidant (un site web, qui l'eut cru), il n'a pas tenu la charge. C'est alors qu'il a fallu développer un moyen d'indexation. Il est moins précis que SQL Server, mais on a gagné un facteur 10 dans les temps de réponses. Sans compter que l'on a pu répartir la charge sur plusieurs serveurs web (et si quelqu'un peut me dire comment "installer/répartir" SQL Server sur plusieurs machines de manière transparente pour le développeur, je suis preneur).

En conclusion, SQL Server est vraiment super, mais attention à la montée en charge.

[camboui]

http://sqlpro.developpez.com/cours/indextextuelle/

Euh... Je viens de lire... très (trop?) "scolaire" et decevant.

[vmolines]

Décris ce qui ne te plait pas dans l'article, ce qui manque selon toi , etc...
Ce sera intéressant pour tout le monde !

edit : et si tu pouvais parler de l'indexation dans ton cas, ca serait interessant aussi.

[caspertn]

camboui

Peux tu nous donner une idée sur le "moyen d'indexation" que vous avez développé?

[camboui]

Désolé d'arriver si tard, je n'avais plus revu ce sujet.

Sommairement donc:

Avant tout, on travaille en fichier custom sur disque: C++ (ou assimilé) avec des fonctions de bas niveau d'accès aux fichiers comme Open, Create, Seek, Read, Write, Close.

Conceptuellement, tous les documents à indexer sont mis bout à bout comme s'il n'y avait qu'un seul document. Ainsi, chaque mot est positionné en une place unique. On conservera une liste annexe qui, pour chaque document, fait correspondre son premier mot dans l'ensemble des mots du document global (par exemple, le document 325 commence au mot 34728 du document global).
Par ailleurs, on construit la liste de tous les mots. Pour chaque mot, on construit une liste contenant chacune de ses positions dans le document global. Grace à la liste annexe, on peut en déduire l'ensemble des documents qui contiennent le mot recherché, et la quantité de fois qu'il y apparait avec ses positions dans le document (utile pour un calcul de pondération, ou la recherche d'expressions ou mots proches par exemple).

La notion de document global permet une indexation incrémentale. Il suffit d'ajouter tout nouveau document à la fin du document global. Les listes avec les positions de chaque mot sont ensuite simplement complétées si nécessaire. De nouveaux mots sont éventuellement ajoutés, les listes existantes n'étant alors pas affectées.

Comme on le constate, mise à part la liste des mots, toutes les listes sont constituées de nombres ordonnés; le tri de ces listes est donc implicite.

Voilà, c'est grossièrement le concept de base.
Au delà, il y a un travail à faire en amont pour définir ce qu'est un "mot". Par exemple, un traitement des caractères accentués, des symboles, de la ponctuation, des formes conjuguées, des synonymes, des anagrammes, des mots vides, etc. On peut aussi faire un traitement contextuel en repérant les mots dans des titres, dans des citations, etc (il faut que les documents originaux soit formattés pour permettre ce repérage).
Et puis il y a le travail en aval. On en arrive à manipuler des listes assez grandes, mais ce n'est pas gênant. La liste de résultats pondérés est construite progressivement, puis triée.