Une (ultime ?) entrée dans dans ce sujet a propos de la recherche textuel pour de vrai.
J’ai essayé trois approches pour la recherche textuelle: A) l’approche par ensembles ordonnées B) l’approche sac-de-mots C) L’approche que je mime sudopython ie. sélection des candidates + score par machine a état.
A) Approche par ensembles ordonnées
L’idée dans cette approche c’est enregistrer les relations mot → document, document → extrait ou pour faire la mise en exergue des termes de recherche présent, il faut aussi enregistrer le texte complet du document. Si on a une demande de recherche terme1 + terme2, il faut trouver les ensembles ordonnées des documents qui contiennent d’une part le terme1 et d’autre part le terme2 et ensuite zigzaguer entre les deux ensembles pour calculer l’intersection, dans le pire des cas si l’intersection est nulle, il faut quand même parcourir les n ensembles qui correspondent au n termes. Si vous trouvez ça nulle, c’est pas fini le niveau de nullité de cet algo. Si il faut prendre en compte les synonymes, stem, lemme etc… il faut tout enregistrer en amont donc non seulement ça fait exploser l’espace disque et mémoire mais aussi le temps de calcul sachant que c’est difficile a paralléliser. Le seul intérêt de cette algo, c’est l’algo de zigzag entre les ensembles ordonnées qui était nouveau pour moi, et que j’ai jamais re-utilise 
J’ai espoir que c’est un problème d’interface entre le clavier et la chaise, vu que j’ai lu a plusieurs endroit que cet approche est génial.
B) Sac de mots
Le sac de mot se construit dans une premiere approche avec un code qui ressemble a:
bag = Counter(document.split())
Il faut enregistrer ces sacs, ainsi que les relation stems (radicaux) → document. Lors de la demande, il faut sélectionner le radical positif de la demande le moins courant de la base, pour chaque document-candidat (en parallèle) calculer le score du document par rapport a la demande.
L’avantage de cette solution, par rapport a la precedente, c’est qu’on evite de recuperer tous les documents associer aux termes de la recherche (meme si c’est juste leur identifiant), la complexite depend du radical le moins courant, multiplie par la complexite de l’algo de calcul du score, au minimum m le nombre de terme donc la complexité dans le pire des cas est pas mieux que la complexité l’algo précédent, sachant que c’est plus facile a paralléliser.
Un autre avantage c’est qu’il est possible de étendre la demande avec les synonymes sans faire exploser l’espace disque et mémoire.
Il reste cela dit des problèmes dans cette approche:
-
La correspondances de demande de phrase est un chouia pas simple, il faut etendre le sac de mot avec la position des mots et rendre possible la recuperation du mot suivant a la position n + 1.
-
Pour les documents semi-structure comme l’html, on peux vouloir applique un algo de scoring différent en fonction d’où se trouve le mot dans le document ie. booster certains champs comme les titres. Dans le sac de mot comme fait avec Counter tous les mots ont la meme valeur quelque soit leur position dans le texte.
-
Pour faire le surlignage, mise en exergue des termes qui correspondent a la demande, il quasiment re-faire la correspondance dans le texte complet après scoring.
C) Score par machine a état
Cette approche est similaire a l’approche par sac de mots, au lieu d’enregistrer les relations stem → document, on enregistre les relations mot → document, tel que les mots apparaissent dans le document. On enregistre aussi l’ensemble du texte potentiellement semi-structure du document.
Lors de la demande terme1 + terme2, A) il faut étendre chacun des termes avec ces synonymes, B) a partir de la demande obtenue a l’étape précédente, étendre chaque terme en parcourant les relations terme → lemme → nouveaux termes et réduire le boost de ces termes car ils sont moins intéressant que les synonymes ou les termes de la demande initiales C) et enfin étendre la demande obtenu a l’étape précédent en parcourant les relations terme → stem → nouveaux termes. On finit avec une demande qu’on peux aplatir et éliminer les doublons, pour obtenir quelque chose comme:
(terme1 OR terme1-synonyme1:0.8 OR terme1-lemme-nouveau-terme:0.5 ...) AND ...
L’opérateur NOT terme ou avec un tiret -terme peux aussi faire partie de la soirée et appliquer un boosting négatif sur les termes obtenues lors de l’extension du terme négatif, si vous avez beaucoup de cœur ne pas assigner les abysses de moins l’infini au document qui contiennent exactement terme de façon a laisser l’algo de scoring contre-balancer une forte pertinence d’un document vis a vis des termes positif, avec une présence rare de terme négatifs.
Après extensions la demande ressemble a une demande que l’utilisateur aurait pu faire en vrai:
(mot1 OR mot2 OR mot3) AND (mot4 OU mot5) (NOT (mot6 AND mot7))
Avec le boosting:
(mot1:1 OR mot2:0.8 OR mot3:0.5) AND (mot4:1 OU mot5:0.5) AND mot6:-1 AND mot7:-1
Remarque: le NOT a été développe en AND et les termes qui étaient dans le NOT ont un boost négatif.
Toutes les valeurs de boosting en exemple sont fictives et si on considère la transitivité des synonymes (ou plus généralement du lexique) ça deviens… …
Vu qu’il y a des OR, la sélection des document-candidats a peu plus complique, en pseudo code:
candidates = min(docs_with(mot1) | docs_with(mot2) ..., (docs_with(mot4) ..., key=len)
Avec docs_with(mot) qui retourne l’ensemble des documents qui contiennent mot, la barre verticale c’est l’union des ensembles, et key=len utilise la cardinalite de l’ensemble pour calculer le min.
Remarque: l’union fait croire que il va y avoir beaucoup plus de candidats que dans l’approche sac-de-mots, en vrai oui car on considere aussi les lemmes et synonymes, il faut aussi noter que dans l’approche precedente on selectionne sur le stem des mots, rien ne se perd, l’union des documents qui contiennent les mots qui on un meme radicale donnée et égale a l’ensemble des documents dont au moins un mot a ce radicale.
Concernant le scoring de chaque document, c’est possible de faire if mot in text: score += tf(mot, text) * idf(mot) * boost mais c’est aussi possible de faire le faire en un seul parcours de text avec une machine a état et par la même occasion préparer le surlignage.
Dans cette explication, j’ai avancée dans le continuum sémantique vers plus de prise en compte du sens a travers le lexique, c’est possible avec l’approche sac de mot aussi et même le boost positif ou negatif des mot de la demande. Les avantages avec cette approche, sont:
- Il est possible de faire le surlignage et le scoring en même temps: c’est plutôt moyen voir faible comme argument, surtout que dans l’approche sac de mot, il est nécessaire de surligner que les textes de la page de résultat demandé.
- L’algorithme du score a besoin que du document original, ie. le sac de mot est inutile => moins d’espace disque necessaire.
- Pas de structure de donnée complexe pour faire la correspondance avec des phrases ou prendre en compte le titrage du texte => moins d’espace disque, et code plus simple sauf que…
- L’algo de parcours du texte est pas trivial (ex: aho-corasick) dans le cas d’un texte non-structures, et si en entrée on accepte l’html + prendre en compte le titrage … on a rien sans rien…
- Si on change d’algo de score, le document original est toujours la, pas besoin de re-index, y a compris pour la sélection des candidats qui utilise les mots présent dans le document, plutôt que les lemmes ou radicaux qui peuvent, en vrai, évoluer.
Et page rank dans tout ca? Le page rank pourrait être pris en compte lors du score pour affiner le résultat de recherche sur une page ou sur l’ensemble mais je trouve cela risque sur l’ensemble des candidats (faut être certains des valeurs du page-rank surtout si c’est dans une multiplication). Il me semble, que même pour google c’est indicatif, d’autant plus que beaucoup de lien aujourd’hui sont dans des prisons dorées 
Il me semble que google fait de la curation assistée par ordinateur par region-langue (il y a bien des humains dans le mix) et a vrai dire mon expérience personnelles de dev c’est que depuis un peu plus d’un an, en fait, depuis que google regroupe les pages du site stackoverflow et quora les resultats sont nulles, voir plus que nulle puisque je trouve des sites de chapeaux noirs dans la première page.
En parlant chapeau noir, soit disant Google évite ça, donc déjà c’est pas complètement vrai même sur un sujet qui buzz autant que l’informatique, d’autre part, Google comme écrit plus haut, il font de la curation donc il faut faire pareil, et en plus de ca, même si je dit qu’il y a des bugs dans leur moteur de recherche, Google a un rôle dissuasif et donc les pratiques de chapeaux noires basiques sont élagues.
Concernant les mots hyper frequents, il y a deux categories A) les mots commun de la langue naturelle (le, la, les, un, une…) ceux la on peux juste les interdire comme racine de selection des candidats B) les autres mots voir nom propre tres repandu dans l’index, genre python sur pypi, dans ce cas la strategie que j’ai pas encore reussit a mettre en place c’est proposer a l’utilisateur de completer la demande avec des bigram mots, trigrammes mots qui inclu un mot beaucoup plus rare contre exemple “for python by python”, exemple “python search engine”.
J’ai effleurer la notion de base de connaissances a travers les synonymes et le lexique, ou la reconnaissance d’entités nommees pour distinguer les concepts qui s’écrivent de la même façon genre: Python le serpent ou Python le langage. Ca concerne un moteur de recherche plus generaliste que pypi, malgré tout c’est interessant sur certaines requetes de decliner une demande style “http” en “http client library”, “http web framework” “http rest” etc… qui peuvent apparaître en tant que trigramme dans l’index mais pas forcement. La ou je veux en venir, et c’est un peu comme d’habitude dans tous les produits logiciels, on peux trouver des parades “produit” a des problèmes techniques, ou des heuristiques issues des besoins ou habitudes des utilisateurs qui simplifient largement le problème et la mise en oeuvre, et meme une solution a base d’interface chaise-clavier comme la curation de l’index.
Un exemple de mise-en-oeuvre de la reconnaissance d’entités nommées dans un moteur de recherche pour pypi: l’utilisateur demande django, actuellement en mono thread ca prend 14 secondes. Paf, on court-circuite la recherche, car le code reconnais django comme projet existant et a la place de résultats de recherche, le site lui propose les projets avec une dépendance vers django qui sont les plus populaires selon github ie. deux jointures et une agrégation sur le graphe dépendances entres projets et la table des meta donnees.