我怎样才能拆分多个连接的单词?

我有一个数组1000个左右的条目,下面的例子:

wickedweather liquidweather driveourtrucks gocompact slimprojector 

我希望能够将这些分成他们各自的单词,如:

 wicked weather liquid weather drive our trucks go compact slim projector 

我希望能有个正则expression式, 但是,既然没有边界可以停下来,也没有任何我可能关注的资本化,我想,对字典的某种提及可能是必要的。

我想这可以通过手工完成,但为什么 – 当它可以用代码完成! =)但是这一直困扰着我。 有任何想法吗?

人能做到吗?

 farsidebag
很远的侧面
背包
远侧袋

你不仅需要使用字典,你可能不得不使用统计方法来找出最有可能的(或者上帝保佑你的人类语言select的实际HMM)

关于如何做统计可能会有所帮助,我把你转到Peter Norvig博士,他解释了21行代码中拼写检查的一个不同但相关的问题: http : //norvig.com/spell-correct.html

(他通过折叠每一个循环成一条线,但仍然)作弊。

更新这卡住了我的头,所以我不得不出生今天。 此代码与Robert Gamble描述的代码类似,但是它会根据提供的字典文件中的字词频率sorting(现在预计这些代码将会是一些代表您的域或英文的文本)来自Norvig的.txt,链接在上面,并收录了一本字典,以涵盖遗漏的单词)。

两个单词的组合将大部分时间击败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文字
 answerveal:2种可能性
  - 回答小牛肉
  - 回答ve al

邪恶的天气:4种可能性
  - 恶劣的天气
  - 邪恶我们在她身上
  - 邪恶的天气
  - 我们在她身边

液体天气:6种可能性
  - 液体天气
  - 我们在她身上的液体
  - 李天气
  - 我们在她身边
  -  li qu id天气
 我们在她身边

 driveourtrucks:1种可能性
  - 驾驶我们的卡车

 gocompact:1种可能性
  - 紧凑

超薄投影机:2种可能性
  - 苗条的投影机
  - 苗条的项目或

 orcore:3种可能性
  - 或核心
  - 或合作
  - 矿石

码:

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

维特比algorithm要快得多。 它计算与德米特里上面的回答中的recursionsearch相同的分数,但是在O(n)时间。 (德米特里的search需要指数的时间;维特比是通过dynamic编程来完成的。)

 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('[az]+', text.lower()) dictionary = Counter(words(open('big.txt').read())) max_word_length = max(map(len, dictionary)) total = float(sum(dictionary.values())) 

testing它:

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

为了实践,你可能需要一些改进:

  • 添加概率的日志,不要乘以概率。 这避免了浮点下溢。
  • 您的input将通常使用不在您的语料库中的单词。 这些子string必须被赋予一个非零的概率作为单词,否则你最终没有解决scheme或一个不好的解决scheme。 (对于上述指数searchalgorithm,情况也是如此)。这个概率必须从语料库词的概率中抽取出来,并在所有其他词候选词之间进行合理分配:一般的主题在统计语言模型中被称为平滑。 (尽pipe你可以避开一些非常粗糙的黑客)。这是O(n)维特比algorithm吹走searchalgorithm的地方,因为考虑到非语料库的话会使分支因素爆炸。

这里的工作最好的工具是recursion,而不是正则expression式。 基本思想是从string的开始处开始寻找一个单词,然后取出string的其余部分并查找另一个单词,依此类推,直到到达string的末尾。 一个recursion的解决scheme是很自然的,因为当给定的string的剩余部分不能被分解成一组单词时,需要发生回溯。 下面的解决scheme使用字典来确定什么是单词,并在find解决scheme时打印出解决scheme(某些string可以分解成多个可能的单词集合,例如,邪恶的天气可能被parsing为“我们对她很邪恶”)。 如果你只想要一组单词,你需要确定select最佳组合的规则,也许可以通过select具有最less字数的解决scheme或通过设置最小字长来确定。

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

我想你是对的,认为这不是一个正则expression式的工作。 我会用字典的想法来解决这个问题 – 查找字典中最长的前缀。 当你发现这一点时,把它砍掉,并对string的其余部分做相同的处理。

上述方法容易模糊,例如“drivereallyfast”会首先find“driver”,然后在“eallyfast”中遇到问题。 所以如果遇到这种情况,你也必须做一些回溯。 或者,因为你没有那么多的string可以分割,只需要手动执行那些自动分割失败的string。

那么,这个问题本身不能用一个正则expression式来解决。 一个解决scheme(可能不是最好的)将是得到一个字典,并为字典中的每个工作进行正则expression式匹配到列表中的每个单词,每当成功时添加空间。 当然,这不会太快,但是编程比较简单,而且比手工更快。

基于字典的解决scheme将是必需的。 如果你有一个可能发生的单词的有限字典,这可能会被简化,否则形成其他单词前缀的单词将成为一个问题。

我可能会为此而下滑,但秘书呢

你会花费更多的时间在字典解决scheme,而不是手动处理。 而且,你不可能对解决scheme有100%的信心,所以你仍然必须给予手动关注。