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

Question

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

abcd
abc
abd
abcd
bcd

并返回:

abcd
abd

uniq , sort -u和 awk '!seen[$0]++'有效地去除重复但不去除多余的字符串:
How to delete duplicate lines in a file without sorting it in Unix?
Remove duplicate lines without sorting
我可以用 grep 递归地遍历每一行但这对于大文件来说很慢。 (我有大约 10^8 行要处理。)
这里有一种在 Python 中使用循环的方法: Remove redundant strings based on partial strings和 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 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 的字符串在几分钟内 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