如何从大文件中提取可覆盖所有条目的最小前缀集合？

问题背景 #

我有一个包含数字条目的大文件，条目示例如下：

1113 1113456 11134567 12345 1734 123 194567

我的需求是找出能代表所有条目的最少前缀集合——简单说就是，如果一个条目是另一个条目的前缀，只保留较短的那个就行。比如保留1113后，1113456和11134567就可以去掉了，最终预期输出是：

1113 123 1734 194567

我之前试过用grep -v ^123这类命令来过滤，但在用while循环处理时，不知道怎么直接从输入文件里删除对应的条目，想找到更靠谱的方法。

高效解决方案：排序+Awk处理 #

首先说一句：不要直接修改原大文件，不仅效率低还容易搞坏数据，我们直接生成符合要求的结果文件就好。

处理这类前缀去重问题，最省心高效的方式是先排序，再用Awk过滤，步骤如下：

1. 先整理条目格式（如果原文件是空格分隔）

如果你的文件是像示例那样用空格分隔所有条目，先把它们转成每行一个的格式，方便后续排序：

tr ' ' '\n' < 你的输入文件名.txt | sort > sorted_entries.txt

如果你的文件已经是每行一个条目，直接跳过这步，对原文件排序就行。

2. 用Awk过滤出最少前缀

排序后，所有前缀相同的条目会挨在一起（比如1113肯定在1113456前面），这时用一行Awk就能搞定：

awk '!($0 ~ "^" prev) {print; prev=$0}' sorted_entries.txt > final_result.txt

原理解释

• 排序后，短前缀会排在它的所有衍生长条目前面。
• Awk脚本里，我们用prev变量记录上一个保留的前缀，每次检查当前行是否以prev开头：
  • 如果不是，说明这是一个新的、需要保留的前缀，打印它并更新prev。
  • 如果是，说明当前行被已有的前缀覆盖，直接跳过。

这样处理完，final_result.txt里就是你要的最少前缀集合了，完全符合预期。

基于你原有思路的优化方案 #

如果你想沿着之前用grep的思路来实现，可以用数组来存储和过滤条目，而不是直接修改文件：

# 把所有条目读入数组（先转成每行一个并排序）
mapfile -t entries < <(tr ' ' '\n' < 你的输入文件名.txt | sort)

# 初始化结果数组
result=()

for entry in "${entries[@]}"; do
    # 检查当前条目是否已经被结果里的前缀覆盖
    is_covered=0
    for r in "${result[@]}"; do
        if [[ "$entry" == "$r"* ]]; then
            is_covered=1
            break
        fi
    done
    # 如果没被覆盖，再检查是否能覆盖结果里的已有条目（排序后这步基本用不上）
    if [[ $is_covered -eq 0 ]]; then
        # 移除结果里被当前条目覆盖的长条目
        new_result=()
        for r in "${result[@]}"; do
            if [[ ! "$r" == "$entry"* ]]; then
                new_result+=("$r")
            fi
        done
        new_result+=("$entry")
        result=("${new_result[@]}")
    fi
done

# 把结果写入文件
printf "%s " "${result[@]}" > final_result.txt
echo >> final_result.txt

这个方法的核心是用数组来管理待保留的条目，避免直接修改原文件的麻烦，排序后也能保证处理逻辑的简洁性。

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