grep et fichier motifs ? Résolu/Fermé

Question

Bonjour, 

j'utilise grep avec un fichier contenant des motifs (~40000 lignes de motifs) pour extraire les données d'un fichier :
grep -f fichier_motif fichier_donnees

il se trouve que je souhaite savoir quels motifs dans le fichier fichier_motif qui pourraient fournir aucune résultat.

Avez vous une solution ?

Merci

Configuration: Windows XP / Firefox 10.0.2

mamiemando · Answer

il se trouve que je souhaite savoir quels motifs dans le fichier fichier_motif qui pourraient fournir aucune résultat.    

Je n'ai pas compris la question. Est-ce que la question est plutôt : parmi tous les motifs listés dans fichier_motif, quels motifs ne sont jamais retrouvés dans fichier_donnees.   

Si c'est le cas :   

for motif in $(cat fichier_motif); do (grep -q $motif fichier_donnees || echo $motif); done

Exemple :   

(mando@aldur) (~) $ cat fichier_motif   
aaa   
bbb   
ggg   

(mando@aldur) (~) $ cat fichier_donnees   
aaabbb   
ccaaadd   
bbbddd   
dddcc   

(mando@aldur) (~) $ for motif in $(cat fichier_motif); do (grep -q $motif fichier_donnees || echo $motif); done   
ggg 

Bonne chance

dubcek · Answer

hello 
essayez avec awk 
$ cat fichier_motif 
aa 
bb 
cc 
dd 
$ cat fichier_donnees 
aaaaa 
xxxxxxx 
dddd 
$  
$ awk 'NR==FNR {m[n++]=$0;next} {for(x=0;x<n;x++)if($0 ~ m[x])t[x]++} END {for(x=0;x<n;x++)if(!t[x])print m[x]}'  fichier_motif fichier_donnees 
bb 
cc 
$

mamiemando · Answer

Même si la solution de dubcek marche, je ne pense pas que ça change forcément grand chose, car pour chaque ligne, on compare avec l'ensemble des motifs.  La boucle for que j'ai écrite en shell raisonne pour chaque motif, puis itère sur tout le fichier, mais globalement on a toujours autant d'itérations (le nombre de ligne du premier fichier fois le nombre de ligne du second fichier). Cela veut dire qu'a priori les deux algorithmes offrent des performances comparable car la complexité est la même.   

Première optimisation (simple) :   

Pour améliorer les performances de cet algorithme, on pourrait commencer par marquer les motifs déjà trouvés une fois pour éviter de les rechercher à nouveau. La complexité dans le pire cas reste la même (si les motifs à trouver sont en fin de fichiers), mais en moyenne elle est meilleure.   

Seconde optimisation (abordable si tu sais un peu développer) :   

On peut avoir un algorithme de complexité linéaire mais cela réclame un peu de programmation. Dans l'idée on peut voir un motif comme un automate. Pour simplifier le principe je vais me limiter au cas où les motifs sont des sous-chaînes de caractères et pas des expressions rationnelles (mais dans le cas d'une expression rationnelle, la démarche reste la même).   

Supposons que je cherche la chaîne "bonjour" et la chaîne "hello". Alors je peux construire deux automates :   

^ -> b -> o -> n -> j -> o -> u -> r -> $   
^ -> h -> e -> l -> l -> o -> $

J'ai donc ici deux automates. Je note    
- ^: l'état initial : pour le moment aucun caractère du motif n'a été lu   
- $: l'état final : si j'atteins cet état, j'ai trouvé le motif avec succès.   

D'un point de vue implémentation, si on se limite aux sous-chaînes, il suffit de stocker un tableau de caractère par motif et de retenir l'index du caractère courant (c'est plus ou moins l'algorithme KMR appliqué à un ensemble de motifs).

Par exemple si j'indexe à partir de 0 et si j'ai lu successivement "bon", je sais que l'état courant du premier automate est 3 (je suis placé sur le n) et 0 pour le second (je suis placé sur ^). Si à l'itération suivante je lis le caractère 'z' par exemple, ceci interrompt la progression dans le premier automate et provoque un retour à l'état 0.   

Plus généralement : je lis caractère par caractère le fichier de données   
- Si le caractère me permet d'avancer dans l'automate, je le fais. Si j'atteins alors la fin de l'automate ($), alors le motif a été trouvé et je peux marquer ce motif comme trouvé. Je peux alors supprimer cet automate de mon ensemble d'automates à évaluer pour éviter d'avoir à faire des calculs par la suite dessus.   
- Si le caractère ne me permet pas d'avancer dans un automate donné, alors je me replace sur l'état ^.   

À la fin, je retourne tous les motifs qui n'ont pas été marqués (ils n'ont jamais été trouvés).   

Plusieurs avantages à cette approche :   
- on élimine les motifs traités (le pire cas étant comme d'habitude, les motifs que l'on cherche sont à la fin du fichier de données)   
- on ne lit qu'une seule fois chaque ligne du fichier de données   
- au lieu de marquer un motif (avec un boolean qui décrit s'il a été vu ou non), on peut maintenir un compteur ce qui permet de compter combien de fois il a été observer sans que cela impacte les performances de l'algorithme   
- l'algorithme reste vrai pour des automates plus compliqués comme ceux engendrés par des expressions rationnelles   

Troisième optimisation (sous certaines hypothèses et si tu sais programmer) :   

Supposons maintenant qu'on se limite à la recherche de sous chaînes (donc on ne supporte pas les expressions rationnelles). Si les motifs à trouver sont "longs" et se ressemblent, on doit pouvoir encore un peu améliorer les performances en stockant les motifs de manières un peu plus subtile. Par exemple "bonjour" et "bonhomme". On peut alors stocker dans un arbre l'ensemble des noeuds.   

^   
\_b_o_n_j_o_u_r_$1   
|     \_h_o_m_m_e_$2   
\_h_e_l_l_o_$3

L'idée consiste ensuite à marquer le(s) noeud(s) courant(s) de l'arbre et tronquer les branches qui ne servent plus quand on atteint un état final.   

Bonne chance

dubcek · Answer

certes, mais la boucle shell va exécuter ~40000 grep du fichier alors que le awk ne l'accède qu'une seule  fois, le reste se passant en mémoire 
morteldrv va nous indiquer les temps de calcul.
on peut rajouter un test qui ne recherche pas dans la ligne un motif déjà trouvé
awk 'NR==FNR {m[n++]=$0;next} {for(x=0;x<n;x++)if(!t[x])if($0 ~ m[x])t[x]++} END {for(x=0;x<n;x++)if(!t[x])print m[x]}'

mamiemando · Answer

Oui tout à fait d'accord, c'est d'ailleurs la première optimisation que je suggérais.

mortelrdv · Answer

J'ai essayé de grappiller un peu en mettant les fichiers dans un ramdisk

mamiemando: ~11mn


dubcek : ta soluce a durée trop longtemps (>30mn) que j'ai laissé tombé.
j'ai bien essayé avec tes exemples ça marche.


le PC :
Intel(R) Pentium(R) 4 CPU 2.50GHz
RAM : 512Mo

dubcek · Answer

et comme ça
$ readarray A < fichier_donnees ; for M in $(cat fichier_motif) ; do grep -q $M <<<"${A[@]}" || echo $M ; done

mortelrdv · Answer

j'ai
-bash: readarray: command not found



PS : 
@mamiemando
étant scripteur du dimanche, je ne vais donc pas trop entrer les optimisations que tu proposes  ;)

dubcek · Answer

avec quel awk as-tu testé, celui du post 3 ou du post 5 ?   
quelle est ta version de bash ?   
$ bash --version   
GNU bash, version 4.1.5(1)-release (i486-pc-linux-gnu)
essayer  
$ IFS=$'
' ; A=($(< fichier_donnees)) ; for M in $(cat fichier_motif) ; do grep -q $M <<<${A[@]} || echo $M ; done

Grep et fichier motifs ?

9 réponses

Discussions similaires