Comment puis-je diviser plusieurs mots joints?

L'algorithme Viterbi est beaucoup plus rapide. Il calcule les mêmes scores que la recherche récursive dans la réponse de Dmitry ci-dessus, mais en temps O (N). (La recherche de Dmitry prend du temps exponentiel; Viterbi le fait par programmation dynamique.)

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()))

Tester:

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

Pour être pratique, vous voudrez probablement quelques améliorations:

• ajoutez des journaux de probabilités, ne multipliez pas les probabilités. Cela évite le sous-débit en virgule flottante.
• vos entrées seront en général utilisées mots qui ne sont pas dans votre corpus. Ces sous-chaînes doivent recevoir une probabilité non nulle en tant que mots, ou vous vous retrouvez avec aucune solution ou une mauvaise solution. (C'est tout aussi vrai pour l'algorithme de recherche exponentielle ci-dessus.) Cette probabilité doit être siphonnée des probabilités des mots du corpus et distribuée de manière plausible entre tous les autres candidats de mots: le sujet général est connu sous le nom de lissage dans les modèles de langage statistique. (Vous pouvez vous en sortir avec des hacks assez rugueux, cependant.) C'est là que le O (N) Viterbi algorithme souffle l'algorithme de recherche, parce que considérer les mots non-corpus explose le facteur de ramification.

Le meilleur outil pour le travail ici est la récursivité, pas les expressions régulières. L'idée de base est de commencer par le début de la chaîne à la recherche d'un mot, puis de prendre le reste de la chaîne et de chercher un autre mot, et ainsi de suite jusqu'à la fin de la chaîne. Une solution récursive est naturelle car le retour en arrière doit se produire lorsqu'un reste donné de la chaîne ne peut pas être divisé en un ensemble de mots. La solution ci-dessous utilise un dictionnaire pour déterminer ce qu'est un mot, et imprime solutions telles qu'elles les trouvent (certaines chaînes peuvent être divisées en plusieurs ensembles de mots possibles, par exemple wickedweather pourrait être analysé comme "wicked we at her"). Si vous voulez juste un ensemble de mots, vous devrez déterminer les règles pour sélectionner le meilleur ensemble, peut-être en sélectionnant la solution avec le moins de mots ou en définissant une longueur de mot minimale.

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

Je pense que vous avez raison de penser que ce n'est pas vraiment un travail pour une expression régulière. J'aborderais cela en utilisant l'idée du dictionnaire-recherchez le préfixe le plus long qui est un mot dans le dictionnaire. Lorsque vous trouvez cela, coupez-le et faites de même avec le reste de la chaîne.

La méthode ci-dessus est sujette à ambiguïté, par exemple "drivereallyfast" trouverait d'abord "driver" et aurait ensuite des problèmes avec "eallyfast". Donc, vous devrez également faire un retour en arrière si vous avez rencontré cette situation. Ou, puisque vous n'avez pas beaucoup de chaînes à diviser, faites simplement à la main celles qui échouent à la division automatisée.

Eh bien, le problème lui-même n'est pas résolu avec juste une expression régulière. Une solution (probablement pas la meilleure) serait d'obtenir un dictionnaire et de faire une correspondance d'expression régulière pour chaque travail dans le dictionnaire à chaque mot de la liste, en ajoutant l'Espace chaque fois que c'est réussi. Certes, ce ne serait pas terriblement rapide, mais il serait facile à programmer et plus rapide que la main le faire.

Une solution basée sur un dictionnaire serait nécessaire. Cela pourrait être simplifié quelque peu si vous avez un dictionnaire limité de mots qui peuvent se produire, sinon les mots qui forment le préfixe d'autres mots vont être un problème.

Ceci est lié à un problème connu sous le nom de identifiant fractionnement ou identifiant nom tokenization. Dans le cas de L'OP, les entrées semblent être des concaténations de mots ordinaires; dans le fractionnement des identifiants, les entrées sont des noms de classe, des noms de fonction ou d'autres identificateurs du code source, et le problème est plus difficile. Je me rends compte que c'est une vieille question et que le PO a résolu leur problème ou est passé à autre chose, mais au cas où quelqu'un d'autre rencontrerait cette question en cherchant identifiant splitters (comme je l'étais, il n'y a pas longtemps), je voudrais offrir spirale ("diviseurs pour les identificateurs: une bibliothèque "). Il est écrit en Python mais est livré avec un utilitaire de ligne de commande qui peut lire un fichier d'identifiants (un par ligne) et diviser chacun.

Diviser les identifiants est trompeusement difficile. Les programmeurs utilisent généralement des abréviations, des acronymes et des fragments de mots lorsqu'ils nomment des choses, et ils n'utilisent pas toujours des conventions cohérentes. Même quand les identificateurs suivent certaines conventions telles que le cas des chameaux, des ambiguïtés peuvent survenir.

Spiral implémente de nombreux algorithmes de fractionnement d'identifiants, y compris un nouvel algorithme appelé Ronin. Il utilise une variété de règles heuristiques, de dictionnaires anglais et de tables de fréquences de jetons obtenues à partir de dépôts de code source miniers. Ronin peut diviser des identifiants qui n'utilisent pas camel case ou d'autres conventions de nommage, y compris des cas tels que le fractionnement de J2SEProjectTypeProfiler en [J2SE, Project, Type, Profiler], ce qui oblige le lecteur à reconnaître J2SE comme une unité. Voici quelques autres exemples de ce que Ronin peut diviser:

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

En utilisant les exemples de la question du PO:

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

Comme vous pouvez le voir, ce n'est pas parfait. Il est à noter que Ronin a un certain nombre de paramètres et que leur ajustement permet également de diviser driveourtrucks, mais au prix d'une détérioration des performances sur les identificateurs de programme.

Plus d'informations peuvent être trouvées dans le dépôt GitHub pour Spirale .

Je peux être downmoded pour cela, mais Demandez à la secrétaire de le faire .

Vous passerez plus de temps sur une solution de dictionnaire qu'il ne faudrait pour traiter manuellement. De plus, vous n'aurez peut-être pas confiance à 100% dans la solution, donc vous devrez quand même lui accorder une attention manuelle.