Chaussettes et Batraciens

Imaginez la situation suivante : vous disposez d'une liste de mots dans un fichier LIST. Vous disposez également d'un dictionnaire dans un fichier DICT. Et vous voulez savoir si tous les mots de LIST apparaissent bien dans DICT.

C'est un problème fréquent en informatique. LIST contient par exemple tous les batraciens et DICT contient tous les animaux. Demander si LIST est incluse dans DICT revient à demander si tous les batraciens sont des animaux.

Dans ce billet je montre deux méthodes en ligne de commande. La première méthode n'est pas efficace mais elle est compacte et facile à mémoriser. La seconde méthode est beaucoup plus efficace.

Méthode 1: grep me, grep me my friend

La première méthode utilise grep(*) dans sa variante fgrep qui cherche les termes littéraux plutôt que les regex. Voici la ligne de commande :

fgrep -vxf DICT LIST

Il faut un peu de temps - et sans doute quelques essais - pour se convaincre que ça réalise bien un test d'inclusion. Cette commande prend tous les mots de DICT et les retranche de LIST. Si au moins un mot est affiché c'est qu'il n'a pas été retranché. Donc il n'était pas dans DICT. Donc LIST n'est pas incluse dans DICT.

Cette solution est très compacte : une seule commande. En revanche la complexité est multiplicative. Je vous passe les détails de calcul, mais c'est mauvais.

Méthode 2: tri et décompte

L'idée est d'amalgamer DICT + DICT + LIST et de conserver seulement les termes uniques. Trois cas sont possibles. Cas 1 : un terme est dans DICT et dans LIST alors il se retrouve trois fois dans l'amalgame et on ne le conserve pas. Cas 2 : un terme est dans DICT mais pas dans LIST alors il se retrouve deux fois dans l'amalgame et on ne le conserve pas. Cas 3 : un terme est dans LIST mais pas dans DICT alors il se retrouve une fois dans l'amalgame et on le conserve. Voici la ligne de commande :

sort <(sed p DICT) <(sort -u LIST) | uniq -u

Il y a des petites astuces. Le sed p DICT c'est pour dupliquer chaque ligne de DICT. Le sort -u LIST c'est pour éliminer d'éventuels doublons dans LIST (qui sinon fausseraient le cas 3). Le uniq -u à la fin c'est pour conserver seulement les termes uniques.

Concernant la complexité : dupliquer les lignes de DICT c'est linéaire, amalgamer c'est linéaire, compter et garder seulement les termes uniques à la fin c'est linéaire. La seule partie non-linéaire c'est le tri de l'amalgame. Cette partie est quasi-linéaire c'est-à-dire en (2m+n).log(2m+n). En pratique c'est bien, même s'il existe encore mieux avec des tables de hachage.

Exemple : un dictionnaire d'animaux, une liste de batraciens et une chaussette

$ cat DICT | column

girafe          singe           serpent

crapaud         panthère        kangourou

éléphant        crocodile       anaconda

zèbre           triton          gnou

grenouille      autruche        mangouste

lion            hippopotame     ornithorynque

tigre           salamandre      gazelle

$ cat LIST 

triton

crapaud

chaussette 

salamandre

grenouille

$ fgrep -vxf DICT LIST

chaussette

$ sort <(sed p DICT) <(sort -u LIST) | uniq -u

chaussette

Les deux commandes ont correctement détecté l'intrus. Un seul intrus suffit à déduire que LIST n'est pas incluse dans DICT. Si maintenant on enlève la chaussette de la liste, les deux commandes ne détectent plus rien, leur sortie est vide, et on en déduit que LIST est incluse dans DICT :

$ fgrep -vxf DICT LIST

$ sort <(sed p DICT) <(sort -u LIST) | uniq -u 

Test booléen

Pour transformer la première commande en un per test booléen, j'utilise l'option quiet de fgrep et des portes logiques && et ||. C'est une façon de faire parmi d'autre mais j'aime le côté one-liner(**) :

    fgrep -vxqf DICT LIST && echo KO || echo OK

Pour la seconde commande, uniq n'offre pas d'option quiet, alors j'utilise une vielle ruse indienne :

    sort <(sed p DICT) <(sort -u LIST) | uniq -u |
    read _ && echo KO || echo OK

Epilogue

J'espère que ce billet vous aura intéressé. Parce que sinon vous venez de perdre un temps précieux à le lire jusqu'ici. Moche. Nan, vraiment. Moche.

Au fait, si on n'est pas joueur/bricoleur on peut aussi utiliser la merveilleuse commande "comm" qui est typiquement faite pour les comparaisons de liste.

comm -13 <(sort -u DICT) <(sort -u LIST) | read _ && echo KO || echo OK

La complexité est meilleure m.log(m) + n.log(n) quoique toujours quasi-linéaire, et c'est assez compact.

(*) Les personnes qui me connaissent savent que je suis obsessionnel de grep et plus généralement des regex. Je me lève grep, me mange des grep au sarrasin, je me couche grep et je recommence le lendemain. Quant aux personnes qui ne me connaissent pas, elles ignorent la chance qu'elles ont.

(**) Quel est le terme français correct pour one-liner ? "Un-lignard" ? Ou "Solicode" "Solocode" "Monocode" ? Un "codounet" une "Codette" ? Pfffff....