我怎样才能拆分多个连接的单词？
我有一个数组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％的信心，所以你仍然必须给予手动关注。
