Dans un site de contenu, pour rechercher les similitudes entre deux documents basée sur les tags qui leur ont été associés, on recherche l'intersection commune. En d'autres termes, on recherche dans le corpus des documents les documents avec le plus grand nombre de tags communs.

Les algorithmes de voisinage, qui sont les plus simples à mettre en oeuvre, permettent de trouver rapidement ces similitudes en disposant dans un espace multidimensionnel les documents. Chaque dimension est un tag et le document se trouve dans cette dimension
à la coordonée 0 ou 1 (le document possède ce tag ou non).

Une fois cette carte dressée, il est possible de retrouver les "voisins" d'un document, c'est-à-dire les documents les plus proche dans l'espace.

Cet algorithme s'appel le k-Nearest Neighbor, ou k-NN.

Le livre de référence en matière de IA ("Artificial Intelligence: A Modern Approach"), propose une implémentation de cet algorthime en Python, disponible sur son site.

Qui sont mes copains ?

Les cas d'utilisations ne manquent pas pour le k-NN. Il peut par exemple être employé pour rechercher des similitudes entres utilisateurs de la même application. C'est le cas par exemple sur Last.Fm, qui propose une fonctionnalité de "Voisinage" où la liste des utilisateurs les plus proches de vos choix en matière de Tags, est affichée. Cette liste de personne est susceptible d'avoir des goûts très similaires aux vôtres.

Le paquet neighbors

Pour une de mes applications, j'ai développé un paquet au dessus du code du livre, qui propose une api simplifié qui permet de retrouver les voisins d'un utilisateur, en fonction des tags utilisés.

Il corrige aussi des erreurs (signalées) dans l'implémentation proposée par le livre et fourni un système de persistence en base, qui permet de découpler le travail de calcul des requêtes: une application peut requêter la base pour connaître les voisins d'un utilisateur, pendant qu'un processus se charge de les calculer et les mettre à jour régulièrement.

Voici le docstring du paquet:

=======
neartag
=======

This module implements the k-nearest neighbor algorithme (k-NN) that allows
to compute the distance between elements, given a set of value. Each value
is a dimension and the set are the coordinates of the element in the multi
dimensional space.

For tags, the idea is to find neighbours of a given user, depending on the
tags she uses. The `NearestByTag` class is instanciated with those tags::

    >>> from neartag import NearestByTag
    >>> tags = ["django", "python", "zen", "fun", "scary"]
    >>> solver = NearestByTag(tags)

Then each user is added with her name and tag values (boolean value)::

    >>> user_1 = 'user 1', ["django", "python"]
    >>> user_2 = 'user 2', ["zen", "fun", "scary"]
    >>> user_3 = 'user 3', ["django"]
    >>> user_4 = 'user 4', ["django", "python"]
    >>> for user, tags in (user_1, user_2, user_3, user_4):
    ...     solver.add_user(user, tags)

The class then will give a sorted list of neighbours of a given user::

    >>> solver.neighbours('user 1')
    [(0.16..., 'user 4'), (0.3..., 'user 3'), (1.0, 'user 2')]
    >>> solver.neighbours('user 2')
    [(0.83..., 'user 3'), (1.0, 'user 1'), (1.0, 'user 4')]
    >>> solver.neighbours('user 3')
    [(0.33..., 'user 1'), (0.33..., 'user 4'), (0.83..., 'user 2')]
    >>> solver.neighbours('user 4')
    [(0.16..., 'user 1'), (0.33..., 'user 3'), (1.0, 'user 2')]

The smallest the returned value is, the closest the user is.

`neighbours` will return at most 10 neighbours, but this size can be changed::

    >>> solver.neighbours('user 1', 1)
    [(0.16..., 'user 4')]

This class works in-memory, since the loaded values are small enough to fit.

How to use it with an application
=================================

Tags changes all the time in an application. The best use is to instanciate
the class over data retrieved from a database and to compute the distances,
then to save them within a dedicated table. Since the computation can take
time, a thread worker can update those distances from time to time in the
background.

Le paquet neighbors est disponible sur mon repository Mercurial: http://hg.programmation-python.org/repositories/public/ (il faut vraiment que je fasse une autre interface web que celle par défaut de Mercurial...)

Merci à Olivier pour ses précieux conseils en IA !

Il y a beaucoup de sites web qui me frustrent : une recherche avec un mot donné ne fonctionne pas alors que je sais qu'il existe sur le site en question des documents correspondants.

La technique la plus simple pour essayer de maximiser les résultats de recherche est d'ajouter un maximum de métadonnées sur les documents, ou d'ajouter une mécanique de synonymes dans le moteur de recherche. Mais ce travail est fastidieux.

Pour faciliter ce travail, j'utilise maintenant une table qui stocke l'intégralité des recherches qui ne donnent aucun résultat, avec pour chacune le nombre de demandes.

Cette table permet de déceler les informations que les utilisateurs tente le plus souvent de trouver sur le site sans succès. La mise en place des métadonnées devient enfantine, et lorsqu'aucun document ne peut correspondre, une attente de contenu est décelée.

Idée simple, pas nouvelle, mais rudement efficace :)

Et vous, connaissez vous des techniques pour améliorer l'indexation d'un site ?

Lorsqu'un site web a besoin d'afficher du contenu récupéré sur un autre site, il rend la rapidité d'affichage dépendante des performances du site tiers. Pour résoudre le problème, la solution la plus simple consiste à rapatrier les ressources pour ne plus avoir à appeler le site tiers, et à les mettre à jour régulièrement.

La mise en place de cette mécanique peut devenir un développement à part entière si l'on souhaite utiliser les ressources depuis plusieurs applications web ou dans une infrastucture redondante pour les montées en charge.

Heureusement il y a Findus Memcached. Ce serveur de cache distribué réduit à quelques lignes le code nécessaire pour fournir à une application Python un système de cache ultra performant. Le framework Django, ansi que de nombeux produits Plone, utilisent d'ors et déjà memcached pour la mise en cache des pages web.

Pour mettre en cache des pages web externes ou des images, le petit module ci-dessous suffit:

import memcache
from urllib2 import urlopen

host = 'localhost:11211'

mc = memcache.Client([host], debug=0)
connected = mc.servers[0].connect() != 0
if not connected:
    raise Exception('%s seems down' % host)

def _get_metadata(url):
    """get url infos"""
    return urlopen(url).info()

def _get_content(url):
    """get url content"""
    return urlopen(url).read()

def get_content(url, control=False):
    """get cached content"""
    cached = mc.get(url)
    if cached is not None:
        infos, cached = cached
        # controls the metadata to see
        # if the source has changed
        if control:
            latest_infos = _get_metadata(url)
            if latest_infos.values() == infos.values():
                return infos, cached
        else:
            return infos, cached
    cached = _get_content(url)
    infos = _get_metadata(url)
    mc.set(url, (infos, cached))
    return infos, cached

Il peut ensuite être utilisé pour l'affichage par le serveur d'application via une de ces solutions:

• Un proxy local appelé via une rewrite rule d'Apache qui repère les éléments externes au domaine par expression régulière. (solution la plus élégante)
• Des urls spécifiques qui appelent une fonction en charge de renvoyer la ressource

Dans Django, avec la solution n°2, une nouvelle expression dans urls.py et une vue spécialisée, en charge de renvoyer la ressource, peuvent être utilisées. Attention cependant à conserver des urls fixes, uniques (REST quoi ;)) pour chaque image, pour ne pas perdre le cache du navigateur coté client.
 
Voici un exemple d'utilisation via Django.

Dans urls.py l'expression régulière suivante :

(r'^ext/(?P<url>.*)$', 'views.get_external')

permet d'intercepter les urls qui commencent par /ext sur le portail. En remplacant les urls des ressources externes par des urls internes et en retirant le http://, on obtient des urls uniques:

http://example.com/media/image1.jpg

devient

/ext/example.com/media/image1.jpg

La vue invoquée peut alors appeler le module de cache:

def get_external(request, url):                                                 
    """retrieves external url""" 
    infos, content = cached_url.get_content('http://%s' % url)                  
    response = HttpResponse(content)
                                                                                
    del response.headers['Content-Type']                                        

    hop_by_hop = ('connection', 'keep-alive', 'proxy-authenticate',             
                  'proxy-authorization', 'te', 'trailers',
                  'transfer-encoding', 'upgrade')                               
  
    for key in infos.keys():
        if key in hop_by_hop:
            continue
        response.headers[key] = infos[key]
 
    # XXX cache info need more infos                                            
    response.headers['via2'] = 'Django memcached App'                           
                                                                                
    return response

Ce qui n'a pas été couvert dans ce billet:

• Le flush
• La gestion fine des timeout du cache, avec le header Age

Il existe d'autres solutions, via des extensions pour Apache, pour mettre en place ce fonctionnement. Mais la simplicité et la rapidité de mise en oeuvre de Memcached est telle qu'il ne faudrait pas s'en priver ;). De plus, si ce sont des images que vous récupérez, vous pouvez imaginer toute sorte de traitement avec PIL avant de les ranger dans le cache, ou même créer un système de thumbnails très performant.

Dans mon post précédent, je parlais de l'indexation avec Xapian. Le fonctionnement du paquet a du être revu pour fonctionner convenablement avec un site Django (ou tout autre site web). En effet un site internet peut manipuler le code par le biais de plusieurs threads et processus, et Xapian ne peut avoir qu'un seul accès en écriture à sa base de données. Il est donc nécessaire de découpler l'indexation des requêtes de recherche.

Une des solutions est de maintenir sur le filesystem un fichier de lock pour s'assurer que la base n'est pas ouverte en écriture par deux threads au même moment, mais cette solution fonctionne mal en cas de crash de l'application. De plus, les données en cours d'indexation peuvent être perdues.

La solution optimale est d'opter pour un pattern producers-consumer avec une pile persistente des données de travail, indépendante du site web, qui ne devient qu'un client parmi d'autres.

Voici les modifications apportées au paquet pour mettre en place ce fonctionnement :

• Les demandes d'indexation sont maintenant stockées dans une base de donnée sqlite. Comme SQLALchemy est employé, un passage à postgres ou mysql est direct.
• Un thread est en charge de lire la base pour récupérer les demandes d'indexations et acter
• L'API de recherche ouvre la base Xapian en lecture seule pour les requêtes

Cette architecture offre en outre un fonctionnement rapide : lorsque des documents sont ajoutés ou modifiés dans le site, leur indexation est fait de manière asynchrone. Le système des signals est utilisé pour déclencher une indexation à chaque modification d'un document basé sur un model. Ce mécanisme, basé sur le framework d'events de Django, est expliqué ici: http://www.mercurytide.com/whitepapers/django-signals/.

Au final, pour utiliser le paquet il faut:

• Lancer le thread en charge des indexations (via le script run.py)
• Importer dans son code les modules searcher et indexer pour travailler

Voici le doctest complet pour bien comprendre le fonctionnement :

=======
indexer
=======

The indexer provides:

- client-side modules : API for client to ask for indexations and query the
  Xapian database. When an indexation is asked, it is stored in a sql
  database;

- server-side application: a standalone thread that indexes what has been
  asked by reading the sql database.


Let's import the modules used by the client-side::

    >>> import indexer
    >>> import searcher

Let's reset the SQL DB first::

    >>> indexer.reset()

Let's also reset the Xapian DB::

    >>> from xapindexer import force_reset
    >>> force_reset()

The Xapian DB should be empty now::

    >>> searcher.corpus_size()
    0

Indexation
==========

Each indexable content has a unique id, and a text to index::

    >>> uid = '1'
    >>> text = 'my taylor is not rich anymore'

Let's index it::

    >>> indexer.index_document(uid, text)

Another one::

    >>> indexer.index_document('2', 'pluto is a dog')

Let's start the worker that is in charge of asynchronous indexation::

    >>> from xapindexer import start_server
    >>> start_server()

Let's wait a bit so the worker has the time to read the SQL Database
and do the work::

    >>> import time
    >>> while indexer.is_working():
    ...     time.sleep(0.2)

`is_working` looks in the SQL DB if there is some work left.

The Xapian DB has two documents now::

    >>> searcher.corpus_size()
    2

Searching
=========

Let's search now, with `searcher`. Operator is AND by default::

    >>> res = searcher.search('rich')
    >>> list(res)
    ['1']
    >>> res = searcher.search('pluto')
    >>> list(res)
    ['2']
    >>> res = searcher.search('dog')
    >>> list(res)
    ['2']
    >>> res = searcher.search('rich dog')
    >>> list(res)
    []

Or operator::

    >>> res = searcher.search('rich dog', or_=True)
    >>> res = list(res)
    >>> res.sort()
    >>> res
    ['1', '2']

We have an API to detect if a document is present::

    >>> searcher.document_exists('2')
    True
    >>> searcher.document_exists('ttt')
    False

And another one to retrieve indexed terms::

    >>> list(searcher.document_terms('2'))
    ['dog', 'is', 'pluto']


Reindexation
============

The document can also be reindexed::

    >>> indexer.index_document('2', 'pluto is a cat')
    >>> indexer.work_in_process()
    ([2], [])

Let's wait a bit::

    >>> while indexer.is_working():
    ...     time.sleep(0.2)

Let's make sure the document has been reindexed::

    >>> list(searcher.document_terms('2'))
    ['cat', 'is', 'pluto']

Then check the indexation has changed::

    >>> res = searcher.search('rich dog', or_=True)
    >>> list(res)
    ['1']

Or deleted::

    >>> res = searcher.search('pluto')
    >>> list(res)
    ['2']
    >>> indexer.delete_document('2')
    >>> while indexer.is_working():
    ...     time.sleep(0.2)
    >>> res = searcher.search('pluto')
    >>> list(res)
    []

Sur la maquette que j'ai monté pour tester l'outil, j'ai été surpris de la rapidité de la solution. Le couple Xapian+Django permet de mettre en place un moteur de recherche très efficace. Lorsque le site en cours de conception sera terminé, je posterais un lien sur mon blog pour démo.

Le code peut être récupéré dans xap ici: http://hg.programmation-python.org/repositories/public/

Prochains billets possibles sur ce sujet (à vous de choisir en commentant ce billet):

• commentaires détailés sur le code conçu
  
• explications sur les signaux dans Django
• ...
  

J'en avais parlé il y a quelques mois, Xapian est très simple à utiliser et à mettre en oeuvre pour des besoins légers d'indexation. Malgré son API très orientée page html (chaque document indexé l'est avec le contenu de la page), l'outil peut être utilisé pour fournir un moteur de recherche light rapide. Le système de Query qui pêchait encore il y a quelque temps (combinaisons limitées) est maintenant plus complet.

Xapian s'installe très facilement, ainsi que son binding Python (voir site)

J'avais besoin d'un petit moteur pour un site que je suis en train de monter en Django. Voici le principe mise en oeuvre:

• Création d'une base de type Flint
• Indexation de documents
• Recherches simples AND ou OR

La base est créé par l'API flint_open:

>>> import xapian
>>> DB = xapian.flint_open('file.db', xapian.DB_CREATE_OR_OPEN)

Puis chaque document est indexé par la création d'un Document et un appel successif à ses méthodes add_term et add_posting, sachant que set_data n'est pas utilisé dans notre cas.

• set_data permet de définir le contenu du document à stocker, puisque le moteur prend aussi en charge les données.
• add_posting permet de stocker les mots-clefs associés au document, qui permettent de le retrouver dans une recherche.
• add_term est utilisé pour stocker la clé unique, préfixée d'un 'Q'
  

Pour des besoins simples d'indexation, set_data se contente de stocker un identifiant unique, comme un uuid ou une url:

>>> uri = '111'
>>> doc = xapian.Document()
>>> doc.add_term('Q%s' % uri, 1)

Enfin, chaque mot est associé au document avec add_posting:

>>> i = 1
>>> for word in ('cat', 'pussy', 'cool'):
...     doc.add_posting(word, i)
...     i += 1

Puis le document ajouté à la base:

>>> DB.add_document(doc)

La recherche est ensuite effectuée par le biais d'un object Query:

>>> enquire = xapian.Enquire(DB)
>>> query = xapian.Query('pussy')
>>> enquire.set_query(query)
>>> res = enquire.get_mset(0, 100)
>>> res[0].document.termlist().next().term[1:]
'111'

Les API delete_document et replace_document permettent aussi de gérer la réindexation, en retrouvant le document déjà indexé par le biais d'une recherche sur le term qui sert de clef.

Xapian fourni également des tokenizers pour faciliter le travail d'extraction des mots à associer au document. J'utilise pour ma part un tokenizer maison plus paramétrable.

Si vous avez envie d'utiliser Xapian pour un projet Python, n'hésitez pas à récupérer le paquet (embryon en cours de conception) que j'ai fait sur mon repository. Il gère l'indexation, la réindexation, la suppression, etc.

Repo (cliquer sur manifest, puis aller dans 'xap'):  http://hg.programmation-python.org/repositories/public/

Il fournit une API extrêment simple à mettre en oeuvre. (c.f. le doctest dans doc/db.txt)

Feedback welcome !

Billet très rapide ;)

mes slides des JFP :

• Présentation sur le DDD
• Le Keynote de démarrage des journées

N'hésitez pas à commenter ce billet pour toute question ou remarque