여러 단어를 어떻게 분리 할 수 ​​있습니까?

Question

이들을 각각의 단어로 나눌 수 있기를 바랍니다.

wicked weather 
liquid weather 
drive our trucks 
go compact 
slim projector 

표현 내 속임수. 그러나 내가 멈추지 않을 경계가 없기 때문에, 내가 핵심이 될 수있는 어떤 종류의 대문자도 없으며 사전에 대한 어떤 종류의 참조가 필요할지도 모른다고 생각하고 있습니까?

나는 그것이 손으로 할 수 있다고 생각하지만, 왜 - 코드로 할 수있을 때! =) 그러나 이것은 나를 곤란하게 만들었습니다. 어떤 아이디어?

Answer 1

인간이 할 수 있습니까?

 
farsidebag 
far sidebag 
farside bag 
far side bag 

뿐만 아니라 당신은, 당신이 가장 가능성의 의미를 알아 내기 위해 통계적 방법을 사용 할 수있는 사전을 사용해야합니까 (선택의 인간의 언어, 신 금지, 실제 HMM 또는 ...) 도움이 될 수있는 통계 작업을 수행하는 방법에 대한

, 나는 다른,하지만 관련 문제를 해결 박사 피터 노빅로 변신 맞춤법 검사 코드의 21 라인 : http://norvig.com/spell-correct.html

을

(he 모든 for 루프를 한 줄로 접어서 속임수를 사용합니다.하지만 여전히).

업데이트이는 내 머리에 갇혀, 그래서 나는 오늘을 출산했다있어.이 코드는 로버트 갬블 (Robert Gamble)이 설명한 것과 비슷한 방식으로 분할하지만 제공된 사전 파일에서 단어 빈도를 기반으로 결과를 정렬합니다 (현재 도메인이나 영어를 나타내는 일부 텍스트로 예상 됨). 위의 링크 된 Norvig의 .txt와 누락 된 단어를 충당하기 위해 사전을 catted).

주파수 차이가 엄청나지 않는 한 두 단어의 조합은 대부분 3 개의 단어 조합을 이길 것입니다.

---

은 내 블로그

http://squarecog.wordpress.com/2008/10/19/splitting-words-joined-into-a-single-string/ 에 약간의 변경이 코드를 게시하고이 코드의 언더 버그에 대해 조금 썼다 .. 난 그냥 조용히 그것을 해결하기 위해 유혹했지만, 이 전에 로그 트릭을 보지 못한 일부 사람들 데 도움이 될 수 있습니다 생각 : 귀하의 단어에 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($@); 
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

정규 표현식에 대한 직업이 아니라고 생각하는 것이 맞다고 생각합니다. 나는 사전 아이디어를 사용하여 이것을 접근 할 것입니다 - 사전에서 단어 인 가장 긴 접두어를 찾으십시오. 당신이 그것을 발견 할 때, 그것을 자르고 나머지 문자열과 똑같이하십시오.

위의 방법은 모호한 경우가 있습니다. 예를 들어 "drivereallyfast"는 먼저 "드라이버"를 찾은 다음 "eallyfast"에 문제가있는 것입니다. 이 상황에 처했을 때 다시 추적해야합니다. 또는 분할 할 문자열이 많지 않으므로 자동 분할에 실패한 문자열을 직접 처리하십시오.

Answer 3

글쎄, 문제 자체는 정규 표현식으로 해결할 수 없습니다. 솔루션 (아마도 최고는 아닐 것입니다)은 사전을 가져 와서 목록의 각 단어에 대한 사전의 각 작업에 대한 정규식 일치를 수행하여 성공할 때마다 공백을 추가하는 것입니다. 분명히 이것은 굉장히 빠르지는 않을 것이지만, 프로그램하기가 쉽고 손으로하는 것보다 빠르다.

Answer 4

사전 기반 솔루션이 필요합니다. 제한된 단어 사전이있는 경우이 방법이 다소 단순화 될 수 있습니다. 그렇지 않으면 다른 단어의 접두사를 구성하는 단어가 문제가 될 수 있습니다.

Answer 5

나는 이것으로 다운 모드 될 수 있지만, 은 비서가으로되어있다.

수작업으로 처리하는 것보다 사전 솔루션에 더 많은 시간을 할애 할 수 있습니다. 또한 솔루션에 100 % 확신을 가지지 않으므로 어쨌든 수동주의를 기울여야합니다.

Answer 6

여기에 작업의 가장 좋은 도구는 재귀하지 정규 표현식입니다. 기본 개념은 단어를 찾는 문자열의 시작부터 시작한 다음 문자열의 나머지 부분을 가져 와서 다른 단어를 찾는 것입니다. 문자열의 끝에 도달 할 때까지 계속됩니다. 문자열의 나머지 부분을 단어 집합으로 나눌 수없는 경우 역 추적이 필요하기 때문에 재귀 적 솔루션은 자연 스럽습니다. 아래의 솔루션은 사전을 사용하여 단어가 무엇인지 판단하고 해결책을 찾아 낼 때이를 인쇄합니다 (일부 문자열은 가능한 여러 단어 집합으로 나눌 수 있습니다. 예를 들어 wickedweather는 "wicked our at her"). 하나의 단어 집합 만 원할 경우 단어 수가 가장 적은 솔루션을 선택하거나 최소 단어 길이를 설정하여 최상의 집합을 선택하는 규칙을 결정해야합니다.

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

Viterbi algorithm은 훨씬 빠릅니다. 위의 드미트리 응답에서 재귀 검색과 동일한 점수를 계산하지만 O (n) 시간에 계산합니다. (드미트리의 검색 지수 시간이 걸립니다, 비터 비 (Viterbi)는 동적 프로그래밍하여 작업을 수행합니다.)

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' 
  

  당신은 가능성이 몇 개선을 할 것 실용적 확률 로그를 추가하고 확률을 곱하지 마십시오. 이렇게하면 부동 소수점 언더 플로가 발생하지 않습니다.

• 귀하의 의견은 일반적으로 귀하의 코퍼스에없는 단어를 사용합니다. 이 하위 문자열에는 단어로 0이 아닌 확률을 지정해야합니다. 그렇지 않으면 해결책이 없거나 나쁜 솔루션으로 끝납니다. (위의 지수 검색 알고리즘의 경우와 마찬가지입니다.)이 확률은 코퍼스 단어의 확률을 어지럽히고 모든 다른 단어 후보자 사이에 그럴듯하게 분포되어야합니다. 일반적인 주제는 통계 언어 모델에서 스무딩이라고합니다. (당신은 꽤 거친 해킹으로 도망 갈 수 있습니다.) 이것은 O (n) 비터 비 알고리즘이 검색 알고리즘을 날려 버리는 곳입니다. 왜냐하면 비 - 코퍼스 단어가 브랜칭 인자를 날려 버리기 때문입니다.