删除多余的字符串而不循环

Question

有没有办法使用 shell 工具从列表中删除重复项和冗余子串？“冗余”是指包含在另一个字符串中的字符串，因此“foo”与“foobar”和“barfoo”是多余的。例如，拿这个列表：

abcd
abc
abd
abcd
bcd

并返回：

abcd
abd

uniq,sort -u并awk '!seen[$0]++'有效删除重复项但不删除 冗余字符串： 如何删除文件中的重复行而不在 Unix 中对其进行排序？删除重复行而不排序

我可以递归地遍历每一行，grep但这对于大文件来说很慢。（我有大约 10^8 行要处理。）这里有一种在 Python 中使用循环的方法：根据部分字符串和 Bash删除冗余字符串：How to check if a string contains a substring in Bash但我正在尝试避免循环。编辑：我的意思是这里的嵌套循环，感谢@shellter 的澄清

有没有办法将 awk 的match()函数与数组索引一起使用？这种方法逐步构建数组，因此不必搜索整个文件，因此对于大文件应该更快。还是我错过了其他一些简单的解决方案？

理想的解决方案将允许匹配指定的列，如上述方法。

编辑

以下两个答案都有效，非常感谢您的帮助。目前在真实数据集上测试性能，将更新结果并接受答案。我在同一个输入文件上测试了这两种方法，该文件有 430,000 行，其中 417,000 行是非冗余的。作为参考，我原来的循环 grep 方法用了 7 小时 30 米处理这个文件。
更新：
James Brown 的原始解决方案耗时 3 小时 15 分，而 Ed Morton 的解决方案耗时 8 小时 59 分。在较小的数据集上，James 的更新版本为 7m，而原始版本为 20m。谢谢两位，这真的很有帮助。

我正在处理的数据每个字符串大约有 110 个字符，每个文件通常有数十万行。这些字符串（它们是抗体蛋白质序列）的创建方式可能导致字符串一端或两端的字符丢失。因此，“bcd”很可能是“abcde”的一个片段。

Answer 1

$ awk '{print length($0), $0}' file |
    sort -k1,1rn -k2 -u |
    awk '!index(str,$2){str = str FS $2; print $2}'
abcd
abd

以上假设一组唯一值将适合内存。

Answer 2

awk 在第一次运行时提取所有子字符串和字符串并将其存储到两个数组中subs，strs并在第二次运行时进行检查：

$ awk '
NR==FNR {                                    # first run 
    if(($0 in strs)||($0 in subs))           # process only unseen strings
        next
    len=length()-1                           # initial substring length
    strs[$0]                                 # hash the complete strings
    while(len>=1) {                          
        for(i=1;i+len-1<=length();i++) {     # get all substrings of current len
            asub=substr($0,i,len)            # sub was already resetved :(
            if(asub in strs)                 # if substring is in strs
                delete strs[asub]            # we  do not want it there
            subs[asub]                       # hash all substrings too
        }
        len--                                
    }
    next
}
($0 in strs)&&++strs[$0]==1' file file

输出：

abcd
abd

我用大约 30 M 条 1-20 个字符的 ACGT 字符串记录测试了该脚本。该脚本运行了 3 分钟 27 秒，并使用了我 16 GB 的大约 20%。在几分钟内使用长度为 1-100 的字符串 I OOM（再次尝试使用大约 400k 条长度为 50-100 的记录，它使用大约 200 GB 并运行大约一个小时）。（1-30 个字符的 20 M 记录运行 7 分 10 秒并使用了 80% 的内存）

所以如果你的数据记录很短或者你有无限的内存，我的解决方案很快，但在相反的情况下它会因为内存不足而崩溃。

编辑：

另一个试图保留内存的版本。第一次检查字符串的最小和最大长度，第二次运行时不会存储短于全局最小值的子字符串。对于长度为 50-100 的大约 400 k 记录，它使用了大约 40 GB 并运行了 7 分钟。我的随机数据没有任何冗余，所以输入==输入。它确实消除了与其他数据集的冗余（1-20 个字符字符串的 2 M 记录）：

$ awk '
BEGIN {
    while((getline < ARGV[1])>0)            # 1st run, check min and max lenghts
        if(length()<min||min=="")           # TODO: test for length()>0, too
            min=length()
        else if(length()>max||max=="")
            max=length()
#       print min,max > "/dev/stderr"       # debug   
        close(ARGV[1])

    while((getline < ARGV[1])>0) {          # 2nd run, hash strings and substrings
#       if(++nr%10000==0)                   # debug
#           print nr > "/dev/stderr"        # debug
        if(($0 in strs)||($0 in subs))
            continue
        len=length()-1
        strs[$0]
        while(len>=min) {
            for(i=1;i+len-1<=length();i++) {
                asub=substr($0,i,len)
                if(asub in strs)
                    delete strs[asub]
                subs[asub]
            }
            len--
        }
    }
    close(ARGV[1])

    while((getline < ARGV[1])>0)             # 3rd run, output 
        if(($0 in strs)&&!strs[$0]++)
            print
}' file