正向最大匹配分词和逆向最大匹配分词

词表

词表为所有可能出现的词语组成的集合。当然，实践中不可能准备包含全所有已知和未知词语词表。

建立词表

1. 从人工标注语料中得到词表。
   由多人讨论并且得到共识的分词标注语料建立词表。这是效果最好，但也是成本最高的方案。
2. 从未标注语料中建立词表。
   可以认为经常重复出现连续字符串属于词语。统计大量未标注语料中的连续字串重复出现频率，将多次重复出现的连续字串作为词语，以此建立词典。
3. 使用输入法，辞典，翻译（例如中英词语互译）词表.
   这是比较容易实现的方法，且这些数据大多能免费下载，有些输入法词表还带词频。

正向最大匹配分词算法

将待分词语句以每个字为开始词语前缀按从左到右的切分顺序与词表匹配，查找到的最长词语为分词结果，并将当前切分位置作为下个词语切分开始位置，如切分片段在在词表中无对应词语，则顺移到下一个字继续切分，把跳过的片段切分为新词（未登陆词）。

此方法分词效果很大程度取决词表，且词表就算包含所有待切分词语，也可能造成分词效果不理想，原因是很多时候按最大长度切分词语可能并不是最优切分。

例如:

待切分词语句: 产量三年中将增长两倍
正向最大匹配: 产量 三年 中将 增长 两倍
最优切分词语: 产量 三年 中 将 增长 两倍

词表中没有 “三年中”，但是有 “中将”, 而事实上 “三年中” 除非作为一个熟词，否则难以作为一个独立词语切分，毕竟还有四年中，五年中，这组合可就多了.

与正向最大匹配分词算法类似的反/逆向最大匹配分词算法, 其改变切分顺序为从右到左.

参考代码摘自 icwb2-data/scripts/mwseg.pl

while (<>) {
    chop;
    s/\s*//g;
    my $text = $_;
    while ($text ne "") {
        $sub = substr($text, 0, $maxwlen);
        while ($sub ne "") {
            if ($dict{$sub}) {
                print "$sub ";
                for (my $i = 0; $i < length($sub); ++$i) {
                    $text =~ s/^.//;
                }
                last;
            }
            $sub =~ s/.$//;
        }
        if ($sub eq "")  {
            if ($text =~ /^([\x21-\x7e])/) {
                print "$1 ";
                $text =~ s/^.//;
            }
            elsif ($text =~ /^([^\x21-\x7e].)/) {
                print "$1 ";
                $text =~ s/^..//;
            }
            else { ## shouldn't happen
                print STDERR "Oops: shouldn't be here: $n\n";
                print "$1 ";
                $text =~ s/^.//;
            }
        }
    }
    print "\n";
    ++$n;
}

用于PKU封闭测试效果

=== SUMMARY:
=== TOTAL INSERTIONS:   9829  
=== TOTAL DELETIONS:    1359  
=== TOTAL SUBSTITUTIONS:    8648  
=== TOTAL NCHANGE:  19836  
=== TOTAL TRUE WORD COUNT:  104372  
=== TOTAL TEST WORD COUNT:  112842  
=== TOTAL TRUE WORDS RECALL:    0.904  
=== TOTAL TEST WORDS PRECISION: 0.836  
=== F MEASURE:  0.869  
=== OOV Rate:   0.058  
=== OOV Recall Rate:    0.059  
=== IV Recall Rate: 0.956