Analyse de réseaux (3): s’il vous plaît… dessine-moi un réseau

Mis en avant

 » – Dessine-moi un mouton. » Alors j’ai dessiné. Il regarda attentivement, puis: « – Non! Celui-là est déjà très malade. Fais-en un autre. » Je dessinai : […] « – Tu vois bien… ce n’est pas un mouton, c’est un bélier. Il a des cornes… » Je refis donc encore mon dessin. Mais il fut refusé, comme les précédents […] Alors, faute de patience, comme j’avais hâte de commencer le démontage de mon moteur, je griffonnai ce dessin-ci. […] « – C’est tout à fait comme ça que je le voulais ! »

                      Le Petit Prince, Antoine de Saint-Exupéry, Chapitre II

Après avoir exploré très succinctement quelques possibilités et limites de l’analyse des réseaux, nous commençons une série d’articles consacrée au travail sur sa propre base de données.

En supposant que la base de données soit déjà créée et bien ordonnée, la première étape du travail est la visualisation de réseaux. C’est une étape cruciale pour comprendre ses données, mais aussi un enjeu important pour la diffusion de sa recherche, et qui comporte plus de risques qu’il n’y paraît. Des dessins radicalement différents peuvent correspondre au même graphe: lequel choisir ?

Il est parfois tentant d’adopter une démarche un brin naïve face à la représentation de notre réseau. Se contenter de choisir l’affichage par défaut minimise la peine, à défaut d’être toujours adéquat. Choisir le plus beau rendu visuel est également un travers séduisant.

Mais le risque le plus grave est ce que j’appellerai le « syndrome du Petit Prince »: demander à ce que le dessin soit fait et refait, jusqu’à ce qu’il apparaisse sous les traits dont nous rêvions, jusqu’à qu’il laisse assez de place à notre imaginaire pour qu’il puisse être interprété comme nous le voulions.

Il est toujours tentant, quand une multiplicité de représentations graphiques est possible, de sélectionner celle qui semble le plus manifestement aller dans le sens de nos hypothèses de départ, celle qui ressemble le plus à l’idée que nous nous étions faites de nos données.

Pour éviter tous ces écueils, nous livrons ici quelques éléments importants pour la construction d’une représentation graphique compréhensible, attrayante, mais avant tout fidèle à nos données.

PARENTHESE TECHNIQUE: LE LOGICIEL GEPHI

  • Pourquoi Gephi ?

Nous choisissons de présenter ici un logiciel développé depuis 2008 à l’université technologique de Compiègne (UTC), et dont l’usage s’impose de plus en plus dans la recherche française et internationale ces dernières années: Gephi. Relativement facile à prendre en main, ce logiciel offre néanmoins de vastes possibilités, en particulier en termes de visualisation.

Il traite tous les types de réseaux, dirigés, non dirigés ou mixtes, et est compatible avec Windows, Linux et Mac OS. C’est de surcroît un logiciel libre, publié sous licence CDDL + GNU GPL 3.

Attirons l’attention sur la version de Gephi utilisée: les changements intervenus entre Gephi 0.8.2 et Gephi 0.9.1 (celle dont nous parlerons) n’ont pas été sans conséquences, notamment en ce qui concerne les plugins. Certains tutoriaux et cours produits pour les versions antérieures ne sont donc plus toujours valables – les suivre à la lettre pouvant provoquer quelques bugs mineurs.

  • Travailler ses données sous Gephi

Gephi supporte des données à différents formats. Le GEXF (Graph Exchange XML Format) est le format développé depuis 2007 par l’équipe Gephi,

Une base de données au format gexf – exemple des la base « Les Misérables »

Notons que ce format permet de décrire explicitement dès l’encodage le caractère dirigé ou non des liens, d’assigner des labels, et d’attribuer des pondérations.

Mais le logiciel accepte bien d’autres formats: GraphML, GraphViz DOT, Netdraw VNA, PajekNET, GDF, GML, Tulip TLP, UCINET DL.

Plus simplement encore il est possible d’importer des fichiers .csv créés sous Excel, OpenOffice Calc ou autre tableur standard. Un simple tableau à deux colonnes – première colonne nœud d’origine, deuxième colonne nœud d’arrivée du lien – peut donc être exploité pour modéliser son réseau dirigé ou non.

  • Manipulations esthétiques et d’étiquetages

Via le menu du bas, minimisé par défaut, on peut appliquer la plupart des variations simples.

Dans l’onglet « global », on permet de changer le zoom ou la couleur du fond. Dans les onglets suivants, on peut modifier les options d’affichage des nœuds et des liens (leur couleur, leur forme, leur épaisseur etc.). Gephi permet par ailleurs d’étiqueter chacun des nœuds – une option activable et configurable sur le même menu.

CHOISIR LA MISE EN FORME DE SON RÉSEAU: LA SPATIALISATION

Une étape cruciale est le choix de la spatialisation, (en anglais du « layout ») c’est à dire de la manière dont l’ordinateur va organiser les points dans l’espace.

Plusieurs options sont proposées dans GEPHI, et doivent être choisies en fonction de ses données et de l’usage que l’on veut faire de la représentation graphique. Nous présentons ici quelques options usuelles, installées par défaut ou accessibles via des plugins spécifiques.

Pour illustrer la grande variété des représentations graphiques, nous utiliserons systématiquement la même base de données (une base de données exemple de Gephi, retranscrivant les liens unissant entre eux les personnages des Misérables de Victor Hugo – son contenu est parfaitement indifférent pour notre propos du moment, nous ne commenterons bien sûr pas les résultats…).

Rapport d’import renvoyé par GEPHI à chaque importation d’une nouvelle base de données – ici pour la base de données exemple « misérables.gexf »

Une base de données de taille particulièrement modeste, qui permet d’appliquer aisément tous les traitements que nous voulions présenter.

Tout répartir au hasard ?

  • Spatialisation aléatoire

Une possibilité pour ne pas « projeter » son interprétation sur ses données, de ne pas imposer de vues au lecteur du graphique, pourrait être de demander à ce que les points soient répartis « au hasard » sur le graphique.

C’est ce que propose l’option « spatialisation aléatoire ». On n’y définit que la taille de l’espace alloué à la représentation graphique (plus l’espace défini est petit, plus le dessin apparaîtra « compact »).

Notre réseau exemple spatialisé avec l’algorithme Spatialisation aléatoire

Si séduisante puisse-t-elle paraître d’un certain point de vue, cette option aboutit cependant à des graphiques souvent impossibles à interpréter, en particulier lorsque la taille du réseau augmente.

Représenter un réseau ayant une « réalité » géographique:

Le cas le plus simple intervient quand le réseau que l’on veut représenter correspond à une réalité physique en général, géographique en particulier. Dans ce cas, les distances entre points sont une fonction de la distance physique séparant chaque point du réseau. Comme toujours en cartographie, le choix de la projection peut bien sûr influer su le regard.

  • Geo Layout

Demande l’installation du plugin GeoLayout.

On entre une base de données dans laquelle les nœuds sont définis par leurs coordonnées géographiques (longitude/latitude). Les points sont alors positionnés en fonction de ces points – les projections les plus usuelles, comme Mercator, étant bien sûr envisageables.

La faible complexité de cette opération permet l’usage de très grandes bases de données (jusqu’à 1.000.000 de nœuds).

  • Map of countries

Demande l’installation du plugin Map of Countries.

Reprenant une grande partie du fonctionnement du plugin précédent, Map of countries permet sans surprise de représenter son réseau sur une carte incluant les tracés des frontières nationales ou régionales.

Mettre en avant les complémentarités: les algorithmes basés sur les forces

La plupart des algorithmes proposés par GEPHI sont des algorithmes de dessin basés sur les forces (Force-directed ou Force-based algorithms).

L’intuition sous-jacente à ces algorithmes est simple: les points reliés entre eux sont attirés les uns envers les autres, tandis que les points isolés sont repoussés. Un mode de pensée inspiré de la physique de l’électro-magnétisme.

  • ForceAtlas:

C’est un des algorithmes « maison » de Gephi, créé par Mathieu Jacomy en 2007.

Il est pensé pour mettre en valeur les réseaux « petit monde » (pour un rappel sur ces réseaux, voir notre premier billet de cette série), et de manière plus générale, les réseaux invariants d’échelle (« scale-free network »).

Notre réseau exemple spatialisé avec l’algorithme ForceAtlas, paramètres par défaut sauf « force de répulsion = 2000.0 »

On prendra garde à la configuration précise de l’algorithme, notamment à celle des forces d’attraction et de répulsion. Une force de répulsion trop faible (ou une force d’attraction trop grande) risque d’aboutir à des superpositions malvenues, et de rendre le graphique illisible.

Notre réseau exemple spatialisé avec l’algorithme ForceAtlas, paramètres par défaut – en particulier avec  « force de répulsion = 200.0 »

L’auteur recommande un usage pour des données ne dépassant pas 10.000 nœuds, du fait de la complexité quadratique de l’algorithme, et du temps de calcul qu’elle engendre.

  • Yifan hu proportionnal

Pour traiter de plus grandes bases de données, on pourra se tourner vers l’option « Yifan Hu proportionnal », du nom d’un chercheur de Yahoo! research qui a produit des travaux remarquables sur la visualisation de grands réseaux, dont on utilise ici un algorithme de 2005. On se référera par ailleurs avec bonheur à sa récente revue de littérature co-écrite avec Lei Shi [2015] pour mieux comprendre l’état actuel des débats sur la visualisation de grands réseaux.

Cet algorithme permet l’exploitation de réseaux allant jusqu’à 100.000 nœuds

Notre réseau exemple spatialisé avec l’algorithme Yifan Hu proportionnel

On note également Force Atlas 2, un autre algorithme spécifique à Gephi, qui utilise certains mécanismes d’approximation similaire pour traiter de très grandes bases de données.

  • Fruchterman Reingold

Pour une base de données peu importante, on pourra choisir l’option « Fruchterman Reingold » d’après l’algorithme de ces deux auteurs [1991].

Notre réseau exemple spatialisé selon l’algorithme de Fruchterman & Reignold (1991) sous Gephi

Une visualisation devenue classique, mais un algorithme d’une complexité importante, qui la disqualifie pour l’étude de grands réseaux.

Une barre d’attente à laquelle il faut s’habituer lorsque l’on utilise cet algorithme avec des données un peu conséquentes…

Insister sur les divisions:

  • Open ord

Open Ord est un algorithme pensé pour décrire des réseaux qui ne seraient pas des petits mondes, et dont on voudrait mettre en avant les différents groupes (clusters) constituant. S’inspirant de Fruchterman-Reingold, qui devient ici un cas particulier des traitements possibles, l’algorithme cherche aussi à s’affranchir de la complexité quadratique inhérente aux modèles « force-based » que nous venons d’évoquer.

Une idée maîtresse pour cet algorithme est de permettre de couper certains liens les plus longs (dans la représentation graphique s’entend) – ce qui augmente l’allure « découpée » du dessin. Le paramétrage de l’option « edge-cut » permet de définir à partir de quelle longueur il est tolérable de couper. La valeur est comprise entre 0, ce qui donnerait dans ce cas le même résultat qu’avec Fruchterman-Reingold, et 1 (niveau qui maximisera le partitionnement visuel des données).

Notre exemple de réseau spatialisé avec Open Ord – edge cut: 0.20

Faire varier cette valeur donne évidemment des graphiques significativement différents.

Notre exemple de réseau spatialisé avec Open Ord – edge cut: 0.95

Ces visualisations ont pour intérêt une certaine clarté, et une bonne capacité à traiter des grandes bases de données. Elles sont toutefois à manier avec précaution.

L’accroissement des distances physiques entre les points donnent l’illusion que certains sont très éloignés, quand la distance qui les sépare dans le graphe est en réalité assez courte. Elles sont par conséquent à réserver à des cas où la séparation du réseau en différents clusters très distincts est véritablement nette et significative.

Privilégier l’ordonnancement des individus selon un critère d’intérêt

Plus qu’au tracé du réseau lui-même, on peut s’intéresser aux places relatives de chacun des nœuds selon un critère particulier. Peu m’importe qui échange avec qui, je m’intéresse ici à qui échange le plus avec les autres, ou qui est le plus central dans les échanges entre individus de mon réseau.

Ces options permettent des visualisations relativement spectaculaires – et c’est bien là leur valeur. En dehors de tout petits réseaux, le tracé du réseau devient illisible. L’information véhiculée par le graphique n’excède alors plus celle qu’aurait donné un tableau ordonnant les individus selon le critère d’intérêt.

  • Circular

Demande l’installation du plugin Circular Layout.

La logique globale de cet algorithme est plutôt simple: on trace un cercle, sur lequel on projette chacun des nœuds, en les ordonnant selon un critère défini par l’utilisateur: du plus haut au plus bas degré par exemple, ou du plus central au moins central…

Notre exemple de réseau spatialisé avec Circular, en choisissant d’ordonner les nœuds par degrés décroissant.

  • Radial Axis

Demande l’installation du plugin Circular Layout.

Là encore, un définit un critère d’intérêt (degré, centralité…), mais au lieu de représenter les nœuds sur le cercle, on les représente sur des axes qui « rayonnent » autour du cercle. Sur chaque axe, on regroupe les individus possédant au même niveau le critère d’intérêt (même degré, même centralité, etc.).

Notre exemple de réseau spatialisé avec Circular, en choisissant d’ordonner les nœuds par degrés décroissant.

Ces deux algorithmes sont d’une complexité limitée (0(n)) , et permettent donc le traitement de grandes bases de données.

VERS UNE ANALYSE MATHÉMATIQUE 

Les possibilités de visualisation d’un réseau sont extrêmement larges, et les graphiques obtenus fondamentalement différents. Il convient donc de se poser les bonnes questions quant à la conception d’un graphique, pour faciliter sa lecture et non la manipuler. Et il convient surtout de passer, une fois la visualisation faite, à une autre étape: celle de l’analyse à proprement parler, qu’aucun graphique ne peut remplacer. Ce sera bien sûr le thème du prochain billet de cette série.

Bibliographie

BASTIAN M., HEYMANN S., JACOMY M. (2009). « Gephi: an open source software for exploring and manipulating networks »International AAAI Conference on Weblogs and Social Media.

FRUCHTERMAN, Thomas M. J,  REINGOLD, Edward M. (1991), « Graph Drawing by Force-Directed Placement », Software – Practice & Experience, Wiley, 21 (11): 1129–1164

MARTIN S., BROWN W.M., KLAVANS R., BOYACK K., (2011)  « OpenOrd: An Open-Source Toolbox for Large Graph Layout« , SPIE Conference on Visualization and Data Analysis, 2011

HU Yifan, LEI Shi, « Visualizing Large Graphs« , (2015)  Wiley Interdisciplinary Reviews: Computational Statistics, Volume 7, pages 115-136.

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

Homemade manuscript OCR (1): OCRopy

Mis en avant

This post is the first of a small series centred on optical text recognition applied to manuscripts. There are many interesting research projects dealing with this question, but my purpose here is quite different: I wish to demonstrate how it is now possible for a single researcher to quickly get usable results with some of the open source tools that are out there, starting with OCRopy and CLSTM.

The field of optical character recognition (OCR) applied to manuscripts (handwritten text recognition) is rapidly evolving, especially now that artificial intelligence methods, such as neural networks, are getting more widespread. For the scholar of medieval manuscripts, it has interesting applications, and it can help in the constitution of textual databases or in the collation of witnesses.

Ocropy is a « collection of document analysis programs »1, that uses a Long Short Term Memory (LSTM) architecture for Recurrent Neural Networks2. It has been successfully applied to a variety of printed scripts, including old prints3. In particular, it is already being used to acquire the texts of incunabula. There are already some very good documentation on this subject, particularly Uwe Springmann’s slides from a workshop in Munich in 20154 and a paper about the Ocrocis environment5.

My interest in OCRopy started with the modest goal of digitising the text of XIXth century editions of Old French texts (namely, the collection of the Anciens poëtes de la France). With it, I got close to 1% error after some time, but soon, motivated by the successful use of OCRopy with incunabula and news I heard from a colleague6, I turned to trying it on manuscripts.

Setting up OCRopy

For the Ubuntu user (probably also for other Linux distributions), OCRopus is very easy to install (it may prove harder with Mac OS, though), following the 4 simple steps described on the repository. Once installed, the next step is getting the image files for the text you want to recognise, preferably in TIF format, and in good resolution (I used 600 DPI images, but the more common recommendation is 300 DPI). Some digital libraries offer such files with an open license, for instance the E-Codices platform7.

Capture d'écran de Scan Tailor. Ici, séparation d'une page en deux

Fig. 1: screenshot of Scan Tailor. Here, splitting the pages.

Depending on the case, you might have to preprocess the images, to rectify orientation, clean the image, crop it, etc. There are many tools to do that, for instance ScanTailor (fig. 1). Once your images are ready, and in a ./tif folder, you are good to go.

Preparing data: from layout analysis to ground truth production

Binarisation and layout analysis: column and line segmentation

Before anything, you will need (if you haven’t done it before) to binarise your images, and to try to detect columns and lines8. This first command,

$ ocropus-nlbin tif/* -o book

will binarise your images and place them in a book folder, and,

$ ocropus-gpageseg book/*.bin.png

will try to perform an identification of columns and lines. For both these commands, you might have to use the -n option, to deactivate error checking, and the skipping of pages or lines in your data. This part of the tools, layout analysis, is not based on training (yet) and can only be configured through a few options, not necessarily very documented. Some are related to scale, others to noise or baseline thresholds; I haven’t had much experience playing with those, so any feedback in comment to this post will be appreciated. Indeed, with manuscripts, this phase is often quite problematic, since lines or columns are not necessarily very regular…

On my experimentations on ms. Bodmer 68, using uniform and gaussian modes, I had the following error rates in column and line segmentation on fol. 134r, 136v and 142r :

fol. Column errors % Line errors %
Default
134r 25 60 6 7
136v 13 31 2 2
142r 22 52 1 1
Gaussian
134r 27 64 4 5
136v 16 38 4 5
142r 22 52 1 1

I do not count here errors related to lines amputated from beginning or end, and false positive (noise lines). In my experience, this is the part were Ocropy (as well as the other tools I tried) are least effective. In the end, I did column segmentation myself, with an image processing tool, and corrected line segmentation manually with Gimp. One can hope there will be improvements in this area in the near future9

Fig. 2a: a successfull segmentation

Fig. 2a: a successful segmentation

Fig. 2b: an extreme segmentation failure

Fig. 2b: an extreme segmentation failure

Ground truth

The first step in training a model to OCR a manuscript will then be to create some ground truth data, that is a correct (or, as correct as possible) transcription of a sample of the manuscript, on which to train the model, so it will learn to recognise the handwriting. This can be easily done with Ocropy, by creating an html file, with line images and text boxes:

$ ocropus-gtedit html -H 35 book/*/*.bin.png -o gt.html

and then,… well, then you have to transcribe a part of the text, to have something to train with (fig. 3).

Fig. 3: ground truth production

Fig. 3: ground truth production

The question is: how many lines do you need to get an effective model? Usually, with deep learning, the answer is: the more data, the better. For my part, I have had good results with as few as 400 lines and have not had the chance to train with more than 2000 yet. According to Uwe Springmann and David Kaumanns10, good results on incunabula were obtained with between 1000 and 5000 training lines, the latter for harder cases. In any case, I would advise you to start small (for instance, 400 lines), then train, use the model to annotate 400 more, correct, re-train, and so on until you get a satisfying model.

Training on a medieval manuscript: the ms. Bodmer 68 of the Chanson d’Otinel

Training

Once you have some ground truth data, you can begin training (that can take some time). First, you will have to extract ground truth from the html file used for transcription:

$ ocropus-gtedit extract gt.html

The lines you transcribed will go into the book folder, into the subfolders created for each page, and will be labelled <image-name>.gt.txt.

Be careful that all the line of the gt.html file containing text will be extracted (empty lines will be skipped), not only the one you edited. So, if you have some uncorrected lines with text, you have to pay attention not to include them in training or testing data.

So, in order to train, place 90% of your data in a train folder, and 10% in a test folder, to estimate the success of each model. It is then time to train. The last thing to do, if you have special characters, is to modify the file chars.py, located in your ocrolib installation (in Ubuntu, it will be in /usr/local/lib/python2.7/dist-packages/ocrolib/). The syntax is simple enough (fig. 4).

Fig. 4: the beginning of my chars.py

Fig. 4: the beginning of my chars.py

Once it is done, you can launch training with:

$ ocropus-rtrain -o myModel -d 1 train/*/*.bin.png

The -d 1 option is here to allow you to visualise the training steps (fig. 5). You can safely remove it if you want to gain time. In each training iteration, a line is read, and the results from the guess of the neural network (OUT) are compared to the ground truth (TRU), and aligned text (ALN).

54009 43.77 (616, 48) train/0017/010014.bin.png
TRU: u'D efo\ua75b\u017f hat\u0131ll\u0131e a une l\u0131ue g\u0363nt'
ALN: u'D efo~~ hat~ll~e a une l~ue g~nt'
OUT: u'D efo~\u203a hat\u2020ll\u2020e a une l\u2020ue gnt'

Fig. 5: Ocropy training

Fig. 5: Ocropy training

The visualisation shows you ground truth and training image, predicted and aligned results, probabilities for characters (green for space, blue for character with highest probability and yellow for absence of character) and the evolution of error11.

Every n iterations, the model is saved (default is 1000, but you can modify it with the -F option). Other useful options are:

-r LRATE, --lrate LRATE
LSTM learning rate, default: 0.0001
-S HIDDENSIZE, --hiddensize HIDDENSIZE
# LSTM state units, default: 100
-N NTRAIN, --ntrain NTRAIN
# lines to train before stopping, default: 1000000
--load LOAD start training with a previously trained model

The --load options allows you to retrain on an existing model (or, if you want, to split training in a few different sessions), and the -N to decide after how many iterations the training must end. But let’s have a look at the two other parameters, that will have an important effect on the training results (and training time); -r is the learning rate. In my experience, the default value is quite good, but I would be happy to have feedback on it; -S is the number of state units of the model. Increasing it to 200 or even 400 did wonder: my models learned faster and/or achieved lower error rates. On the other hand, training was more computing-intensive, and it considerably augmented the time/computing power needed for each iteration. I will develop this point in my next post, about CLSTM.

The other question is how long a training is needed to get good results. According to Uwe Springmann and David Kaumanns experiments on incunabula, they got best results with 30,000 to 200,000 iterations. Expressed as a number of epochs (an epoch is a number of iterations equal to the number of training lines, so with 400 training (ground truth) lines, it will be 400 iterations), they advise a number of 100 epochs12. As for me, best results were obtained for each model:

  • on modern print: 6 epochs (6287 training lines, 39 000 iterations, error at 1.75%, 200 state units);
  • on manuscript Bodmer 68: training 1, after 27 epochs (1722 training lines, 46 000 iterations, error at 17%, 100 state units); training 2, 31 epochs (1722 training lines, 54 000 iterations, error at 9.7%, 100 state units);
  • on manuscript Digby 23, with CLSTM: 74 epochs (403 training lines, 30 000 iterations, error at 9%, 400 state units).

For now, it seems that the raw number of iterations is a better indicator that the number of epochs, and 30 000 iterations is a good start, but it remains largely to be explored.

If you have such feedback to share, please do not hesitate to put it in a comment or send it to me. If I get enough of it, I will try to statistically estimate better configurations and make a post about it.

Evaluating the results

Once you have trained and produced a few models, the next step is to comparatively assess their performance and error rate. To do that, you can use the following bash code:
for i in *.pyrnn.gz; do
echo "$i" >> modeltest
ocropus-rpred -m $i test/*/*.bin.png
ocropus-errs test/*/*.gt.txt 2>>modeltest
done

This way, you will get a modeltest file, with the error rate of all models. For each model, you will have something like this:
bodmer-00054000.pyrnn.gz
errors 615
missing 0
total 6340
err 9.700 %
errnomiss 9.700 %

that is, the raw number of errors, of missing characters, total number of characters, and percentage of error.

On manuscript Bodmer 68, I started a first training, with 1722 lines of my transcription of the Chanson d’Otinel, and the error followed the evolution presented in fig. 6.

Fig. 6: first training on manuscript Bodmer 68

Fig. 6: first training on manuscript Bodmer 68

As you can see, the model soon arrived at around 20% of error; at iteration 46 000, it was at 16,32% of error, and never decreased afterwards.

I wasn’t quite satisfied with these results, that were not so usable. So, I went through a phase of checking the correctness of training data and its alignment with segmented lines, editing chars.py to include all the characters I needed (such as long ſ), etc. And I trained again: you can see how effective the increase of quality of input data was on this new training (fig. 7).

Fig. 7: second training on manuscript Bodmer 68

Fig. 7: second training on manuscript Bodmer 68

This time, the model got to 9.7% error, at iteration 54 000, and error never decreased afterwards. You can also observe some punctual spikes in error at iteration 23 000 and 57 000.

To understand the source of the errors, and eventually do some post-treatment to lower error rate, you can have a look at the confusions of characters, using the command:

$ ocropus-econf test/*/*.gt.txt

This will give you the most frequent confusions, in a form similar to:

32 _
29 _
21 _
13 _ ı
10 _
8 z _
7 n m
6 _
6 _ t
6 _ u

As you can see, in my case, most errors were related to whitespace, or confusions between whitespace and characters or abbreviations, or, also, in the succession of strokes constituting n, m or ı. If you want to see as well if the errors are dependant of a certain context, you can try the -C option:

$ ocropus-econf -C2 test/*/*.gt.txt

In my case, the most frequent confusions with context were more explicit:

5 Q _nt Q ͣnt
4 ml_t ml̃t
2 t_re t͛re
2 aı_n aı́n
1 cuıne cum_e
1 e ot e_ot
1 m_nt munt
1 tr_uſ trıuſ

As you can see, most errors were related to abbreviations (superscript a, tildes, etc.) or succession of minim strokes (ı, n, m, u and their various combinations) that are also hard for humans when they cannot perceive the full word.

On the other hand, the results obtained were quite usable, now. To give you an idea, here is a sample of the recognition, compared with the binarised folio of the manuscript (fig. 8). I underline errors, and indicate missing characters with ø.

v erent leſ noz uenør tut eſfreez
p aſſent auant ſıſ ont returnez
p ar gͣnt eſfoeꝛ ont paıenſ reculez
Q uatte aıpenz δe terre meſurez
D eſ abatuz e δeſaceruelez
e ſt tut lı champ pleıø e ẽꝯbrez
L ez vn pareı ſa reſteıt coꝛſabrez
Ø enſeınıe eſcrıe paıen a meı eſtez
L eſcu enbrace verſ leſ noø eſt alez
p ar gͣnt u͛tu eſt aſ eſtrøuſ fermez
Ø a euſt leſ noz Gtaanẽt δeſturbez
Q nt en leſcu la feru amırez [missing accent]
p ar teu u͛tu ken ſun frũt lar entez
Deſuz le halme a lun δeſ oılz quaſøeø
L ı paıen eſt δel colp eſpontez
N en a ſucurſ tut eſt abanδunez
J gnelemẽt le laıſıſt amørez
ø reıſ bonſ uaſſalſ a lenfeſ apelez
c o eſt Galδı́n e fauchet lı haſtez
e δaıgremũt balδeδeı́n lafıez .

Fig. 8: ms. Bodmer 68, col. 221b, binarised.

Fig. 8: ms. Bodmer 68, col. 221b, binarised.

In some cases, it might be useful to do some automatic post-treatment, to correct the most frequent errors, for instance with a database of known/existing words. In any case, once you are satisfied with your model, it is time to OCR the rest of the manuscript.

Acquiring the rest of the text and extracting it

To apply recognition to the full document, you can do:

$ ocropus-rpred -m myModel.pyrnn.gz book/*/*.bin.png

This will predict the text of the full book folder. You can then extract it in several formats. You can get it as HOCR, using:

$ ocropus-hocr book/*.bin.png

The HOCR format is interesting, as it gives you, for each text line, its alignment with the original document (that you can transform, with XSLT, to TEI facsimile elements, if you so wish):

<div class='ocr_page' title='image book2/0001.bin.png; bbox 0 0 2140 2836'>
<span class='ocr_line' title='bbox 375 173 1813 296'>Q uatre cenz mılıe cheualerſ puıſ aueır.</span><br />
<span class='ocr_line' title='bbox 374 264 1492 354'>p uıſ men cũbatre a carll̃ ⁊ a franceıſ.</span><br />
<span class='ocr_line' title='bbox 322 342 1382 437'>G ueneſ reſpunt ne uuſ a ceſte feız.</span><br />
<span class='ocr_line' title='bbox 361 429 1586 520'>D e uoz paıenſ mult grant ꝑte ı au͛reız.</span><b

The only problem with this format is with extracting manually corrected lines, that I fear may be omitted in the export procedure. You can also extract it with:

$ ocropus-gtedit text book/*/*.bin.png

This will give you a correct.txt file, with the text, and a separate reference.html file, with the indexed line images.

If you want to correct the results from the prediction, before extracting it, you can do instead:

$ ocropus-gtedit html -H30 book/*/*.bin.png

It will give you a correction.html file, that you can again edit and correct. Here, we have to be cautious, because, when extracting text, the predicted (.txt) lines are used by default, instead of the ground truth ones (.gt.txt). So, once we have corrected, we will need to remove all existing text files, extract, and rename the files from .gt.txt to .txt (yes, it is a bit of a bother):

rm book/*/*.txt
ocropus-gtedit extract correction.html
rename "s/.gt.txt/.txt/g" book/*/*.gt.txt
ocropus-gtedit text book/*/*.bin.png
ocropus-hocr book/*.bin.png

And now you have your text ! You can convert it to TEI or some other format, and start editing.

From one manuscript to the next: trying to reuse a model on another manuscript

So, from the beginning of this post, I have talked of training a model for a specific manuscript. One question remains: can this model be applied to another similar manuscript, or retrained on an other manuscript ?

I tried to apply the model created for Bodmer 68 (last third of the XIIIth century, Gothic Textualis libraria, anglo-norman) to another, quite different, manuscript I wanted to OCR, the Digby 23 (first half of the XIIth century, Praegothica, anglo-norman as well). I will talk more about the model developed for this manuscript with CLSTM in my next post, but the outline is that, without retraining, I had an error of 33% (instead of 9.7%). After a few epochs of retraining (with the --load option), it went down to 15%, but never below. In the same time, parts of the model started “exploding”, and lowering learning rate13 did not solve the problem:

# oops, got FloatingPointError overflow encountered in exp
 Traceback (most recent call last):
 File "/usr/local/bin/ocropus-rtrain", line 286, in
 pcs = network.trainSequence(line,cs,update=do_update,key=fname)
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 890, in trainSequence
 self.outputs = array(self.lstm.forward(xs))
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 605, in forward
 xs = net.forward(xs)
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 661, in forward
 outputs = [net.forward(xs) for net in self.nets]
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 559, in forward
 self.WIP,self.WFP,self.WOP)
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 428, in forward_py
 go[t] = ffunc(gox[t])
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 376, in ffunc
 return 1.0/(1.0+exp(-x))

It soon turned out a lot more effective to retrain a new model from scratch. Actually, every time, in my experience, retraining an existing model, be it for print or manuscript, though it might be faster, was less effective in the end.

That’s it for now ! Do not hesitate to leave observations, remarks or feedback in the comments.

Cite this post as: Jean-Baptiste Camps, « Homemade manuscript OCR (1): OCRopy », Sacré Gr@@l, 6 février 2017, http://graal.hypotheses.org/786 (consulté le 29 mars 2017).

  1. Thomas M. Breuel, Ocropy: Python-based tools for document analysis and OCR, 2014, https://github.com/tmbdev/ocropy. []
  2. Thomas M. Breuel, Adnan Ul-Hasan, Mayce Ali Al-Azawi and Faisal Shafait, « High-Performance OCR for Printed English and Fraktur Using LSTM Networks », 2013 12th International Conference on Document Analysis and Recognition, 2013, DOI: 10.1109/icdar.2013.140, URL: http://staffhome.ecm.uwa.edu.au/%7E00082689/papers/Breuel-LSTM-OCR-ICDAR13.pdf. []
  3. You can find a list of publications related to Ocropy on the project wiki, http://github.com/tmbdev/ocropy/wiki/Publications. For an example of application to modern print, you can see the blogs posts by Dan Vanderkam, « Extracting text from an image using Ocropus », danvk.org, http://www.danvk.org/2015/01/09/extracting-text-from-an-image-using-ocropus.html ; Id, « Training an Ocropus OCR model », danvk.org, http://www.danvk.org/2015/01/09/extracting-text-from-an-image-using-ocropus.html. []
  4. OCR und Nachkorrektur alter Drucke für die Geisteswissenschaften / OCR and postcorrection of early printings for digital humanities, Centrum für Informations- und Sprachverarbeitung (CIS) Ludwig-Maximilians-Universität München, 2015, http://www.cis.uni-muenchen.de/ocrworkshop/program.html []
  5. Uwe Springmann and David Kaumanns, Ocrocis: a high accuracy OCR method to convert early printings into digital text, 2015, http://cistern.cis.lmu.de/ocrocis/tutorial.pdf. []
  6. Thanks to Thibault Clérice for the ideas and discussions, and for initially pointing me to the documentation for using OCRopy. []
  7. E-Codices: Virtual Manuscript Library of Switzerland, http://www.e-codices.ch/. []
  8. I used the same folder architecture as the one in the documentation by U. Springmann, of the cited workshop, OCR and postcorrection… []
  9. From what I understand from the Ocropy Github page, the original developer of Ocropy, T. Breuel, is planning on working on deep learning for layout analysis. []
  10. U Springmann and D. Kaumanns, Ocrocis…, p. 13 []
  11. For more information, have again a look at U. Springmann’s slides. []
  12. U. Springmann and D. Kaumanns, Ocrocis…, p. 13 []
  13. As advised in a Github issue of Ocropy, http://github.com/tmbdev/ocropy/issues/5 []

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 «Technologies numériques appliquées à l'histoire» à l'École nationale des chartes. [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

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 «Technologies numériques appliquées à l'histoire» à l'École nationale des chartes. [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

Python’s Flying Circus épisode 2: vous aimez les Perl, mais aimez vous les Ruby ?

Après notre comparatif rapide entre Python et Perl, il convenait tout de même de présenter un autre langage de programmation concurrent: Ruby. Comme Python et Perl, Ruby est un langage libre, de très haut niveau, multi-plateforme, générique, multi-paradigme, et doté d’un typage dynamique fort.

Dans l’esprit, Ruby est cependant plus proche de Perl. Son créateur Yukihiro Matsumoto (dit « Matz ») s’est en effet inspiré de certains principes de Perl pour concevoir son langage. En particulier, il s’est opposé au Zen de Python1 selon lequel  « il doit y avoir une – et de préférence seulement une – manière de faire ce que l’on veut ». Dans une interview donnée en 20032, Matsumoto déclarait ainsi :

Ruby a hérité de la philosophie de Perl le fait de laisser plus d’une manière de faire la même chose. Je tiens cette philosophie de Larry Wall, qui est véritablement mon héros. Je veux libérer les utilisateurs de Ruby. Je veux leur donner la liberté de choisir .

Dans l’usage, Ruby est comme Perl, moins diffusé que Python. Il est très utilisé dans la programmation web grâce au succès de Ruby on Rails. Mais il ne faut pas oublier pour autant que ses compétences vont bien au-delà, et qu’il peut donc aussi nous être très utile. Il est d’ailleurs assez riche par défaut – de nombreuses fonctions existant par défaut sur Ruby devant être importée depuis des modules spécifiques dans Python. Après le passage de la version 1.9 à une version stable 2.0, qui doit avoir lieu sous peu, nous nous attacherons donc à vous montrer quelques unes des applications que l’on peut dessiner pour nos domaines avec ce langage.

  1. Lisible par exemple ici. []
  2. VENNERS Bill, « The Philosophy of Ruby – A Conversation with Yukihiro Matsumoto », 29 septembre 2003 [En ligne]. URL: http://www.artima.com/intv/rubyP.html []

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

Python’s Flying Circus épisode 1: Python vs. Perl

Jusqu’ici, le langage que nous avons utilisé a toujours été Perl. Mais nous ne pouvions pas, surtout vu l’intitulé de notre blog, ignorer trop longtemps un des langages « rivaux » de celui-ci: Python. Notons que le rapprochement entre le nom de ce langage et une célèbre troupe de comédiens britanniques ne vient pas que de mon appétence visiblement pas assez modérée pour les jeux de mots ; c’est bien en honneur des Monty Python, dont il était un grand admirateur, que Guido van Rossum a nommé en 1989 son nouveau langage de programmation de la sorte.

Le premier billet à propos de Python reprendra un sujet déjà largement débattu : Perl ou Python ?

Les points communs

Avant d’examiner les raisons qui feraient choisir un ou autre langage, commençons d’abord par comprendre pourquoi on peut hésiter entre ces deux langages.

Perl et Python ont tous les deux des usages variés

Même s’ils ont chacun des domaines de prédilection, Python et Perl sont tous deux des langages génériques, utilisables dans des contextes fort nombreux, en particulier grâce à  l’utilisation de bibliothèques spécialisées.

Perl et Python sont tous les deux multi-plateformes

Vous êtes un geek assumé travaillant chez vous sur une distribution obscure de Linux, mais à votre université, on s’acharne à vouloir accroître les profits de Microsoft ? Vous avez toujours votre brave vieux PC sous Windows XP, mais votre laboratoire s’est équipé en iMac 27 pouces Quad-Core flambant neufs (je m’adresse là à d’éventuels visiteurs qui ne seraient pas dans la recherche publique française, bien entendu) ? N’ayez crainte! Aussi bien Perl que Python peuvent être utilisés quel que soit le système d’exploitation. C’est un magnifique avantage pour les situations plus ou moins crédibles que nous venons d’évoquer, et pour beaucoup d’autres d’ailleurs. Mais ce n’est donc pas un facteur de choix entre ces deux langages.

Perl 6 et Python 3 ne sont pas rétro-compatibles

Quand vous apprenez l’un ou l’autre de ces langages, vous apprenez un langage qui n’est pas compatible (ou du moins, pas fait pour être compatible) avec ses versions antérieures. Ce point peut-être gênant si vous cherchez à intégrer votre travail à un projet réalisé avec une version antérieure de ces langages. Des solutions ont été proposées de chaque côté. Du côté de Perl, un mode de compatibilité a cependant mis en place pour aider la portabilité entre Perl 5 et Perl 6. Du côté de Python, par contre, on a choisi de continuer à améliorer Python 2 au fur et à mesure des actualisations faites pour Python 3 – le but étant que les utilisateurs de Python ne soient pas obligés d’apprendre la nouvelle version pour bénéficier de ses améliorations. Mais si vous êtes un nouvel utilisateur de Python et que vous voulez produire un travail compatible avec Python 2, il vous faudra apprendre et Python 2 et Python 3.

Perl et Python utilisent un typage dynamique

La chose peut paraître anecdotique – mais elle me permet de revenir sur un des points du « hello world! ».  Comme Jean-Baptiste le faisait remarquer, C++ demande à l’utilisateur de déclarer le type de la variable qu’il crée: s’agit-il d’un nombre entier, d’un nombre réel (« à virgule flottante », si on aime cet anglicisme), d’une chaîne de caractères etc.  ? On parle pour les langages agissant de la sorte de « typage statique ». A l’opposé, pas plus Perl que Python ne vous demanderont cette information.  Ils utilisent un « typage dynamique ». Jean-Baptiste ayant déjà illustré ce point sous Perl, je me charge uniquement d’expliciter ce phénomène sous Python. Plutôt que de demander la nature d’une variable (son « type »), Python va regarder ses attributs pour déduire de lui-même le type. On parle de « duck typing »: si je vois un oiseau qui nage dans une mare, doté  d’un joli col vert et de palmes jaunes, qui se manifeste par des « coin-coin » aussi élégants que sonores, j’appelle cet oiseau « canard »1. Python fait de même: si je lui crée trois variables de types différents, il observe leurs caractéristiques et infère leur type.

Ainsi, Python reconnaît-il sans aide que la constante de Planck est un nombre réel (float), que 42 est un entier (int – pour « integer ») et que « coin coin » est une chaîne de caractères (str, pour « string »).

Les différences

Python: un langage plus rapide ?

Pour la plupart des tâches testées, l’exécution d’un code Python se fait plus rapidement que celle d’un code Perl2. Avouons-le, ce dernier point n’est pas crucial dans la plupart des applications en littérature et en sciences humaines – mais selon vos utilisations, il peut tout de même avoir de l’importance.

Python: un langage plus simple ?

De l’avis de beaucoup, et en particulier depuis la version 3 de Python, ce langage est globalement plus simple à apprendre. Un de ses avantages est ainsi d’avoir été conçu pour que chaque tâche ne puisse être exécutée que si l’on écrit un ensemble précis et unique de lignes de codes. En résulte un code  lisible et facile à maîtriser. A l’opposé, en Perl, il peut exister beaucoup de solutions différentes pour réaliser la même opération, ce qui rend difficile, même pour un utilisateur avancé, de lire le code d’un autre programmeur. C’est ce point qui a probablement le plus aidé à la diffusion de Python, plus répandu que Perl aujourd’hui.

Perl vs. Python: littéraire contre scientifique ?

A ce stade, avouons-le, on ne voit pas bien pourquoi certains pourraient préférer Perl à Python. Pourtant, Perl a lui aussi des avantages clefs, en particulier pour les domaines qui nous intéressent. Perl a ainsi été conçu pour extraire au mieux des informations d’un texte, et de générer des rapports à partir de ses analyses. C’est donc naturellement que Perl est devenu le langage de prédilection des linguistes – et qu’il peut être celui des philologues, voire des historiens, sociologues ou juristes voulant analyser des corpus textuels importants. Python est quant à lui plus à l’aise avec les tâches plus calculatoires, ou mathématiques en général, en particulier avec l’aides de modules comme  NumPy, SciPy, ou Matplotlib. Il est grâce à cela populaire dans des domaines comme la bio-informatique, la finance, et généralement pour l’analyse de données scientifiques. Bien sûr, Python ou Perl peuvent être utilisés sur les terrains de prédilection de l’autre  avec une certaine efficacité – mais nous y reviendrons dans de prochains billets.

Au final, le choix entre Python et Perl est délicat, et dépend de vos centres d’intérêts précis. En dehors de l’analyse textuelle, il  paraît clair qu’un expert en humanités devrait préférer débuter Python, qui reste plus facile d’accès que Perl. Pour l’analyse textuelle, Perl est probablement le bon choix – mais nous mettrons régulièrement ce choix à l’épreuve, en comparant l’efficacité de Perl et Python sur différentes tâches d’analyse de corpus au cours des prochains billets.

  1. C’est bien là l’origine de ce terme, rarement traduit en français – « duck typing » préservant une impression de sérieux, contrairement à « typage canard ». On trouve trace de cette expression et de ce raisonnement pour la première fois en 2000 dans la bouche d’Alex Martelli sur ce newsgroup. []
  2. Les sources de ces tests sont trop nombreuses à citer. Juste en clin d’oeil à notre premier billet, on pourra par exemple consulter cette évaluation sur le blog d’Ivan Zahariev []

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

Identification automatique des noms propres

Voici un des premiers résultats de mes expérimentations avec Perl, à savoir un script qui permet, avec une marge d’erreur relativement faible (env. 1% dans mon corpus test1) d’identifier automatiquement les noms propres.

L’idée originelle est d’utiliser l’encodage « naturel» des textes, c’est-à-dire l’ensemble des  symboles et diacritiques traditionnels (ponctuations, accents, majuscules, etc.). En l’occurrence, pour les noms propres, cet encodage consiste en l’utilisation d’une majuscule au début du mot. Le problème principal réside alors dans la présence de majuscules également en tête de phrase (heureusement que nous ne prenons pas comme exemple un texte allemand contemporain !). Dans un premier temps, après avoir nettoyé tout ce qui ne nous est pas nécessaire, le script constitue donc deux listes. La première contient tout les mots commençant par une majuscule et ne se trouvant pas en début de phrase et qui sont donc nécessairement des noms propres ; la seconde, tous les mots se trouvant en début de phrase, qui peuvent être des noms propres, mais pas forcément.

#on récupère tout les mots qui commencent par une majuscule, sans être précédé par un point ou un guillemet.
@NomP = $texte =~ /[^.!?«»]\s+(\b[A-Z]\w+)/g;
@NomP = grep {/\w+/} @maj;
#Puis on récupère tout ce qui correspond à un point ou un guillemet, un espace, et une majuscule.
@debutPhrase = $texte =~ /[.!?«»]\s+([A-Z]\w+)/g;
@debutPhrase = grep {/[^\s.!?«»]/} @debutPhrase;

Maintenant que nous avons ces deux listes, nous avons d’ores et déjà récupéré une bonne partie des noms propres, mais il est encore possible d’améliorer le script et de faire diminuer le nombre de mots incertains (ceux de la liste @debutPhrase). Pour ce faire, on procède à une comparaison des deux listes (en incluant la variation du système bicasuel de l’occitan médiéval). Si le mot « indécis » correspond à un de ceux de la liste de noms propres, il est transféré dans cette liste2 :

Comparaison entre les deux listes (en incluant les variations graphiques)

De 57 mots dans la liste @debutPhrase, on passe à 40, dont seulement 6 vrais noms propres, chiffre qui est à opposer aux  460 noms propres trouvés, soit 98,71% de réussite, ce qui n’est pas si mal que ça (je suis bien sûr preneur de toute suggestion d’amélioration).

  1. Ce corpus test se compose d’une quarantaine de vidas, courts textes biographiques occitans du XIIIe siècle, racontant la vie d’un troubadour. []
  2. Autrement dit, si notre mot qui porte une majuscule et se trouve en début de phrase apparaît ailleurs dans le texte, portant une majuscule, mais sans être en début de phrase, il s’agira d’un nom propre. Dans le cas contraire, la situation reste indécise : il peut soit s’agir d’un nom commun, soit bel et bien d’un nom propre n’apparaissant qu’une seule et unique fois dans le corpus []

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 «Technologies numériques appliquées à l'histoire» à l'École nationale des chartes. [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

Réaliser un tableau d’occurrences lexicales avec Perl

Voici un exemple des traitements que l’on peut réaliser (relativement) aisément avec Perl. Il s’agit ici d’un petit script permettant, à partir d’un fichier en entrée contenant plusieurs textes séparés par le symbole §, de créer un tableau au format csv contenant, pour chaque texte, le nombre d’occurrences de chaque forme.

Pour commencer, il nous faut nettoyer en supprimant les majuscules et la ponctuation du texte, contenu dans la variable $texte, puis créer une liste d’occurrences des formes du texte complet, sous la forme d’une table de hachage, en utilisant une sous-routine compteur dont il sera question plus loin :

$texte =~ s/\_|\t|\.|\:|\,|\;|\«|\»|\)|\(|\'|\~|’|…|\?|\n/ /g;
%occurrencesTexteComplet = &compteur($texte);

Une fois cette tâche effectuée, nous allons maintenant séparer le texte complet, en une série de sous-textes en utilisant le symbole § :
@sous_textes = split(/§/, $texte);

Nous pouvons à présent comparer les listes d’occurrences de chaque sous-texte avec celui du texte complet :

Comparaison des deux tableaux d'occurrences

Et voilà, il ne nous reste plus qu’à générer le fichier de sortie, au format csv, que l’on pourra par la suite ouvrir avec Calc (ou Excel), importer dans R, etc.

Mise en forme du csv

La sous-routine compteur

Il s’agit d’une sous-routine que Perl rend assez simple, car c’est le type de traitement pour lequel il a été conçu. Elle compte un à un les mots d’un texte, et, à chaque fois qu’un mot réapparaît, elle ajoute 1 au compteur :

La sous-routine compteur

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 «Technologies numériques appliquées à l'histoire» à l'École nationale des chartes. [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

Première quête: à la recherche d’Excalibur

« What is your quest ? » Bien entendu, « to seek the Holy Grail »  (ou « Holy Gr@il » dans notre cas…). Mais pour s’aventurer dans une quête aussi périlleuse, on ne saurait s’aventurer sans armes. Et parmi les armes, il faut choisir: impossible d’apporter tous les types d’armes sur son dos, c’est bien trop lourd.

C’est à faire ce choix difficile parmi le vaste arsenal des armes informatiques disponibles que nous allons nous attacher dans les premiers moments de ce blog. Aujourd’hui, il est quasiment impossible de maîtriser le fonctionnement de tous ces outils disponibles, même pour un professionnel de l’informatique. Et dans la foule des langages de programmation et des logiciels disponibles, il est souvent difficile de se repérer : de quoi aurais-je besoin ? qu’est-ce qui sera le plus maniable ? le plus puissant ? le plus simple d’usage ? Au gré de nos propres expérimentations, nous vous livrerons donc des éléments vous permettant de discerner les outils informatiques qui seraient utiles à vos recherches.

Retour sur notre « hello world »: langage de haut niveau et langage de bas niveau

Dans notre premier billet, Jean-Baptiste nous montrait la différence de codage d’une instruction très simple – saluer nos visiteurs autant fois qu’ils le désirent – entre C++ et Perl. Plus généralement, cette différence est celle que l’on trouve entre des langages de plus ou moins « haut niveau ».

Qu’on ne se méprenne pas sur cette appellation: il ne s’agit pas de distinguer une élite de langages de programmation d’une sorte de plèbe informatique. Un langage dit de bas niveau est un langage qui se rapproche de celui qu’utilise la machine, le processeur. Le plus  bas niveau serait ainsi de coder directement ses instructions en binaire – ce qu’on n’a plus à faire depuis des décennies, pour notre plus grand bonheur. D’un peu plus haut niveau, on trouvera la programmation en hexadécimal, le langage assembleur, puis le C etc. Et assez haut, on trouvera par exemple Perl, ou son rival Python.

Les langages de bas niveau sont cruciaux dans nombre de domaines de l’informatique. Ils permettent d’exploiter toutes les capacités de la machine employée, en étant au plus proche se son fonctionnement. Ils sont également d’une très grande rapidité d’exécution. Cependant, dans le cas des recherches en humanités qui nous occupent ici, ces langages sont assez significativement dominés par des langages de haut niveau.

Comme le premier post le montrait, il faut beaucoup moins de lignes de codes pour écrire un programme avec un langage de plus haut niveau (C++ n’étant pas à proprement parler un langage de bas niveau, mais étant toutefois de moins haut niveau d’abstraction que Perl par exemple). Et qui dit moins de lignes de codes dit moins de temps passé à coder, moins de fautes de frappe ou d’étourderie commises en écrivant le programme – et donc moins de temps passé à s’énerver en cherchant les bogues… En bref, un langage comme Perl (mais il n’y a pas que lui) est plus maniable, plus rapide à coder, et d’une certaine manière plus « magique »: avec très peu de lignes, il fait faire une masse prodigieuse d’opérations à notre machine. Voilà peut-être notre Excalibur…

Pour ces raisons, nous ne présenterons que des langages de programmation de  (très) haut niveau au cours des prochains posts.

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

Un premier pas avec Perl

Dans la perspective de choisir un langage de programmation pour réaliser des programmes de traitement textuel, je me suis décidé, pour commencer, à comparer deux langages, un de relativement bas niveau (en l’occurence C++, mais j’aurais également pu choisir Java) et un de plus haut niveau (en l’occurence Perl, mais j’aurais pu aussi choisir Python).

 

Le test consiste à réaliser, sans connaissance a priori de ces deux langages, en un quart d’heure ou une demie heure, un programme très simple, version un tout petit peu plus évoluée d’un hello world ! qui demande à l’utilisateur combien de fois il veut qu’on lui dise « Bonjour ! » et effectuant cette opération1 :

À gauche, le code C++, à droite le code Perl

Première constatation, Perl paraît à la fois plus concis et un petit peu moins précis (moins propre ?) puisqu’on ne déclare pas la nature de la variable. En dehors de cela, rien de trépidant. Ce qui est plus intéressant, en revanche, c’est que l’on dispose d’au moins une autre solution très simple en Perl (qui, admettons-le, a été créé pour faire des traitements textuels, ce qui n’est pas le cas de C++) :

Alternative en Perl

Et voilà ! En un mirobolant total de 3 lignes de code, c’est fait. Voilà qui aurait tendance à prêcher pour Perl, même si ça n’a pas la rigueur et la beauté abstraite du C++.

  1. Je précise que je ne suis pas informaticien de formation, et ai donc sur le sujet le regard, peut-être un peu naïf, du néophyte. Que les programmeurs veuillent bien m’en excuser ! []

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 «Technologies numériques appliquées à l'histoire» à l'École nationale des chartes. [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn