如何拆分多个连接词?
nlp
5
0

我有大约1000个条目的数组,下面是示例:

wickedweather
liquidweather
driveourtrucks
gocompact
slimprojector

我希望能够将它们分为各自的词,例如:

wicked weather
liquid weather
drive our trucks
go compact
slim projector

我希望我能做到一个正则表达式。但是,由于我没有止境可言,因此我也没有可能要大写的任何大写字母,因此可能需要某种对字典的引用?

我想可以手工完成,但是为什么-什么时候可以用代码完成! =)但是,这让我感到难过。有任何想法吗?

参考资料:
Stack Overflow
收藏
评论
共 6 个回答
高赞 时间 活跃

最好的工具是递归,而不是正则表达式。基本思想是从字符串的开头开始寻找一个单词,然后从字符串的其余部分开始寻找另一个单词,依此类推,直到到达字符串的末尾。递归解决方案是很自然的,因为当字符串的给定其余部分不能分解为一组单词时,需要进行回溯。下面的解决方案使用词典来确定什么是单词,并在找到它们时打印出解决方案(一些字符串可以分解为多个可能的单词集,例如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;
}
收藏
评论

点安装wordninja

>>> import wordninja
>>> wordninja.split('bettergood')
['better', 'good']
收藏
评论

Viterbi算法要快得多。它计算与上述Dmitry答案中的递归搜索相同的分数,但是时间为O(n)。 (Dmitry的搜索花费了指数时间; 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'

实际上,您可能需要进行一些改进:

  • 添加概率日志,不要乘以概率。这样可以避免浮点下溢。
  • 您的输入通常会使用不在您的语料库中的单词。这些子字符串必须被指定为非零概率的单词,否则您最终将无解或有坏解。 (上面的指数搜索算法也是如此。)必须从语料库词的概率中抽取这种可能性,并在所有其他候选词之间合理地分配这种可能性:一般主题在统计语言模型中被称为平滑。 (不过,您可以逃脱一些相当粗暴的技巧。)这是O(n)Viterbi算法使搜索算法无效的地方,因为考虑非语料词会使分支因子增大。
收藏
评论

我认为您认为对正则表达式实际上不是一项工作是正确的。我将使用字典的想法来解决这个问题-寻找字典中一个单词的最长前缀。找到后,将其切碎,然后对字符串的其余部分执行相同的操作。

上面的方法存在歧义,例如“ drivereallyfast”将首先找到“ driver”,然后在使用“ eallyfast”时遇到麻烦。因此,如果遇到这种情况,您还必须做一些回溯。或者,由于您无需拆分太多字符串,因此只需手动执行自动拆分失败的字符串即可。

收藏
评论

这与称为标识符拆分标识符名称标记化的问题有关。在OP的情况下,输入似乎是普通单词的串联;在标识符拆分中,输入的是类名,函数名或源代码中的其他标识符,问题更加棘手。我意识到这是一个老问题,OP已经解决了他们的问题或继续前进,但是如果其他人在寻找标识符分割器时遇到了这个问题(就像我不久前一样),我想提供Spiral ( “ 标识符的分散器:库 ”)。它是用Python编写的,但带有一个命令行实用程序,该实用程序可以读取一个标识符文件(每行一个)并拆分每个标识符。

分割标识符似乎很难。程序员在命名事物时通常使用缩写词,首字母缩写词和单词片段,并且他们并不总是使用一致的约定。即使在标识符确实遵循某种约定(例如骆驼案)的情况下,也可能出现歧义。

Spiral实现了多种标识符拆分算法,包括一种称为Ronin的新颖算法。它使用各种启发式规则,英语词典以及从挖掘源代码存储库获得的令牌频率表。 Ronin可以拆分不使用驼峰式大小写或其他命名约定的标识符,包括将J2SEProjectTypeProfiler拆分为[ J2SEProjectTypeProfiler ]之类的情况,这要求读者将J2SE识别为一个单元。以下是Ronin可以拆分的更多示例:

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

使用OP问题中的示例:

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

如您所见,它并不完美。值得注意的是,罗宁(Ronin)有许多参数,对其进行调整也可以拆分driveourtrucks ,但代价是程序标识符的性能driveourtrucks

SpiralGitHub存储库中可以找到更多信息。

收藏
评论

人类可以做到吗?

farsidebag
far sidebag
farside bag
far side bag

您不仅需要使用字典,还可能需要使用统计方法来找出最可能的方法(或者,上帝禁止,您所选择的人类语言的实际HMM ...)

有关如何做可能有用的统计信息,请转到Peter Norvig博士,他在21行代码中解决了另一个不同但相关的拼写检查问题: http : //norvig.com/spell-correct.html

(他确实通过将每个for循环折叠为一行来作弊。

更新这卡在我的脑海,所以我今天必须出生。这段代码与Robert Gamble所描述的代码类似,但是它根据提供的字典文件中的单词频率对结果进行排序(现在期望该文件通常代表您的域或英语。我使用了big链接到上方的Norvig的.txt,并为其添加了字典,以弥补遗漏的单词)。

除非频率差异很大,否则两个单词的组合通常会击败三个单词的组合。


我在博客上发布了此代码,并做了一些小的更改

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";
}
收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号