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

Ответ 1

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

Ответ 2

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

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

comm -1 wordlist.txt text.txt

Ответ 3

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

 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 

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

Ответ 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);

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

Ответ 6

Первое решение 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 слов, например. Хотя мы используем функцию mapcar Lisp, список генерируется "на лету", и поскольку мы не сохраняем ссылку на mapcar списка, он имеет право на сбор мусора.

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

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

Ответ 7

Второе решение TXR (http://www.nongnu.org/txr)

@(next :args)
@wordfile
@textfile
@(do 
  (defvar trigraph-to-words (hash :equal-based))
  (defvar digraphs (hash :equal-based))
  (defvar unigraphs (hash :equal-based))
  (defvar word-occurs (hash :equal-based))

  (defun lazy-line-list (file)
    (let ((stream (open-file file "r")))
      (let (line) (gen (set line (get-line stream)) line))))

  (defun get-trigraphs (str)
    (mappend (lambda (i)
               (list [str i..(+ i 3)]))
             (range 0 (- (length str) 3))))

  (defun get-digraphs (str)
    (mappend (lambda (i)
               (list [str i..(+ i 2)]))
             (range 0 (- (length str) 2))))

  (each ((word (lazy-line-list wordfile)))
    (cond
     ((> (length word) 3)
      (push word  [trigraph-to-words [word 0..3]]))
     ((eql (length word) 3)
      (push word [trigraph-to-words word]))
     ((eql (length word) 2)
      (set [digraphs word] t))
     (t (set [unigraphs word] t))))

  (each ((line (lazy-line-list textfile)))
    ;; If the short-words hashes have no entries
    ;; replace them with nil, so we do not bother
    ;; considering those words any more.
    (if (and digraphs (zerop (hash-count digraphs)))
      (set digraphs nil))
    (if (and unigraphs (zerop (hash-count unigraphs)))
      (set unigraphs nil))

    ;; Find all trigraphs in this line, and
    ;; for each trigraph, find words which
    ;; contain that trigraph. Those words may 
    ;; occur in this line, which can be double
    ;; checked by a substring search.
    (if (>= (length line) 3)
      (each ((tg (get-trigraphs line)))
        (each ((word [trigraph-to-words tg])) 
          (if (not [word-occurs word])
            (if (search-str line word 0)
              (progn
                (set [word-occurs word] t)))))))

    ;; If there remain digraphs words in the dictionary
    ;; that have not occurred, then break the line
    ;; into digraphs, and see if any of
    ;; those digraphs occur.
    (if (and digraphs (>= (length line) 2))
      (each ((dg (get-digraphs line)))
        (if [digraphs dg]
          (progn (set [word-occurs dg] t)
                 (del [digraphs dg])))))

    ;; Finally, for each line, check individual
    ;; characters against the unigraph list
    (if unigraphs
      (each ((letter (split-str line "")))
        (if [unigraphs letter]
          (progn (set [word-occurs letter] t)
                 (del [unigraphs letter]))))))

  (dohash (word occurs word-occurs)
    (put-line word))

  (put-string ""))

Я запускал это на ноутбуке Core 2 Duo (P8400, 2.26GHz), где VirtualBox работает под управлением Ubuntu поверх Windows. В тестовом примере находится файл /usr/share/dict/words, содержащий более 90 000 записей, по сравнению с полным текстом английского перевода Толстойской войны и мира, снятого с проекта Гутенберг (около 3,3 мегабайта).

Оперативная память fooprint быстро поднялась до 10700 байт, когда словарный словарь был прочитан, а затем остался плоским во время сканирования текста. Единственные системные вызовы, которые я наблюдал с strace, в течение оставшейся части часа составляли 4096 байт, читали текст.

Результаты:

$ time txr words2.txr /usr/share/dict/words /tmp/tolstoy-war-and-peace-gutenberg-2600.txt > war-and-peace-words.txt
real  66m49.914s
user  65m15.277s
sys   0m49.043s

$ head war-and-peace-words.txt 
concourse
pursuits
recruits
appreciated
unappreciated
perceive
cobblestone
commiserating
build
mild

$ tail war-and-peace-words.txt 
curiously
populated
appraise
essayist
disguised
disguise
championship
approaches
mosquito
lorgnette

$ wc /tmp/tolstoy-war-and-peace-gutenberg-2600.txt 
  65336  565454 3288739 /tmp/tolstoy-war-and-peace-gutenberg-2600.txt
$ wc /usr/share/dict/words
 98569  98568 931708 /usr/share/dict/words
$ wc war-and-peace-words.txt 
 19344  19344 158153 war-and-peace-words.txt

При следующем изменении, которое требует последней TXR от git, время работы уменьшается до 11 минут и 6 секунд. Недавно открытая функция дошла до 21 минуты, а затем небольшое исправление для глупого поведения в сборщике мусора улучшило его:

    ;; Find all trigraphs in this line, and
    ;; for each trigraph, find words which
    ;; contain that trigraph. Those words may 
    ;; occur in this line, which can be double
    ;; checked by a substring search.
    (if (>= (length line) 3)
      (each ((tg (get-trigraphs line))
             (pos (range 0)))
        (let* ((words [trigraph-to-words tg])
               (len (match-str-tree line words pos))
               (word (if len [line pos..(+ pos len)])))
          (if (and word (not [word-occurs word]))
            (set [word-occurs word] t)))))

real  11m6.787s
user  10m44.356s
sys   0m9.893s

Ответ 8

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

Ответ 9

Простейший способ с bash script:

• Предварительная обработка сначала с помощью "tr" и "sort" для форматирования одного слова на строку и удаления дублированных строк.

• Сделайте это:

cat wordlist.txt | при чтении i; do grep -E "^ $i $" text.txt; сделанный;

Это список слов, которые вы хотите...

Ответ 10

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

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

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

Ответ 11

Попробуйте следующее: cat wordlist.txt | при чтении строки делать если [[grep -wc $line text.txt -gt 0]] тогда   echo $line фи сделано

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

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

Ответ 12

Это решение находится в perl, поддерживает ваши оригинальные symantics и использует предложенную вами оптимизацию.

#!/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;

Ответ 13

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

1) sort и uniq в 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.txt для конкатенации

Это ускорит обработку, и вы сможете использовать инструменты, которые вы могли бы понять. Это упростит "стоимость".

script почти идентичный, который вы использовали в первую очередь.

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}