string - spanish - spacy sentence recognition

¿Cómo puedo dividir varias palabras juntas?

Question

Tengo un conjunto de 1000 o más entradas, con ejemplos a continuación:

wickedweather
liquidweather
driveourtrucks
gocompact
slimprojector

Me gustaría poder dividir estos en sus respectivas palabras, como:

wicked weather
liquid weather
drive our trucks
go compact
slim projector

Esperaba que una expresión regular hiciera el truco. Pero, dado que no hay límite para detenerse, ni hay ningún tipo de capitalización que pueda activar, estoy pensando que podría ser necesario algún tipo de referencia a un diccionario.

Supongo que podría hacerse a mano, pero ¿por qué? ¡Cuando se puede hacer con código! =) Pero esto me ha dejado perplejo. ¿Algunas ideas?

Answer 1

¿Puede un humano hacerlo?

farsidebag far sidebag farside bag far side bag

No solo tiene que usar un diccionario, puede que tenga que usar un enfoque estadístico para descubrir qué es lo más probable (o, Dios no lo quiera, un HMM real para su lenguaje humano preferido ...)

Para saber cómo hacer estadísticas que podrían ser útiles, lo dirijo al Dr. Peter Norvig, quien aborda un problema diferente, pero relacionado, de la corrección ortográfica en 21 líneas de código : http://norvig.com/spell-correct.html

(Él hace trampa un poco doblando cada bucle en una sola línea ... pero aún así).

Actualización Esto se quedó en mi cabeza, así que tuve que nacer hoy. Este código realiza una división similar a la descrita por Robert Gamble, pero luego ordena los resultados en función de la frecuencia de las palabras en el archivo de diccionario proporcionado (que ahora se espera que sea un texto representativo de su dominio o inglés en general. .txt de Norvig, vinculado anteriormente, y le echó un diccionario, para cubrir palabras faltantes).

Una combinación de dos palabras la mayoría de las veces superará una combinación de 3 palabras, a menos que la diferencia de frecuencia sea enorme.

Publiqué este código con algunos cambios menores en mi blog

http://squarecog.wordpress.com/2008/10/19/splitting-words-joined-into-a-single-string/ y también escribió un poco sobre la falla de subdesbordamiento en este código ... Estuve tentado de solo en silencio arréglelo, pero cree que esto puede ayudar a algunas personas que no han visto el truco de registro antes: http://squarecog.wordpress.com/2009/01/10/dealing-with-underflow-in-joint-probability-calculations/

Dé salida a sus palabras, más algunas propias: observe lo que sucede con "orcore":

perl splitwords.pl big.txt words answerveal: 2 possibilities - answer veal - answer ve al wickedweather: 4 possibilities - wicked weather - wicked we at her - wick ed weather - wick ed we at her liquidweather: 6 possibilities - liquid weather - liquid we at her - li quid weather - li quid we at her - li qu id weather - li qu id we at her driveourtrucks: 1 possibilities - drive our trucks gocompact: 1 possibilities - go compact slimprojector: 2 possibilities - slim projector - slim project or orcore: 3 possibilities - or core - or co re - orc ore

Código:

#!/usr/bin/env perl

use strict;
use warnings;

sub find_matches($);
sub find_matches_rec($/@/@);
sub find_word_seq_score(@);
sub get_word_stats($);
sub print_results($@);
sub Usage();

our(%DICT,$TOTAL);
{
  my( $dict_file, $word_file ) = @ARGV;
  ($dict_file && $word_file) or die(Usage);

  {
    my $DICT;
    ($DICT, $TOTAL) = get_word_stats($dict_file);
    %DICT = %$DICT;
  }

  {
    open( my $WORDS, ''<'', $word_file ) or die "unable to open $word_file/n";

    foreach my $word (<$WORDS>) {
      chomp $word;
      my $arr = find_matches($word);


      local $_;
      # Schwartzian Transform
      my @sorted_arr =
        map  { $_->[0] }
        sort { $b->[1] <=> $a->[1] }
        map  {
          [ $_, find_word_seq_score(@$_) ]
        }
        @$arr;


      print_results( $word, @sorted_arr );
    }

    close $WORDS;
  }
}


sub find_matches($){
    my( $string ) = @_;

    my @found_parses;
    my @words;
    find_matches_rec( $string, @words, @found_parses );

    return  @found_parses if wantarray;
    return /@found_parses;
}

sub find_matches_rec($/@/@){
    my( $string, $words_sofar, $found_parses ) = @_;
    my $length = length $string;

    unless( $length ){
      push @$found_parses, $words_sofar;

      return @$found_parses if wantarray;
      return  $found_parses;
    }

    foreach my $i ( 2..$length ){
      my $prefix = substr($string, 0, $i);
      my $suffix = substr($string, $i, $length-$i);

      if( exists $DICT{$prefix} ){
        my @words = ( @$words_sofar, $prefix );
        find_matches_rec( $suffix, @words, @$found_parses );
      }
    }

    return @$found_parses if wantarray;
    return  $found_parses;
}


## Just a simple joint probability
## assumes independence between words, which is obviously untrue
## that''s why this is broken out -- feel free to add better brains
sub find_word_seq_score(@){
    my( @words ) = @_;
    local $_;

    my $score = 1;
    foreach ( @words ){
        $score = $score * $DICT{$_} / $TOTAL;
    }

    return $score;
}

sub get_word_stats($){
    my ($filename) = @_;

    open(my $DICT, ''<'', $filename) or die "unable to open $filename/n";

    local $/= undef;
    local $_;
    my %dict;
    my $total = 0;

    while ( <$DICT> ){
      foreach ( split(//b/, $_) ) {
        $dict{$_} += 1;
        $total++;
      }
    }

    close $DICT;

    return (/%dict, $total);
}

sub print_results($@){
    #( ''word'', [qw''test one''], [qw''test two''], ... )
    my ($word,  @combos) = @_;
    local $_;
    my $possible = scalar @combos;

    print "$word: $possible possibilities/n";
    foreach (@combos) {
      print '' -  '', join('' '', @$_), "/n";
    }
    print "/n";
}

sub Usage(){
    return "$0 /path/to/dictionary /path/to/your_words";
}

Answer 2

Bueno, el problema en sí mismo no se puede resolver con solo una expresión regular. Una solución (probablemente no la mejor) sería obtener un diccionario y hacer una coincidencia de expresión regular para cada trabajo en el diccionario con cada palabra en la lista, agregando el espacio cada vez que sea exitoso. Ciertamente, esto no sería terriblemente rápido, pero sería fácil de programar y más rápido que hacerlo manualmente.

Answer 3

Creo que tienes razón al pensar que no es realmente un trabajo para una expresión regular. Me acercaría a esto usando la idea del diccionario: busque el prefijo más largo que es una palabra en el diccionario. Cuando lo encuentres, córtalo y haz lo mismo con el resto de la cadena.

El método anterior está sujeto a ambigüedad, por ejemplo, "drivereallyfast" encontraría primero "driver" y luego tendría problemas con "eallyfast". Así que también tendrías que hacer un poco de retroceso si te topas con esta situación. O bien, dado que no tiene tantas cadenas para dividir, simplemente haga a mano las que fallan en la división automática.

Answer 4

El algoritmo de Viterbi es mucho más rápido. Calcula los mismos puntajes que la búsqueda recursiva en la respuesta de Dmitry anterior, pero en O (n) tiempo. (La búsqueda de Dmitry toma tiempo exponencial, Viterbi lo hace mediante programación dinámica).

import re
from collections import Counter

def viterbi_segment(text):
    probs, lasts = [1.0], [0]
    for i in range(1, len(text) + 1):
        prob_k, k = max((probs[j] * word_prob(text[j:i]), j)
                        for j in range(max(0, i - max_word_length), i))
        probs.append(prob_k)
        lasts.append(k)
    words = []
    i = len(text)
    while 0 < i:
        words.append(text[lasts[i]:i])
        i = lasts[i]
    words.reverse()
    return words, probs[-1]

def word_prob(word): return dictionary[word] / total
def words(text): return re.findall(''[a-z]+'', text.lower()) 
dictionary = Counter(words(open(''big.txt'').read()))
max_word_length = max(map(len, dictionary))
total = float(sum(dictionary.values()))

Probándolo:

>>> viterbi_segment(''wickedweather'')
([''wicked'', ''weather''], 5.1518198982768158e-10)
>>> '' ''.join(viterbi_segment(''itseasyformetosplitlongruntogetherblocks'')[0])
''its easy for me to split long run together blocks''

Para ser práctico, es probable que desee un par de mejoras:

• Agregue registros de probabilidades, no multiplique las probabilidades. Esto evita el underflow del punto flotante.
• Sus entradas en general usarán palabras que no están en su corpus. A estas subcadenas se les debe asignar una probabilidad distinta de cero como palabras, o terminas sin solución o una mala solución. (Esto es igualmente cierto para el algoritmo de búsqueda exponencial anterior). Esta probabilidad tiene que desviarse de las probabilidades de las palabras del corpus y distribuirse de manera plausible entre todas las demás palabras candidatas: el tema general se conoce como suavizado en modelos de lenguaje estadístico. (Sin embargo, puedes salirte con algunos trucos bastante toscos). Aquí es donde el algoritmo de O (n) Viterbi elimina el algoritmo de búsqueda, porque considerar las palabras que no son del corpus hace explotar el factor de ramificación.

Answer 5

Esto está relacionado con un problema conocido como división de identificador o tokenización de nombre de identificador . En el caso del OP, las entradas parecen ser concatenaciones de palabras ordinarias; en la división de identificadores, las entradas son nombres de clase, nombres de funciones u otros identificadores del código fuente, y el problema es más difícil. Me doy cuenta de que esta es una vieja pregunta y el OP ha resuelto su problema o seguido, pero en caso de que alguien más se encuentre con esta pregunta mientras busca divisores de identificador (como hace poco), me gustaría ofrecerle Spiral ( " SPLITTERS PARA IDENTIFICADORES: UNA BIBLIOTECA "). Está escrito en Python pero viene con una utilidad de línea de comandos que puede leer un archivo de identificadores (uno por línea) y dividir cada uno.

Dividir identificadores es engañosamente difícil. Los programadores comúnmente usan abreviaturas, acrónimos y fragmentos de palabras al nombrar cosas, y no siempre usan convenciones consistentes. Incluso cuando los identificadores siguen alguna convención como el caso camel, pueden surgir ambigüedades.

Spiral implementa numerosos algoritmos de división de identificador, incluido un nuevo algoritmo llamado Ronin. Utiliza una variedad de reglas heurísticas, diccionarios de inglés y tablas de frecuencias de tokens obtenidas de los repositorios de código fuente de minería de datos. Ronin puede dividir identificadores que no usan camel case u otras convenciones de nomenclatura, incluidos casos como la división de J2SEProjectTypeProfiler en [ J2SE , Project , Type , Profiler ], que requiere que el lector reconozca J2SE como una unidad. Aquí hay algunos ejemplos más de lo que Ronin puede dividir:

# spiral mStartCData nonnegativedecimaltype getUtf8Octets GPSmodule savefileas nbrOfbugs
mStartCData: [''m'', ''Start'', ''C'', ''Data'']
nonnegativedecimaltype: [''nonnegative'', ''decimal'', ''type'']
getUtf8Octets: [''get'', ''Utf8'', ''Octets'']
GPSmodule: [''GPS'', ''module'']
savefileas: [''save'', ''file'', ''as'']
nbrOfbugs: [''nbr'', ''Of'', ''bugs'']

Usando los ejemplos de la pregunta del OP:

# spiral wickedweather liquidweather  driveourtrucks gocompact slimprojector
wickedweather: [''wicked'', ''weather'']
liquidweather: [''liquid'', ''weather'']
driveourtrucks: [''driveourtrucks'']
gocompact: [''go'', ''compact'']
slimprojector: [''slim'', ''projector'']

Como puede ver, no es perfecto. Vale la pena señalar que Ronin tiene una serie de parámetros y ajustarlos hace posible dividir driveourtrucks también, pero a costa de empeorar el rendimiento en los identificadores de programa.

Se puede encontrar más información en el Spiral .

Answer 6

La mejor herramienta para el trabajo aquí es la recursión, no las expresiones regulares. La idea básica es comenzar desde el principio de la cuerda buscando una palabra, luego tomar el resto de la cuerda y buscar otra palabra, y así sucesivamente hasta que se llegue al final de la cuerda. Una solución recursiva es natural, ya que el retroceso debe suceder cuando un resto determinado de la cadena no se puede dividir en un conjunto de palabras. La siguiente solución usa un diccionario para determinar qué es una palabra e imprime las soluciones a medida que las encuentra (algunas cadenas se pueden dividir en múltiples conjuntos de palabras posibles, por ejemplo, wickedweather podría analizarse como "malvados en ella"). Si solo desea un conjunto de palabras, necesitará determinar las reglas para seleccionar el mejor conjunto, tal vez seleccionando la solución con el menor número de palabras o estableciendo una longitud de palabra mínima.

#!/usr/bin/perl

use strict;

my $WORD_FILE = ''/usr/share/dict/words''; #Change as needed
my %words; # Hash of words in dictionary

# Open dictionary, load words into hash
open(WORDS, $WORD_FILE) or die "Failed to open dictionary: $!/n";
while (<WORDS>) {
  chomp;
  $words{lc($_)} = 1;
}
close(WORDS);

# Read one line at a time from stdin, break into words
while (<>) {
  chomp;
  my @words;
  find_words(lc($_));
}

sub find_words {
  # Print every way $string can be parsed into whole words
  my $string = shift;
  my @words = @_;
  my $length = length $string;

  foreach my $i ( 1 .. $length ) {
    my $word = substr $string, 0, $i;
    my $remainder = substr $string, $i, $length - $i;
    # Some dictionaries contain each letter as a word
    next if ($i == 1 && ($word ne "a" && $word ne "i"));

    if (defined($words{$word})) {
      push @words, $word;
      if ($remainder eq "") {
        print join('' '', @words), "/n";
        return;
      } else {
        find_words($remainder, @words);
      }
      pop @words;
    }
  }

  return;
}

Answer 7

Me pueden descifrar por esto, pero que la secretaria lo haga .

Pasará más tiempo en una solución de diccionario de lo que le llevaría procesar manualmente. Además, posiblemente no tendrá una confianza del 100% en la solución, por lo que igual tendrá que darle atención manual.

Answer 8

Se requeriría una solución basada en diccionario. Esto podría simplificarse un poco si tiene un diccionario limitado de palabras que puede ocurrir, de lo contrario las palabras que forman el prefijo de otras palabras van a ser un problema.