sudopython - moteur de recherche textuel

Suite au meetup, j’ai publier le code.

Je suis rassure sur le faisabilité d’un moteur de recherche textuel avec l’intelligence en Python et ceci malgré le Global Interpreter Lock. Cela ne veux pas dire qu’il faut TOUT faire en Python comme whoosh ou en Java comme fait Lucene / Solr / ElasticSearch qui re-invente (apparament) mal la roue niveau stockage.

Niveau stockage c’est possible d’utiliser une base SQL sans avoir a utiliser les fonctionnalités dites plein texte (full-text).

Dans la v1 de sudopython, il y a une idée présente dans les deux algorithmes qui n’est pas exactement un algorithme “diviser pour régner”. Je ne connais pas le nom de ce type d’algorithme. J’ai trouve dans mon chapeau “select candidates and refine”:

  • Dans l’algo de typofix, on calcule les k-voisins (candidats) d’une chaîne de caractères, ensuite le code va calculer le score de chaque candidat vis-a-vis de la chaîne de caractères en entrée. Le résultat est approximatif, car le calcul des k-voisins est approximatif.

  • Dans l’algo de recherche textuel, on calcule le plus petit ensemble qui contiens les résultats attendus en utilisant l’association radical -> document ou le radical est actuellement le stem issue de l’algo snowball. Donc les candidats sont les documents qui contiennent le radical positif de la requête en entrée qui est le moins courant dans le corpus. Ensuite, on calcule le score de chaque candidat vis-a-vis de la requête en entrée.

Je persiste a croire que c’est possible qu’un meilleur algo en python soit plus efficace (temps cpu, mémoire et occupation du disque) et plus simple a maintenir que l’équivalent elasticsearch dans le cas de la recherche textuel. C’est plus facile de résoudre efficacement un problème identifie, que fournir un maximum d’outils pour d’être prêt a résoudre n’importe quelles problèmes (outil expert vs. outil generaliste…).

Je rebondis sur le paragraphe précédent, pour faire remarquer que “calculer la distance” c’est plus complexe que “calculer la distance inférieur a n”. Remarque: python-levenshtein est tellement rapide par rapport a CPython, cela ne vaut pas le cout de faire ca, avec CPython. Aussi, il faut remarquer que le typofix, sélectionne des mots proches donc la distance de levenshtein est jamais très grande donc en pratique c’est jamais le pire des cas, donc osef de l’algo a complexité moins grande dans le pire des cas.

benchmarks

typofix

on teste d’abord la typo correction

% python distance-benchmark.py c uvicron
0.14711737632751465
-2 icron
-2 micron
-2 ucron
-2 unicon
-2 uvicorn
-2 viron
-3 aicon
-3 aiocron
-3 apiron
-3 avion
% python distance-benchmark.py best uvicron
0.17464399337768555
86 uvicorn
83 icron
83 ucron
83 viron
77 micron
77 unicon
77 vicero
73 cron
73 icon
73 iron

C’est les resultats quand le code teste uvicron avec tous les noms de packages aka. le meilleur resultat possible sans recherche approximative.

test avec bbkh dans le mix:

% python sudopython-typofix.py best uvicron
0.027647018432617188
86 uvicorn
86 victron
0 m-validator
0 validator
0 validator.
0 pvalidator
0 ipvalidator
0 id-validator
0 card-validator
0 variation

On divise par 6 le temps de calcul mais avec un score de precision-rappel tres bas: 2 resultat vrai positif, 8 resultat faux positif, et aussi par rapport au benchmark, a mon sens il y au moins 5 faux-negatifs (icron, ucron, viron, micron, unicon).

On peux filtrer les faux positif avec un score = 0, mais surtout il y a pas assez de bon résultat. Je pense que c’est une régression par rapport a mon algo prototype.

search (aka. query)

maintenant on teste la recherche (encore naive au niveau calcul du score) et single core:

% python sudopython-query.py http web framework
0.21697688102722168
3.5 jasmine - jasmine is a behavior driven development testing framework for javascript. it does not rely on browsers, dom, or any javascript framework. thus it's suited for websites, node.js (http://nodejs.org) projects, or anywhere that javascript can run.
3.5 jasmine-core - jasmine is a behavior driven development testing framework for javascript. it does not rely on browsers, dom, or any javascript framework. thus it's suited for websites, node.js (http://nodejs.org) projects, or anywhere that javascript can run.
3 dyndns - a simple dynamic dns update http based api using python and the flask web framework.
3 limetree - async http/2 web framework
2.5 interest - interest is a event-driven web framework on top of aiohttp/asyncio.
2.5 koa - koa.js web framework port for asyncio + aiohttp
2.5 mead - flexible aiohttp web framework
2.5 mrhttp - a python web framework written in c
2.5 navigator-api - navigator web framework based on aiohttp, with batteries included.

Les resultats sont bof vis-a-vis de ce qui est populaire dans la communaute (aka. les etoiles github) mais pertinent du point de vu textuel, meme avec peu d’effort dans la prise en charge du sens des mots ie. a gauche dans le continum semantique.

% python sudopython-query.py uvicorn
0.15401053428649902
1 gunicorn-json-logger - json log configuration for gunicorn+uvicorn

Il y a clairement un bug uvicorn devrait etre dans les resultats.

Le pire des cas, c’est le radical le plus courant:

% python sudopython-query.py python
0.5274147987365723
5 python-etl - python-etl is an open-source extract, transform, load (etl) library written in python. it allows data to be read from a variety of formats and sources, where it can be cleaned, merged, and transformed using any python library and then finally saved into all formats python-etl supports. ported from cardsharp by chris bergstresser.
4 pywapa-3k - python whatever parser is a python markup converter from xml, json, yaml and ini to python dictionary. it allows also conversion between markup languages. python 3 compatible version.
4 justredis - a redis client for python supporting many redis features and python synchronous (python 3.5+) and asynchronous (python 3.6+) communication.
3 cloudxns-api-sdk-python - cloudxns-api-sdk-python: cloudxns api python software development kit.
3 create-python-project - create-python-project is a cli application to facilitate python project management
3 dawg-python - pure-python reader for dawgs (dafsas) created by dawgdic c++ library or dawg python extension.
3 jianfan - a python library for translation between traditional and simplified chinese. support python2 and python3.
3 khayyam3 - khayyam3(jalali persian datetime) library. this is fork of the original khayyam library which supports both python 2.6 above and python 3. the original khayyam library is available at: https://pypi.python.org/pypi/khayyam
3 pywapa - python whatever parser is a python markup converter from xml, json, yaml and ini to python dictionary. it allows also conversion between markup languages.
3 python-deprecated - python @deprecated decorator to deprecate old python classes, functions or methods.

python est un des mots les plus courant du corpus, donc son radical est un des plus courant, meme en single core, le temps de reponse est convenal. 500 + 300 < 1000 ms donc c’est jouable mm avec un serveur en Australie. J’insiste sur le multi-core, avec 5 coeurs, au mieux on divise par 5 le temps de recherche, donc on obtiens 100ms au mieux, 400ms avec la requete HTTP.

Si on recherche un stopword par exemple for:

% python sudopython-query.py for
0.8341526985168457

Moins d’une seconde…

Le depot est GitHub - amirouche/sudopython

Pour la base pypi.okvslite

bbkh et typofix

L’idée de bbkh c’est capturer des infos d’une séquence de symboles string dans le prefixe d’une autre séquence de symboles que j’appelle bbkh(string) avec la propriétés que plus la distance entre deux séquences est faible, plus le plus préfixe commun de leur bbkh est long.

Lorsque les symboles sont 0 et 1, le bbkh(string) se calcule en deux étapes:

Etape 1: Calculer l’arbre de Merkle de la sequence avec l’operateur boolean OR comme fonction de hash.

Etape 2: Serializer l’arbre en le parcourant de haut en bas et de gauche a droite.

Exemple: Si en entree on a 0011,

A la première étape:

          [1]
      /        \
   [0]       [1]
  /   \      /   \
[0] [0] [1] [1]

A la deuxième étape, on obtiens la séquence:

1
01
0011

Donc:

1010011

Dans ce cas, il faut compléter avec un bit pour faire un nombre entier d’octet.

Zero est la seule sequence qui a comme bbkh zero. Aussi, tous les autres hash commence par 1 donc le bit le plus signifiant dans l’encodage des entiers, est insignifiant dans le cadre du bbkh.

Le OR va diffuser l’information des bits vers l’avant du hash. Par exemple, au deuxième étage on a 01 donc on est sur d’avoir au moins un bit a 1 dans la second partie de la séquence d’entrée.

Dans le typofix, en entrée c’est une chaine de characteres ascii, je me souviens pas si c’est essaye mais je pense que ca marche moins bien d’appliquer bbkh sur les chaines ascii. Pourquoi ? Parce que dans l’encodage ascii deux caracters differents vont avoir des bits en communs:

In [1]: bin(ord('a'))
Out[1]: '0b1100001'

In [2]: bin(ord('b'))
Out[2]: '0b1100010'

Les deux premiers bits sont les memes.

D’autres part, si le hash utilise l’encodage ascii, il fait 1 octet par caractères, donc plus la chaîne est grande, plus le bbkh sera grand, et se serait le comble pour un hash. Au lieu d’utiliser l’encoding ascii, le code utilise l’encodage one-hot, avec une position par bigram caractères. Le bigram capture plus d’information sur les mots que l’encoding one hot sur un seul caractères et donne des hash plus grand. De même, introduire ou coupler avec les trigrammes, va probablement aider mais çà fait des bbkh plus grand.

Conclusion: quelque soit le mot en entrée, on obtiens une séquence de booléens, qui capturent la similarité de l’ensemble du mot dans son préfixe, et ce hash a une taille fixe, actuellement dans le code c’est 2 ** 11 = 2048 bits = 256 octets autrement dit il faut au moins 4 000 mots pour que l’index mesure 1 mégaoctet.

Note: Dans bbkh c’est un mix de deux algo one-hot encoding sur les bigram caractères + la sérialisation de la séquence obtenu avec merkle tree a l’aide de l’opérateur booléen OR. C’est possible d’utiliser les deux separemment, par exemple utiliser simhash en premier et passer ca dans le merkle tree.

Note2: C’est possible qu’un algorithme similaire soit utiliser en bio-informatque pour l’alignement ou recherche de séquences ADN / ARN.

Note3: Plus le nombre de symboles en entrée est grand, plus le hash est grand. Si il y a 65536 symboles différent en entrée, ET que le code utilise les bigram, chaque hash fait 0.5G:

In [8]: (65536 * 65536 / 8) / (1024 ** 3)
Out[8]: 0.5

C’est le produit cartésien issue de l’utilisation des bigram qui fait exploser l’index. Anyway, il faudrait faire une vérification plus méticuleuse, mais il me semble c’est mieux de faire de la translittération vers ASCII des symboles utf-8.

Il y avait un bug majeur dans le code du bbkh. En remplacant big par little lors de la serailization en bytes, ca marche beaucoup mieux:

J’en est profite pour ajouter le support des trigrams que je passe dans une moulinette mulitcore.

% python benchmark-typofix.py uvcorn
0.5239260196685791
92 uvicorn
80 corn
80 ucon
77 unicorn
77 uvicore
73 acorn
73 corun
73 mucor
73 uconf
73 ucron
0.1378026008605957
92 uvicorn
77 uvicore
67 uvc
62 uvarint
60 uvsc
60 uvio
53 uvincenty
53 uvcclient
50 uvpool
46 uvoauth

La recherche reste approximative, et on obtiens pas forcement ce qu’on attend:

% python benchmark-typofix.py django-saerch
0.5557940006256104
92 django-search
88 django-saber
87 django-sae
87 django-sec
86 django-tsearch2
85 django-scaler
85 django-sencha
83 django-appsearch
83 djangocms-search
83 django-echo
0.13120555877685547
80 django-saber
78 django-sae
75 django-safe
71 django-saferpay
71 django-safeform
69 django-saddle
69 django-safespace
69 django-safety
65 django-safemigrate
64 django-sabridge

Aussi j’ai remplace lsmdb par leveldb. Le calcul des bbkh meme en multicore est tres long.

De meme, je prend en compte le README en plus du nom du package et de la description. Ce qui explique que le projet uvicorn etait absent de la rercherche sur uvicorn. Consequence: c’est tres long.

Prochaine etapes:

  • Passer en multicore la creation de l’index
  • Passer a postgresql avec asyncpg
  • Tester avec pypy

Le calcul de la typo correction “naive” est réalisé a l’aide de python-Lenveshtein, et fuzzywuzzy voici le code:

def score(a, b):
    d = c.distance(a, b)
    if d > 3:
        return 0
    return fuzzywuzzy.fuzz.ratio(a, b)

Voici le temps de calcul en secondes et les résultats pour uvcron:

0.18534088134765625
91 ucron
80 cron
80 ucon
77 devcron
77 uvicorn
73 auron
73 creon
73 crone
73 crono
73 cronq

De même avec l’algo du bbkh qui utilise les bigrams:

0.03765416145324707
91 ucron
62 upscrot
60 ucnn

En doublant l’effort, on peut obtenir:

0.06331205368041992
91 ucron
80 ucon
77 uvicorn
73 uconf
67 utmcon
67 unicon
67 urconf
67 urecon
62 upscrot
60 ucnn

Un truc évident c’est que bbkh plus rapide.

Si je prend du recule et que je considère comment est utilisé cette fonction, la différence entre 60 millisecondes et 200 millisecondes est insignifiante vis-a-vis du maximum de temps de réponse que je me suis fixe a 1000 millisecondes. 200 ms + 100 ms (ping) = 300ms << 1 000 ms. D’autres part, même si la bonne réponse (gold standard) est difficile a établir, le résultat de la solution naïve est suffisamment bon, plus facile a expliquer, plus facile a maintenir etc… sachant que l’ensemble des mots qu’on considère tiens largement en mémoire vive.

Note: Je considére que 200ms c’est le temps moyen et c’est probablement aussi le temps max quand la chaîne en entrée (uvcron dans ce cas) est raisonnable. En effet, le score sans valeur minimal, peux prendre un certains temps et dépends du min ou du max des tailles des chaînes en entrées.

1 J'aime

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 :sweat_smile:

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… :sweat_smile:

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 :roll_eyes: 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.