logo标签列表

不使用循环删除冗余字符串

stringshellawkduplicates
5

有没有一种使用shell工具从列表中删除重复和冗余子字符串的方法？这里所说的“冗余”是指包含在另一个字符串中的字符串，因此“foo”与“foobar”和“barfoo”重复。

例如，考虑以下列表：

abcd
abc
abd
abcd
bcd

并返回：
abcd
abd
uniq，sort -u和awk '!seen[$0]++'可以有效地去除重复的字符串，但不能去除冗余的字符串。如何在不排序文件的情况下删除文件中的重复行？删除非排序重复行 我可以使用grep递归遍历每一行，但对于大型文件来说速度相当慢。(我需要处理大约10^8行。)这里有一种使用Python循环的方法：基于部分字符串删除冗余字符串以及Bash中的方法：如何检查一个字符串是否包含子字符串但我试图避免循环。编辑：我指的是嵌套循环，在此感谢@shellter的澄清。
有没有办法使用awk的match()函数与数组索引一起使用？这种方法逐步构建数组，因此永远不必搜索整个文件，因此应该对大型文件更快。或者我错过了其他简单的解决方案吗？
理想的解决方案将允许匹配指定的列，就像上面的方法一样。
编辑
以下两个答案都有效，非常感谢帮助。目前正在测试实际数据集的性能，将用结果更新并接受一个答案。我在相同的输入文件上测试了两种方法，该文件有430,000行，其中417,000行是非冗余的。供参考，我的原始循环grep方法对此文件需要7h30m。
更新：
James Brown的原始解决方案需3h15m，而Ed Morton的则需8h59m。在较小的数据集上，James的更新版本为7m，而原始版本为20m。谢谢你们俩，这真的很有帮助。
我正在处理大约110个字符每个字符串，通常每个文件有数以千计的行。创建这些字符串(抗体蛋白质序列)的方式可能会导致字符串的一个或两个末尾的字符丢失。因此，"bcd"很可能是"abcde"的一个片段。
1
请清晰地定义“冗余字符串”。 - Paul Hodges
@KamilCuk 不好意思，抱歉让你产生了困惑。已经编辑过来反映实际的文件结构了。 - garethmorgan
那么ab是否应该被视为对abcd的冗余？那只有a呢...嗯，或者只有b呢？此外，请定义循环。任何读取完整文件的脚本都是一个循环，如果需要返回进行双重检查，则将是另一个循环（我不会担心这个问题，先清楚地定义和解决您的问题，然后再考虑循环;-)）。祝你好运！ - shellter
文件中的实际字符串有多长？ - James Brown
3个回答
5
$ awk '{print length($0), $0}' file |
    sort -k1,1rn -k2 -u |
    awk '!index(str,$2){str = str FS $2; print $2}'
abcd
abd

以上假设集合中的唯一值可以放入内存中。
1
那个字符串搜索是一种很棒的优化。之前做过，但是想着如何不存储整个数据集来解决问题。我猜你得这么做。 - Paul Hodges
2
首先进行排序似乎是必须的。我在一个小字典上进行了一些测试。1) 这个任务的瓶颈在于最后一部分，我发现使用 index 方法比像 '{for (i in a) if (i ~ $2) next} {a[$2]; print $2}' 这样的方法快几倍。2) 可以通过在第一个 awk 中使用 !a[$0]++{...} 来去除重复项，因为这样排序会更快，只需要像 sort -rn 一样排序即可（无需拆分），除非您有其他原因需要进行排序。 - thanasisp
1
@PaulHodges 它不会存储整个数据集，只会存储之前读取的字符串中不存在的子字符串。因此，如果您读取像 abcd 这样的字符串，它将作为 str 的一部分存储，但是未来从输入中读取的像 ab、abc、bcd 这样的字符串不会被存储，因为它们不需要被存储。 - Ed Morton
1
@thanasisp 我不确定在awk中进行唯一性测试是否真的会更快，但可能会更快，我不知道。然而，它将使用更多的内存，因为输入中的每个唯一字符串都需要被存储在内存中，即使它是另一个字符串的子字符串。如果我们不必添加“-u”来删除重复项，则sort -rn就可以了。 - Ed Morton
1
这似乎不太可能，只有当字符串“str”变长时index()才会变慢。当然，有各种方法可以加速它，但它们都涉及到循环，而你想避免循环。 - Ed Morton
显示剩余2条评论
5
第一次运行提取并存储所有子字符串和字符串到两个数组 subs 和 strs 中的 awk，在第二次运行时检查：
$ 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字符串的脚本进行测试。该脚本运行了3m27s，使用了大约我16 GB内存的20％。当使用长度为1-100的字符串时，我在几分钟内发生了OOM错误（再次尝试使用长度为50-100的400k条记录，它使用了约200 GB并运行了约一小时）。 （20M条1-30个字符的记录运行时间为7m10s，使用了80％的内存）

因此，如果您的数据记录很短或您拥有无限的内存，则我的解决方案非常快速，但在相反情况下，它将因为内存不足而崩溃。

编辑：

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

$ 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
我得了流感（但愿只是普通的季节性流感），所以我希望这个脚本不是完全的灾难... - James Brown
1
我发布的脚本主要是为了满足OP的陈述“我试图避免循环”，所以我并没有特别追求速度，但听到它比你发布的脚本慢，我感到非常惊讶，因为你的脚本中有一个嵌套循环。你能否在问题中分享一个脚本来生成你正在运行的输入？ - Ed Morton
1
我手头有一个随机的30 MB ACGT字符串，我用这个命令把它切成小段： awk '{i=1;while(i<length()-20){r=1+int(rand()*20);print substr($0,i,r);i+=r}}' string30M > file 所以，基本上不需要了。 :D（现在得去睡觉了，晚安） - James Brown
工作非常好，速度很快。我认为对于普通单词（平均8-10个字符），没有太多的大字符串（100个字符），内存使用不会太大，因为子字符串会被重复使用很多次。 - thanasisp
2

编辑

@Ed的解决方案是我能想象到的最好的想法，没有明确的循环，甚至在每个记录上隐式扫描接近整个增长历史的数据。这必须要做。

你现有的资源能否在内存中保存整个列，加上每个记录的分隔符？如果不能，那么你将被困在非常复杂的优化算法或非常缓慢的冗余搜索中。

原始帖子保留供参考，以防它给其他人带来灵感。

给定原始输入文件，

while read next
do [[ "$last" == "$next" ]] && continue                    # throw out repeats
   [[ "$last" =~ $next   ]] && continue                    # throw out sustrings
   [[ "$next" =~ $last   ]] && { last="$next"; continue; } # upgrade if last a substring of next
   echo $last                  # distinct string
   last="$next"                # set new key
done < file

产量
abcd
abd

对于这样大小的文件，我不会信任那种排序方式。排序将非常缓慢且需要大量资源，但可以给您更可靠的结果。如果您可以对文件进行一次排序并使用该输出作为输入文件，则很好。如果不能，请用done < <( sort -u file )或类似的内容替换最后一行。

在awk中重新设计这个逻辑会更快。

$: sort -u file | awk '1==NR{last=$0} last~$0{next} $0~last{last=$0;next} {print last;last=$0}'

除了sort之外，它使用微不足道的内存，并应该非常快速和高效，对于一个包含10^8行的文件而言，这是某种程度上"快速"的。

我曾以为 sort | awk 脚本会忽略 bc 作为冗余的内容，即使上一行是 abc 和 ab，尽管 bc 是 abc 的子字符串。但是当我尝试在由 printf 'abc\nab\bc\n' 生成的输入上运行它时，我根本没有得到任何输出，虽然它没有输出 abc 这个结果，但这不是我预期的结果！ - Ed Morton
\b 会让你感到困惑。:) 不过你的观点完全正确。这个程序没有足够的复杂性来处理这个问题。:( - Paul Hodges
1
糟糕，我实际上是手动创建了该文件，我只是在注释中添加了printf以尝试更轻松地解释如何创建这样的文件，当然我搞砸了！我当然是指printf 'abc\nab\nbc\n'。是的，仅查看前一行的脚本无法解决这个问题，因为当前行可能是早于它之前的某一行的子字符串。 - Ed Morton
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接