L’Information retrieval appliquée à la philologie. I. Approximate string matching

Le domaine de l’Information retrieval, profondément lié dans son histoire à l’informatique, connaît sans cesse des développements très importants, au cœur de l’activité du Web, de la documentation, des moteurs de recherche. On peut comprendre la tentation d’exploiter certains des acquis de cette science pour l’appliquer aux domaines qui nous intéressent, ou, pour reprendre une métaphore dans la tonalité générale de notre carnet, de boire à cette coupe qui ne se tarit jamais. Toutefois, une telle démarche ne peut aller sans une réflexion préalable.

Il ne faut pas en effet oublier que ces outils ont été créés non pas pour faciliter le travail des philologues, pour opérer des traitements scientifiques sur des corpus de textes, mais bien dans une optique de recherche d’information et de pertinence qui diffère sensiblement de la nôtre. Ce billet se veut le premier d’une série cherchant, sans exhaustivité, à passer en revue certains des outils les plus fréquents dans le domaine de l’Information retrieval et de voir en quoi ils peuvent nous être utiles, s’ils sont applicables ou adaptables à nos sciences. À cette fin, nous commencerons par un des éléments les plus « classiques », l’Approximate string matching, dont nous connaissons tous empiriquement le principe, ne serait-ce que par notre utilisation des moteurs de recherche…

Exemple sur Google

Exemple sur Google...

1. Algorithmes et calculs de distance

La Distance de Levenshtein

La mesure de distance décrite en 1965 par le mathématicien soviétique Vladimir Levenshtein1 consiste en la somme des suppressions, remplacements ou insertions qu’il faudrait effectuer pour passer d’une chaîne de caractères à une autre. De cette façon, pour passer de

Philologe à Philologie

la distance est de 1 (une insertion) ou env. 11%. Et entre :

Philologie et Philosophie

la distance est de 3 (deux remplacements et une insertion) ou 30%. La distance de Levenshtein a été implémentée par les informaticiens Robert Wagner et Michael Fischer2  (on parle alors d’algorithme de Wagner-Fischer).

La distance de Damerau–Levenshtein

La distance dite de Damerau–Levenshtein, du nom du chercheur d’IBM Frederick J. Damerau, quant à elle, se distingue de la distance de Levenshtein en ce qu’elle inclue, outre les suppressions, remplacements ou insertions, un quatrième type d’opération, à savoir l’interversion de caractères adjacents. Ainsi, la distance  entre

Philoloige et Philologie

est de 2 selon la mesure de Levenshtein, et seulement de 1 selon la mesure de Damerau-Levenshtein.

Autres mesures de distance

Si ces deux mesures de distance entre chaînes de caractères sont celles que l’on rencontre le plus fréquemment, il en existe d’autres. On citera ainsi pour mémoire la Distance de Hamming, qui ne fonctionne qu’avec des chaînes du même nombre de caractères et consiste en la somme de caractères différents à la même position. D’après cette mesure, la distance entre

Histoire et Histeire

est de 1, tandis qu’entre

Histoire et Hstoires

elle est de 7. Il faut dire que cette mesure de distance, qui correspond assez peu au fautes de frappe habituelles, est peu utilisée en tant que telle dans le domaine de la recherche d’information.

2. Mise en œuvre

Des modules Perl existant permettent de mettre en œuvre ces calculs. Nous parlerons ici brièvement des deux principaux, Text::WagnerFischer et String::Approx (je déconseille d’utiliser Text::Levenshtein qui a apparemment des problèmes avec utf8 et,  chez moi  en tout cas, donne des résultats faux…).

Text::WagnerFischer sert à la comparaison entre deux chaînes de caractères et permet d’obtenir le résultat de  la mesure de distance, ainsi :

#!/usr/bin/perl
use Text::WagnerFischer qw(distance);
print distance("bonjour","bonsoir") ;

donne comme résultat 2 (deux substitutions en l’occurrence). Mais ce module permet également d’aller un peu plus loin en configurant séparément (mais dans cet ordre) le coût d’une correspondance, d’une suppression/insertion, et d’une substitution. Ainsi, pour reprendre l’exemple précédent :

print distance([0,1,1],"bonjour","bonsoir") ;
print distance([-1,2,3],"bonjour","bonsoir");

Si le résultat de la première commande donnera toujours 2 (deux substitutions dont le coût est 1), la seconde donnera cinq correspondances et deux substitutions, soit -1*5 + 3 *2, c’est-à-dire 1 (ce n’est qu’un exemple).

Le module String::Approx, quant à lui, permet, de façon relativement simple, non plus de simplement comparer des chaînes de caractères (i.e. établir la distance qui les sépare), mais de relever directement les chaînes qui correspondent à une autre pour une distance préétablie (par défaut 10%). Ainsi, dans le script suivant :

use String::Approx 'amatch';
@mots = qw("bonjous", "bonjours", "bonsoir", "adieu");
@resultat1 = amatch("bonjour", @mots);
@resultat2 = amatch("bonjour",["25%"], @mots);

la liste @resultat1 comprendra les mots « bonjous », « bonjours » et la liste @resultat2 les mots « bonjous », « bonjours », « bonsoir » (la distance spécifiée étant de 25%).

3. Exemple d’application

Pour prendre un exemple un peu plus intéressant, j’ai testé ce module sur un corpus de textes occitans médiévaux. J’y ai recherché le terme cansos avec la distance par défaut de 10%. Dans ma liste de résultats se trouvent les termes suivants :

cansonetas, 1
cansos, 5
cansson, 5
canssons, 5
canssos, 7
chansos, 2

Ce résultat est intéressant, car ne s’y trouvent en effet que des graphies différentes de cansos, (excepté cansonetas, ce qui nous apprend par la même occasion que amatch est programmé pour s’arrêter dès qu’il trouve une correspondance, en l’occurrence canson[etas], ce qui peut-être particulièrement gênant si l’on veut traiter des monosyllabes). Toutefois, toutes les formes de cansos ne figurent pas dans cette liste : il y manque notamment chansson, chanssons et chanssos. On peut tenter d’augmenter la distance, en la fixant par exemple à 20%, mais dans ce cas, on obtient également tout une série de termes qui on peu de choses à voir avec nos chansons, en vrac canorgues, Cartosa, enansset, fermanssa, percassava3

Pour conclure, on pourra noter que, si ces modules peuvent en effet donner des résultats intéressants, il manque, pour correspondre tout à fait à nos besoins, la possibilité de configurer indépendamment des coûts permettant de différencier certaines substitutions bénignes (comme la simple variation graphique entre i et y ou l’alternance c/ch par exemple) de celles qui ne le sont pas. Pour ce faire, a priori, il faudra plutôt recourir à une grammaire d’expressions régulières.

  1. Vladimir I. Levenshtein, « Binary codes capable of correcting deletions, insertions, and reversals », dans Soviet Physics Doklady, 10 (1966), p. 707-710. []
  2. Robert A.Wagner et Michael J.Fischer, « The string- to-string correction problem », dans Journal of the ACM, 21(1974), p. 168–173. []
  3. Les précédentes versions de String::Approx contenaient une commande aregex() qui aurait permis de contourner en partie ces difficultés par l’emploi d’expressions régulières, mais celle-ci n’existe hélas plus dans la dernière version. []

Jean-Baptiste Camps

Diplômé de l'École nationale des chartes et docteur en études médiévales de l'Université Paris-Sorbonne (la Chanson d'Otinel…, dir. Dominique Boutet ), Jean-Baptiste Camps est responsable pédagogique du master «Humanités numériques» à l'École nationale des chartes (PSL). [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

Les logiciels statistiques t.1: les logiciels commerciaux

Pour cette nouvelle année que nous vous souhaitons aussi heureuse que possible,  nous ouvrons un nouveau chapitre dans notre série « à la recherche d’Excalibur ». Sans pour autant clore notre petit tour des langages de programmation utiles en sciences humaines, nous allons nous attacher un instant à vous présenter le riche marché des logiciels statistiques, grâce auxquels vous passerez, j’en suis sûr, de grands moments de plaisirs.

"Piled Higher and Deeper" by Jorge Cham www.phdcomics.com

Commençons d’abord par les logiciels commerciaux, que nous nous devons de présenter,  même si au cours de nos recherches et de nos prochains billets, nous utiliserons essentiellement (euphémisme, quand tu nous tiens!) des logiciels libres. L’importante utilisation de ce type de logiciels dans des situations commerciales (finance, étude de marché, biostatistique) a incité de nombreuses firmes à développer des programmes performants (il en existe aujourd’hui plusieurs dizaines), et somme toute assez diffusés dans le milieu de la recherche. Nous en présentons ici quelques uns.

SAS – Statistical Analysis System

Répandu dans le monde universitaire français, en particulier chez les économistes (le fait qu’il s’agisse du logiciel qu’utilise l’INSEE n’y est pas étranger), le logiciel SAS est, dans sa version « standard », un logiciel généraliste permettant la création et l’édition de base de données, y compris de très grandes envergures, et leur analyse. Le langage de ce logiciel est d’ailleurs basé sur cette distinction. D’un côté, grâce aux « étapes data », vous pouvez modifier, fusionner, recomposer comme bon vous semble vos bases de données – par exemple, créer une base de données « sacregraal » à partir d’une base données originelle « graal », en supprimant des variables gênantes:

Etape data sous SAS

De l’autre côté, grâce aux « procédures » (proc), vous pouvez réaliser vos régressions, vos analyses factorielles, faire éditer des statistiques descriptives, ou créer des graphiques prêts à exporter – mais ce n’est pas pour le côté visuel de ces derniers qu’on admirera SAS. Vous pourrez par exemple tenter d’expliquer les rires devant Sacré Graal par la présence de tel ou tel acteur, grâce à une régression logistique de premier choix:

Régression logistique sous SAS

Des macros vous permettront par ailleurs de réaliser des tâches automatiques – un outil bien utile.

SAS en est aujourd’hui à sa version 9.2, datant de 2008. Mais il peut malgré tout être utilisé de sorte qu’il soit entièrement à la pointe de l’actualité.  SAS permet en effet d’appeler des fonctions depuis le logiciel libre R, et de coder en R directement dans son interface,  grâce à SAS/IML(R) Studio 3.3. Ceci permet de profiter de toutes les innovations réalisées dans les packages pour R, avant que celles-ci ne soient éventuellement retranscrites dans le logiciel (nous reviendrons sur ces points quand nous parlerons de R dans un prochain billet).

Stata

Pas d’acronyme cette fois pour le nom de ce logiciel, qui n’est que la contraction de « stat » et « data ». Développé depuis plus de 25 ans par la Stata Corporation, Stata est certainement le rival majeur de SAS dans le monde académique, en particulier en économie, mais aussi en sciences médicales.

Lui aussi à vocation généraliste (on y retrouve peu ou prou les mêmes fonctions que dans SAS), Stata a néanmoins une originalité majeure pour un logiciel propriétaire et commercial: il permet aux utilisateurs de créer ses propres extensions (« ado-files »), qui peuvent être ensuite proposées au téléchargement. Un avantage certain, augmenté de l’abondante littérature autour de ce logiciel. Une revue à comité de lectures, le Stata Journal, ainsi qu’une mailing list, la Statalist, documentent abondamment potentialités et les mises à jour du logiciel.

En terme de langage, Stata paraît peut-être moins systématiquement construit que SAS, mais donne des programmes particulièrement courts à écrire. La régression logistique de tout à l’heure s’écrirait ainsi tout simplement (à la déclaration de la base de données près):

logistic laugh tgilliam tjones gchapman jcleese eidle mpalin

Si Stata a par contre un désavantage, c’est son prix: aux dernières nouvelles, environ 500 euros pour la licence « académique »…

Autres logiciels utiles

Les historiens s’intéressant régulièrement à des séries temporelles, ils pourront utiliser avec profit EViews, spécialisé dans ce domaine – bien qu’il assure également la plupart des fonctions des logiciels généralistes. Les étudiants ont accès à une version bridée de EViews 6 (taille maximale des bases de données réduite, ce qui n’est pas  si souvent gênant) vendue à 39,95 $. RATS (Regression Analysis of Time Series), son concurrent direct, permet également de puissants calculs autour des séries temporelles, mais gère aussi des fonctions plus rares comme les réseaux de neurone. La licence étudiante de RATS 8.0 coutera par contre 300$, la licence complète 500$…

Ceci reste toutefois donné comparé au très célèbre logiciel généraliste SPSS (Statistical Package for the Social Sciences), récemment devenu propriété d’IBM, qui s’oriente de plus en plus vers les professionnels et de moins en moins vers l’université. SPSS a l’avantage d’être particulièrement agréable à manier pour l’utilisateur, mais ceci a un prix. Toutefois, une version d’essai gratuite de 14 jours de SPSS 19 est disponible, pour quiconque voudrait s’en faire une idée plus précise. Son rival Statistica 10, lui aussi surtout destiné aux entreprises, préserve néanmoins une influence importante sur les campus nord-américains ; il n’est donc pas inintéressant de savoir le manier dans cette optique, d’autant que ces performances en terme de « data mining » sont très intéressantes. Lui aussi très à l’aise dans ce domaine, et champion des analyses factorielles – le logiciel français SPAD pourra certainement séduire, d’autant que son interface graphique est plutôt avenante, rendant le logiciel assez simple d’utilisation.

Notons enfin l’existence du logiciel Stat Transfer, qui permet de convertir tous types de bases de données en le langage que votre logiciel préféré vous demande . Pour l’utiliser, il vous en coutera 59$ pour la version étudiante, 179$ par poste pour la version académique.

Voilà! Avec tout ça, vous êtes armés ! Ruinés, mais armés… C’est déjà ça…

Florian CAFIERO

Ancien élève de l'Ecole Normale Supérieure, Florian Cafiero enseigne les méthodes quantitatives appliquées à la philologie à l'Ecole nationale des chartes, ainsi que les humanités numériques à Paris Sciences et Lettres (PSL).

More Posts

Follow Me:
TwitterLinkedIn