Как быстро найти и заменить многие элементы в списке без замены ранее замененных элементов в BASH? - PullRequest
Новая
       18

Как быстро найти и заменить многие элементы в списке без замены ранее замененных элементов в BASH?

1 голос
/ 05 ноября 2011

Я хочу выполнить несколько операций поиска и замены над текстом. У меня есть файл CSV UTF-8, содержащий то, что найти (в первом столбце) и чем его заменить (во втором столбце), упорядоченный от самого длинного до самого короткого.

например:. 

orange,fruit2
carrot,vegetable1
apple,fruit3
pear,fruit4
ink,item1
table,item2

Оригинальный файл: 

"I like to eat apples and carrots"

Результирующий выходной файл: 

"I like to eat fruit3s and vegetable1s."

Тем не менее, я хочу убедиться, что если одна часть текста уже была заменена, то это не мешает тексту, который уже был заменен. Другими словами, я не хочу, чтобы это выглядело так (оно соответствует «таблице» из vegetable1): 

"I like to eat fruit3s and vegeitem21s."

В настоящее время я использую этот метод, который довольно медленный, потому что я должен сделать весь поиск и заменить дважды:

(1) Преобразовать CSV в три файла, например ::

a.csv     b.csv   c.csv
orange    0001    fruit2
carrot    0002    vegetable1
apple     0003    fruit3
pear      0004    fruit4
ink       0005    item1
table     0006    item 2

(2) Затем замените все элементы из a.csv в file.txt на соответствующий столбец в b.csv, используя ZZZ вокруг слов, чтобы убедиться, что позже не будет ошибок при сопоставлении чисел: 

a=1
b=`wc -l < ./a.csv`
while [ $a -le $b ]
do
    for i in `sed -n "$a"p ./b.csv`; do
        for j in `sed -n "$a"p ./a.csv`; do
            sed -i "s/$i/ZZZ$j\ZZZ/g" ./file.txt
            echo "Instances of '"$i"' replaced with '"ZZZ$j\ZZZ"' ("$a"/"$b")."
            a=`expr $a + 1`
            done
    done
done

(3) Затем снова запустите этот же скрипт, но замените ZZZ0001ZZZ на fruit2 из c.csv.

Выполнение первой замены занимает около 2 часов, но поскольку я должен выполнить этот код дважды, чтобы избежать редактирования уже замененных элементов, это занимает вдвое больше времени. Есть ли более эффективный способ выполнить поиск и замену, который не выполняет замены для уже замененного текста?

Ответы [ 9 ]

6 голосов
/ 09 июля 2013

Вот решение Perl, которое выполняет замену в «одну фазу». 

#!/usr/bin/perl
use strict;
my %map = (
       orange => "fruit2",
       carrot => "vegetable1",
       apple  => "fruit3",
       pear   => "fruit4",
       ink    => "item1",
       table  => "item2",
);
my $repl_rx = '(' . join("|", map { quotemeta } keys %map) . ')';
my $str = "I like to eat apples and carrots";
$str =~ s{$repl_rx}{$map{$1}}g;
print $str, "\n";
3 голосов
/ 09 июля 2013

Tcl имеет команду, чтобы сделать именно это: string map

tclsh <<'END'
set map {
    "orange" "fruit2"
    "carrot" "vegetable1"
    "apple" "fruit3"
    "pear" "fruit4"
    "ink" "item1"
    "table" "item2"
}
set str "I like to eat apples and carrots"
puts [string map $map $str]
END

I like to eat fruit3s and vegetable1s

Вот как это реализовать в bash (требуется bash v4 для ассоциативного массива) 

declare -A map=(
    [orange]=fruit2
    [carrot]=vegetable1
    [apple]=fruit3
    [pear]=fruit4
    [ink]=item1
    [table]=item2
)
str="I like to eat apples and carrots"
echo "$str"
i=0
while (( i < ${#str} )); do
    matched=false
    for key in "${!map[@]}"; do
        if [[ ${str:$i:${#key}} = $key ]]; then
            str=${str:0:$i}${map[$key]}${str:$((i+${#key}))}
            ((i+=${#map[$key]}))
            matched=true
            break
        fi
    done
    $matched || ((i++))
done
echo "$str"

I like to eat apples and carrots
I like to eat fruit3s and vegetable1s

Это не будет быстрым.

Очевидно, что вы можете получить другие результаты, если вы по-другому заказываете карту. На самом деле, я считаю, что порядок "${!map[@]}" не указан, поэтому вы можете явно указать порядок ключей: 

keys=(orange carrot apple pear ink table)
# ...
    for key in "${keys[@]}"; do
2 голосов
/ 05 ноября 2011

Один из способов сделать это - выполнить двухфазную замену: 

phase 1:

s/orange/@@1##/
s/carrot/@@2##/
...

phase 2:
s/@@1##/fruit2/
s/@@2##/vegetable1/
...

Маркеры @@ 1 ## следует выбирать так, чтобы они не появлялись в исходном тексте или замене курса.

Вот реализация концепции в Perl: 

#!/usr/bin/perl -w
#

my $repls = $ARGV[0];
die ("first parameter must be the replacement list file") unless defined ($repls);
my $tmpFmt = "@@@%d###";

open(my $replsFile, "<", $repls) || die("$!: $repls");
shift;

my @replsList;

my $i = 0;
while (<$replsFile>) {
    chomp;
    my ($from, $to) = /\"([^\"]*)\",\"([^\"]*)\"/;
    if (defined($from) && defined($to)) {
        push(@replsList, [$from, sprintf($tmpFmt, ++$i), $to]);
    }
}

while (<>) {
    foreach my $r (@replsList) {
        s/$r->[0]/$r->[1]/g;
    }
    foreach my $r (@replsList) {
        s/$r->[1]/$r->[2]/g;
    }
    print;
}
1 голос
/ 16 июля 2013

Здесь уже есть много интересных ответов.Я публикую это, потому что я придерживаюсь немного другого подхода, делая некоторые большие предположения о данных для замены (на основе данных примера):

  1. Слова для замены не содержат пробелов
  2. Слова заменяются на основе самого длинного, точно совпадающего префикса
  3. Каждое слово для замены точно представлено в csv

Это единственный проход, ответ только на awk сочень небольшое регулярное выражение.

Он считывает файл "repl.csv" в ассоциативный массив (см. BEGIN {}), а затем пытается сопоставить префиксы каждого слова, когда длина слова ограничена длиной ключа.ограничивает, стараясь по возможности избегать поиска в ассоциативном массиве: 

#!/bin/awk -f

BEGIN {
    while( getline repline < "repl.csv" ) {
        split( repline, replarr, "," )
        replassocarr[ replarr[1] ] = replarr[2]
            # set some bounds on the replace word sizes
        if( minKeyLen == 0 || length( replarr[1] ) < minKeyLen )
            minKeyLen = length( replarr[1] )
        if( maxKeyLen == 0 || length( replarr[1] ) > maxKeyLen )
            maxKeyLen = length( replarr[1] )
    }
    close( "repl.csv" )
}

{
    i = 1
    while( i <= NF ) { print_word( $i, i == NF ); i++ }
}

function print_word( w, end ) {
    wl = length( w )
    for( j = wl; j >= 0 && prefix_len_bound( wl, j ); j-- ) {
        key = substr( w, 1, j )
        wl = length( key )
        if( wl >= minKeyLen && key in replassocarr ) {
            printf( "%s%s%s", replassocarr[ key ],
                substr( w, j+1 ), !end ? " " : "\n" )
            return
        }
    }
    printf( "%s%s", w, !end ? " " : "\n" )
}

function prefix_len_bound( len, jlen ) {
    return len >= minKeyLen && (len <= maxKeyLen || jlen > maxKeylen)
}

На основе таких вводных данных, как: 

I like to eat apples and carrots
orange you glad to see me
Some people eat pears while others drink ink

.Конечно, любая «экономия», связанная с отсутствием поиска replassocarr, исчезает, когда заменяемые слова переходят в length = 1 или если средняя длина слова намного больше, чем заменяемые слова.

1 голос
/ 15 июля 2013

Это может работать для вас (GNU sed): 

sed -r 'h;s/./&\\n/g;H;x;s/([^,]*),.*,(.*)/s|\1|\2|g/;$s/$/;s|\\n||g/' csv_file | sed -rf - original_file

Преобразовать файл csv в скрипт sed.Хитрость здесь в том, чтобы заменить строку замещения на строку, которая не будет заменена заново.В этом случае каждый символ в строке подстановки заменяется собой и \n.Наконец, когда все замены выполнены, \n удаляются, оставляя готовую строку.

1 голос
/ 12 июля 2013

AKK + SED подход: 

awk -F, '{a[NR-1]="s/####"NR"####/"$2"/";print "s/"$1"/####"NR"####/"}; END{for (i=0;i<NR;i++)print a[i];}' replace-list.csv > /tmp/sed_script.sed
sed -f /tmp/sed_script.sed input.txt

Подход кошка + седь + седь: 

cat -n replace-list.csv | sed -rn 'H;g;s|(.*)\n *([0-9]+) *[^,]*,(.*)|\1\ns/####\2####/\3/|;x;s|.*\n *([0-9]+)[ \t]*([^,]+).*|s/\2/####\1####/|p;${g;s/^\n//;p}' > /tmp/sed_script.sed
sed -f /tmp/sed_script.sed input.txt

Механизм:

  1. Здесь он сначала генерирует скрипт sed, используя csv в качестве входного файла.
  2. Затем использует другой экземпляр sed для работы с input.txt

Примечания:

  1. Сгенерированный промежуточный файл - sed_script.sed можно использовать повторно, если только не изменился входной CSV-файл.
  2. ####<number>#### выбран в качестве некоторого шаблона, которого нет во входном файле. Измените этот шаблон, если требуется.
  3. cat -n | не является UUOC:)
1 голос
/ 11 июля 2013

Подход bash + sed: 

count=0
bigfrom=""
bigto=""

while IFS=, read from to; do
   read countmd5sum x < <(md5sum <<< $count)
   count=$(( $count + 1 ))
   bigfrom="$bigfrom;s/$from/$countmd5sum/g"
   bigto="$bigto;s/$countmd5sum/$to/g"
done < replace-list.csv

sed "${bigfrom:1}$bigto" input_file.txt

Я выбрал md5sum для получения уникального токена.Но некоторый другой механизм также может быть использован для генерации такого токена;как чтение из /dev/urandom или shuf -n1 -i 10000000-20000000

1 голос
/ 09 июля 2013

Я полагаю, что большая часть вашей медлительности связана с созданием большого количества команд sed, каждая из которых должна индивидуально обрабатывать весь файл. Некоторые незначительные изменения в вашем текущем процессе могут значительно ускорить это, запустив 1 sed на файл на шаг. 

a=1
b=`wc -l < ./a.csv`
while [ $a -le $b ]
do
    cmd=""
    for i in `sed -n "$a"p ./a.csv`; do
        for j in `sed -n "$a"p ./b.csv`; do
            cmd="$cmd ; s/$i/ZZZ${j}ZZZ/g"
            echo "Instances of '"$i"' replaced with '"ZZZ${j}ZZZ"' ("$a"/"$b")."
            a=`expr $a + 1`
        done
    done

    sed -i "$cmd" ./file.txt
done
1 голос
/ 09 июля 2013

Выполнение этого дважды, вероятно, не ваша проблема. Если бы вам удалось сделать это один раз, используя базовую стратегию, это все равно заняло бы у вас час, верно? Вам, вероятно, нужно использовать другую технологию или инструмент. Переключение на Perl, как указано выше, может сделать ваш код намного быстрее (попробуйте)

Но, продолжая идти по пути других постеров, следующим шагом может стать конвейерная обработка. Напишите небольшую программу, которая заменяет два столбца, затем запустите эту программу дважды одновременно. При первом запуске строки в столбце 1 заменяются строками в столбце 2, а в следующем случае строки в столбце 2 заменяются строками в столбце 3.

Ваша командная строка будет выглядеть так 

cat input_file.txt | perl replace.pl replace_file.txt 1 2 | perl replace.pl replace_file.txt 2 3 > completely_replaced.txt

И replace.pl был бы таким (аналогично другим решениям) 

#!/usr/bin/perl -w

my $replace_file = $ARGV[0];
my $before_replace_colnum = $ARGV[1] - 1;
my $after_replace_colnum = $ARGV[2] - 1;

open(REPLACEFILE, $replace_file) || die("couldn't open $replace_file: $!");

my @replace_pairs;

# read in the list of things to replace
while(<REPLACEFILE>) {
    chomp();

    my @cols = split /\t/, $_;
    my $to_replace = $cols[$before_replace_colnum];
    my $replace_with = $cols[$after_replace_colnum];

    push @replace_pairs, [$to_replace, $replace_with];
}

# read input from stdin, do swapping
while(<STDIN>) {
    # loop over all replacement strings
    foreach my $replace_pair (@replace_pairs) {
        my($to_replace,$replace_with) = @{$replace_pair};
        $_ =~ s/${to_replace}/${replace_with}/g;
    }
    print STDOUT $_;
}
...