如何从列表中删除可以在列表中其他较长行中找到的行？

Question

我有一个文件list.txt,像这样:

cat
bear
tree
catfish
fish
bear

我需要删除文档中其他地方已经完全找到的任何行,可以是重复行,也可以在另一行中找到.例如,"熊"和"熊"的行是相同的,因此删除其中一行; "猫"可以完全在"鲶鱼"中找到,因此"猫"被删除.输出看起来像这样:

catfish
tree
bear

如何删除所有重复行,包括在列表中较长行中找到的行？

到目前为止,我有这个:

#!/bin/bash
touch list.tmp
while read -r line
do
    found="$(grep -c $line list.tmp)"
    if [ "$found" -eq "1" ]
    then
        echo $line >> list.tmp
        echo $line" added"
    else
        echo "Not added."
fi
done < list.txt

Answer 1

由于子字符串问题，这将非常困难。最初，我正在考虑对我的列表进行排序，并将诸如 和 之类的东西cat放在catfish一起，但是看看这个列表::

bug
bear
calf
catbug
catbear

对此列表进行排序不会有帮助。另外，这个又如何呢？

concatenate
cat
bear
bug

我要遗漏吗cat？它已经在词中了吗concatenate？

那这个呢：

cat
concatenate
bear
bug

在本例中，单词cat和concatenate都在列表中，因为cat位于列表中的第一个位置，位于concatenate之前。由于没有任何单词已经是concatenate的一部分，因此它会进入列表。

除非我需要检查两种方式。我要添加到列表中的单词是否已在列表中，并且该单词是否已在列表中包含在我正在查看的单词中。

这不仅是一个定义不明确的问题，而且代码也很混乱。编码实际上很简单，但最终形成了 O ²类型的算法。这意味着列表大小加倍会导致处理时间加倍。如果我可以在一秒钟内处理100个单词，那么我需要4秒处理200个单词，8秒处理400个单词，16秒处理800个单词。差不多20秒就可以写完1000个单词。

这里使用您的定义，其中顺序很重要。也就是说，如果cat出现在 之前catbug，则两者都在您批准的列表中，但如果catbug出现在 之前cat，则cat不会出现在列表中：

#! /usr/bin/env perl
#
use strict;
use warnings;
use autodie;
use feature qw(say);
use Data::Dumper;

use constant {
    LIST_FILE => "text.txt",
};

open my $list_fh, "<", LIST_FILE;
my @approved_list;
while ( my $new_word = <list_fh> ) {
    chomp $new_word;
    my $new_word_in_list = 0;
    for my $word_already_in_list ( @approved_list ) {
        if ( $word_already_in_list =~ /\Q$new_word\E/ ) {
            # Word is already in the list or in a word in the list
            $new_word_in_list = 1;
            last;
        }
    }
    if ( not $new_word_in_list ) {
        push @approved_list, $new_word;
    }
}
say Dumper \@approved_list;

冥想

我早些时候意识到我可以使用grep而不是内部循环：

#! /usr/bin/env perl
#
use strict;
use warnings;
use autodie;
use feature qw(say);
use Data::Dumper;

use constant {
    LIST_FILE => "text.txt",
};

open my $list_fh, "<", LIST_FILE;
my @approved_list;
while ( my $new_word = <$list_fh> ) {
    chomp $new_word;
    if ( not grep { /\Q$new_word\E/ } @approved_list ) {
        push @approved_list, $new_word;
    }
}
say Dumper \@approved_list

该程序看起来更短，似乎只需要一个循环，但grep隐藏了内部循环。为了使 grep 工作，它仍然需要遍历数组中的每个条目。这就是为什么我决定不使用grep，而是让内部循环更加明确。

但是，如果我可以使用字符串而不是数组来保存单词，并且我用某个字符将单词分开，我可以保证该字符不在单词中，该怎么办？也许我可以在字符串上使用正则表达式。这样会更有效率吗？

#! /usr/bin/env perl
#
use strict;
use warnings;
use autodie;
use feature qw(say);
use Data::Dumper;

use constant {
    LIST_FILE => "text.txt",
};

open my $list_fh, "<", LIST_FILE;
my $approved_list = "";
while ( my $new_word = <$list_fh> ) {
    chomp $new_word;
    if ( not $approved_list =~ /\Q$new_word\E/ ) {
        $approved_list = ( $approved_list ) ? "$approved_list\0$new_word" : $new_word;
    }
}
say Dumper split /\0/, $approved_list;

在上面，我将批准的单词列表放入名为 的标量中$approved_list。我用NUL 字符分隔单词，假设单词不包含该NUL字符。现在，我可以用新词来 grep 标量。如果它不在 中$approved_list，我会在其前面添加字符NUL( \0)。我稍后可以分开NUL再次返回列表。

使用正则表达式会更快吗？如果我批准的列表包含 1000 个单词，平均每个单词 5 个字符（可能更长，因为较长的单词比较短的单词更有可能出现）怎么办？我正在对这个 6000 个字符的字符串执行正则表达式。这样效率更高吗？很难说。

解决方案有以下三种：

1. 第一个使用隐式内部循环。
2. 第二个用于grep隐藏内循环。
3. 第三个将单词列表串成一个由字符分隔的字符串，我绝对确定它不在字符串中。（我的钱已经到了NUL）。

判断的唯一方法是在所有三个上使用Benchmark::Timer之类的东西，看看哪一个是最有效的——这可能会根据列表大小、单词等而变化。