ruby - ¿Cuál es la forma más rápida de eliminar líneas en un archivo que no coinciden en un segundo archivo?

perl bash

Question

Tengo dos archivos, wordlist.txt y text.txt .

El primer archivo, wordlist.txt , contiene una enorme lista de palabras en chino, japonés y coreano, por ejemplo:

你
你们
我

El segundo archivo, text.txt , contiene pasajes largos, por ejemplo:

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

Quiero crear una nueva lista de palabras ( wordsfount.txt ), pero solo debería contener aquellas líneas de wordlist.txt que se encuentran al menos una vez dentro de text.txt . El archivo de salida de lo anterior debería mostrar esto:

你
你们

"我" no se encuentra en esta lista porque nunca se encuentra en text.txt .

Quiero encontrar una forma muy rápida de crear esta lista que solo contiene líneas del primer archivo que se encuentra en el segundo.

Conozco una forma sencilla en BASH para revisar cada línea en worlist.txt y ver si está en text.txt usando 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

Desafortunadamente, como wordlist.txt es una lista muy larga, este proceso toma muchas horas. Debe haber una solución más rápida. Aquí hay una consideración:

Como los archivos contienen letras CJK, pueden considerarse como un alfabeto gigante con aproximadamente 8,000 letras. Así que casi todas las palabras comparten caracteres. P.ej:

我
我们

Debido a este hecho, si "我" nunca se encuentra dentro de text.txt , entonces es bastante lógico que "我们" nunca aparezca tampoco. Una secuencia de comandos más rápida tal vez marque primero "我", y al encontrar que no está presente, evitaría revisar cada palabra subsiguiente contenida dentro de wordlist.txt que también estaba contenida en wordlist.txt . Si se encuentran alrededor de 8,000 caracteres únicos en wordlist.txt , entonces el script no debería tener que marcar tantas líneas.

¿Cuál es la forma más rápida de crear la lista que contiene solo las palabras que están en el primer archivo que también se encuentran en algún lugar dentro del segundo?

Answer 1

Esta solución está en Perl, mantiene su Symantics original y utiliza la optimización que sugirió.

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

Esto podría funcionar para usted:

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

Básicamente, cree una nueva lista de text.txt desde text.txt y grep contra el archivo wordlist.txt .

NB Es posible que desee utilizar el software que utilizó para crear la wordlist.txt original.txt. En cuyo caso todo lo que necesitas es:

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

Answer 3

La forma más sencilla con bash script:

1. Preproceso primero con "tr" y "ordenar" para formatearlo en una palabra por línea y eliminar las líneas duplicadas.

2. Hacer esto:

cat wordlist.txt | mientras leo i; hacer grep -E "^ $ i $" text.txt; hecho;

Esa es la lista de palabras que quieres ...

Answer 4

Primera solución Lisp de TXR ( 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))

La estrategia aquí es reducir el corpus de palabras a una tabla hash que se indexa en caracteres individuales, dígrafos y trigrafos que aparecen en las líneas, asociando estos fragmentos con las líneas. Luego, cuando procesamos la lista de palabras, esto reduce el esfuerzo de búsqueda.

En primer lugar, si la palabra es corta, tres caracteres o menos (probablemente es común en las palabras chinas), podemos intentar obtener una coincidencia instantánea en la tabla hash. Si no hay coincidencia, la palabra no está en el corpus.

Si la palabra tiene más de tres caracteres, podemos intentar obtener una coincidencia para los tres primeros caracteres. Eso nos da una lista de líneas que contienen una coincidencia para el trigraph. Podemos buscar esas líneas exhaustivamente para ver cuáles de ellas coinciden con la palabra. Sospecho que esto reducirá en gran medida el número de líneas que se deben buscar.

Necesitaría sus datos, o algo representativo de los mismos, para poder ver cómo es el comportamiento.

Ejecución de la muestra:

$ 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 lee UTF-8 y realiza toda la manipulación de cadenas en Unicode, por lo que las pruebas con caracteres ASCII son válidas).

El uso de listas perezosas significa que no almacenamos la lista completa de 300,000 palabras, por ejemplo. Aunque estamos usando la función mapcar Lisp, la lista se está generando sobre la marcha y debido a que no mantenemos la referencia al encabezado de la lista, es elegible para la recolección de basura.

Desafortunadamente, tenemos que mantener el corpus de texto en la memoria porque la tabla hash asocia las líneas.

Si eso es un problema, la solución podría revertirse. Escanee todas las palabras y luego procese el texto del texto perezosamente, etiquetando las palabras que aparecen. Luego elimina el resto. Voy a publicar una solución de este tipo también.

Answer 5

Probablemente usaría 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);

Esto no será demasiado lento, pero si nos permite saber el tamaño de los archivos con los que está trabajando, podría intentar escribir algo mucho más inteligente con tablas hash.

Answer 6

Prueba esto: cat wordlist.txt | mientras se lee la línea haz si [[ grep -wc $line text.txt -gt 0]] entonces echo $ line fi hecho

Hagas lo que hagas, si usas grep debes usar -w para hacer coincidir una palabra completa. De lo contrario, si tienes foo en wordlist.txt y foobar en text.txt, obtendrás una coincidencia incorrecta.

Si los archivos son MUY grandes, y este bucle tarda mucho tiempo en ejecutarse, puede convertir text.txt en una lista de trabajo (fácil con AWK) y usar comm para encontrar las palabras que están en ambas listas.

Answer 7

Seguro que no es la solución más rápida, pero al menos una que funciona (espero).

Esta solución necesita Ruby 1.9, se espera que el archivo de texto sea 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")
}

¿Puedes dar un ejemplo más grande para hacer un punto de referencia en diferentes métodos? (Tal vez algunos archivos de prueba para descargar?)

Por debajo de un punto de referencia con cuatro métodos.

#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

Creo que la variante solution_gsub no es correcta. Ver el comentario en la definición del método. Si CJK puede permitir esta solución, por favor, dame un comentario. Esa variante es la más lenta en mi prueba, pero quizás se ajuste con ejemplos más grandes. Y tal vez se pueda sintonizar un poco.

La variante de combine también es muy lenta, pero sería interesante lo que sucede con un ejemplo más grande.

Answer 8

Solo usa comm

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

comm -1 wordlist.txt text.txt

Answer 9

Tomé el texto de Guerra y paz del proyecto Gutenberg y escribí el siguiente guión. Si imprime todas las palabras en /usr/share/dict/words que también están en war_and_peace.txt . Puedes cambiar eso con:

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

En mi computadora, toma poco más de un segundo en ejecutarse.

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";
}
}

Y aquí está mi tiempo:

• [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 10

Use grep con semánticas de cadenas fijas ( -F ), esto será más rápido. De manera similar, si desea escribirlo en Perl, use la función de index lugar de expresiones regulares.

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

Me sorprende que ya haya cuatro respuestas, pero nadie ha publicado esto todavía. La gente simplemente ya no sabe su caja de herramientas.

Answer 11

Utilice el procesamiento paralelo para acelerar el procesamiento.

1) ordenar y unificar en wordlist.txt, luego dividirlo en varios archivos (X) Hacer algunas pruebas, X es igual a los núcleos de su computadora.

 split -d -l wordlist.txt

2) use xargs -p X -n 1 script.sh x00> output-x00.txt para procesar los archivos en paralelo

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

3) salida cat *> output.txt concatenar archivos de salida

Esto acelerará el procesamiento lo suficiente y podrá utilizar herramientas que pueda entender. Esto facilitará el "costo" de mantenimiento.

El script casi idéntico al que usaste en primer lugar.

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 12

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