Didacticiel :
Écrire son parseur à la main — chroniques d'une mauvaise bonne idée

Nobody expect to be able to parse any old C.S.V.

Nobody expect to be able to parse any (old) C.S.V. Crédit: Paul Downey

Partie 1

Où l'on prend conscience de l'existence de standards, et de leur nécessité.

Tout petit programme s'éveillant au monde se trouvera un jour face à ses obligations : s’interfacer avec ce dernier. La lumière extérieure devra alors pénétrer son petit antre, apportant malicieusement l'information de mille autres petits programmes, si hétéroclites et désordonnés que nul ne sais vraiment qui fait quoi. Tous forment ainsi un monde d'information partiellement structurée, riche de diversité et de liberté.

Un jour fût définit le mot «bordel» comme «le meilleur adjectif décrivant cet ensemble».

Le nombre de standards est beaucoup trop grand.

Le nombre de standards est beaucoup trop grand.

Et, afin de permettre à ce bordel de continuer à exister, furent définies des règles précises, des conventions, des standards permettant à tout un chacun d'enrichir le chaos ambiant dans un respect mutuel, ou le chaos mutuel dans un respect ambiant selon les auteurs.

Et ces normes, il y en a de gargantuesques pelletées, ne serait-ce que pour l'organisation des données dans les fichiers.

Normal : on a plein de choses différentes à raconter, et d'ailleurs, ce n'est pas du tout le sujet de cet article.

 

 

 


 

Partie 2

Où l'on prend conscience des bases d'un standard.

 

Parmi les standards, l'un d'entre eux est prince en de nombreux pays : le CSV, pour Comma Separated Value, ou plus généralement DSV, pour Delimiter-Separated Value, où les données sont organisées en table et dont le standard prévoit moult richesses. La principale caractéristique de ce format est de séparer des champs de données (fields) définis (et finis) par un délimiteur (la virgule dans le cas du CSV), et de regrouper les informations liées sur une seule entrée (record), en général une ligne.

Le format CSV est utilisable pour tout type de données : taux d'expression des gènes d'une PCR, résultats du cross des enfants de ce week-end, interfaçage avec une base de données, stockage des info utilisateurs d'un système, mesures d'altitude d'un marteau et d'une plume chutant de concert et des mains d'un cosmonaute,…

Ce format est aussi utilisé (dans une certaine mesure) par les tableurs pour conserver les données dans des fichiers.

Voici des données formatées en un CSV typique :

Nous observons ici distinctement cinq particularités :

  • la première ligne (et première entrée) définit 3 champs, qui devraient être compris comme les noms des colonnes, autrement dit le header.
  • la deuxième ligne est une entrée : elle définit un gène, nommé lacA, ayant un ratio d'expression de 0.23 et un temps d'incorporation désigné comme «long».
  • La troisième ligne est une troisième entrée définissant un autre gène, lacZ, avec un ratio d'expression non communiqué et un temps d'incorporation marqué comme «long».
  • La quatrième ligne est une quatrième entrée définissant Pépin, avec un ratio d'expression de 0.01, ce qui est bien mais pas top, et un temps d'incorporation désigné comme «bref».
  • On observe que les entrées partagent éventuellement des données identiques, par exemple lacA et lacZ ont toutes deux le temps d'incorporation long, alors que Pépin le bref.

À toutes ces remarques, il est important d'ajouter les suivantes:

  • les entrées sont indépendantes
  • les entrées doivent fournir des valeurs pour tous les champs (même si cette valeur est une chaîne vide)
  • une entrée ne doit pas fournir de valeur pour un champ qui n'est point dans le header (Comme spécifié dans la RFC 4180 : «Each line should contain the same number of fields throughout the file» Cette RFC est néanmoins à considérer avec du recul : elle ne concerne que le CSV, et n'existe que pour pallier l'absence de spécification formelle.)
  • le caractère délimiteur, la virgule, pourrait être n'importe quel caractère ou chaîne de caractère pourvu qu'il reste constant dans tout le fichier.

Ce format, simple et épuré, est très en vogue dans de nombreux milieux (et largement usité en de nombreux extrêmes).

 

 

 

 


 

Partie 3

Où l'on apprend que nombreux sont les rigolos qui jouent avec le feu, et que moins nombreux (mais plus sagaces, comme Sam) sont ceux qui jouent également avec des gants ignifugés.

 

Et comment fait-on en Python, par exemple, pour s'interfacer avec un tel format ?

Voici le code habituellement produit par les programmeurs, d'après mon petit doigt droit, toujours à la pointe de l'information pifométrique :

Simple, beau, efficace. (nous verrons plus tard que les véritables termes sont simpliste, bête, effiloché)

 

Pourtant, il existe un ensemble de personnes, qui, lorsqu'elles ont besoin de s'interfacer avec ce format d'une simplicité monstrueuse, se lancent dans la doc plutôt que le code, et dans le standard plutôt que le pifomètre :

C'est s'embêter pour pas grand chose, n'est-ce pas ? En plus, faut lire la doc.

Franchement, quelle différence ? C'est une lib en plus à importer, à comprendre, et à débugger, et si c'est juste pour pas avoir à faire un appel à join ou split, ce n'est franchement pas un bon deal.

Franchement, arrêtons hic et nunc cet article, personne ne voit où l'auteur veut aller.

 

 

 


 

Partie 4

Où l'on apprend que l'usage des gants ignifugés ne relève pas seulement de la paranoïa, ni du gras pédantisme d'un étudiant en fin de vie, étudiante elle aussi.

 

Ci-après est montré un petit fichier CSV fort rigolo. Question : combien y a-t-il d'entrées, et combien y a-t-il de champs pour chacune ?

Petite expérience simple et désuète : lancer son parseur maison (fait à la mimine) sur ce fichier et afficher les entrées détectées, puis utiliser la lib standard pour faire le même job.

Pour les courageux qui n'ont pas envie d'écrire tout ça eux-même, il y a un dépôt git qui héberge une automatisation de l'expérience.

 

Attention, spoiler !

 

Le fichier CSV balancé un peu plus haut contient deux lignes, dont la première est particulièrement tordue, et la seconde tout à fait réaliste. Voici les lignes détectées par le parseur maison, qui ne résiste pas à la tentation de nous trouver moult information dont nous nous serions bien passé :

Cela fait donc 4 lignes de 3 champs, sauf la dernière qui en contient 4.

Alors que le parseur standard détecte bien les 2 lignes, incluant les deux pièges dont il s'est bien protégé :

mon collègue parsait le CSV avec un line.split. Parsait.

mon collègue analysait le CSV avec un line.split. Analysait.

Ici, les pièges reposent essentiellement sur le caractère de champ de texte libre, le double guillemet (mais pas le guillemet simple), qui permet d'entrer n'importe quel caractère sans influer sur la structure de données. Autrement dit, en mettant des caractères de séparation entre double guillemets, celui-ci sera interprété comme une chaîne de caractères et non comme une séparation de champs.

Le parseur maison n'implémente aucune gestion de ce champ de texte libre, et (phrase d'accroche pour la prochaine partie : ) il n'existe aucun moyen de le faire simplement.

 

 

 

 


 

Partie 5

Où l'auteur, passablement aigris par les énergumènes délaissant les gants ignifugés pour l’insouciance de la jeunesse, lance un dernier cri dans la nuit noire et obscure, avant de se cogner contre un mur (celui-là même qui clôt l'article et laisse la place aux commentaires).

 

Les résultats sont formels : le parseur standard est bien plus robuste aux méchancetés du monde extérieur que le parseur maison.

Son secret : il utilise un automate à état fini pour parser les données, et cela est nécessaire pour gérer le cas du double guillemet pour les champs de texte libre. Dans le code C derrière CPython, implémentant le parseur en 1600 lignes, on trouve la gestion de transition des états sous la forme d'un gros switch, et leurs définitions comme une énumération.

Je ne parse jamais un fichier CSV moi-même… Mais quand je le fais, j'utilise un automate à état fini.

Je ne parse jamais un fichier CSV moi-même… Mais quand je le fais, j'utilise un automate à état fini.

Enfin, la dernière update de ce code, à l'écriture de cet article, date du jour même. Ce module, bien que parfaitement fonctionnel, continue à recevoir des corrections répondant à des cas d'erreur tout à fait imprévisibles.

 

La conclusion à tout cela est la suivante : même pour un format tout simpliste, n'écrivez jamais de parseur à la main. De nombreuses personnes travaillent déjà dessus, et il est peu productif d'essayer de les doubler.

Bien sûr, cela n'est valide que lorsque le langage utilisé possède une lib bien fichue pour faire le job. Python, par exemple, n'a pas été choisi au hasard pour faire cet article, car il possède une librairie standard exemplairement complète et efficace. En C, il n'y pas de telle librairie standard, mais de nombreux codes éparpillés coexistent, alors que Perl possède un module standard. En Java, de nombreux modules de tierce partie existent, notamment OpenCSV.

Et si d'aventure vous deviez écrire le vôtre (certainement parce que le langage utilisé ou sa communauté n'offre aucune solution satisfaisante), assurez-vous absolument de tester votre parseur avec les plus terribles immondices de formatage possible.

 

Enfin, l'auteur tiens à ajouter quelque chose qui lui semble un tantinet important, qui servira de mise en perspective et d'ouverture. On parle souvent de TSV, pour Tab Separated Value, et parfois de SCSV, pour Semicolon Separated Value. L'idée essentielle est que tous ces formats sont des CSV où l'on a changé le caractère séparant les valeurs, ou, plus fondamentalement, des instances de DSV où les délimiteurs sont précisément définis.

Personne n'a jamais eu fondamentalement besoin du CSV ou de ses variantes, mais il suffit d'une limite et de l'inertie technique, et les bonnes solutions se perdent.

Saviez-vous qu'il existe des caractères ASCII décrivant la séparation des entrées et des champs ? Dommage qu'ils ne soient pas sur les claviers, ç'aurait probablement changé la face du DSV.

 

 

L'auteur tiens également à remercier les relecteurs Ismael P., Nico M., Sylvain P. et Yoann M. pour leurs relectures, sans lesquelles le nombre de lecteur arrivant jusqu'ici eût été sensiblement diminué ; si vous êtes là, c'est grâce à eux.

  • À propos de
  • Étudiant en bioinformatique, pythonista, fan d'ASP.

4 commentaires sur “Écrire son parseur à la main — chroniques d'une mauvaise bonne idée

  1. rhooo, j\'le ferai plus (ou alors quand personne ne regarde)
    (commentaire en une ligne et deux champs en csv)

  2. Quand les dépendances ne sont pas un problème, Pandas est (à mon avis) le meilleur outil pour charger et traiter des donnés tabulées qui peuvent être contenues en mémoire.

    http://wesmckinney.com/blog/a-new-high-performance-memory-efficient-file-parser-engine-for-pandas/

    En plus de bonnes performances (performances du C), il est très flexible : read_csv peut inférer les types des colonnes et réaliser des conversions, gérer les NaN, etc.

    Pandas est utile pour ses fonctionnalités d\'entrées/sorties (SQL, CSV, HDF5, ...), cependant le cœur de la bibliothèque est orienté pour faire des statistiques et de l\'algèbre relationnelle (groupby, join, etc). Le système d\'indexes est spécifiquement adapté aux séries temporelles (pour l\'analyse financière, etc), mais avec quelques modifications et astuces, il doit être possible de travailler avec des coordonnées génomiques.

    Dans le cas ou le dataset ne tient pas en mémoire, il est nécessaire faire du streaming. Là encore, les besoins pour l\'analyse de données finnancières sont similaires et leurs outils peuvent intéresser les bio-informaticiens. Par exemple une solution semi-commerciale (OpenSaaS) en Haskell : https://www.fpcomplete.com/business/research/ https://youtu.be/gxrp3YTe7Ws

    Haskell se prête bien à la conception de mini-languages intégrés (EDSL). Un language permettant d\'écrire des générateurs/co-routines pour faire du streaming (comme en Python, mais produisant du code compilé avec des optimisations de fusion : https://www.fpcomplete.com/blog/2014/08/conduit-stream-fusion ).

    Un autre exemple de mini-languages en rapport avec le sujet est celui des \"recursive descent parser combinators\" (Attoparsec et Parsec en Haskell). Écrire un parser en Haskell est si simple que les expressions régulières sont bannies pour la plupart des usages. Le format d\'arbres Newick est l\'exemple typique où un parser récursif colle bien aux données.

  3. Waoh ! merci pour la mise en perspective finale, une vraie découverte pour moi !

    Et pour compléter le commentaire de Maël, j\'ai l\'impression que les travaux sur Spark (le projet Apache) explore les terres du streaming in memory (et pandas que je ne connais que de nom, est une source d\'inspiration , ex : https://databricks.com/blog/2015/08/12/from-pandas-to-apache-sparks-dataframe.html)

    Mais c\'est déjà là un autre sujet.
    Bye

  4. To the point...
    Comme quoi, on peut lire des fichiers csv en Python depuis des années, et décider de changer sa méthode du jour au lendemain en lisant un article sur bioinfo-fr... 😉
    Nice work

Laisser un commentaire