Используя grep -f, чтобы найти шаблон, который имеет совпадения

Question

Я пытаюсь дать grep файл шаблона (через -f), но я хочу узнать, какие шаблоны соответствуют чему-либо в файле поиска

Например, задано 1.txt:

a/(.*)
b/(.*)
b/c/(.*)
b/foo/(.*)
d/(.*)
e/(.*)

и 2.txt:

a/
a/foo/bar/
b/foo/
d/foo/

Шаблоны из 1.txt, которые соответствуют чему-то в 2.txt, (без суффикса (.*)) следующие:

a/
b/
b/foo/
d/

Как я могу "найти список шаблонов, у которых есть совпадение"?

РЕДАКТИРОВАТЬ: Я только ищу совпадение префикса, но я думаю, чтовопрос достаточно интересен для общего сопоставления с образцом.

---

РЕДАКТИРОВАТЬ: Поскольку дано решение на основе for -циклов, я должен сказать, что я не смотрю на вызов grep 10000раз.:) Рабочее решение, которое у меня уже есть (указано ниже), довольно медленное:

for line in "${file1_arr[@]}"; do
  if ! grep -qE "^$v(.*)\$"; then
    echo "$line"
  fi
done

В идеале я ищу один grep вызов или около того с меньшими накладными расходами.

Answer 1

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

Вот в основном все.

text="$(cat 2.txt)"                   # read 2.txt

while read -r line; do                # for each 'line' from 1.txt
    re=[^\b]*${line}                  # prepend ^ or \b to the pattern
    if [[ "$text" =~ $re ]]; then     # match the pattern to 2.txt
        echo "${line}"                # if there's a match, print the pattern
    fi
done < <(cat "1.txt")

Так как это не порождает никаких дополнительных процессов, а просто делает это в памяти, я подозреваю, что это довольно эффективно.Мои тесты с файлами, которые я связал под ответом Джеймса, показывают 8-9 секунд для этого.

Answer 2

В awk:

$ awk 'NR==FNR{a[$0]=FNR;next}{for(i in a)if($0 ~ i)print i,$0}' 1.txt 2.txt
a/(.*) a/
a/(.*) a/foo/bar
b/(.*) b/foo
d/(.*) d/foo

Объяснено:

$ awk '                 # yes
NR==FNR {               # process first file
    a[$0]=FNR           # hash regex, store record number just in case
    next                # process next record
}
{                       # process second file
    for(i in a)         # loop every entry in 1.txt
        if($0 ~ i)      # if regex matches record 
            print i,$0} # print all matching regex and record
' 1.txt 2.txt           

Редактировать: Вывести каждое регулярное выражение только один раз (как показано здесь в ожидаемом результате) вы можете delete регулярное выражение из a, как только оно будет использовано, таким образом, оно не будет сопоставлено и выдано более одного раза:

$ awk '
NR==FNR { a[$0]; next }
{
    for(i in a)
        if($0 ~ i) {
            print i
            delete a[i]      # deleted regex wont get matched again
        }
}' 1.txt 2.txt
vendor/cloud.google.com/go/compute/metadata/(.*)$
vendor/cloud.google.com/go/compute/(.*)$
vendor/cloud.google.com/go/(.*)$
vendor/cloud.google.com/(.*)$
vendor/github.com/Azure/azure-sdk-for-go/arm/dns/(.*)$
vendor/github.com/Azure/azure-sdk-for-go/arm/(.*)$
vendor/github.com/Azure/azure-sdk-for-go/(.*)$
vendor/github.com/Azure/(.*)$
vendor/github.com/(.*)$

Также, Мой тест показал примерно на 60% (мини-ноутбук, от 1:16 до 29 с) время с этой модификацией для GNU awk (используя данные, которые вы предоставили в комментариях, file1.txt и file2.txt):

$ awk '
BEGIN {
    FS="."                   # . splits the url
}
NR==FNR { a[$1][$0]; next }  # we index on the first part of url
{
    for(i in a[$1])          # search space decreased
        if($0 ~ i) {
            print i
            delete a[$1][i]
    }
}' file1.txt file2.txt

Ускорение уменьшает пространство поиска за счет использования начала строк до первого периода в качестве ключа для хэша, т. Е.:

FS="."                                           # split at first .
...
a[vendor/github][vendor/github.com/Azure/(.*)$]  # example of a hash
...
for(i in a[$1])                                  # search space decreased

Теперь не нужно искать весьхеш для соответствующего регулярного выражения.Возможно, более практичным было бы использовать FS="/" ; a[$1 FS $2], но это был всего лишь быстрый тест.

Answer 3

Я не вижу решения с grep, но sed является альтернативой awk.С sed я хотел бы видеть шаблоны типа b/foo/.* в 1.txt, но я покажу решение на основе (.*).
Целью первой команды является создание конструкций sed, которые будутзамените строку ввода регулярным выражением, если оно совпадает с регулярным выражением.Различные выходные строки должны выглядеть следующим образом:

sed -rn 's#b/c/(.*)#b/c/#p' 2.txt

, и это можно сделать с помощью

# Use subprocess 
sed 's/\(.*\)\(([.][*])\)/s#\1\2#\1#p/' 1.txt
# resulting in
sed -rnf <(sed 's/\(.*\)\(([.][*])\)/s#\1\2#\1#p/' 1.txt) 2.txt| sort -u

Решение немного сложное для чтения, что вызвало bij макет 1.txt, гдеЯ хотел бы строки как b/foo/.*.

Вышеуказанные команды будут иметь 2 ошибки:

Когда совпадение находится на части строки, несоответствующая часть будет показана в выходных данных.Это можно исправить с помощью сопоставления мусора

# Use lines like 's#.*b/foo(.*)#b/foo#p'
sed -rnf <(sed 's/\(.*\)\(([.][*])\)/s#.*\1\2#\1#p/' 1.txt) 2.txt| sort -u

Вторая ошибка заключается в том, что строки в 2.txt, имеющие два совпадения, будут сопоставляться только один раз (первое совпадение будет редактировать строку в потоке).
Это можно исправить, добавив некоторый уникальный маркер (я буду использовать \a) для совпадающих строк и повторив строки ввода на выходе (с \n&).Вывод можно просмотреть, выполнив поиск маркеров \a.

sed -rnf <(sed 's/\(.*\)\(([.][*])\)/s#.*\1\2#\\a\1\\n\&#p/' 1.txt) 2.txt| 
sed -rn '/\a/ s/.(.*)/\1/p' | sort -u

РЕДАКТИРОВАТЬ:
Обход с маркером и восстановление исходного ввода не требуется, если вы придерживаетесь другого подхода.
В sed вы можете распечатать что-то на стандартный вывод без изменения потока.
Одна из возможностей (медленная для этой ситуации) - использовать

sed '/something/ eecho "something" '

Другая возможность - использовать команду "x" (который обменивает пространство образца с буфером удержания).Вы действительно хотите иметь сценарий sed с такими командами, как

\%a/% {h;s%.*%a/%p;x}
\%b/% {h;s%.*%b/%p;x}
\%b/c/% {h;s%.*%b/c/%p;x}
\%b/foo/% {h;s%.*%b/foo/%p;x}
\%d/% {h;s%.*%d/%p;x}
\%e/% {h;s%.*%e/%p;x}

. При использовании вышеуказанного метода решение sed упрощается до

sed -nf <(
   sed 's#([.][*])##; s#.*#\\%&% {h;s%.*%&%p;x} #'  1.txt
   ) 2.txt | sort -u

Когда файл 1.txt не изменяетсячасто вам может понадобиться предварительно обработать этот файл.

sed 's#([.][*])##; s#.*#\\%&% {h;s%.*%&%p;x} #'  1.txt > /tmp/sed.in
sed -nf /tmp/sed.in 2.txt | sort -u

Answer 4

Следующий скрипт:

#!/usr/bin/env bash                                                               

lines=$(wc -l < 1.txt)                                                          
for (( i=1; i<=$lines; i++ )); do                                               
    line=$(sed -n "$i"p 1.txt)                                                  
    line=$(sed "s/\/(.*)$//" <<< "$line")                                       
    grep -E "$line" 2.txt 1>/dev/null && echo "$line"                           
done                                                                            

печатает строки в 1.txt, которые соответствуют 2.txt:

a                                                                               
b                                                                               
b/foo                                                                           
d                                                                               

комментарии:

# gets a single line from 1.txt
line=$(sed -n "$i"p 1.txt)                                                  

# removes trailing pattern /(.*) from $line variable
line=$(sed "s/\/(.*)$//" <<< "$line")

# if $line matches in 2.txt, print $line
grep -E "$line" 2.txt 1>/dev/null && echo "$line"