全部 android asp.net C/C++ cshap IOS Java javascript nodejs perl php python ruby web容器 其他 前端 数据库 第三方平台 混合式APP 网络 系统 默认分类

开源中文分词工具探析(三):Ansj

0 37

Ansj是由孙健(ansjsun)开源的一个中文分词器,为ICTLAS的Java版本,也采用了Bigram + HMM分词模型(可参考我之前写的文章):在Bigram分词的基础上,识别未登录词,以提高分词准确度。虽然基本分词原理与ICTLAS的一样,但是Ansj做了一些工程上的优化,比如:用DAT高效地实现检索词典、array + linked-list方式实现分词DAG、支持自定义词典与自定义消歧义规则等。

1. 前言

Ansj支持多种分词方式,其中ToAnalysis为店长推荐款:

它在易用性,稳定性.准确性.以及分词效率上.都取得了一个不错的平衡.如果你初次尝试Ansj如果你想开箱即用.那么就用这个分词方式是不会错的.

因此,本文将主要分析ToAnalysis的分词实现。以下代码分析基于ansj-5.1.0版本。

ToAnalysis继承自抽象类org.ansj.splitWord.Analysis,重写了抽象方法getResult。其中,分词方法的依赖关系:ToAnalysis::parse -> Analysis::parseStr -> Analysis::analysisStr。analysisStr方法就干了两件事:

  1. 按照消歧义规则分词;
  2. 在此基础上,按照核心词典分词;

analysisStr方法的最后调用了抽象方法getResult,用于对分词DAG的再处理;所有的分词类均重写这个方法。为了便于理解ToAnalysis分词,我用Scala 2.11重写:

import java.util

import org.ansj.domain.{Result, Term}
import org.ansj.recognition.arrimpl.{AsianPersonRecognition, ForeignPersonRecognition, NumRecognition, UserDefineRecognition}
import org.ansj.splitWord.Analysis
import org.ansj.util.TermUtil.InsertTermType
import org.ansj.util.{Graph, NameFix}

/**
  * @author rain
  */
object ToAnalysis extends Analysis {
  def parse(sentence: String): Result = {
    parseStr(sentence)
  }

  override def getResult(graph: Graph): util.List[Term] = {
    // bigram分词
    graph.walkPath()

    // 数字发现
    if (isNumRecognition && graph.hasNum)
      new NumRecognition().recognition(graph.terms)
    // 人名识别
    if (graph.hasPerson && isNameRecognition) {
      // 亚洲人名识别
      new AsianPersonRecognition().recognition(graph.terms)
      // 词黏结后修正打分, 求取最优路径
      graph.walkPathByScore()
      NameFix.nameAmbiguity(graph.terms)
      // 外国人名识别
      new ForeignPersonRecognition().recognition(graph.terms)
      graph.walkPathByScore()
    }

    // 用户自定义词典的识别
    new UserDefineRecognition(InsertTermType.SKIP, forests: _*).recognition(graph.terms)
    graph.rmLittlePath()
    graph.walkPathByScore()

    import scala.collection.JavaConversions._
    val terms = graph.terms
    new util.ArrayList[Term](terms.take(terms.length - 1).filter(t => t != null).toSeq)
  }
}

如果没看懂,没关系,且看下小节分解。

2. 分解

分词DAG

分词DAG是由类org.ansj.util.Graph实现的,主要的字段termsorg.ansj.domain.Term数组。其中,类Term为DAG的节点,表示一个词,字段包括:offe首字符在句子中的位置、next具有相同首字符的节点、from前驱节点、score打分。从上述表述,我们可以发现DAG是用array + linked-list方式所实现的。

Bigram模型

Bigram模型对应于一阶Markov假设,词只与其前面一个词相关,其对应的分词公式为:

\begin{equation} \arg \max \prod_{i=1}^m P(w_{i} | w_{i-1}) = \arg \min - \sum_{i=1}^m \log P(w_{i} | w_{i-1}) \label{eq:bigram} \end{equation}

对应的词典为bigramdict.dic,格式如下:

始##始@和  11
和@尚 1
和@尚未    1
世纪@末##末 3
...

初始状态\(w_0\)对应于Bigram词典中的“始##始”,\(w_{m+1}\)对应于“末##末”。Bigram分词的实现为Graph::walkPath函数:

/**
 * bigram分词
 * @param relationMap 干涉性打分, key为"first_word \tab second_word", value为干涉性score值
 */
public void walkPath(Map<String, Double> relationMap) {
  Term term = null;
  // 给terms[0] bigram打分, 且前驱节点为root_term "始##始"
  merger(root, 0, relationMap);
  // 从第一个字符开始往后更新打分
  for (int i = 0; i < terms.length; i++) {
    term = terms[i];
    while (term != null && term.from() != null && term != end) {
      int to = term.toValue();
      // 给terms[to] bigram打分, 更新最小非零score值对应的term为前驱
      merger(term, to, relationMap);
      term = term.next();
    }
  }
  // 求解最短路径
  optimalRoot();
}

条件概率做了如下的平滑处理:

\[ \begin{aligned} - \log P(w_{i} | w_{i-1}) & \approx - \log \left[ aP(w_{i-1}) + (1-a) P(w_{i}|w_{i-1}) \right] \\ & \approx - \log \left[ a\frac{f(w_i)}{N} + (1-a) \left( \frac{(1-\lambda)f(w_{i-1},w_i)}{f(w_{i-1})} + \lambda \right) \right] \end{aligned} \]

其中,\(a=0.1\)为平滑因子,\(N=2079997\)为训练语料中的总词数,\(\lambda = \frac{1}{N}\)。上述平滑处理实现函数为MathUtil.compuScore

式子\eqref{eq:bigram}的最小值等价于求解分词DAG的最短路径。Ansj在寻找最短路径时,没有采用Dijkstra等动态算法,而是依据每一个节点的最短边从尾节点往前求解(具体参看代码Graph::walkPathGraph::optimalRoot)。因此,Ansj不能保证所得分词路径为\eqref{eq:bigram}的最优解。

自定义词典

Ansj支持自定义词典分词,是通过词黏结的方式——如果相邻的词正好为自定义词典中的词,则可以被分词——实现的。换句话说,如果自定义的词未能完全覆盖相邻词,则不能被分词。举个例子:

import scala.collection.JavaConversions._
val sentence = "倒模,替身算什么?钟汉良、ab《孤芳不自赏》抠图来充数"
println(ToAnalysis.parse(sentence).mkString(" "))
// 倒/v 模/ng ,/w 替身/n 算/v 什么/r ?/w 钟汉良/nr 、/w ab/en 《/w 孤芳/nr 不/d 自赏/v 》/w 抠/v 图/n 来/v 充数/v

DicLibrary.insert(DicLibrary.DEFAULT, "么钟汉")
DicLibrary.insert(DicLibrary.DEFAULT, "抠图")
println(ToAnalysis.parse(sentence).mkString(" "))
// 倒/v 模/ng ,/w 替身/n 算/v 什么/r ?/w 钟汉良/nr 、/w ab/en 《/w 孤芳/nr 不/d 自赏/v 》/w 抠图/userDefine 来/v 充数/v

3. 参考资料

[1] goofyan, ansj词典加载及简要分词过程.

热忱回答0

要回复文章请先登录注册