如何拆分多个连词?

Viterbi algorithm 要快得多。它计算的分数与上面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'

为了实用,您可能需要一些改进:

• 添加概率日志,不要将概率相乘。这避免了浮点下溢。

人类能做到吗?

farsidebag
far sidebag
farside bag
far side bag

在21行代码中 : http://norvig.com/spell-correct.html

使现代化

两个单词的组合在大多数情况下会超过三个单词的组合,除非频率差异很大。

我在我的博客上发布了这段代码,并做了一些小改动

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";
}

>>> import wordninja
>>> wordninja.split('bettergood')
['better', 'good']

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

我认为你认为这不是正则表达式的工作是对的。我会使用字典的思想来处理这个问题——在字典中查找单词的最长前缀。当你找到它时,把它切掉,然后用剩下的绳子做同样的事情。

上述方法存在歧义,例如“DriveRealFast”会首先找到“driver”,然后遇到“eallyfast”问题。因此,如果遇到这种情况,您还必须进行一些回溯。或者,由于您没有那么多字符串要拆分,只需手动执行自动拆分失败的字符串即可。

这与一个称为 或 . 在OP的例子中,输入似乎是普通单词的串联;在标识符拆分中,输入的是类名、函数名或源代码中的其他标识符,问题更难解决。我意识到这是一个老问题,OP要么解决了他们的问题,要么继续前进,但如果其他人在寻找标识符拆分器时遇到这个问题(就像我不久前遇到的),我愿意提供 Spiral (" 它是用Python编写的,但附带了一个命令行实用程序,可以读取标识符文件(每行一个)并拆分每个标识符。

螺旋形的 实现了许多标识符拆分算法,包括一个名为Ronin的新算法。它使用各种启发式规则、英语词典和从挖掘源代码存储库获得的令牌频率表。Ronin可以拆分不使用驼峰大小写或其他命名约定的标识符,包括拆分等情况 J2SEProjectTypeProfiler J2SE , Project Type , Profiler ],这需要读者识别 J2SE

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

driveourtrucks 同样,但代价是程序标识符的性能恶化。

更多信息可在 GitHub repo for Spiral

这个问题本身不能用正则表达式来解决。一个解决方案(可能不是最好的)是获得一个字典,并为字典中的每个工作与列表中的每个单词进行正则表达式匹配,只要成功,就添加空格。当然这不会太快,但编程很容易,而且比手工操作要快。

需要基于词典的解决方案。如果你有一个有限的词汇词典,这可能会被简化,否则形成其他单词前缀的单词将成为一个问题。

Santhosh thottingal发布了一个名为mlmorph的python包,可用于形态学分析。

https://pypi.org/project/mlmorph/

示例:

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

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

他还写了一篇关于这个话题的博客 https://thottingal.in/blog/2017/11/26/towards-a-malayalam-morphology-analyser/

Python的一个简单解决方案:安装 wordsegment pip install wordsegment .

$ echo thisisatest | python -m wordsegment
this is a test

其中一种解决方案可以是递归(同样可以转换为动态规划):

static List<String> wordBreak(
    String input,
    Set<String> dictionary
) {

  List<List<String>> result = new ArrayList<>();
  List<String> r = new ArrayList<>();

  helper(input, dictionary, result, "", 0, new Stack<>());

  for (List<String> strings : result) {
    String s = String.join(" ", strings);
    r.add(s);
  }

  return r;
}

static void helper(
    final String input,
    final Set<String> dictionary,
    final List<List<String>> result,
    String state,
    int index,
    Stack<String> stack
) {

  if (index == input.length()) {

    // add the last word
    stack.push(state);

    for (String s : stack) {
      if (!dictionary.contains(s)) {
        return;
      }
    }

    result.add((List<String>) stack.clone());

    return;
  }

  if (dictionary.contains(state)) {
    // bifurcate
    stack.push(state);
    helper(input, dictionary, result, "" + input.charAt(index),
           index + 1, stack);

    String pop = stack.pop();
    String s = stack.pop();

    helper(input, dictionary, result, s + pop.charAt(0),
           index + 1, stack);

  }
  else {
    helper(input, dictionary, result, state + input.charAt(index),
           index + 1, stack);
  }

  return;
}

Tries

我可能会为此感到沮丧,但是 .

function spinalCase(str) {
  let lowercase = str.trim()
  let regEx = /\W+|(?=[A-Z])|_/g
  let result = lowercase.split(regEx).join("-").toLowerCase()

  return result;
}

spinalCase("AllThe-small Things");

output :-
['better', 'good'] ['coffee', 'shop']
['coffee', 'shop']

    pip install wordninja
import wordninja
n=wordninja.split('bettergood')
m=wordninja.split("coffeeshop")
print(n,m)

list=['hello','coffee','shop','better','good']
mat='coffeeshop'
expected=[]
for i in list:
    if i in mat:
        expected.append(i)
print(expected)