Remplacez plusieurs chaînes en une seule passe

11

Je cherche un moyen de remplacer les chaînes d'espace réservé dans un fichier de modèle par des valeurs concrètes, avec des outils Unix courants (bash, sed, awk, peut-être perl). Il est important que le remplacement soit effectué en un seul passage, c'est-à-dire que ce qui est déjà numérisé / remplacé ne doit pas être pris en compte pour un autre remplacement. Par exemple, ces deux tentatives échouent:

echo "AB" | awk '{gsub("A","B");gsub("B","A");print}'
>> AA

echo "AB" | sed 's/A/B/g;s/B/A/g'
>> AA

Le résultat correct dans ce cas est bien sûr BA.

En général, la solution doit être équivalente à balayer l'entrée de gauche à droite pour une correspondance la plus longue avec l'une des chaînes de remplacement données, et pour chaque correspondance, effectuer un remplacement et continuer à partir de ce point dans l'entrée (aucune des déjà lu, ni les remplacements effectués ne doivent être pris en compte pour les correspondances). En fait, les détails n'ont pas d'importance, juste que les résultats du remplacement ne sont jamais pris en compte pour un autre remplacement, en tout ou en partie.

REMARQUE Je recherche uniquement des solutions génériques correctes. Veuillez ne pas proposer de solutions qui échouent pour certaines entrées (fichiers d'entrée, recherche et remplacement de paires), aussi improbables qu'elles puissent paraître.

Ambroz Bizjak
la source
Je suppose qu'ils sont plus longs qu'un caractère? Pour cela, vous pouvez utiliser tr AB BA.
Kevin
3
Et franchement, je ne serais pas surpris si quelqu'un considérait votre note un peu grossière.
peterph
1
Comment vous attendez-vous à «n'obtenir que des solutions correctes» lorsque vous n'avez pas fourni d'échantillon d'entrée ou de sortie?
jasonwryan
1
Je crains que vous n'ayez besoin de le faire exactement comme vous le décrivez - analysez depuis le début et remplacez au fur et à mesure - c'est-à-dire pas avec des expressions régulières.
peterph
2
C'est une bonne question, mais la réponse est que vous avez besoin d'un analyseur de machine d'état , ce que fournit la réponse de rici (dans le vrai style des pirates, je pense). En d'autres termes, vous sous-estimez la complexité de la tâche, ala "Je veux analyser génériquement (HT | X) ML avec des expressions régulières" -> La réponse est NON. Vous ne pouvez pas (simplement) utiliser sed. Vous ne pouvez pas (simplement) utiliser awk. AFAIK, il n'y a aucun outil existant qui fera cela hors de la boîte. L'exploit de Sans rici, vous devez écrire du code.
goldilocks

Réponses:

10

OK, une solution générale. La fonction bash suivante nécessite des 2karguments; chaque paire se compose d'un espace réservé et d'un remplacement. C'est à vous de citer les chaînes de façon appropriée pour les passer dans la fonction. Si le nombre d'arguments est impair, un argument vide implicite sera ajouté, ce qui supprimera efficacement les occurrences du dernier espace réservé.

Ni les espaces réservés ni les remplacements ne peuvent contenir de caractères NUL, mais vous pouvez utiliser des C- \Escapes standard, par exemple \0si vous avez besoin de NULs (et par conséquent, vous devez écrire \\si vous voulez un \).

Il nécessite les outils de construction standard qui devraient être présents sur un système de type posix (lex et cc).

replaceholder() {
  local dir=$(mktemp -d)
  ( cd "$dir"
    { printf %s\\n "%option 8bit noyywrap nounput" "%%"
      printf '"%s" {fputs("%s", yyout);}\n' "${@//\"/\\\"}"
      printf %s\\n "%%" "int main(int argc, char** argv) { return yylex(); }"
    } | lex && cc lex.yy.c
  ) && "$dir"/a.out
  rm -fR "$dir"
}

Nous supposons qu'il \est déjà échappé si nécessaire dans les arguments, mais nous devons échapper les guillemets doubles, le cas échéant. C'est ce que fait le deuxième argument du second printf. Puisque l' lexaction par défaut est ECHO, nous n'avons pas à nous en préoccuper.

Exemple d'exécution (avec des horaires pour les sceptiques; c'est juste un ordinateur portable bon marché):

$ time echo AB | replaceholder A B B A
BA

real    0m0.128s
user    0m0.106s
sys     0m0.042s
$ time printf %s\\n AB{0000..9999} | replaceholder A B B A > /dev/null

real    0m0.118s
user    0m0.117s
sys     0m0.043s

Pour des entrées plus importantes, il pourrait être utile de fournir un indicateur d'optimisation ccet, pour la compatibilité Posix actuelle, il serait préférable d'utiliser c99. Une implémentation encore plus ambitieuse pourrait essayer de mettre en cache les exécutables générés au lieu de les générer à chaque fois, mais ils ne sont pas exactement coûteux à générer.

Éditer

Si vous avez tcc , vous pouvez éviter les tracas de la création d'un répertoire temporaire et profiter du temps de compilation plus rapide qui vous aidera sur les entrées de taille normale:

treplaceholder () { 
  tcc -run <(
  {
    printf %s\\n "%option 8bit noyywrap nounput" "%%"
    printf '"%s" {fputs("%s", yyout);}\n' "${@//\"/\\\"}"
    printf %s\\n "%%" "int main(int argc, char** argv) { return yylex(); }"
  } | lex -t)
}

$ time printf %s\\n AB{0000..9999} | treplaceholder A B B A > /dev/null

real    0m0.039s
user    0m0.041s
sys     0m0.031s
rici
la source
Je ne sais pas si c'est une blague ou pas;)
Ambroz Bizjak
3
@ambrozbizjak: Cela fonctionne, c'est rapide pour les grandes entrées et assez rapide pour les petites entrées. Il peut ne pas utiliser les outils auxquels vous pensiez, mais ce sont des outils standard. Pourquoi serait-ce une blague?
rici
4
+1 Pour ne pas être une blague! : D
goldilocks
Ce serait comme POSIX portable fn() { tcc ; } <<CODE\n$(gen code)\nCODE\n. Puis-je demander - c'est une réponse géniale et je l'ai votée dès que je l'ai lue - mais je ne comprends pas ce qui se passe avec le tableau de shell? Qu'est- "${@//\"/\\\"}"ce que cela fait?
mikeserv
@mikeserv: «Pour chaque argument sous la forme d'une valeur entre guillemets (" $ @ "), remplacez toutes les occurrences (//) d'une citation (\") par (/) une barre oblique inverse (\\) suivie d'une citation (\ ") ». Voir Extension des paramètres dans le manuel bash.
rici
1
printf 'STRING1STRING1\n\nSTRING2STRING1\nSTRING2\n' |
od -A n -t c -v -w1 |
sed 's/ \{1,3\}//;s/\\$/&&/;H;s/.*//;x
     /\nS\nT\nR\nI\nN\nG\n1/s//STRING2/
     /\nS\nT\nR\nI\nN\nG\n2/s//STRING1/
     /\\n/!{x;d};s/\n//g;s/./\\&/g' |
     xargs printf %b

###OUTPUT###

STRING2STRING2

STRING1STRING2
STRING1

Quelque chose comme ça ne remplacera toujours chaque occurrence de vos chaînes cibles qu'une seule fois car elles se produisent dans sed's in stream à une bouchée par ligne. C'est le moyen le plus rapide que j'imagine que vous feriez. Là encore, je n'écris pas C. Mais cela gère de manière fiable les délimiteurs nuls si vous le souhaitez. Voir cette réponse pour savoir comment cela fonctionne. Cela ne pose aucun problème avec les caractères de shell spéciaux contenus ou similaires - mais il est spécifique aux paramètres régionaux ASCII ou, en d'autres termes, odne produira pas de caractères multi-octets sur la même ligne et n'en fera qu'un par. Si c'est un problème, vous voudrez l'ajouter iconv.

mikeserv
la source
+1 Pourquoi dites-vous que cela ne remplace que "la première occurrence de vos chaînes cibles"? Dans la sortie, il semble qu'ils les remplacent tous. Je ne demande pas à le voir, mais cela pourrait-il être fait de cette façon sans coder en dur les valeurs?
goldilocks
@goldilocks - Oui - mais seulement dès qu'ils se produisent. Je devrais peut-être reformuler cela. Et oui - vous pouvez simplement ajouter un milieu sedet enregistrer jusqu'à une valeur nulle ou quelque chose, puis faire sedécrire le script de celui-ci; ou le mettre dans une fonction shell et lui donner des valeurs à une bouchée par ligne comme "/$1/"... "/$2/"- peut-être que j'écrirai ces fonctions aussi ...
mikeserv
Cela ne semble pas fonctionner dans le cas où les espaces réservés sont PLACE1, PLACE2et PLA. PLAgagne toujours. OP dit: "équivalent à balayer l'entrée de gauche à droite pour une correspondance la plus longue avec l'une des chaînes de remplacement données" (non souligné dans l'original)
rici
@rici - merci. Ensuite, je devrai faire les délimiteurs nuls. De retour en un éclair.
mikeserv
@rici - J'étais sur le point de publier une autre version, qui gérera ce que vous décrivez, mais en la regardant à nouveau et je ne pense pas que je devrais. Il dit le plus longtemps pour l' une des chaînes de remplacement données. Cela fait ça. Rien n'indique qu'une chaîne est un sous-ensemble d'une autre, seulement que la valeur remplacée peut l'être. Je ne pense pas non plus que l'itération sur une liste soit un moyen valable de résoudre le problème. Étant donné le problème tel que je le comprends, il s'agit d'une solution de travail.
mikeserv
1

Une perlsolution. Même si certains ont déclaré que ce n'était pas possible, j'en ai trouvé un, mais en général, une simple correspondance et remplacement n'est pas possible et même cela empire en raison du retour en arrière d'un NFA, le résultat peut être inattendu.

En général, et cela doit être dit, le problème donne des résultats différents qui dépendent de l'ordre et de la longueur des tuples de remplacement. c'est à dire:

A B
AA CC

et l'entrée se AAAtraduit par BBBou CCB.

Voici le code:

#!/usr/bin/perl

$v='if (0) {} ';
while (($a,$b)=split /\s+/, <DATA>) {
  $k.=$a.'|';
  $v.='elsif ($& eq \''.$a.'\') {print \''.$b.'\'} ';
}
$k.='.';
$v.='else {print $&;}';

eval "
while (<>) {
  \$_ =~ s/($k)/{$v}/geco;
}";  
print "\n";


__DATA__
A    B
B    A
abba baab
baab abbc
abbc aaba

Checkerbunny:

$ echo 'ABBabbaBBbaabAAabbc'|perl script
$ BAAbaabAAabbcBBaaba

la source