TD 6

Jointure de fichiers CSV

Cet exercice a pour objectif de calculer la jointure de deux fichiers au format CSV selon l’une de leur colonnes. Les fichiers CSV sont des représentations textuelles de tableaux de données :

• chaque ligne du fichier représente une ligne du tableau ;
• les cellules de chaque ligne sont séparées par un caractère spécifique, généralement le caractère ','.

Nous ferons quelques hypothèses simplificatrices sur la présentation des fichiers CSV :

• qu’il n’y a pas d’en-tête (généralement la première ligne sert à donner un nom à chaque colonne) ;
• que chaque ligne du fichier contient le même nombre de cellules ;
• que les valeurs contenues dans les cellules ne contiennent pas le caractère ',' et que la valeur y est directement représentée (pas de guillemets ou d’espaces parasites).

Nous allons représenter les fichiers CSV en utilisant les types suivants :

type Cellule = String
type Ligne   = [Cellule]
type CSV     = [Ligne]

1. Découpage de listes

Nous allons commencer par définir une fonction decoupe qui prend un élément c de type a et une liste d’éléments l de type a et qui renvoie la liste des listes obtenue en découpant l avec le séparateur c.

>>> decoupe 0 [1,2,3,0,4,5,6,0,7,8,0,0,9]
[[1,2,3],[4,5,6],[7,8],[],[9]]
>>> decoupe ';' "Jeanne;Henri;Claire;Ahmed;John"
["Jeanne","Henri","Claire","Ahmed","John"]

Le type de cette fonction est donc :

decoupe :: Eq a => a -> [a] -> [[a]]

On a besoin que le type générique a implémente la classe Eq, de manière à être sûrs que l’on puisse comparer notre séparateur et les éléments de la liste.

Une façon naturelle de définir cette fonction en haskell est d’utiliser un fold. Par exemple :

decoupe :: Eq a => a -> [a] -> [[a]]
decoupe c l = foldr ajoute [[]] l
    where
        ajoute a ls@(l:ls') | c == a    = [] : ls
                            | otherwise = (a:l) : ls'

Ça paraît un peu mystique comme ça, mais si on reprend dans l’ordre ce que l’on fait dans le pli :

1. L’accumulateur qu’on veut au début c’est une liste contenant une liste vide. La liste extérieure va toutes les sous listes et on commence avec une liste vide à l’intérieur qui servira à concaténer les premiers éléments.
2. À chaque pli, on va comparer l’élément de la liste avec notre séparateur. On a alors deux possibilités :
   • soit l’élément est le même que le séparateur, dans ce cas on doit commencer une nouvelle liste pour les éléments suivants et passer à l’élément suivant ;
   • soit ce n’est pas un séparateur et dans ce cas, on l’ajoute à la dernière liste qu’on a créée.

Un petit exemple ?

decoupe 0 [1,2,3,0,4,5,6,0,7,8,0,0,9]

1. On commence avec l’accumulateur initial, donc [[]].
2. Comme on plie par la droite, on commence par comparer notre séparateur avec le dernier élement. 9 étant différent de 0, on l’ajoute à la première liste de l’accumulateur. On a donc [[9]].
3. On a ensuite un 0, notre séparateur. Du coup, on va ajouter une nouvelle liste à l’accumulateur, soit [[], [9]].
4. On a ensuite encore un 0, donc on fait pareil et on a [[], [], [9]].
5. Après on a un 8, donc on l’ajoute à la première liste de l’accumulateur, soit : [[8], [], [9]].
6. Après on a un 7, donc on fait pareil, soit : [[7, 8], [], [9]].

et ainsi de suite.

2. Lecture d’un fichier CSV

En utilisant la fonction decoupe, on va écrire une fonction csv qui prend en argument une chaîne de caractères et renvoie une valeur de type CSV qui représente le tableau CSV contenu dans cette chaîne de caractères. On considère que les colonnes sont délimitées par le caractère ','. On pourra utiliser la fonction map :: (a -> b) -> [a] -> [b].

Ici, il faut se souvenir qu’on va récupérer une chaîne de caractères qui contient plusieurs lignes. Chaque ligne sera une ligne de notre format CSV. Il faut donc :

1. que l’on découpe la première chaîne pour récupérer la liste des lignes ;
2. que l’on découpe chacune de ces listes pour récupérer la liste des cellules.

Récupérer la liste des lignes, c’est facile, il suffit de découper avec le caractère de retour à la ligne : decoupe '\n' texte.

Par exemple, si on a le document suivant (ne pas faire attention au \, ils servent juste à écrire sur plusieurs lignes) :

file :: String
file = "1,Bob,18\n\
       \2,Alice,13\n\
       \3,George,3"

On va récupérer assez facilement :

fileDec = ["1,Bob,18", "2,Alice,13", "3,George,3"]

Au niveau du typage, on est bon, parce qu’on est passé de String = [Char] à [String] = [[Char]] avec un séparateur Char.

Maintenant, on veut séparer les contenus des éléments de cette liste en fonction du séparateur ','. Pour ça, on va encore utiliser decoupe, mais cette fois-ci, il faut qu’on l’applique à chaque sous-liste, ce qui se fait naturellement avec un…

map (decoupe ',').

fileDecDec = [["1", "Bob", "18"], ["2", "Alice", "13"], ["3", "George", "3"]]

Et les types ici ? On est encore bon, parce qu’on est passé de String = [Char] à [String] = [[Char]] avec un séparateur Char.

Si on met tout ensemble, on a alors :

csv :: String -> CSV
csv = map (decoupe ',') . (decoupe '\n')

3. Extraction de la \(i\)-ème cellule d’une ligne

Pour pouvoir spécifier la jointure à calculer, on désigne les colonnes par leur indice. Pour faire ceci de manière simple, on va redéfinir l’opérateur (!!) :: [a] -> Int -> a, de manière sûre.

On crée donc l’opérateur (!?) :: [a] -> Int -> Maybe a. On adopte la même convention que l’indice du premier élément est 0.

L’implémentation que nous allons proposer utilise une fonction bien choisie : find :: (a -> Bool) -> [a] -> Maybe a qui renvoie le premier élément d’une liste qui respecte un prédicat donné, s’il y en a un.

(!?) :: [a] -> Int -> Maybe a
l !? n = fst <$> (find (\(_, k) -> k == n) (zip l [0..]))

L’idée ici, c’est de ruser un peu. On commence par zipper la liste initiale avec la liste infinie [0..], ce qui va créer des tuples avec pour chaque élément de la liste, son index.

Ensuite, on va aller trouver (avec find) le premier (et normalement le seul) élément dont l’index correspond à celui recherché.

Finalement, on a un petit problème. Notre find renvoie un Maybe (a, Int) et pas un Maybe a. Il faut que l’on puisse récupérer le premier élément du tuple, sans retirer l’effet du Maybe. Pour cela, on utilise la fonction fst, qui est fmappée pour agir dans le Maybe.

4. Implémenter la jointure (1er essai)

On commence par une implémentation naïve de la jointure de deux valeurs de type CSV.

Il s’agit de la fonction joinN :: Int -> Int -> CSV -> CSV -> CSV,

joinN i j csv1 csv2 renvoie la structure CSV qui contient les lignes l1 ++ l2 telles que :

• l1 est une ligne de csv1 ;
• l2 est une ligne de csv2 ;
• la \(i\)-ème cellule de l1 et la \(j\)-ème cellule de l2 contiennent la même valeur ;
• on considère que si les lignes de csv1 n’ont pas de \(i\)-ème cellule et que si les lignes de csv2 n’ont pas de \(j\)-ème cellule alors toutes les lignes de csv1 et de csv2 peuvent être appariées. En pratique, cela signifie qu’il suffit de comparer les résultats de l’opérateur (!?) pour savoir si deux lignes de csv1 et de csv2 doivent être appariées dans la jointure.

L’algorithme implémenté par joinN consiste à parcourir les lignes de csv1 et de chercher dans csv2 les lignes qui peuvent lui être appariées dans la jointure.

Ici encore, il paraît naturel (si, si, promis) qu’utiliser un pliage permet de faire cette fonction élégamment.

Ce qu’on veut faire finalement, c’est que pour chaque ligne du premier fichier, on va regarder chaque ligne du deuxième. Si elles ont les bons attributs, on joint les lignes en les concaténant.

joinN :: Int -> Int -> CSV -> CSV -> CSV
joinN i j csv1 csv2 = foldr joinLine [] csv1
    where
        joinLine l1 jr = let k1 = l1 !? i in
            map (l1 ++) (filter (\l2 -> k1 == (l2 !? j)) csv2) ++ jr

Encore une fois, ça peut paraître mystique au premier abord. Mais décortiquons un peu ce qu’on fait.

1. L’accumulateur que l’on veut au début, c’est une liste vide. C’est cette liste qui va contenir l’ensemble des lignes du nouveau fichier que l’on va construire.
2. À chaque pli, on va prendre la ligne courante et filtrer dans les lignes du deuxième fichier celles qui ont la clé qui correspond. Ensuite on va concaténer la ligne courante avec chacune des lignes filtrées et ajouter ça dans l’accumulateur.

Un petit exemple ?

On considère les CSV suivants :

"1","Bob"
"2", "Alice"

"Bob", "13"
"Alice", "12"
"Bob", "4"

1. Quand on commence, l’accumulateur vaut [], c’est normal.
2. Ensuite, on commence à replier avec la dernière ligne du csv1. Dans ce cas, l1 vaut ["2", "Alice"] et k1 = "Alice".
3. On filtre ensuite les lignes de csv2. Ici, on va récupérer la liste [["Alice", "12"]].
4. Maintenant, pour chaque élément de cette liste, on va concaténer l1 devant, soit [["2", "Alice", "Alice", "12"]].
5. Finalement, on ajoute ça à notre accumulateur, qui pour le moment est vide.

On continue ainsi pour tous les éléments de la première liste, ce qui donnerait :

[
    ["1","Bob","Bob","13"],
    ["1","Bob","Bob","4"],
    ["2","Alice","Alice","12"]
]

5. Vers une implémentation plus efficace

Si les fichiers CSV avec lesquels on travaille sont volumineux, l’algorithme implémenté par joinN i j csv1 csv2 peut prendre un temps important. En effet, il s’exécute en \(\mathcal{O}(n1 \times n2 )\) si \(n1\) et \(n2\) sont respectivement le nombre de lignes de csv1 et csv2.

On va donc utiliser un autre algorithme qui va consister à commencer par trier les lignes des données de type CSV puis s’appuyer sur le fait que les données sont triées pour calculer la jointure. Si chaque ligne est associée à au plus \(k\) lignes dans la jointure, le temps d’exécution devient alors \(\mathcal{O}(n1 + k \times n2 )\) pour la jointure proprement dite et \(\mathcal{O}(n1\cdot\mathsf{log}(n1) + n2\cdot\mathsf{log}(n2))\) pour trier les données.

Si \(n1 = n2 = 10^8\), \(k = 1\) et que l’on peut traiter \(10^9\) lignes par seconde, alors joinN i j csv1 csv2 s’exécute en \(\frac{10^8 \times 10^8}{10^9} = 10^7\) secondes soit en 2800 heures, plus de 100 jours. En utilisant le nouvel algorithme, le temps d’exécution devient (environ) \(\frac{10^8 + 10^8 +20 \times 10^8 + 20 \times 10^8} {10^9} = 4,2\) secondes.

Même si les calculs sont très approximatifs, les ordres de grandeurs sont corrects et montrent très clairement que nous avons intérêt à utiliser ce second algorithme.

Pour cela, on va commencer par une fonction intermédiaire avance :: Int -> Int -> Ligne -> CSV -> (CSV, CSV) telle que avance i j l csv, où csv est une structure de type CSV dont les lignes sont triées par rapport à la colonne j, renvoie la paire (csv1, csv2) telle que :

• csv1 sont les lignes de csv dont la \(j\)-ème colonne est égale à la \(i\)-ème colonne de l ;
• csv2 sont les lignes de csv dont la \(j\)-ème colonne contient une valeur supérieure ou égale à la \(i\)-ème colonne de l.

On va donner une implémentation de avance, en utilisant les fonctions

• dropWhile :: (a -> Bool) -> [a] -> [a] ;
• takeWhile :: (a -> Bool) -> [a] -> [a] ; et
• l’opérateur (!?).

On a donc besoin de :

1. récupérer la clé à la \(i\)-ème position de l, avec k = l !? i
2. avoir un prédicat (pour utiliser dans takeWhile / dropWhile), qui dit que la ligne qu’on regarde a une correspondance de clé. Par exemple, quelque chose comme ligneOK l' = l' !? j == k.
3. on veut commencer à la première ligne qui a une correspondance, donc on jette toutes les lignes du début qui n’en ont pas avec dropWhile (not . ligneOK) csv
4. ensuite, on renvoie la paire comme convenu.

Ça peut donner quelque chose comme ça :

avance :: Int -> Int -> Ligne -> CSV -> (CSV, CSV)
avance i j l csv = (takeWhile ligneOK csv1, csv1)
    where
        k = l !? i
        ligneOK l' = l' !? j == k
        csv1 = dropWhile (not . ligneOK) csv

6. Implémentation de la jointure à base de tri

On peut maintenant implémenter le nouvel algorithme de jointure join :: Int -> Int -> CSV -> CSV -> CSV tel que :

1. on commence par trier les deux fichiers
2. pour chaque ligne du premier fichier, on avance dans le deuxième en accumulant les lignes qui sont compatibles pour former la jointure

Pour ça, on va utiliser :

• avance et (!?)
• sortOn :: Ord b => (a -> b) -> [a] -> [a], qui trie la liste donnée en suivant l’ordre induit par la fonction en paramètre.

join :: Int -> Int -> CSV -> CSV -> CSV
join i j csv1 csv2 = go (sortOn (!? i) csv1) (sortOn (!? j) csv2)
    where
        go [] _ = []
        go (l1:csv1') csv2' = map (l1++) j2 ++ go csv1' csv2R
            where
                (j2, csv2R) = avance i j l1 csv2'