Какой самый быстрый способ удаления строк в файле, которые не совпадают во втором файле?

Question

У меня есть два файла, wordlist.txt и text.txt.

Первый файл, wordlist.txt, содержит огромный список слов на китайском, японском и корейском языках, например:

你
你们
我

Второй файл, text.txt, содержит длинные отрывки, например:

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

Я хочу создать новый список слов (wordsfount.txt), но он должен содержать только те строки изwordlist.txt, которые встречаются хотя бы один раз в пределах text.txt.Выходной файл из вышеупомянутого должен показать это:

你
你们

"我" не найден в этом списке, потому что он никогда не найден в text.txt.

Я хочу найти оченьбыстрый способ создать этот список, который содержит только строки из первого файла, найденные во втором.

Я знаю простой способ в BASH, чтобы проверить каждую строку в worlist.txt и посмотреть, если она в text.txt используя grep:

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, их можно рассматривать как гигантский алфавит, содержащий около 8000 букв.Так что почти каждое слово делится символами.Например:

我
我们

Из-за этого факта, если «我» никогда не найден в пределах text.txt, то вполне логично, что «我们» также никогда не появляется.Более быстрый сценарий может сначала проверить «我», и, обнаружив, что его нет, не будет проверять каждое последующее слово, содержащееся в wordlist.txt, которое также содержится в wordlist.txt.Если в wordlist.txt найдено около 8000 уникальных символов, сценарию не нужно проверять столько строк.

Какой самый быстрый способ создать список, содержащий только те слова, которые находятся в первом файлекоторые также находятся где-то во втором?

Answer 1

Я взял текст Войны и мира из проекта Гутенберга и написал следующий сценарий.If печатает все слова в /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

Answer 2

Это может работать для вас:

 tr '[:punct:]' ' ' < text.txt | tr -s ' ' '\n' |sort -u | grep -f - wordlist.txt

По сути, создайте новый список слов из text.txt и сопоставьте его с файлом wordlist.txt.

N.B. Возможно, вы захотите использовать программное обеспечение, которое вы использовали для создания оригинального wordlist.txt. В этом случае все, что вам нужно, это:

yoursoftware < text.txt > newwordlist.txt
grep -f newwordlist.txt wordlist.txt 

Answer 3

Просто используйте комм

http://unstableme.blogspot.com/2009/08/linux-comm-command-brief-tutorial.html

comm -1 wordlist.txt text.txt

Answer 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 и выполняет все операции со строками в Юникоде, поэтому тестирование с использованием символов ASCII допустимо.)

Использование ленивых списков означает, что мы не храним, например, весь список из 300 000 слов. Хотя мы используем функцию Lisp mapcar, список создается на лету, и поскольку мы не храним ссылку на заголовок списка, он пригоден для сбора мусора.

К сожалению, мы должны хранить корпус текста в памяти, потому что хеш-таблица связывает строки.

Если это проблема, решение может быть отменено. Просканируйте все слова, а затем лениво обработайте текстовый корпус, помечая те слова, которые встречаются. Тогда устраните все остальное. Я также опубликую такое решение.

Answer 5

Я бы, вероятно, использовал 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);

Это не будет слишком медленно, но если бы вы могли сообщить нам размер файлов, с которыми вы имеете дело, я мог бы написать что-то более умное с помощью хеш-таблиц

Answer 6

Конечно, не самое быстрое решение, но хотя бы рабочее (надеюсь).

Для этого решения требуется 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 также очень медленный, но было бы интересно, что произойдет с большим примером.

Answer 7

Используйте grep с семантикой с фиксированными строками (-F), это будет быстрее всего.Точно так же, если вы хотите написать это на Perl, используйте функцию index вместо регулярных выражений.

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

Я удивлен, что уже есть четыре ответа, но ни одинопубликовал это еще.Люди просто больше не знают своего инструментария.

Answer 8

Используйте параллельную обработку для ускорения обработки.

1) отсортировать & uniq на wordlist.txt, затем разделить его на несколько файлов (X) Проведите некоторое тестирование, X равно вашим ядрам компьютера.

 split -d -l wordlist.txt

2) использовать xargs -p X -n 1 script.sh x00> output-x00.txt обрабатывать файлы в paralel

 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}

Answer 9

Это решение написано на 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;

Answer 10

Попробуйте это: cat wordlist.txt |в то время как read line делает if [[grep -wc $line text.txt -gt 0]], затем echo $ line fi done

Что бы вы ни делали, если вы используете grep, вы должны использовать -w для соответствия целому слову.В противном случае, если у вас есть foo в wordlist.txt и foobar в text.txt, вы получите неправильное совпадение.

Если файлы ОЧЕНЬ большие, и этот цикл занимает слишком много времени, вы можете преобразовать текст.txt к списку работ (легко с AWK) и используйте comm, чтобы найти слова, которые есть в обоих списках.