mapas - ruby file file

¿Hay una manera eficiente de realizar cientos de sustituciones de texto en Ruby?

Question

Estoy tratando de usar una lista de cientos de faltas de ortografía comunes para limpiar algunas entradas antes de buscar duplicados.

Es un proceso de tiempo crítico, así que espero que haya una manera más rápida que tener cientos de expresiones regulares (o una con cien ramas).

¿Hay una manera eficiente de realizar cientos de sustituciones de texto en Ruby?

Answer 1

Pruébalo al revés. En lugar de corregir errores ortográficos y buscar duplicados en el resultado, coloque todo en un formato similar (como Metaphone o Soundex) y verifique si hay duplicados en ese formato.

Ahora, no sé qué camino será más rápido: por un lado, tienes cientos de expresiones regulares, cada una de las cuales no coincidirá casi al instante y regresará. Por otro lado, tienes 30 reemplazos de expresiones regex potenciales, uno o dos de los cuales sin duda coincidirán con cada palabra.

Ahora, el metafonía es bastante rápido, realmente no hay mucho para el algoritmo, así que solo puedo sugerir que lo pruebes y midas si es lo suficientemente rápido para usarlo.

Answer 2

Me complace decir que acabo de encontrar " RegexpTrie ", que es un reemplazo utilizable para el código, y la necesidad de Perl''s Regexp :: Assemble.

Instálalo y pruébalo:

require ''regexp_trie''

foo = %w(miss misses missouri mississippi)

RegexpTrie.union(foo)
# => /miss(?:(?:es|ouri|issippi))?/

RegexpTrie.union(foo, option: Regexp::IGNORECASE)
# => /miss(?:(?:es|ouri|issippi))?/i

Aquí hay una comparación de las salidas. Las primeras salidas comentadas en la matriz son de Regexp :: Assemble y la salida final es de RegexpTrie:

require ''regexp_trie''

[
  ''how now brown cow'',                           # /(?:[chn]ow|brown)/
  ''the rain in spain stays mainly on the plain'', # /(?:(?:(?:(?:pl|r)a)?i|o)n|s(?:pain|tays)|mainly|the)/
  ''jackdaws love my giant sphinx of quartz'',     # /(?:jackdaws|quartz|sphinx|giant|love|my|of)/
  ''fu foo bar foobar'',                           # /(?:f(?:oo(?:bar)?|u)|bar)/
  ''ms miss misses missouri mississippi''          # /m(?:iss(?:(?:issipp|our)i|es)?|s)/
].each do |s|
  puts "%-43s # /%s/" % [s, RegexpTrie.union(s.split).source]
end

# >> how now brown cow                           # /(?:how|now|brown|cow)/
# >> the rain in spain stays mainly on the plain # /(?:the|rain|in|s(?:pain|tays)|mainly|on|plain)/
# >> jackdaws love my giant sphinx of quartz     # /(?:jackdaws|love|my|giant|sphinx|of|quartz)/
# >> fu foo bar foobar                           # /(?:f(?:oo(?:bar)?|u)|bar)/
# >> ms miss misses missouri mississippi         # /m(?:iss(?:(?:es|ouri|issippi))?|s)/

En cuanto a cómo usar el enlace de Wikipedia y las palabras mal escritas:

require ''nokogiri''
require ''open-uri''
require ''regexp_trie''

URL = ''https://en.wikipedia.org/wiki/Wikipedia:Lists_of_common_misspellings/For_machines''

doc = Nokogiri::HTML(open(URL))
corrections = doc.at(''div#mw-content-text pre'').text.lines[1..-1].map { |s|
  a, b = s.chomp.split(''->'', 2)
  [a, b.split(/,/s+/) ]
}.to_h
#  {"abandonned"=>["abandoned"],
#   "aberation"=>["aberration"],
#   "abilityes"=>["abilities"],
#   "abilties"=>["abilities"],
#   "abilty"=>["ability"],
#   "abondon"=>["abandon"],
#   "abbout"=>["about"],
#   "abotu"=>["about"],
#   "abouta"=>["about a"],
#   ...
#   }

misspelled_words_regex = //b(?:#{RegexpTrie.union(corrections.keys, option: Regexp::IGNORECASE).source})/b/i
# => //b(?:(?:a(?:b(?:andonned|eration|il(?:ityes|t(?:ies|y))|o(?:ndon(?:(?:ed|ing|s))?|tu|ut(?:it|the|a)...

En este punto, puede usar gsub(misspelled_words_regex, corrections) , sin embargo, los valores en las corrections contienen algunas matrices porque se podrían haber usado varias palabras o frases para reemplazar la palabra mal escrita. Deberá hacer algo para determinar cuál de las opciones usar.

A Ruby le falta un módulo muy útil que se encuentra en Perl, llamado Regexp :: Assemble . Python tiene hachoir-regex que parece hacer el mismo tipo de cosas.

Regexp :: Assemble crea una expresión regular muy eficiente, basada en listas de palabras y expresiones simples. Es realmente notable ... o ... ¿diabólico?

Vea el ejemplo para el módulo; Es extremadamente simple de usar en su forma básica:

use Regexp::Assemble;

my $ra = Regexp::Assemble->new;
$ra->add( ''ab+c'' );
$ra->add( ''ab+-'' );
$ra->add( ''a/w/d+'' );
$ra->add( ''a/d+'' );
print $ra->re; # prints a(?:/w?/d+|b+[-c])

Observe cómo se combinan los patrones. Haría lo mismo con las palabras regulares, solo que sería aún más eficiente porque las cuerdas comunes se combinarán:

use Regexp::Assemble;

my $lorem = ''Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.'';

my $ra = Regexp::Assemble->new(''flags'' => ''i'');

$lorem =~ s/[^a-zA-Z ]+//g;

$ra->add(split('' '', lc($lorem)));
print $ra->anchor_word(1)->as_string, "/n";

Qué salidas:

/b(?:a(?:dipisicing|liqua|met)|(?:consectetu|tempo)r|do(?:lor(?:emagna)?)?|e(?:(?:li)?t|iusmod)|i(?:ncididunt|psum)|l(?:abore|orem)|s(?:ed|it)|ut)/b

Este código ignora el caso y respeta los límites de las palabras.

Recomiendo escribir una pequeña aplicación Perl que pueda tomar una lista de palabras y usar ese módulo para generar la versión codificada del patrón de expresiones regulares. Deberías poder importar ese patrón en Ruby. Eso te permitiría encontrar rápidamente palabras mal escritas. Incluso podría hacer que muestre el patrón en un archivo YAML, luego cargue ese archivo en su código Ruby. Analice periódicamente las páginas de palabras mal escritas, ejecute la salida a través del código de Perl y su código de Ruby tendrá un patrón de actualización.

Podría usar ese patrón contra un fragmento de texto solo para ver si hay palabras mal escritas. Si es así, divida el texto en oraciones o palabras y verifique nuevamente la expresión regular. No evalúe inmediatamente las palabras porque la mayoría de las palabras se escribirán correctamente. Es casi como una búsqueda binaria en contra de su texto: pruebe todo, si hay un golpe, divídalo en bloques más pequeños para reducir la búsqueda hasta que haya encontrado los errores ortográficos individuales. La forma de descomponer los fragmentos depende de la cantidad de texto entrante. Un patrón de expresión regular puede probar todo el bloque de texto y devolver un valor nulo o de índice, además de las palabras individuales de la misma manera, por lo que gana mucha velocidad haciendo grandes fragmentos del texto.

Entonces, si sabe que tiene una palabra mal escrita, puede hacer una búsqueda hash para la ortografía correcta. Sería un gran hachís, pero la tarea de analizar la ortografía buena frente a la mala es lo que tardará más tiempo. La búsqueda sería extremadamente rápida.

Aquí hay un código de ejemplo:

get_words.rb

#!/usr/bin/env ruby

require ''open-uri''
require ''nokogiri''
require ''yaml''

words = {}
[''0-9'', *(''A''..''Z'').to_a].each do |l|
  begin
    print "Reading #{l}... "
    html = open("http://en.wikipedia.org/wiki/Wikipedia:Lists_of_common_misspellings/#{l}").read
    puts ''ok''
  rescue Exception => e
    puts "got /"#{e}/""
    next
  end

  doc = Nokogiri::HTML(html)
  doc.search(''div#bodyContent > ul > li'').each do |n| 
    n.content =~ /^(/w+) /s+ /(([^)]+)/x
    words[$1] = $2 
  end
end

File.open(''wordlist.yaml'', ''w'') do |wordfile|
  wordfile.puts words.to_yaml
end

regex_assemble.pl

#!/usr/bin/env perl

use Regexp::Assemble;
use YAML;

use warnings;
use strict;

my $ra = Regexp::Assemble->new(''flags'' => ''i'');

my %words = %{YAML::LoadFile(''wordlist.yaml'')};
$ra->add(map{ lc($_) } keys(%words));

print $ra->chomp(1)->anchor_word(1)->as_string, "/n";

Ejecute el primero, luego ejecute el segundo canalizando su salida a un archivo para capturar la expresión regular emitida.

Y más ejemplos de palabras y el resultado generado:

''how now brown cow'' => //b(?:[chn]ow|brown)/b/
''the rain in spain stays mainly on the plain'' => //b(?:(?:(?:(?:pl|r)a)?i|o)n|s(?:pain|tays)|mainly|the)/b/
''jackdaws love my giant sphinx of quartz'' => //b(?:jackdaws|quartz|sphinx|giant|love|my|of)/b/
''fu foo bar foobar'' => //b(?:f(?:oo(?:bar)?|u)|bar)/b/
''ms miss misses missouri mississippi'' => //bm(?:iss(?:(?:issipp|our)i|es)?|s)/b/

La Regexp.union de Ruby no se acerca a la sofisticación de Regexp::Assemble . Después de capturar la lista de palabras mal escritas, hay 4225 palabras, que constan de 41,817 caracteres. Después de ejecutar Regexp :: Assemble de Perl contra esa lista, se generó una expresión regular de 30,954 caracteres. Yo diría que eso es eficiente.

Answer 3

Un enfoque alternativo, si sus datos de entrada son palabras separadas, sería simplemente construir una tabla hash de {error => correction} .

La búsqueda en la tabla Hash es rápida , por lo que si puede doblar sus datos de entrada a este formato, es casi seguro que será lo suficientemente rápido.