Как я могу разделить несколько соединенных слов?

Ответ 1

Может ли человек это сделать?

farsidebag
far sidebag
farside bag
far side bag

Вам не только нужно использовать словарь, возможно, вам придется использовать статистический подход, чтобы выяснить, что наиболее вероятно (или, боже, запретите, реальный HMM для вашего человеческого языка выбора...)

Для того, чтобы сделать статистику, которая может быть полезна, я обращаюсь к доктору Питеру Норвигу, который рассматривает другую, но связанную с этим проблему проверки орфографии в 21 строке кода: http://norvig.com/spell-correct.html

(он немного обманывает, складывая каждый цикл в одну строку... но все же).

Обновление Это застряло у меня в голове, поэтому мне пришлось родить его сегодня. Этот код выполняет аналогичный раскол, описанный Робертом Гэмблом, но затем он заказывает результаты на основе частоты слов в предоставленном файле словаря (который в настоящее время ожидается как часть текста, представляющего ваш домен или английский в целом..txt от Norvig, связанный выше, и привязал к нему словарь, чтобы покрыть недостающие слова).

Комбинация из двух слов будет в большинстве случаев бить комбинацию из трех слов, если разность частот огромна.

Я разместил этот код с некоторыми незначительными изменениями в своем блоге

http://squarecog.wordpress.com/2008/10/19/splitting-words-joined-into-a-single-string/ а также немного написал об ошибке underflow в этом коде. Мне было очень просто исправить это, но подумал, что это может помочь некоторым людям, которые еще не видели ловушку: http://squarecog.wordpress.com/2009/01/10/dealing-with-underflow-in-joint-probability-calculations/

Выведите на свои слова, а также несколько моих собственных - обратите внимание, что происходит с "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

код:

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

Ответ 2

алгоритм Витерби намного быстрее. Он вычисляет те же оценки, что и рекурсивный поиск в ответе Дмитрия выше, но в O (n) времени. (Поиск Дмитрием занимает экспоненциальное время, Витерби делает это путем динамического программирования.)

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

Тестирование:

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

Чтобы быть практичным, вам, вероятно, понадобятся несколько уточнений:

• Добавить журналы вероятностей, не умножать вероятности. Это позволяет избежать переполнения с плавающей запятой.
• Ваши входы будут использоваться в основном не в вашем корпусе. Этим подстрокам должна быть назначена отличная от нуля вероятность в виде слов, иначе вы не получите решения или плохого решения. (Это так же справедливо для вышеупомянутого алгоритма экспоненциального поиска.) Эта вероятность должна быть исключена из вероятностей слов корпуса и распределена правдоподобно среди всех других кандидатов слов: общая тема известна как сглаживание в моделях статистических языков. (Тем не менее, вы можете избавиться от некоторых довольно грубых хаков.) Именно здесь алгоритм O (n) Витерби сбрасывает алгоритм поиска, потому что, рассматривая не-корпусные слова, раздувает фактор ветвления.

Ответ 3

Лучшим инструментом для задания здесь является рекурсия, а не регулярные выражения. Основная идея - начать с начала строки, ищущей слово, затем взять оставшуюся часть строки и искать другое слово и так далее, пока не будет достигнут конец строки. Рекурсивное решение является естественным, так как обратное отслеживание должно происходить, когда данный остаток строки не может быть разбит на множество слов. В приведенном ниже решении используется словарь для определения того, что является словом, и распечатывает решения по мере их нахождения (некоторые строки могут быть разбиты на несколько возможных наборов слов, например, wickedweather может быть проанализирован как "злой у нас" ). Если вам нужен только один набор слов, вам нужно будет определить правила для выбора наилучшего набора, возможно, выбрав решение с наименьшим количеством слов или установив минимальную длину слова.

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

Ответ 4

Я думаю, вы правы, думая, что это не работа для регулярного выражения. Я бы подошел к этому, используя идею словаря - ищите самый длинный префикс, который является словом в словаре. Когда вы обнаружите это, отрубите его и сделайте то же самое с оставшейся частью строки.

Вышеуказанный метод подвержен двусмысленности, например "drivereallyfast" сначала найдет "драйвер", а затем будет иметь проблемы с "eallyfast". Таким образом, вы также должны были бы сделать откат, если бы столкнулись с этой ситуацией. Или, поскольку у вас не так много строк для разделения, просто делайте вручную те, которые не автоматизированы.

Ответ 5

Это связано с проблемой, известной как разделение идентификатора или токенизация имени идентификатора. В случае OP входные данные кажутся связями обычных слов; при разделении идентификаторов входными данными являются имена классов, имена функций или другие идентификаторы из исходного кода, и проблема сложнее. Я понимаю, что это старый вопрос, и ОП либо решил их проблему, либо пошел дальше, но в случае, если кто-то еще сталкивался с этим вопросом при поиске сплиттеров идентификаторов (как я это делал не так давно), я хотел бы предложить Spiral ( "Сплиттеры для Идентификаторов: Библиотека"). Он написан на Python, но поставляется с утилитой командной строки, которая может читать файл идентификаторов (по одному на строку) и разбивать каждый из них.

Разделение идентификаторов обманчиво сложно. Программисты обычно используют аббревиатуры, сокращения и фрагменты слов при именовании вещей, и они не всегда используют согласованные соглашения. Даже в тех случаях, когда идентификаторы действительно следуют некоторому соглашению, такому как случай верблюда, могут возникнуть неоднозначности.

В Spiral реализованы многочисленные алгоритмы разделения идентификаторов, в том числе новый алгоритм под названием Ronin. Он использует множество эвристических правил, английских словарей и таблиц частот токенов, полученных из хранилищ исходного кода майнинга. Ronin может разделять идентификаторы, которые не используют регистр верблюдов или другие соглашения об именах, включая такие случаи, как разделение J2SEProjectTypeProfiler на [ J2SE, Project, Type, Profiler ], что требует от читателя распознавать J2SE как единое целое. Вот еще несколько примеров того, что может разделить Ронин:

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

Используя примеры из вопроса ОП:

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

Как видите, он не идеален. Стоит отметить, что у Ronin есть ряд параметров, и их регулировка позволяет также разделять driveourtrucks, но за счет снижения производительности по идентификаторам программ.

Больше информации можно найти в репозитории GitHub для Spiral.

Ответ 6

Ну, сама проблема не разрешима с помощью обычного выражения. Решение (возможно, не самое лучшее) было бы получить словарь и выполнить регулярное выражение для каждой работы в словаре по каждому слову в списке, добавив пространство всякий раз, когда это удастся. Конечно, это было бы не очень быстро, но было бы легко программировать и быстрее, чем делать вручную.

Ответ 7

Требуется решение на основе словаря. Это может быть несколько упрощено, если у вас есть ограниченный словарь слов, который может произойти, иначе слова, которые образуют префикс других слов, будут проблемой.

Ответ 8

Я могу смириться с этим, но попросите секретаря сделать это.

Вы потратите больше времени на решение словаря, чем потребовалось бы для ручного процесса. Кроме того, у вас не будет 100% -ной уверенности в решении, поэтому вам все равно придется уделять ему внимание вручную.

Ответ 9

Существует пакет Python, выпущенный Сантошом, называемый mlmorph, который можно использовать для морфологического анализа.

https://pypi.org/project/mlmorph/

Примеры:

from mlmorph import Analyser
analyser = Analyser()
analyser.analyse("കേരളത്തിന്റെ")

дает

[('കേരളം<np><genitive>', 179)]

Он также написал блог на тему https://thottingal.in/blog/2017/11/26/towards-a-malayalam-morphology-analyser/

Ответ 10

Простое решение с помощью Python: установите пакет wordsegment: pip install wordsegment.

$ echo thisisatest | python -m wordsegment
this is a test

Ответ 11

pip install wordninja

>>> import wordninja
>>> wordninja.split('bettergood')
['better', 'good']