Подсчет перекрывающихся вхождений подстроки * в очень большом файле * с использованием Bash

Question

У меня есть файлы порядка нескольких десятков гигабайт (данные генома), по которым мне нужно найти количество вхождений для подстроки. Хотя ответы, которые я здесь видел, используют grep -o, а затем wc -l, это выглядит как хакерский способ, который может не работать с очень большими файлами, с которыми мне нужно работать.

Имеет ли grep -o / wc -l метод масштабирования хорошо для больших файлов? Если нет, то как еще мне go сделать это?

Например,

aaataaaagtcgaaaaagtccatgcatatgatacttttttttttttttttt
111
    222
     333
            444
             555
              666 

должен вернуть 6 вхождений для aaa. (За исключением, может быть, еще 10 миллионов строк этого.)

Answer 1

Найдите 6 перекрывающихся подстрок aaa в строке

line="aaataaaagtcgaaaaagtccatgcatatgatacttttttttttttttttt"

Вы не хотите видеть строки, вы хотите их посчитать. Когда вы пытаетесь

# wrong
grep -o -F "aaa" <<< "${line}" | wc -l

, вам не хватает перекрывающихся строк.
С подстрокой aaa у вас есть 5 попаданий в aaaaaaa, так как же обрабатывать ${line}?
Начните с

grep -Eo "a{3,}" <<< "${line}"

Результат

aaa
aaaa
aaaaa

Сколько у нас хитов? 1 для aaa, 2 для aaaa и 3 для aaaaa. Сравните общее количество символов с количеством строк (wc):

 match lines chars  add_to_total
   aaa     1     4      1
  aaaa     1     5      2
 aaaaa     1     6      3

Для каждой строки вычтите 3 из общего количества символов для этой строки.
Когда результат содержит 3 строки и 15 символов, рассчитать

15 characters - (3 lines * 3 characters) = 15 - 9 = 6

В коде:

read -r lines chars < <(grep -Eo "a{3,}" <<< "${line}" | wc -lc)
echo "Substring count: $((chars - (3 * lines)))"

Или для файла

read -r lines chars < <(grep -Eo "a{3,}" "${file}" | wc -lc)
echo "Substring count: $((chars - (3 * lines)))"

aaa было "легко", как насчет других searchstrings?
Я думаю, вам нужно искать подстроку и думать о формуле, которая работает для этой подстроки. abcdefghi не будет иметь перекрывающихся строк, но abcdabc может.
Потенциальные совпадения с abcdabc:

abcdabc
abcdabcdabc
abcdabcdabcdabc

Использовать тестовую линию

line="abcdabcdabcdabc something else abcdabcdabcdabc no match here abcdabc and abcdabcdabc"

вам нужно "abc(dabc)+" и иметь

          match   lines    chars  add_to_total
abcdabcdabcdabc       1      16    3
abcdabcdabcdabc       1      16    3
        abcdabc       1       8    1
    abcdabcdabc       1      12    2

Для каждой строки вычесть 4 из общего количества символов и разделить ответ на 4. Или (characters/4) - nr_line. Если результат содержит 4 строки и 52 символа, вычислите

(52 characters / fixed 4) / 4 lines = 13 - 4 = 9

В коде:

read -r lines chars < <(grep -Eo "abc(dabc)+" <<< "${line}" | wc -lc)
echo "Substring count: $(( chars / 4 - lines))"

Если у вас большой файл, вы можете сначала разделить его.