使用 Bash 计算子字符串*在非常大的文件中*的重叠出现次数

Question

我有几十千兆字节(基因组数据)的文件，我需要在其中找到子字符串的出现次数。虽然我在这里看到的答案使用grep -o然后wc -l，这似乎是一种黑客方式，可能不适用于我需要处理的非常大的文件。

grep -o/wc -l方法对于大文件是否具有良好的扩展性？如果没有，我还能怎么做呢？

例如

aaataaaagtcgaaaaagtccatgcatatgatacttttttttttttttttt
111
222
333
444
555
666 

必须返回 6 次出现才能aaa。(除了可能还有1000万行。

Answer 1

在字符串中找到 6 个重叠的子字符串aaa

line="aaataaaagtcgaaaaagtccatgcatatgatacttttttttttttttttt"

你不想看到字符串，你想计算它们。 当你尝试时

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

您缺少重叠的字符串。
使用子字符串aaa您在aaaaaaa中有 5 次命中，那么如何处理${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"简单"，那么其他搜索字符串呢？
我认为您必须寻找子字符串并考虑一个适用于该子字符串的公式。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))"

当您有一个大文件时，您可能希望先拆分它。

Answer 2

我想有两种方法(两种方法都报告了 2 条测试行的29/6)：

1. 使用求和方法：

   # WHINY_USERS=1 is a shell param for mawk-1 to pre-sort array
   ${input……} | WHINY_USERS=1 {m,g}awk '
   BEGIN {
   1      FS = "[^a]+(aa?[^a]+)*"
   1      OFS = "|"
   1      PROCINFO["sorted_in"] = "@ind_str_asc"
   } {
   2        _ = ""
   2      OFS = "|"
   2      gsub("^[|]*|[|]*$",_, $!(NF=NF))
   2      split(_,__)
   split($-_,___,"[|]+")
   12      for (_ in ___) {
   12          __[___[_]]++
   }
   2      _____=____=_<_
   2      OFS = "t"
   2      print " -- line # "(NR)
   7      for (_ in __) {
   7          print sprintf(" %20s",_), __[_], 
   ______=__[_] * (length(_)-2),
   "| "(____+=__[_]), _____+=______
   }
   print "" }'
   

|

-- line # 1
aaa   3   3   | 3 3
aaaa   2   4   | 5 7
aaaaa   3   9   | 8 16
aaaaaaaaaaaaaaa   1   13  | 9 29
-- line # 2
aaa   1   1   | 1 1
aaaa   1   2   | 2 3
aaaaa   1   3   | 3 6

2. 打印出该子字符串的所有副本：

   {m,g}awk' {
   2   printf("%s%.*s",____=$(_=_<_),_, NF=NF)
   9   do { _+=gsub(__,_____)
   } while(index($+__,__))
   2   if(_) {
   2       ____=substr(____,-_<_,_)
   2       gsub(".", (":")__, ____)
   2       print "}-[(# " (_) ")]--;fb" substr(____, 2)
   } else { print "" } }' FS='[^a]+(aa?[^a]+)*' OFS='|' __='aaa' _____='aa'  
   

|

aaagtcgaaaaagtccatgcaaataaaagtcgaaaaagtccatgcatatgatactttttttttt
tttttttaaagtcgaaaaagaaaaaaaaaaaaaaatataaaatccatgc}-[(# 29)]--;

aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:
aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa:aaa
aaataaaagtcgaaaaagtccatgcatatgatacttttttttttttttttt}-[(# 6)]--;
aaa:aaa:aaa:aaa:aaa:aaa