字符串-如何拆分多个连接的单词?

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

wickedweather
liquidweather
driveourtrucks
gocompact
slimprojector

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

wicked weather
liquid weather
drive our trucks
go compact
slim projector

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

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

Taptronic asked 2020-06-30T05:24:32Z
11个解决方案
73 votes

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算法使搜索算法无效的地方,因为考虑非语料词会使分支因子增大。
Darius Bacon answered 2020-06-30T05:26:01Z
33 votes

人类可以做到吗?

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";
}
SquareCog answered 2020-06-30T05:25:22Z
8 votes

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

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

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

Greg Hewgill answered 2020-06-30T05:26:47Z
2 votes

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

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

Spiral实现了多种标识符拆分算法,包括一种称为Ronin的新颖算法。 它使用各种启发式规则,英语词典以及从挖掘源代码存储库获得的令牌频率表。 Ronin可以拆分不使用驼峰大小写或其他命名约定的标识符,包括将driveourtrucks拆分为[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,但代价是程序标识符的性能下降。

在Spiral的GitHub存储库中可以找到更多信息。

mhucka answered 2020-06-30T05:27:31Z
1 votes

好吧,仅凭正则表达式无法解决问题。 一个解决方案(可能不是最好的)是获取字典并对字典中的每个工作与列表中的每个单词进行正则表达式匹配,并在成功时添加空格。 当然,这并不会很快,但是比手工编写起来容易编程并且速度更快。

Zoe Gagnon answered 2020-06-30T05:27:52Z
1 votes

将需要基于字典的解决方案。 如果您可以使用的单词词典有限,则可以在某种程度上简化此操作,否则形成其他单词前缀的单词将成为一个问题。

Mitch Wheat answered 2020-06-30T05:28:12Z
0 votes

我可能为此感到沮丧,但请秘书来做。

与手动处理相比,您在词典解决方案上花费的时间更多。 此外,您可能不会对解决方案有100%的信心,因此无论如何,您仍然必须手动解决该问题。

Dave Ward answered 2020-06-30T05:28:36Z
0 votes

有Santhosh thottingal发布的python软件包,称为mlmorph,可用于形态分析。

[HTTPS://皮衣皮.org/project/美丽morph/]

例子:

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

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

他还写了一个关于[https://thottingal.in/blog/2017/11/26/towards-a-malayalam-morphology-analyser/]的博客。

adam shamsudeen answered 2020-06-30T05:29:14Z
0 votes

使用Python的简单解决方案:安装wordegment软件包:pip install wordsegment

$ echo thisisatest | python -m wordsegment
this is a test
Rabash answered 2020-06-30T05:29:34Z
0 votes

点安装wordninja

>>> import wordninja
>>> wordninja.split('bettergood')
['better', 'good']
kamran kausar answered 2020-06-30T05:29:54Z
translate from https://stackoverflow.com:/questions/195010/how-can-i-split-multiple-joined-words