logo标签列表

什么是在文件中删除没有匹配项的行的最快方法？

rubyperlbashpython-2.7cjk
19

我有两个文件，wordlist.txt和text.txt。

wordlist.txt这个文件中包含了大量的中文、日文和韩文单词，例如：

你
你们
我

第二个文件是 text.txt，包含长篇章节，例如：

你们要去哪里？
卡拉OK好不好？

我想创建一个新的单词列表（wordsfount.txt），但它应该只包含在text.txt中至少出现一次的来自wordlist.txt的那些行。上述操作的输出文件应该显示为：

你
你们
因为在text.txt中从未找到"我"，所以在此列表中未找到它。
我想找到一种非常快速的方法来创建此列表，该列表仅包含在第二个文件中找到的第一个文件中的行。
我知道在BASH中使用grep的简单方法，可以检查worlist.txt中的每一行，并查看它是否在text.txt中。
a=1
while read line
do
    c=`grep -c $line text.txt`
    if [ "$c" -ge 1 ]
    then
    echo $line >> wordsfound.txt
    echo "Found" $a
fi
    echo "Not found" $a
    a=`expr $a + 1`
done < wordlist.txt

很不幸，由于wordlist.txt非常长，这个过程需要花费几个小时的时间。必须要有更快的解决方案。以下是一个考虑：

由于文件包含CJK字母，它们可以被视为一个拥有大约8,000个字母的巨型字母表。所以几乎每个单词都共享字符。例如：

我
我们

由于这个事实，如果在text.txt中从未找到“我”，那么“我们”从未出现也是相当合理的。一个更快的脚本可能会先检查“我”，并在发现不存在时，避免检查包含在wordlist.txt中的每个后续单词，它们都包含在wordlist.txt中。如果wordlist.txt中有大约8,000个独特字符，那么脚本应该不需要检查那么多行。

如何最快地创建仅包含第一个文件中也在第二个文件中某处找到的单词列表？

2
假设“我”在“wordlist.txt”中，但“我们”不在其中。 假设“我们”出现在“text.txt”中，这是否与“我”匹配？也就是说，您是否真正匹配单词，还是仅匹配汉字的任意子串，这些子串可能是单词的片段？ - Kaz
我的目标是创建一个新的、缩短的wordlist.txt，其中不包含不匹配的单词，以便后来更复杂的脚本可以更快地完成工作。新列表大约是原始长度的5%。如果找到了“我们”，但从未发现孤立的“我”，理想情况下，新的单词列表不显示“我”，但如果这个额外的检查非常难以实现，那么它是不必要的。 - Village
1
不是针对Village，但你一直在问“有没有更快的方法”？坦率而诚实的答案是，实际上没有。在未排序的集合中检查值的最快方法就是暴力搜索，永远不会有更快的方法。你可以添加许多特定的条件来利用二分搜索，但一般情况下，它永远不会比暴力搜索更快。抱歉。搜索是一个非常消耗资源的过程，大量的研究正在进行中，以优化它们，但通常它们涉及以某种方式对数据进行排序。 - FrankieTheKneeMan
12个回答
12

我从古腾堡计划中获取了《战争与和平》的文本并编写了以下脚本。它会打印出/usr/share/dict/words中与war_and_peace.txt相同的所有单词。您可以通过以下方式进行更改：

perl findwords.pl --wordlist=/path/to/wordlist --text=/path/to/text > wordsfound.txt

在我的电脑上，运行时间略长于一秒钟。
use strict;
use warnings;
use utf8::all;

use Getopt::Long;

my $wordlist = '/usr/share/dict/words';
my $text     = 'war_and_peace.txt';

GetOptions(
    "worlist=s" => \$wordlist,
    "text=s"    => \$text,
);

open my $text_fh, '<', $text
    or die "Cannot open '$text' for reading: $!";

my %is_in_text;
while ( my $line = <$text_fh> ) {
    chomp($line);

    # you will want to customize this line
    my @words = grep { $_ } split /[[:punct:][:space:]]/ => $line;
    next unless @words;

    # This beasty uses the 'x' builtin in list context to assign
    # the value of 1 to all keys (the words)
    @is_in_text{@words} = (1) x @words;
}

open my $wordlist_fh, '<', $wordlist
    or die "Cannot open '$wordlist' for reading: $!";

while ( my $word = <$wordlist_fh> ) {
    chomp($word);
    if ( $is_in_text{$word} ) {
        print "$word\n";
    }
}

这是我的计时：

• [ovid] $ wc -w war_and_peace.txt 
565450 war_and_peace.txt
• [ovid] $ time perl findwords.pl > wordsfound.txt 

real    0m1.081s
user    0m1.076s
sys 0m0.000s
• [ovid] $ wc -w wordsfound.txt 
15277 wordsfound.txt
1
在 split 之前的 grep {$_} 的目的是什么？ - Freek Kalter
1
Freek：这是为了过滤掉空字符串。使用split函数会得到一些空字符串。 - Ovid
1
这看起来适用于西方语言，但它如何处理中文、日文和韩文呢？因为这是 Village 所计划使用该代码的语言。请记住，如果有一个单词列表 A、AB 和 C，那么包含 ABDEFG 的文本文件将生成一个结果文件，其中包含两行；A 和 AB。这个脚本会产生这样的结果吗？ - swampf0etus
1
swampf0etus：utf8::all这一行确保所有文件句柄（包括输入和输出）都是utf8编码，因此读取其他字符集也将没有问题。我有一个注释说/[[:punct:][:space:]]/正则表达式可能需要根据用户的需求进行更改。简而言之，这应该是一个合理的解决方案，只需要稍微调整一下即可。 - Ovid
1
@Ovid 你可以使用 @is_in_text{@words} = undef; 来缩短代码，稍后再用 if( exists $is_in_text{$word} ) 进行检查。这样可以避免创建临时数组 (1) x @words。 - dgw
显示剩余4条评论
5
这个方法或许适合你：
 tr '[:punct:]' ' ' < text.txt | tr -s ' ' '\n' |sort -u | grep -f - wordlist.txt

基本上，从text.txt文件中创建一个新单词列表，并将其与wordlist.txt文件进行匹配。
注意：您可能希望使用建立原始wordlist.txt的软件。如果是这样，您只需要执行以下操作：
yoursoftware < text.txt > newwordlist.txt
grep -f newwordlist.txt wordlist.txt
这似乎假定text.txt中的单词由空格分隔，并且使用标准标点符号，但由于所有内容都是中文、日文或韩文，因此单词之间没有空格，并且使用不同的标点符号。 - Village
1
设置LC*变量会对这个解决方案的工作方式产生影响吗？祝大家好运。 - shellter
5
我创建了一些测试文件，但它总是打印出wordlist.txt中包含的每个单词，即使它们从未出现在text.txt中。 - Village
1
输入的 comm 是否排序最优？对于现代 shell，可以使用 comm -1 <(sort wordlist.txt) <(sort text.txt) 命令。祝大家好运。 - shellter
4

我比较确定这不是最快的解决方案，但至少是可行的（希望如此）。

这个解决方案需要 Ruby 1.9，文本文件必须是 UTF-8 编码。

#encoding: utf-8
#Get test data
$wordlist = File.readlines('wordlist.txt', :encoding => 'utf-8').map{|x| x.strip}
$txt = File.read('text.txt', :encoding => 'utf-8')

new_wordlist = []
$wordlist.each{|word|
  new_wordlist << word if $txt.include?(word)
}

#Save the result
File.open('wordlist_new.txt', 'w:utf-8'){|f|
  f << new_wordlist.join("\n")
}

能否提供更大的示例以便在不同的方法上进行基准测试？（可以提供一些可下载的测试文件吗？）

下面是四种方法的基准测试结果。

#encoding: utf-8
require 'benchmark'
N = 10_000 #Number of Test loops

#Get test data
$wordlist = File.readlines('wordlist.txt', :encoding => 'utf-8').map{|x| x.strip}
$txt = File.read('text.txt', :encoding => 'utf-8')

def solution_count
    new_wordlist = []
    $wordlist.each{|word|
      new_wordlist << word if $txt.count(word) > 0
    }
    new_wordlist.sort
end

#Faster then count, it can stop after the first hit
def solution_include
    new_wordlist = []
    $wordlist.each{|word|
      new_wordlist << word if $txt.include?(word)
    }
    new_wordlist.sort
end
def solution_combine()
    #get biggest word size
    max = 0
    $wordlist.each{|word| max = word.size if word.size > max }
    #Build list of all letter combination from text
    words_in_txt = []
    0.upto($txt.size){|i|
      1.upto(max){|l|
        words_in_txt << $txt[i,l]
      }
    }
    (words_in_txt & $wordlist).sort
end
#Idea behind:
#- remove string if found.
#- the next comparison is faster, the search text is shorter.
#
#This will not work with overlapping words.
#Example:
#  abcdef contains def.
#  if we check bcd first, the 'd' of def will be deleted, def is not detected.
def solution_gsub
    new_wordlist = []
    txt = $txt.dup  #avoid to manipulate data source for other methods
    #We must start with the big words.
    #If we start with small one, we destroy  long words
    $wordlist.sort_by{|x| x.size }.reverse.each{|word|
      new_wordlist << word if txt.gsub!(word,'')
    }
    #Now we must add words which where already part of longer words
    new_wordlist.dup.each{|neww|
      $wordlist.each{|word|          
        new_wordlist << word if word != neww and neww.include?(word)
      }
    }
    new_wordlist.sort
end

#Save the result
File.open('wordlist_new.txt', 'w:utf-8'){|f|
  #~ f << solution_include.join("\n")
  f << solution_combine.join("\n")
}

#Check the different results
if solution_count != solution_include
  puts "Difference solution_count <> solution_include"
end
if solution_gsub != solution_include
  puts "Difference solution_gsub <> solution_include"
end
if solution_combine != solution_include
  puts "Difference solution_combine <> solution_include"
end

#Benchmark the solution
Benchmark.bmbm(10) {|b|

  b.report('count') { N.times { solution_count } }
  b.report('include') { N.times { solution_include } }
  b.report('gsub') { N.times { solution_gsub } } #wrong results
  b.report('combine') { N.times { solution_gsub } } #wrong results

} #Benchmark

我认为，solution_gsub 变体不正确。请查看方法定义中的注释。如果CJK允许此方案，则请给我反馈。 在我的测试中，该变体是最慢的，但也许会随着更大的示例而改进。 或许可以对其进行一些调整。 combine变体也非常慢，但使用更大的示例会很有趣。
4

我可能会使用Perl；


use strict;

my @aWordList = ();

open(WORDLIST, "< wordlist.txt") || die("Can't open wordlist.txt);

while(my $sWord = <WORDLIST>)
{
   chomp($sWord);
   push(@aWordList, $sWord);
}

close(WORDLIST);

open(TEXT, "< text.txt") || die("Can't open text.txt);

while(my $sText = <TEXT>)
{
   foreach my $sWord (@aWordList)
   {
      if($sText =~ /$sWord/)
      {
          print("$sWord\n");
      }
   }
}


close(TEXT);

这不会太慢，但如果您能告诉我们处理的文件大小，我可以尝试使用哈希表编写更加智能的代码。

wordlist.txt文件可能包含近30万行。text.txt文件的长度各不相同，从非常短的到数百万个字符不等。 - Village
1
当对《战争与和平》和Unix字典运行时，这需要很长时间。我目前正在开发一个更快的哈希表版本。 - swampf0etus
4

第一个TXR Lisp解决方案（http://www.nongnu.org/txr）：

(defvar tg-hash (hash)) ;; tg == "trigraph"

(unless (= (len *args*) 2)
  (put-line `arguments required: <wordfile> <textfile>`)
  (exit nil))

(defvar wordfile [*args* 0])

(defvar textfile [*args* 1])

(mapcar (lambda (line)
          (dotimes (i (len line))
            (push line [tg-hash [line i..(succ i)]])
            (push line [tg-hash [line i..(ssucc i)]])
            (push line [tg-hash [line i..(sssucc i)]])))
        (file-get-lines textfile))

(mapcar (lambda (word)
          (if (< (len word) 4)
            (if [tg-hash word]
              (put-line word))
            (if (find word [tg-hash [word 0..3]]
                      (op search-str @2 @1))
              (put-line word))))
        (file-get-lines wordfile))

这里的策略是将单词语料库缩小为一个哈希表，该哈希表以出现在行中的单个字符、二元组和三元组为索引，将这些片段与行相关联。然后，当我们处理单词列表时，这将减少搜索的工作量。

首先，如果单词很短，三个字符或更少（可能是汉语词汇普遍存在的情况），我们可以尝试在哈希表中进行即时匹配。如果没有匹配，那么这个单词不在语料库中。

如果单词超过三个字符，我们可以尝试获取前三个字符的匹配项。这给了我们一个包含匹配三元组的行列表。我们可以详尽地搜索这些行，以查看其中哪些与单词匹配。我怀疑这将大大减少必须搜索的行数。

我需要您的数据或类似代表性数据，以便能够看到行为如何。

示例运行：

$ txr words.tl words.txt text.txt
water
fire
earth
the

$ cat words.txt
water
fire
earth
the
it

$ cat text.txt
Long ago people
believed that the four
elements were
just
water
fire
earth

(TXR读取UTF-8编码并在Unicode中进行所有字符串操作，因此使用ASCII字符进行测试是有效的。)
使用惰性列表意味着我们不会存储整个30万单词的列表。虽然我们使用了Lisp的mapcar函数，但是该列表是动态生成的，并且由于我们没有保留对列表头的引用，它可以被垃圾回收。
不幸的是，我们必须将文本语料库保存在内存中，因为哈希表关联行。
如果这是一个问题，解决方案可以反过来。扫描所有单词，然后懒惰地处理文本语料库，标记出现的单词。然后消除其余的单词。我也会发布这样的解决方案。
感谢您的赏金；识别和修复那个愚蠢的垃圾收集器行为确实是我在此过程中所需要的全部奖励。 - Kaz
4

使用带有固定字符串（-F）语义的grep，这样速度最快。同样，如果您想用Perl编写它，请使用index函数而不是正则表达式。

sort -u wordlist.txt > wordlist-unique.txt
grep -F -f wordlist-unique.txt text.txt

我很惊讶已经有四个答案了，但是没有人发表过这个观点。人们只是不熟悉自己的工具箱了。

这段代码会在 text.txt 中查找并打印出包含 wordlist.txt 中单词的行，但是我只想打印出在 text.txt 中有匹配的行。 - Village
1
@Village 我想你可以给 grep 添加一个 -o（仅显示匹配的部分），然后使用 sort -u 再次进行去重。 - Michael Kohl
1
@daxim：这在一般情况下是行不通的。例如，如果您的单词列表包含“foo”和“foobar”，而文本包含“foobar”，那么这只会返回“foobar”。当然，使用单词列表中的匹配项进行另一次搜索可以检测到这样的子字符串匹配。 - l0b0
3
这个解决方案是用Perl编写的，保留了你原来的语义，并使用了你建议的优化技巧。
#!/usr/bin/perl
@list=split("\n",`sort < ./wordlist.txt | uniq`);
$size=scalar(@list);
for ($i=0;$i<$size;++$i) { $list[$i]=quotemeta($list[$i]);}
for ($i=0;$i<$size;++$i) {
    my $j = $i+1;
    while ($list[$j]=~/^$list[$i]/) {
            ++$j;
    }
    $skip[$i]=($j-$i-1);
}
open IN,"<./text.txt" || die;
@text = (<IN>);
close IN;
foreach $c(@text) {
    for ($i=0;$i<$size;++$i) {
            if ($c=~/$list[$i]/) {
                    $found{$list[$i]}=1;
                    last;
            }
            else {
                    $i+=$skip[$i];
            }
    }
}
open OUT,">wordsfound.txt" ||die;
while ( my ($key, $value) = each(%found) ) {
        print OUT "$key\n";
}
close OUT;
exit;
1
这与我提供的方法类似，但我不认为将结果添加到哈希表中进行迭代并在最后打印有任何好处。你会花费时间（和内存）将内容添加到哈希表中，然后遍历并打印哈希表的内容，而你可以在找到每个结果时就打印它。此外，你正在将整个文件读入数组中。由于这些文件可能相当大，因此可能会消耗大量内存。 - swampf0etus
1
我理解的要求是结果只显示一次，因此使用哈希表。我已经测试了一个包含20万个单词的wordlist.txt文件，只需要几秒钟就能完成。现在发布者说wordlist.txt非常大，但text.txt大小不确定。由于wordlist.txt已经排序，可以像发布者建议的那样进行一些优化。 - pizza
1
我是指2000k而不是200k，基于wordlist.txt大约有300k行的假设，CJK词通常由1-3个字符组成，假设所有单词都是3个字符+行末（每行8个字节）。内存需求大约为几兆字节。优化是现实的，因为有相当多的单词以相同的字符或某些字符子集开头。 - pizza
3

使用并行处理加速处理过程。

1）对wordlist.txt进行排序和去重，然后将其分割成几个文件（X）。进行一些测试，X应该等于您计算机的核心数。

 split -d -l wordlist.txt

2) 使用 xargs -p X -n 1 script.sh x00 > output-x00.txt 命令以并行方式处理文件。

 find ./splitted_files_dir -type f -name "x*" -print| xargs -p 20 -n 1 -I SPLITTED_FILE script.sh SPLITTED_FILE

3) cat output* > output.txt 将输出文件连接起来

使用这种方法可以提高处理速度，而且您可以使用自己能够理解的工具。这将降低“成本”。

脚本与您最初使用的脚本几乎完全相同。

script.sh
FILE=$1
OUTPUTFILE="output-${FILE}.txt"
WORDLIST="wordliist.txt"
a=1
while read line
do
    c=`grep -c $line ${FILE} `
    if [ "$c" -ge 1 ]
    then
    echo $line >> ${OUTPUTFILE}
    echo "Found" $a
fi
    echo "Not found" $a
    a=`expr $a + 1`
done < ${WORDLIST}
1
这将会在中等大小的单词列表上显得非常缓慢而无用。对于大量文本语料库的每一行，你都希望通过大量单词表进行grep。此外，你正在错误地执行grep操作：你正在查看整个文本行（由许多单词组成）是否出现在单词列表中。 - Kaz
1
在规范中，单词列表每行包含一个单词。Linux内核将缓存文本文件，因此速度非常快。是的，我已经替换了单词列表/文本列表文件，我将编辑脚本。这种方法可以与任何其他脚本一起使用，我在这里使用shell脚本，因为请求者似乎很懂shell脚本。 - user1126070
3
new file newlist.txt
for each word in wordlist.txt:
    check if word is in text.txt (I would use grep, if you're willing to use bash)
    if yes:
        append it to newlist.txt (probably echo word >> newlist.txt)
    if no:
        next word
考虑到wordlist.txt中许多字符出现多次的事实，这个程序能否更快地运行？ - Village
1
你可以在grep中使用-L选项，它会在第一次匹配后短路并关闭。 - FrankieTheKneeMan
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接