如何用awk处理无法载入内存的跨多行空格分隔数字序列替换

问题背景 #

当输入文件过大无法装入RAM，且空格分隔的数字序列跨多行时，需要实现指定序列的替换，要求处理过程中不加载整个文件到内存，同时正确处理跨多行的序列匹配，解决原实现中的回溯逻辑缺失问题。

示例输入 #

3  12  3   4
   0   6   7  10
   8   9  12   3
   4   6   7  8
  10  6   6   7
  9 199  10  11
  11

替换规则 #

• 将3 4替换为&
• 将6 7 8替换为9 9
• 将6 7 9替换为8 8
• 将7 10替换为11 12
• 将0替换为空
• 将10替换为13 10
• 将8 9 12 3 5替换为#

期望输出（每个结果占一行） #

3
12
&

6
11 12
8
9
12
&
9 9
13 10
6
8 8
199
13 10
11
11

原实现的问题 #

原尝试用awk模拟伪B树动态状态机，但存在回溯逻辑缺失的问题：当当前构建的状态路径不在前缀树中时，仅输出缓冲的第一个字符，没有考虑到长序列匹配失败但其中子序列是有效规则的情况，导致匹配错误或遗漏。

解决方案：前缀树+状态回溯的有限状态自动机 #

我们可以用前缀树（Trie）存储所有替换规则的前缀，维护当前状态链，同时记录所有可能的匹配位置，当无法继续匹配时回溯到最近的有效匹配点，确保所有规则都能被正确匹配，且逐token处理，不依赖内存加载整个文件。

修正后的awk代码 #

tr -s '[:space:]' '\n' < input.txt |
awk '
    BEGIN {
        # 构建前缀树：state_map[当前状态, token] = 下一个状态
        # replace_map[状态] = 替换结果（仅叶子节点有值）
        state_id = 1
        for (i = 2; i < ARGC; i += 2) {
            n = split(ARGV[i], tokens)
            curr_state = 0
            for (j = 1; j <= n; j++) {
                key = curr_state SUBSEP tokens[j]
                if (!(key in state_map)) {
                    state_map[key] = state_id++
                }
                curr_state = state_map[key]
            }
            replace_map[curr_state] = ARGV[i+1]
            # 删除命令行参数，避免awk处理为输入文件
            delete ARGV[i]
            delete ARGV[i+1]
        }
    }

    # 处理每个token
    {
        token = $1
        # 初始化状态链的占位（初始状态0）
        state_chain[1] = {state=0, prev_len=0}
        token_chain[1] = ""
        new_chain_len = 0
        last_match_pos = 0
        last_match_replace = ""

        # 遍历所有可能的当前状态，尝试转移
        for (s = 1; s <= length(state_chain); s++) {
            curr_state = state_chain[s].state
            key = curr_state SUBSEP token
            if (key in state_map) {
                new_state = state_map[key]
                new_chain_len++
                new_state_chain[new_chain_len] = {state=new_state, prev_len=s}
                new_token_chain[new_chain_len] = token_chain[s] (token_chain[s] != "" ? " " : "") token
                # 记录这个状态是否是匹配终点
                if (new_state in replace_map) {
                    last_match_pos = new_chain_len
                    last_match_replace = replace_map[new_state]
                }
            }
        }

        # 检查是否有有效转移
        if (new_chain_len == 0) {
            # 没有转移，回溯到最近的匹配点
            if (last_match_pos > 0) {
                # 输出匹配结果（空值则输出空行）
                print last_match_replace
                # 处理未匹配的部分：从匹配点之后的token开始
                unmatch_start = last_match_pos + 1
                for (s = unmatch_start; s <= length(state_chain); s++) {
                    split(token_chain[s], tokens, " ")
                    for (t in tokens) {
                        print tokens[t]
                    }
                }
                # 重置状态，尝试用当前token重新开始匹配
                key = 0 SUBSEP token
                if (key in state_map) {
                    new_state_chain[1] = {state=state_map[key], prev_len=0}
                    new_token_chain[1] = token
                    if (state_map[key] in replace_map) {
                        last_match_pos = 1
                        last_match_replace = replace_map[state_map[key]]
                    }
                    new_chain_len = 1
                } else {
                    # 完全不匹配，直接输出当前token
                    print token
                    new_chain_len = 0
                }
            } else {
                # 没有任何匹配，直接输出当前token
                print token
                new_chain_len = 0
            }
        }

        # 更新状态链和token链
        delete state_chain
        delete token_chain
        for (s = 1; s <= new_chain_len; s++) {
            state_chain[s] = new_state_chain[s]
            token_chain[s] = new_token_chain[s]
        }
        delete new_state_chain
        delete new_token_chain
    }

    # 处理结束时的剩余状态链
    END {
        # 先输出最近的匹配结果
        if (last_match_pos > 0) {
            print last_match_replace
            # 输出未匹配的剩余token
            unmatch_start = last_match_pos + 1
            for (s = unmatch_start; s <= length(state_chain); s++) {
                split(token_chain[s], tokens, " ")
                for (t in tokens) {
                    print tokens[t]
                }
            }
        } else {
            # 没有匹配，输出所有剩余token
            for (s = 1; s <= length(state_chain); s++) {
                split(token_chain[s], tokens, " ")
                for (t in tokens) {
                    print tokens[t]
                }
            }
        }
    }
' - \
    '3 4'        '&'     \
    '6 7 8'      '9 9'   \
    '6 7 9'      '8 8'   \
    '7 10'       '11 12' \
    '0'          ''      \
    '10'         '13 10' \
    '8 9 12 3 5' '#'

代码解释 #

1. 前缀树构建：在BEGIN块中遍历所有替换规则，将每个规则的token序列转化为状态转移路径，叶子节点存储对应的替换结果，实现规则的高效存储。
2. 状态链维护：每处理一个token，遍历当前所有可能的状态尝试转移，生成新的状态链，同时记录最近的有效匹配位置和替换结果。
3. 回溯处理：当无法继续转移时，回溯到最近的匹配点输出替换结果，再处理未匹配的token，确保不会遗漏任何可能的匹配。
4. 大文件适配：通过tr将所有空格替换为换行，实现逐token处理，awk每次仅处理一行（一个token），无需加载整个文件到内存，适配超大文件场景。

内容的提问来源于stack exchange，提问作者Fravadona