Recherche avec auto-complétion multi-mots et Postgresql

L’auto-complétion multi-mots ? Kézako ? Bon c’est un terme que j’ai un peu inventé (oui je me la raconte ;)), mais je vais vous expliquer la théorie rapidement.

Avec une auto-complétion normale, sur une base importante, on utilise en général like ‘blabla%’. Avec un index sur le champ concerné, les performances sont très correctes, et ce genre de méthode est fréquemment utilisée.

Mon problème: j’aimerai effectuer une recherche auto-complétée à partir de n’importe quel mot d’un titre.

Exemple: Trouver « Tour Eiffel » en tapant « eif ».

Exemple 2: Trouver « Tour Eiffel » en tapant « eiffel to ».

Ceci est impossible avec l’auto-complétion basique. Il faudrait taper « tou » pour trouver ce que l’on veut. De plus, un problème de casse apparait (sauf si l’on utilise ilike).

L’idée alors est de découper tous les titres par mot, et de les rassembler dans une seule et même table. Ceci fonctionne bien mais que pour l’exemple 1.

Pour l’exemple 2, j’utilise en plus le Full Text Search.

Dans la suite de cette article, j’utilise une table film avec pour champs id et titre.

Postgresql 9.1 est utilisé sur une Ubuntu 12.04 LTS.

Formatage des textes

Dans un premier temps j’ai créé une fonction qui me permet de formater tous mes titres sans majuscule, ni accent. Un avantage, l’utilisateur ne sera pas obligé de mettre toutes les majuscules et/ou accents afin de trouver ce qu’il veut.

Création de la fonction dans postgresql:

CREATE OR REPLACE FUNCTION vclean(text)
  RETURNS text AS
$BODY$
select lower(unaccent($1));
$BODY$
  LANGUAGE sql IMMUTABLE
  COST 100;

Si unaccent n’est pas disponible sur votre serveur, il faut installer postgresql-contrib, qui contient plusieurs fonctions d’aide comme unaccent.

Mise en place du Full Text Search

Dans un premier je créé une nouvelle colonne dans ma table film:

ALTER TABLE film ADD COLUMN titre_vector tsvector;

Ensuite je remplis la colonne à partir des titres de mes films:

UPDATE film SET titre_vector=to_tsvector(titre);

Et pour finir la mise en place de l’index:

CREATE INDEX x_titre_vector ON film USING gin (titre_vector);

On peut d’ores et déjà tester le Full Text Search.

SELECT id, titre FROM film WHERE titre_vector @@ to_tsquery('mechant');

12345: Moi moche et méchant
23421: Le grand méchant loup
56778: Pas si méchant que ca

"Total runtime: 11.980 ms"

Le Full Text Search est un outil très puissant pour la recherche de mots dans un document. Le problème ici c’est que l’utilisateur est obligé de taper le mot entier pour avoir une réponse. Pas très pratique.

Mise en place de la table de mots

Cette table de mots permet d’avoir une auto-complétion avec n’importe quels mots des titres des films.

On commence donc par créer une nouvelle table:

CREATE TABLE c_words (
    id      integer,
    word        varchar(100),
    CONSTRAINT c_words_id FOREIGN KEY (id)
      REFERENCES film(id) MATCH SIMPLE
      ON UPDATE NO ACTION ON DELETE CASCADE;
);

Puis remplir la table:

WITH title_words AS (
  SELECT id, regexp_split_to_table(vclean(titre), E'\\\\s+') AS word FROM film
)
INSERT INTO words SELECT * FROM title_words;

Ici la fonction un peu magique c’est regex_split_to_table, qui permet de spliter une chaine de caractères suivant un modèle; ici l’espace et ensuite de créer plusieurs entrées à partir d’une seule.

On rajoutes les index pour que ce soit un minimum efficace:

CREATE INDEX x_words_word ON c_words USING btree (word text_pattern_ops);
CREATE INDEX x_words_id ON c_words USING btree (id);

Et voila le système est mis en place.

On peut tester les 2 systèmes en même temps:

SELECT film.id, film.titre FROM film
NATURAL JOIN c_words
WHERE titre_vector @@ to_tsquery('mechant')
AND word LIKE vclean('moc%');

12345: Moi Moche et méchant

"Total runtime: 8.514 ms"

Voila on voit que la requête est exécutée très rapidement. Si je compare cet exemple à l’utilisation de like ‘%mechant%’, la vitesse de résultat n’est pas du tout la même et ne pas être utilisé dans un cas d’auto-complétion.

SELECT titre FROM film WHERE vclean(titre) LIKE vclean('%mechant%');

"Total runtime: 3661.387 ms"

Maintenant il ne reste plus qu’à intégrer tout ça avec Jquery et PHP.

Intégration

Jquery

J’utilise Jquery UI avec le widget Autocomplete, c’est simple et rapide à mettre en place:

$('#input_search').autocomplete({
        delay: 200,
        source: "http://monsite.fr/search.php",
        minLength: 3,
        autoFocus: true,
        select: function(event, ui) {
                console.log('ok');
        }

});

PHP

Et les fonctions pour la recherche en PHP avec Codeigniter comme d’habitude

public function search_activity($q) {
    $part = explode(' ', $q);
    if (count($part) == 1) {
        $r = $this->search_like($q);
    }
    else {
        $r = $this->search_hybrid($part);
    }
    return $r;
}

private function search_like($q) {

    $sql = "SELECT film.id, film.titre FROM film
            NATURAL JOIN c_words
            WHERE word LIKE vclean(?)
            LIMIT 5";

    return $this->db->query($sql, $q.'%')
                    ->result();
}

private function search_hybrid($part){

    $n = count($part);
    $fts = $part[0];
    $ac = end($part);
    if ( $n > 2 ){    
        for ( $i=1; $i<$n; $i++ ){
            $fts .= ' & ' . $part[$i];
        }
    }
    $sql = "SELECT film.id, film.titre FROM film
            NATURAL JOIN c_words
            WHERE titre_vector @@ to_tsquery(?)
            AND word LIKE vclean(?)
            LIMIT 5";

    return $this->db->query($sql, array($fts, $ac.'%'))
                    ->result();
}

Maintenant vous avez tout à votre disposition pour mettre vous aussi en place une auto-complétion multi-mots.

Avantage:

• Extrêmement performant (testé sur une table de 600 000 titres et un peu plus de 1 100 000 de mots)

Inconvénients:

• Base de données plus lourde
• Impossible de trouver « Tour eiffel » si la personne tape « ffel » comme peut le faire like ‘%bla%’