поиск позиции многострочного текста

#c #unix #shell

имеется большой текстовый файл1. например:

a
b
c
d
e


имеется другой текстовый файл2 с несколькими строками. например:

b
c
d


как с помощью posix-утилит (или хотя бы gnu-утилит, а в крайнем случае — на максимально
платформо-неспецифичном си) найти номер строки в первом файле, начиная с которой эти
файлы совпадают? для приведённого примера — это будет 2 (начиная со второй строки в
первом файле содержатся точно такие же строки, как и во втором).



на данный момент нашёл лишь способ узнать, входит ли второй файл в первый:

$ grep -qzP "$(sed ':a;N;$!ba;s/\n/\\n/g' файл2)" файл1 && echo входит


но он не позволяет узнать номер строки, с которой началось совпадение.

пояснение по поводу программы для sed: она заменяет каждый перевод строки в файле2
на два символа \n (обратный слэш и n), чтобы получилось регулярное выражение для grep-а.
позаимстовавана отсюда: How can I replace a newline (\n) using sed?.
    

Ответы

Ответ 1

C помощью patch

if line=$(diff -U0 файл2 /dev/null | patch -f --dry-run файл1 - | sed -rn 's/^Hunk
#1 succeeded at ([0-9]+) .*/\1/p; /FAILED/ q1')
then echo строка ${line:-1}
else echo фрагмент не найден
fi


Создаём патч удаляющий из файла-образца все строки и пытаемся его применить ко второму
файлу в режиме проверки (dry-run). Если это возможно, patch  сообщает найденное смещение,
если оно не нулевое. Если нет - сообщает об ошибке.

С помощью diff.

Это был мой первый вариант, оставил его на всякий случай. Вроде работает, но как
поведёт себя с очень большими файлами, не знаю:

diff -U0 файл2 файл1 | sed -rn '1!{/^-/q1}; 3{s/@@ -0,0 \+(1,([0-9]+)|(1)).*/\2\3/p};
/^@@ -[1-9]/ {G; h; /@@\n@@/ q1 }'


Только строки нумеруются с 0.

Возможно будет неоправданно долго работать с большим файлом, так как diff будет выводить
весь файл1 несовпадающий с файл2.

Если совпадений нет и при частичном совпадении возвращает статус 1, текст при этом
стоит игнорировать.
Если файлы совпадают с самого начала, ничего не выводится, статус=0.

Пояснения по программе.

diff -U0 выдаёт патч в унифицированном формате без контекстных строк.

Первая группа отлавливает строки начинающиеся с минуса, кроме первой строки. Если
такие строки присутствуют, значит diff не нашёл какой-то строки из файл2, программа
завершается с кодом ошибки 1.

Вторая группа отлавливает начало фрагмента который diff считает, как добавленное
перед строками из файл2. Отсюда берётся число строк этого фрагмента. Заголовок этого
фрагмента должен выглядеть как @@ -0,0 +1,n @@, где n - количество его строк. n равное
1 опускается.

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


Ответ 2

придумал вариант на awk (скрипт.awk):

BEGIN {
  n=1 # инициализируем номер строки
  r=1 # умолчальный код возврата - 1
} 

{
  # если удалось прочитать следующую строку из файла2
  if ((getline l < f2) > 0) {
    if (l!=$0) { # и она не равна очередной строке из файла1
      close(f2)  # то закрываем файл2 (очередной getline откроет его заново)
      n=NR+1     # кандидатом на совпадение считаем следующую строку файла1
    }
  } else {   # если файл2 закончился
    r=0      # код возврата - 0 (удача)
    print n  # номер строки, где началось совпадение
    nextfile # завершаем чтение текущего файла
             # а так он единственный - файл1 - то это означает переход
             # к секции END
  } 
} 

END {
  exit r # завершаем программу с указанным кодом возврата
}


вызывать так:

$ awk -v f2=файл2 -f скрипт.awk файл1


имя второго файла передаётся через переменную f2.

возвращает либо номер строки из файла1, начиная с которой файл2 целиком содержится
в файл1, либо ничего и код возврата — 1 («нет совпадения»).

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



$ awk 'BEGIN{f2="файл2";n=1;r=1}{if((getline l0){if(l!=$0){close(f2);n=NR+1}}else{r=0;print
n;nextfile}}END{exit r}' файл1


Ответ 3

Чтобы напечатать, где строки, общие для обоих файлов, начинаются в файл1:



$ diff \
    --old-group-format='' \
    --changed-group-format='' \
    --new-group-format='' \           
    --unchanged-group-format='%df'$'\n' файл1 файл2
2


Line Group Formats.




  глобальная задача — слить два частично пересекающихся файла: некоторое неизвестное
количество строк в конце одного файла повторяется в начале другого, и требуется получить
в одном файле: уникальные строки из первого, затем общие строки, затем уникальные строки
из второго.


#!/bin/bash
function cleanup {
  rm -rf sorted{1,2}
}
trap cleanup EXIT

# sort, remove duplicates
sort -u файл1 > sorted1
sort -u файл2 > sorted2

# print unique lines from файл1
comm -23 sorted{1,2}
# print common lines 
comm -12 sorted{1,2}
# print unique lines from файл2
comm -13 sorted{1,2}



  в данном случае сортировка исключается: 1. важен порядок строк; 2. многие строки
могут неоднократно повторяться. примерная аналогия: частично перекрывающиеся лог-файлы
без меток времени


Чтобы объединить файлы, содержащие общие строчки:

$ diff \
--old-group-format='%<' \
--new-group-format='%>' \
old new


Ответ 4

Вариант на Си для *nix с использованием mmap, для максимальной экономии памяти.

// avp 2016 find one file (av[2]) into other file (av[1])
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

struct fmap {
  char *data; // don't maps empty (filesize == 0) files
  size_t len; // filesize from fstat
  int errn;   // errno after mapfile() (0 for empty file !!!)
};


struct fmap
mapfile (const char *fn)
{
  struct fmap fm = {0, 0, EINVAL}; // it's for C++ (it can't {.errn=EINVAL})

  if (fn) {
    int old = errno;
    errno = 0;
    int fd = open(fn, O_RDONLY);
    struct stat st;

    if (fd > -1)
      if ((fstat(fd, &st), fm.len = st.st_size) &&
          (fm.data = (char *)mmap(NULL, st.st_size,
                                  PROT_READ, MAP_PRIVATE, fd, 0))) {
        madvise(fm.data, fm.len, MADV_SEQUENTIAL);
        close(fd);
      }
    fm.errn = errno;
    errno = old;
  }

  return fm;
}

static inline size_t skipnl (struct fmap *p, size_t from) {
  while (from < p->len && p->data[from++] != '\n');

  return from;
}

int
main (int ac, char *av[])
{
  if (ac != 3)
    err(EX_USAGE,
        "search file2 in file1 (by lines) Usage: %s file1 file2", av[0]);
  struct fmap f1 = mapfile(av[1]),
    f2 = mapfile(av[2]);

  if (!f1.data) 
    (errno = f1.errn) ? err(EX_DATAERR, "file %s", av[1]) :
                        errx(EX_DATAERR, "empty file %s", av[1]);
  if (!f2.data)
    (errno = f2.errn) ? err(EX_DATAERR, "file %s", av[2]) :
                        errx(EX_DATAERR, "empty file %s", av[2]);

  size_t i = 0,
    lineno = 0, // current line number in f1
    n2l = 0;    // number of '\n' in f2 (for adjust lineno when found f2 in f1)
  for (i = 0; i < f2.len; i++)
    if (f2.data[i] == '\n')
      n2l++;
  // continue search after successful matching from the beginning of new line
  int need_skipnl = f2.data[f2.len - 1] != '\n';

  i = 0;
  while (i < f1.len) {
    if (memcmp(f1.data + i, f2.data, f2.len) == 0) {
      printf("%ld\n", (long)lineno + 1);
      lineno += n2l;
      i += f2.len;
      if (need_skipnl)
        i = skipnl(&f1, i), lineno++;
    } else
      i = skipnl(&f1, i), lineno++;
  }

  return munmap(f1.data, f1.len) + munmap(f2.data, f2.len) ? EX_OSERR : 0;
}


Возможно стоит как-то по другому спроектировать коды возврата. Например, если ничего
не найдено, возвращать 1 (сейчас  (ubuntu /usr/include/sysexits.h) возвращает 0, 64,
65 и 71).

P.S.
граничные условия (размеры файлов кратны странице) не тестировал.