string - word_tokenize - remove punctuation python nltk




Come posso dividere più parole unite? (6)

Ho una matrice di circa 1000 voci, con esempi di seguito:

wickedweather
liquidweather
driveourtrucks
gocompact
slimprojector

Vorrei poterli dividere nelle loro rispettive parole, come:

wicked weather
liquid weather
drive our trucks
go compact
slim projector

Speravo in un'espressione regolare, il mio è il trucco. Ma, dato che non ci sono limiti su cui fermarsi, né esiste una qualche forma di capitalizzazione a cui potrei mai affidarmi, sto pensando, che potrebbe essere necessaria una sorta di riferimento a un dizionario?

Suppongo che potrebbe essere fatto a mano, ma perché - quando può essere fatto con il codice! =) Ma questo mi ha messo in difficoltà. Qualche idea?


Bene, il problema in sé non è risolvibile con solo un'espressione regolare. Una soluzione (probabilmente non la migliore) sarebbe quella di ottenere un dizionario e fare una corrispondenza di espressioni regolari per ogni lavoro nel dizionario per ogni parola nella lista, aggiungendo lo spazio ogni volta che ha successo. Certamente questo non sarebbe terribilmente veloce, ma sarebbe facile da programmare e più veloce della mano che lo fa.


Ciò è correlato a un problema noto come tokenizzazione del codice identificativo o identificatore del nome dell'identificatore . Nel caso del PO, gli input sembrano concatenazioni di parole ordinarie; nella divisione dell'identificatore, gli input sono nomi di classi, nomi di funzioni o altri identificatori del codice sorgente e il problema è più difficile. Mi rendo conto che questa è una vecchia domanda e l'OP ha risolto il problema o spostato, ma nel caso in cui qualcun altro si imbattesse in questa domanda mentre cercava i separatori di identificatori (come lo ero io, non molto tempo fa), vorrei offrire Spiral ( " SPlitters for IdentifieRs: A Library "). È scritto in Python ma viene fornito con un'utilità della riga di comando in grado di leggere un file di identificatori (uno per riga) e dividerli.

La divisione degli identificatori è ingannevolmente difficile. I programmatori usano comunemente abbreviazioni, acronimi e frammenti di parole quando nominano le cose, e non sempre usano convenzioni coerenti. Anche quando gli identificatori seguono alcune convenzioni come il caso dei cammelli, possono sorgere ambiguità.

Spiral implementa numerosi algoritmi di suddivisione degli identificativi, incluso un nuovo algoritmo chiamato Ronin. Usa una varietà di regole euristiche, dizionari inglesi e tabelle di frequenze token ottenute dagli archivi di codice sorgente di minatori. Ronin può dividere gli identificatori che non usano il caso cammello o altre convenzioni di denominazione, inclusi casi come la divisione di J2SEProjectTypeProfiler in [ J2SE , Project , Type , Profiler ], che richiede al lettore di riconoscere J2SE come un'unità. Ecco alcuni esempi di ciò che Ronin può dividere:

# 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']

Utilizzando gli esempi dalla domanda dell'OP:

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

Come puoi vedere, non è perfetto. Vale la pena notare che Ronin ha un numero di parametri e la loro regolazione consente di dividere anche il driveourtrucks , ma al costo di peggiorare le prestazioni sugli identificatori del programma.

Ulteriori informazioni possono essere trovate nel Spiral .


Lo strumento migliore per il lavoro qui è la ricorsione, non le espressioni regolari. L'idea di base è iniziare dall'inizio della stringa cercando una parola, quindi prendere il resto della stringa e cercare un'altra parola, e così via fino al raggiungimento della fine della stringa. Una soluzione ricorsiva è naturale poiché il backtracking deve accadere quando un dato resto della stringa non può essere spezzato in un insieme di parole. La soluzione seguente utilizza un dizionario per determinare cos'è una parola e stampa le soluzioni così come le trova (alcune stringhe possono essere suddivise in più possibili gruppi di parole, ad esempio wickedweather potrebbe essere analizzato come "malvagio noi a lei"). Se si desidera solo un set di parole, sarà necessario determinare le regole per selezionare il set migliore, magari selezionando la soluzione con il minor numero di parole o impostando una lunghezza minima della parola.

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

Penso che tu abbia ragione nel pensare che non è davvero un lavoro per un'espressione regolare. Mi avvicinerei a questo usando l'idea del dizionario: cerca il prefisso più lungo che è una parola nel dizionario. Quando lo trovi, taglialo e fai lo stesso con il resto della stringa.

Il metodo di cui sopra è soggetto ad ambiguità, per esempio "drivereallyfast" dovrebbe prima trovare "driver" e quindi avere problemi con "eallyfast". Quindi dovresti fare qualche passo indietro se ti sei imbattuto in questa situazione. Oppure, dato che non hai molte stringhe da dividere, fai semplicemente a mano quelle che falliscono la divisione automatica.


Può un umano farlo?

farsidebag
far sidebag
farside bag
far side bag

Non solo devi usare un dizionario, potresti dover usare un approccio statistico per capire cosa è più probabile (o, dio non voglia, un vero HMM per il tuo linguaggio umano di scelta ...)

Per come fare statistiche che potrebbero essere utili, ti rivolgo al Dr. Peter Norvig, che affronta un problema diverso ma correlato di controllo ortografico in 21 righe di codice : http://norvig.com/spell-correct.html

(fa un cheat un po 'piegando ogni ciclo for in una sola riga .. ma ancora).

Aggiornamento Mi sono bloccato nella mia testa, quindi ho dovuto nascerlo oggi. Questo codice fa una divisione simile a quella descritta da Robert Gamble, ma poi ordina i risultati in base alla frequenza delle parole nel file dizionario fornito (che ora dovrebbe essere un testo rappresentativo del tuo dominio o inglese in generale. .txt da Norvig, linkato sopra, e ha un dizionario di catture ad esso, per coprire le parole mancanti).

Una combinazione di due parole per la maggior parte del tempo batte una combinazione di 3 parole, a meno che la differenza di frequenza non sia enorme.

Ho postato questo codice con alcune modifiche minori sul mio blog

http://squarecog.wordpress.com/2008/10/19/splitting-words-joined-into-a-single-string/ e ha anche scritto un po 'sul bug di underflow in questo codice .. Sono stato tentato di tranquillamente risolvilo, ma ho pensato che questo potrebbe aiutare alcune persone che non hanno visto il trucco del registro prima: http://squarecog.wordpress.com/2009/01/10/dealing-with-underflow-in-joint-probability-calculations/

Uscita sulle tue parole, più alcune mie - osserva cosa succede 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

Codice:

#!/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([email protected]);
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([email protected]){
    #( '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";
}

Sarebbe necessaria una soluzione basata su dizionario. Questo potrebbe essere semplificato se si dispone di un dizionario limitato di parole che possono verificarsi, altrimenti le parole che formano il prefisso di altre parole saranno un problema.





nlp