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

Nobody expect to be able to parse any old C.S.V.
Nobo­dy expect to be able to parse any (old) C.S.V. Cré­dit : Paul Dow­ney

Partie 1

Où l'on prend conscience de l'existence de stan­dards, et de leur néces­si­té.

Tout petit pro­gramme s'éveillant au monde se trou­ve­ra un jour face à ses obli­ga­tions : s’interfacer avec ce der­nier. La lumière exté­rieure devra alors péné­trer son petit antre, appor­tant mali­cieu­se­ment l'information de mille autres petits pro­grammes, si hété­ro­clites et désor­don­nés que nul ne sais vrai­ment qui fait quoi. Tous forment ain­si un monde d'information par­tiel­le­ment struc­tu­rée, riche de diver­si­té et de liber­té.

Un jour fût défi­nit le mot « bor­del » comme « le meilleur adjec­tif décri­vant cet ensemble ».

Le nombre de standards est beaucoup trop grand.
Le nombre de stan­dards est beau­coup trop grand.

Et, afin de per­mettre à ce bor­del de conti­nuer à exis­ter, furent défi­nies des règles pré­cises, des conven­tions, des stan­dards per­met­tant à tout un cha­cun d'enrichir le chaos ambiant dans un res­pect mutuel, ou le chaos mutuel dans un res­pect ambiant selon les auteurs.

Et ces normes, il y en a de gar­gan­tuesques pel­le­tées, ne serait-ce que pour l'organisation des don­nées dans les fichiers.

Nor­mal : on a plein de choses dif­fé­rentes à racon­ter, 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 stan­dard.

 

Par­mi les stan­dards, l'un d'entre eux est prince en de nom­breux pays : le CSV, pour Com­ma Sepa­ra­ted Value, ou plus géné­ra­le­ment DSV, pour Deli­mi­ter-Sepa­ra­ted Value, où les don­nées sont orga­ni­sées en table et dont le stan­dard pré­voit moult richesses. La prin­ci­pale carac­té­ris­tique de ce for­mat est de sépa­rer des champs de don­nées (fields) défi­nis (et finis) par un déli­mi­teur (la vir­gule dans le cas du CSV), et de regrou­per les infor­ma­tions liées sur une seule entrée (record), en géné­ral une ligne.

Le for­mat CSV est uti­li­sable pour tout type de don­nées : taux d'expression des gènes d'une PCR, résul­tats du cross des enfants de ce week-end, inter­fa­çage avec une base de don­nées, sto­ckage des info uti­li­sa­teurs d'un sys­tème, mesures d'altitude d'un mar­teau et d'une plume chu­tant de concert et des mains d'un cos­mo­naute,…

Ce for­mat est aus­si uti­li­sé (dans une cer­taine mesure) par les tableurs pour conser­ver les don­nées dans des fichiers.

Voi­ci des don­nées for­ma­tées en un CSV typique :

Nous obser­vons ici dis­tinc­te­ment cinq par­ti­cu­la­ri­tés :

  • la pre­mière ligne (et pre­mière entrée) défi­nit 3 champs, qui devraient être com­pris comme les noms des colonnes, autre­ment dit le hea­der.
  • la deuxième ligne est une entrée : elle défi­nit un gène, nom­mé lacA, ayant un ratio d'expression de 0.23 et un temps d'incorporation dési­gné comme « long ».
  • La troi­sième ligne est une troi­sième entrée défi­nis­sant un autre gène, lacZ, avec un ratio d'expression non com­mu­ni­qué et un temps d'incorporation mar­qué comme « long ».
  • La qua­trième ligne est une qua­trième entrée défi­nis­sant Pépin, avec un ratio d'expression de 0.01, ce qui est bien mais pas top, et un temps d'incorporation dési­gné comme « bref ».
  • On observe que les entrées par­tagent éven­tuel­le­ment des don­nées iden­tiques, par exemple lacA et lacZ ont toutes deux le temps d'incorporation long, alors que Pépin le bref.

À toutes ces remarques, il est impor­tant d'ajouter les sui­vantes :

  • les entrées sont indé­pen­dantes
  • les entrées doivent four­nir des valeurs pour tous les champs (même si cette valeur est une chaîne vide)
  • une entrée ne doit pas four­nir de valeur pour un champ qui n'est point dans le hea­der (Comme spé­ci­fié dans la RFC 4180 : « Each line should contain the same num­ber of fields throu­ghout the file » Cette RFC est néan­moins à consi­dé­rer avec du recul : elle ne concerne que le CSV, et n'existe que pour pal­lier l'absence de spé­ci­fi­ca­tion for­melle.)
  • le carac­tère déli­mi­teur, la vir­gule, pour­rait être n'importe quel carac­tère ou chaîne de carac­tère pour­vu qu'il reste constant dans tout le fichier.

Ce for­mat, simple et épu­ré, est très en vogue dans de nom­breux milieux (et lar­ge­ment usi­té en de nom­breux extrêmes).

 

 

 

 


 

Partie 3

Où l'on apprend que nom­breux sont les rigo­los qui jouent avec le feu, et que moins nom­breux (mais plus sagaces, comme Sam) sont ceux qui jouent éga­le­ment avec des gants igni­fu­gés.

 

Et com­ment fait-on en Python, par exemple, pour s'interfacer avec un tel for­mat ?

Voi­ci le code habi­tuel­le­ment pro­duit par les pro­gram­meurs, d'après mon petit doigt droit, tou­jours à la pointe de l'information pifo­mé­trique :

Simple, beau, effi­cace. (nous ver­rons plus tard que les véri­tables termes sont sim­pliste, bête, effi­lo­ché)

 

Pour­tant, il existe un ensemble de per­sonnes, qui, lorsqu'elles ont besoin de s'interfacer avec ce for­mat d'une sim­pli­ci­té mons­trueuse, se lancent dans la doc plu­tôt que le code, et dans le stan­dard plu­tôt que le pifo­mètre :

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

Fran­che­ment, quelle dif­fé­rence ? C'est une lib en plus à impor­ter, à com­prendre, et à débug­ger, et si c'est juste pour pas avoir à faire un appel à join ou split, ce n'est fran­che­ment pas un bon deal.

Fran­che­ment, arrê­tons hic et nunc cet article, per­sonne ne voit où l'auteur veut aller.

 

 

 


 

Partie 4

Où l'on apprend que l'usage des gants igni­fu­gés ne relève pas seule­ment de la para­noïa, ni du gras pédan­tisme d'un étu­diant en fin de vie, étu­diante elle aus­si.

 

Ci-après est mon­tré un petit fichier CSV fort rigo­lo. Ques­tion : com­bien y a‑t-il d'entrées, et com­bien y a‑t-il de champs pour cha­cune ?

Petite expé­rience simple et désuète : lan­cer son par­seur mai­son (fait à la mimine) sur ce fichier et affi­cher les entrées détec­tées, puis uti­li­ser la lib stan­dard pour faire le même job.

Pour les cou­ra­geux qui n'ont pas envie d'écrire tout ça eux-même, il y a un dépôt git qui héberge une auto­ma­ti­sa­tion de l'expérience.

 

Atten­tion, spoi­ler !

 

Le fichier CSV balan­cé un peu plus haut contient deux lignes, dont la pre­mière est par­ti­cu­liè­re­ment tor­due, et la seconde tout à fait réa­liste. Voi­ci les lignes détec­tées par le par­seur mai­son, qui ne résiste pas à la ten­ta­tion de nous trou­ver moult infor­ma­tion dont nous nous serions bien pas­sé :

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

Alors que le par­seur stan­dard détecte bien les 2 lignes, incluant les deux pièges dont il s'est bien pro­té­gé :

mon collègue parsait le CSV avec un line.split. Parsait.
mon col­lègue ana­ly­sait le CSV avec un line.split. Ana­ly­sait.

Ici, les pièges reposent essen­tiel­le­ment sur le carac­tère de champ de texte libre, le double guille­met (mais pas le guille­met simple), qui per­met d'entrer n'importe quel carac­tère sans influer sur la struc­ture de don­nées. Autre­ment dit, en met­tant des carac­tères de sépa­ra­tion entre double guille­mets, celui-ci sera inter­pré­té comme une chaîne de carac­tères et non comme une sépa­ra­tion de champs.

Le par­seur mai­son n'implémente aucune ges­tion de ce champ de texte libre, et (phrase d'accroche pour la pro­chaine par­tie : ) il n'existe aucun moyen de le faire sim­ple­ment.

 

 

 

 


 

Partie 5

Où l'auteur, pas­sa­ble­ment aigris par les éner­gu­mènes délais­sant les gants igni­fu­gés pour l’insouciance de la jeu­nesse, lance un der­nier cri dans la nuit noire et obs­cure, avant de se cogner contre un mur (celui-là même qui clôt l'article et laisse la place aux com­men­taires).

 

Les résul­tats sont for­mels : le par­seur stan­dard est bien plus robuste aux méchan­ce­tés du monde exté­rieur que le par­seur mai­son.

Son secret : il uti­lise un auto­mate à état fini pour par­ser les don­nées, et cela est néces­saire pour gérer le cas du double guille­met pour les champs de texte libre. Dans le code C der­rière CPy­thon, implé­men­tant le par­seur en 1600 lignes, on trouve la ges­tion de tran­si­tion des états sous la forme d'un gros switch, et leurs défi­ni­tions comme une énu­mé­ra­tion.

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 auto­mate à état fini.

Enfin, la der­nière update de ce code, à l'écriture de cet article, date du jour même. Ce module, bien que par­fai­te­ment fonc­tion­nel, conti­nue à rece­voir des cor­rec­tions répon­dant à des cas d'erreur tout à fait impré­vi­sibles.

 

La conclu­sion à tout cela est la sui­vante : même pour un for­mat tout sim­pliste, n'écrivez jamais de par­seur à la main. De nom­breuses per­sonnes tra­vaillent déjà des­sus, et il est peu pro­duc­tif d'essayer de les dou­bler.

Bien sûr, cela n'est valide que lorsque le lan­gage uti­li­sé pos­sède une lib bien fichue pour faire le job. Python, par exemple, n'a pas été choi­si au hasard pour faire cet article, car il pos­sède une librai­rie stan­dard exem­plai­re­ment com­plète et effi­cace. En C, il n'y pas de telle librai­rie stan­dard, mais de nom­breux codes épar­pillés coexistent, alors que Perl pos­sède un module stan­dard. En Java, de nom­breux modules de tierce par­tie existent, notam­ment OpenCSV.

Et si d'aventure vous deviez écrire le vôtre (cer­tai­ne­ment parce que le lan­gage uti­li­sé ou sa com­mu­nau­té n'offre aucune solu­tion satis­fai­sante), assu­rez-vous abso­lu­ment de tes­ter votre par­seur avec les plus ter­ribles immon­dices de for­ma­tage pos­sible.

 

Enfin, l'auteur tiens à ajou­ter quelque chose qui lui semble un tan­ti­net impor­tant, qui ser­vi­ra de mise en pers­pec­tive et d'ouverture. On parle sou­vent de TSV, pour Tab Sepa­ra­ted Value, et par­fois de SCSV, pour Semi­co­lon Sepa­ra­ted Value. L'idée essen­tielle est que tous ces for­mats sont des CSV où l'on a chan­gé le carac­tère sépa­rant les valeurs, ou, plus fon­da­men­ta­le­ment, des ins­tances de DSV où les déli­mi­teurs sont pré­ci­sé­ment défi­nis.

Per­sonne n'a jamais eu fon­da­men­ta­le­ment besoin du CSV ou de ses variantes, mais il suf­fit d'une limite et de l'inertie tech­nique, et les bonnes solu­tions se perdent.

Saviez-vous qu'il existe des carac­tères ASCII décri­vant la sépa­ra­tion des entrées et des champs ? Dom­mage qu'ils ne soient pas sur les cla­viers, ç'aurait pro­ba­ble­ment chan­gé la face du DSV.

 

 

L'auteur tiens éga­le­ment à remer­cier les relec­teurs Ismael P., Nico M., Syl­vain P. et Yoann M. pour leurs relec­tures, sans les­quelles le nombre de lec­teur arri­vant jusqu'ici eût été sen­si­ble­ment dimi­nué ; si vous êtes là, c'est grâce à eux.



Pour continuer la lecture :


Commentaires

5 réponses à “Écrire son parseur à la main — chroniques d'une mauvaise bonne idée”

  1. Avatar de Olivier
    Olivier

    rhooo, j'le ferai plus (ou alors quand per­sonne ne regarde)
    (com­men­taire en une ligne et deux champs en csv)

  2. Quand les dépen­dances ne sont pas un pro­blème, Pan­das est (à mon avis) le meilleur outil pour char­ger et trai­ter des don­nés tabu­lées qui peuvent être conte­nues en mémoire.

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

    En plus de bonnes per­for­mances (per­for­mances du C), il est très flexible : read_​csv peut infé­rer les types des colonnes et réa­li­ser des conver­sions, gérer les NaN, etc.

    Pan­das est utile pour ses fonc­tion­na­li­tés d'entrées/sorties (SQL, CSV, HDF5, …), cepen­dant le cœur de la biblio­thèque est orien­té pour faire des sta­tis­tiques et de l'algèbre rela­tion­nelle (group­by, join, etc). Le sys­tème d'indexes est spé­ci­fi­que­ment adap­té aux séries tem­po­relles (pour l'analyse finan­cière, etc), mais avec quelques modi­fi­ca­tions et astuces, il doit être pos­sible de tra­vailler avec des coor­don­nées géno­miques.

    Dans le cas ou le data­set ne tient pas en mémoire, il est néces­saire faire du strea­ming. Là encore, les besoins pour l'analyse de don­nées fin­nan­cières sont simi­laires et leurs outils peuvent inté­res­ser les bio-infor­ma­ti­ciens. Par exemple une solu­tion semi-com­mer­ciale (Open­SaaS) en Has­kell : https://​www​.fpcom​plete​.com/​b​u​s​i​n​e​s​s​/​r​e​s​e​a​r​ch/ https://​you​tu​.be/​g​x​r​p​3​Y​T​e​7Ws

    Has­kell se prête bien à la concep­tion de mini-lan­guages inté­grés (EDSL). Un lan­guage per­met­tant d'écrire des géné­ra­teurs/­co-rou­tines pour faire du strea­ming (comme en Python, mais pro­dui­sant du code com­pi­lé avec des opti­mi­sa­tions de fusion : https://​www​.fpcom​plete​.com/​b​l​o​g​/​2​0​1​4​/​0​8​/​c​o​n​d​u​i​t​-​s​t​r​e​a​m​-​f​u​s​ion ).

    Un autre exemple de mini-lan­guages en rap­port avec le sujet est celui des "recur­sive des­cent par­ser com­bi­na­tors" (Atto­par­sec et Par­sec en Has­kell). Écrire un par­ser en Has­kell est si simple que les expres­sions régu­lières sont ban­nies pour la plu­part des usages. Le for­mat d'arbres Newick est l'exemple typique où un par­ser récur­sif colle bien aux don­nées.

  3. Waoh ! mer­ci pour la mise en pers­pec­tive finale, une vraie décou­verte pour moi !

    Et pour com­plé­ter le com­men­taire de Maël, j'ai l'impression que les tra­vaux sur Spark (le pro­jet Apache) explore les terres du strea­ming in memo­ry (et pan­das que je ne connais que de nom, est une source d'inspiration , ex : https://​data​bricks​.com/​b​l​o​g​/​2​0​1​5​/​0​8​/​1​2​/​f​r​o​m​-​p​a​n​d​a​s​-​t​o​-​a​p​a​c​h​e​-​s​p​a​r​k​s​-​d​a​t​a​f​r​a​m​e​.​h​tml)

    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éci­der de chan­ger sa méthode du jour au len­de­main en lisant un article sur bioin­fo-fr… 😉
    Nice work

  5. Avatar de Pierre Fauconnier
    Pierre Fauconnier

    "La conclu­sion à tout cela est la sui­vante : même pour un for­mat tout sim­pliste, n'écrivez jamais de par­seur à la main. De nom­breuses per­sonnes tra­vaillent déjà des­sus, et il est peu pro­duc­tif d'essayer de les dou­bler."

    Heu­reu­se­ment que le pre­mier gars qui a écrit un par­ser est allé au delà de ce conseil. Tiens, au fait, "les nom­breuses per­sonnes qui tra­vaillent déjà des­sus", elles en font quoi, de ce com­men­taire ?

    L'évolution, la nou­veau­té, d'autres manières de faire, sont nées du fait que des gens ne se sont pas arrê­tés à "oui mais un autre l'a déjà fait avant moi"… Avec le rai­son­ne­ment que vous prô­nez, la roue serait tou­jours à l'état d'idée et le fil à cou­per le beurre ne sau­rait pas qu'il peut ser­vir à cou­per le beurre…

Laisser un commentaire