RMMSeg: Ruby 实现中文分词

January 31, 2008 – 2:54 pm

我在前面曾经提到过,中文分词比较困难,不像英文那样,直接在空格和标点符号的地方断开就可以了。 Jack评论中提到即使是英文,在进行短语层次的分“词”时也会有类似的困难。还有在进行手写识别时,空格有时候不能很精确地识别出来,也会要用到中文分词中的一些技术。

RMMSeg 我近日做的一个 Ruby 的中文分词实现,下一步是和 Ferret 进行集成。不过,在介绍 RMMSeg 之前让我先来简要介绍一下中文分词。

如何分词?

那么中文分词究竟要如何做呢?想想你自己看到一个句子的时候,如何进行分词?似乎是及其复杂的吧?好像感觉到现在的电脑还达不到这个层次,至少一台普通 PC 机不可能拥有一个人的大脑那么多的后备知识可用。但是若是只要求百分之八九十的准确率的话,要实现一个分词算法也并不困难。

这里又要说 80/20 原则了,要实现一个在 80% 的情况下能工作的算法通常不会太难,但是要保证另外 20% 也能正常工作的话,通常难度相差不止 N 个数量级。何况这个问题并不是 100% 可解的,一些固有歧义的情况及时是人也无法选择一个更好的分词方法来。

一个最直接的分词方法就是每一个字符作为一个单独的词,因为汉字里面几乎每一个字都是可以独立成词的。但是这样分词的结果几乎不能保留多少句子原来的意思,如果用于搜索的索引建立的话,直接后果就是搜索结果会包含大量相关程度很小甚至根本不相关的结果。那么如何实现一个简单有效的分词算法呢?——用词典进行最大匹配。简单地说,就是依次读入字符,直到找到一个最长的词。例如本段的第一句话用这种分词算法分割的结果如下:

那么 如何 实现 一个 简单 有效 的 分词 算法 呢

但是我们都知道,贪心算法并不总是能得到最优解,这里也是一样,比如在分割“研究生命起源”的时候就犯错误了:

研究生 命 起源

通过最大匹配找到了“研究生”一个词,进而吞掉了本该属于“生命”的“生”字。要如何解决这类问题呢?咋一看是没有办法了,除非理解这个句子,其实不然,有不少(比起“理解句子”来说)简单得多的算法可以排除不少错误的分割。不过,在介绍他们之前,值得注意一下的是,如果把最大匹配算法的扫描方向由正向改为反向,精确度可以提高不少。不过有时候拿到的是一个文本流,就没有办法首先得到末尾了。

MMSeg

MMSeg 算法是由 Chih-Hao Tsai 提出的一种基于最大匹配的分词算法。算法以最大匹配为基础,通过几条规则的修正,达到了很高的精确度。按照作者的说法,在一个 1013 的词的测试输入中,词语的正确识别率达到了 98.41% 。下面我简单地介绍一下 MMSEG 算法,更详细的介绍可以参考 Chih-Hao Tsai 的文章

MMSEG 算法主要分为两种:simple 和 complex 。simple 算法就是前面提到的最简单的正向最大匹配算法。为了解决 simple 算法的不足,MMSEG 又提供了另一种选择:complex 算法。该算法使用了 Chen K. J. 和 Liu S. H. 于 1992 年在 Word identification for Mandarin Chinese sentences 中提出的一种最大匹配算法的变种。

这种算法的基本思想是:找到所有从当前位置开始的三个连续词语的块,总长度最大的块是最优解。例如,分割“眼看就要来了”这个句子,从“眼”字开始,可能构成的三个连续词的块有(注意每一个单字通常都可以独立成词):

眼 看 就
眼 看 就要
眼看 就 要
眼看 就要 来
眼看 就要 来了

总长度最大的块就是最后一行的三词块,即最优分解。当然这只是“经验公式”,比如,分割“如果一个人生三子则得奖”这个句子,在处理到“人”字的时候,以下两种选择:

人 生 三
人生 三 子

应当是前者是最优分解,然而后者才是总长度最大的块。在使用 complex 算法的时候,即使用了最大匹配,有时候还是会得到多个结果,例如,假如到了文本的末尾有“国际化”这个词,三个选择:

国际化
国际 化
国 际 化

拥有同样的最大长度。为了在这种情况下选出一个最有分割,使用了一个最大平均长度的规则(Largest average word length):即选择块里平均词语长度最大的块。这条规则只有在文本末尾,无法构成三个词的块时才有用,如果所有的块都是三个词的话,他们的平均长度必然是一样的(经过由最大匹配算法之后留下的块必定都是总长度最大的)。虽然如此,这仍然是一条非常有用的规则,因为文本末尾不仅会出现在文件的末尾,一个句子的末尾(由标点符号标识)也会构成文本末尾。

但是光凭这条规则不足以解决所有的歧义,所以 MMSEG 还使用了另外两条规则:

  1. 词语长度变化最小的原则(Smallest variance of word lengths)。例如前面举过的“研究生命起源”的例子就可以用这种方法选出“研究 生命 起源”这个最优的分割,因为三个词的长度都是 2 ,长度变化是 0 。
  2. Largest sum of degree of morphemic freedom of one-character words 规则。通过各个单字在平时被使用的频率数据,就可以用于在不同的块中选出频率最高的一个块。例如“主要是因为”的两个分割“主要 是 因为”和“主要是 因为”,由于单字“是”比单字“主”出现的频率要高,因此可以选出“主要 是 因为”这个分割,通常这也就是最优分割。

通过三个额外的解决歧义的规则,complex 算法通常比 simple 算法具有更高的精确度。

RMMSeg

Chih-Hao Tsai 还提供了一个 C 语言的实现以及所需的词典可供下载,不过他的程序和辞典都是针对 big5 编码的繁体中文的。不过最近 SoloL 做了一个 Java 的 MMSEG 实现,并让他可以和 Lucene 集成起来。我也做了一个 Ruby 的实现(叫做 RMMSeg )用于和 Ferret (Ruby 下的 Lucene)进行集成。

我的实现实际上主要是参考了 SoloL 的 Java 实现,而且他的词典是简体中文的,我几乎直接用了他的实现里所带的词典。

RMMSeg 也实现了 simple 和 complex 两种算法。解析词语的基本步骤是创建可能匹配的块( Chunk ),然后将各个规则应用到得到的 Chunk 上,选出最佳的 Chunk

get_cjk_word(create_chunks(chars, index))

以下是 get_cjk_word 的代码:

def get_cjk_word(chunks)
  i = 0
  while i < @rules.length
    break if chunks.length < 2
    chunks = @rules[i].filter(chunks)
    i += 1
  end
 
  if chunks.length > 1
    if Config.on_ambiguity == :raise_exception
      raise Ambiguity, "Can't solve ambiguity on #{chunks}"
    end
  end
 
  word = chunks[0].words[0]
  return word.value, word.length
end

SimpleAlgorithmComplexAlgorithm 分别实现了各自的 create_chunk 并维护了各自的规则列表( @rules )。如 MMSEG 算法中描述的那样, SimpleAlgorithm 构建所有可能的单词 Chunk ,而 ComplexAlgorithm 则构建所有可能的三词 Chunk

SimpleAlgorithm 只有最大匹配一条规则,而 ComplexAlgorithm 则包含了全部四条规则:

module RMMSeg
  class ComplexAlgorithm
    include Algorithm
 
    def initialize
      @rules = [
                MMRule.new,
                LAWLRule.new,
                SVWLRule.new,
                LSDMFOCWRule.new
               ]
    end
 
    # ...
  end
end

各个规则的实现也是大同小异,使用合适的规则对 Chunk 进行排序,并选出值最大(或最小)的 Chunk ,例如,下面是词语长度变化最小的原则的代码:

module RMMSeg
  class SVWLRule
    def filter(chunks)
      chunks.sort { |a, b|
        a.variance <=> b.variance
      }.similar_elements { |a, b|
        a.variance == b.variance
      }
    end
  end
end

其中 similar_elements 是对 Array 类的一个 Monkey Patching ,用于选出数组中相邻的所有“类似”的元素:

class Array
  # Return an array of _similar_ elements neighbouring to each
  # other. e.g.
  #   [1,2,2,2,3,3,5].similar_elements(1) => [2,2,2]
  # and (maybe more useful example)
  #   ["Kid", "Kily", "KDE", "Foo", "Food"].similar_elements { |a, b|
  #     a[0] == b[0]
  #   } => ["Kid", "Kily", "KDE"]
  def similar_elements(index=0)
    i = index+1
    loop do
      break if i >= self.length
      if block_given?
        break unless yield(self[index], self[i])
      else
        break if self[index] == self[i]
      end
      i += 1
    end
    self[index...i]
  end
end

另外就是 Dictionary 的实现,正如我在关于提升 Ruby 效率的那篇文章提到的那样,使用了惰性构造的办法,效率提升了不少。

我在 RubyForge 那里为 RMMSeg 申请了一个项目,虽然项目的主页正在制作中,但是项目页面 是现成的。目前已经有一个命令行的 bin/rmmseg 可以用于分词,做好了和 Ferret 集成的代码之后我会以 Rubygems 的形式发布。 :) 最新代码总是可以通过 svn 从 RubyForge 上下载到:

svn checkout http://rmmseg.rubyforge.org/svn/

或者使用 svn://rubyforge.org/var/svn/rmmseg 也可以。最后是一个例子:

通过 最大 匹配 找到了 “ 研究生 ” 一个 词 , 进而 吞掉 了 本该 属
于 “ 生命 ” 的 “ 生 ” 字 。 要 如何 解决 这类 问题 呢 ? 咋 一看 是 没
有 办法 了 , 除非 理解 这个 句子 , 其实不然 , 有 不少 ( 比起 “ 理解
句子 ” 来说 ) 简单 得 多的 算法 可以 排除 不少 错误 的 分割 。 不过 ,
在 介绍 他们 之前 , 值得注意 一下 的 是 , 如果 把 最大 匹配 算法 的
扫描 方向 由 正向 改为 反向 , 精确度 可以 提高 不少 。 不过 有时候 拿到
的 是 一个 文本 流 , 就 没有 办法 首先 得到 末尾 了 。

以上就是在本文中选取一段文本进行分词的结果。

  1. 9 Responses to “RMMSeg: Ruby 实现中文分词”

  2. 啊~ 终于知道前一篇日志的词典是什么了

    By hsys on Jan 31, 2008

  3. Pluskid, You should learn something about machine learning. Talk about NLP when you r back :)

    By Jack on Feb 2, 2008

  4. @Jack:
    Hmm, I may have a try. But don’t know where to start. I just know nothing about machine learning right now. :(

    By pluskid on Feb 2, 2008

  5. wow ,good work

    By wyh on Sep 15, 2011

  1. 5 Trackback(s)

  2. Feb 1, 2008: Free Mind » Blog Archive » [ANN]RMMSeg 0.0.1 Released
  3. Feb 7, 2008: Free Mind » Blog Archive » Screencast: RMMSeg/Ferret Demo
  4. Feb 9, 2009: Free Mind » 漫谈 Clustering (番外篇): Expectation Maximization
  5. Mar 22, 2009: 流浪汗 » 中文分词 mmseg4j
  6. Apr 15, 2015: 漫谈 Clustering (番外篇): Expectation Maximization | 阅读纵横

Post a Comment