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
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
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 serpentcrapaud panthère kangourouéléphant crocodile anacondazèbre triton gnougrenouille autruche mangoustelion hippopotame ornithorynquetigre salamandre gazelle
$ cat LIST
tritoncrapaudchaussettesalamandregrenouille
$ 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
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
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....
