MeCab ソースコードリーディング私的メモ（形態素解析編）

先日、次のエントリーを書きました。
日本語形態素解析の裏側を覗く！MeCab はどのように形態素解析しているか - クックパッド開発者ブログ

このエントリーを書く際に MeCab のソースコードをそれなりに読んだので、記憶が薄れないうちにメモっておきます。とりあえず形態素解析部分です。コスト算出部分は気が向いたら書きます・・・。
勘違いしている箇所もあるかと思うので、気付いたら指摘してもらえると嬉しいです！

形態素解析時の主要クラス

形態素解析時に関連するクラスとして特に意識しないといけないのは以下のクラスかと思います。メソッドも主要なものしか表示していません。

Show the source

@startuml
skinparam classAttributeIconSize 0

class Model {
  +viterbi()
}

class Tagger {
  +parse()
}

class Tokenizer {
  +getBOSNode()
  +getEOSNode()
  +lookup()
}
note left: 文の指定された位置に対応するノード（単語）\nを返したりする。未知語処理も行う。

class Viterbi {
  +analyze()
  -viterbi()
  -buildBestLattice()
}
note left: 与えられた文に対して viterbi アルゴリズムにより\n最適なパスを求める。

class CharProperty {
  +seekToOtherType()
  +getCharInfo()
}
note bottom: char.bin の情報から文字種情報\n（SPACE, KANJI etc.）に関する処理を行う

class Dictionary {
  +commonPrefixSearch()
}
note bottom: 辞書（sys.dic etc.）の情報を保持する

class Lattice {
  +toString()
}
note right: 解析対象の文を保持したり、\nViterbi#analyze() の結果を格納したりする

class Connector {
  +cost()
}
note bottom: matrix.bin の情報から\n2ノード（単語）間の連接コストを返したりする

Model *--> Viterbi : -viterbi_
Tagger *--> Model : -current_model_
Tagger *--> Lattice : -lattice_

Viterbi *--> Tokenizer : -tokenizer_
Viterbi *--> Connector : -connector_

Tokenizer *--> Dictionary : -unkdic, -dic_
Tokenizer *--> CharProperty : -property_

@enduml

形態素解析時のシーケンス図

主要クラスを把握したら、次は解析の流れです。クラス図のとおり model が viterbi を所有していますが、model()->viterbi()->analyze(lattice)という形で tagger から model 経由で viterbi の analyze メソッドを呼んで lattice に解をセットしています。

Show the source

@startuml

actor user
participant main
participant model
participant tagger
participant viterbi
participant tokenizer

user -> main : mecab
  main -> main : mecab_do(argc, argv)
  activate main
  create model
  main -> model : open(param)
    create viterbi
      model -> viterbi : open(param)
        create tokenizer
          viterbi -> tokenizer : open(param)
            tokenizer -> tokenizer : Open unk.dic, char.bin,\nsys.dic, and user dics
          tokenizer --> viterbi
        create connector
          viterbi -> connector : open(param)
            connector -> connector : Open matrix.bin
          connector --> viterbi
      viterbi --> model
  model --> main

  main -> model : createTagger()
    create tagger
      model -> tagger : open(*this)
      tagger --> model
  model --> main

  loop
    user -> main : Input sentence
    main -> main : Read input and set it to ibuf
    main -> tagger : parse(ibuf)
    tagger -> tagger : parse(lattice)
    tagger -> viterbi : analyze(lattice)
    viterbi -> viterbi : viterbi(lattice)
    viterbi -> viterbi : buildBestLattice(lattice)
    viterbi --> tagger
    tagger --> main : lattice->toString()
    main --> user : Show the result
  end
  deactivate main
@enduml

比較的複雑な主要メソッド

bool Viterbi::viterbi(Lattice *lattice)

ラティスの構築を行うメソッド。

• begin_node_list: 指定した位置から始まる単語（ノード）を保持するリスト。同じ位置のノードは bnext で繋がっている。
• end_node_list: 指定した位置で終わる単語（ノード）を保持するリスト。同じ位置のノードは enext で繋がっている。

template <bool IsAllPath> bool connect(size_t pos, Node *rnode, …)

viterbi メソッドの中で呼ばれるメソッド。viterbi メソッドで取得した現在位置に対する全ノード (right_node) に対して、一つ手前の全ノードとの連接コストを matrix.bin から取得し、累積コストが最小になる左側のノード (best_node) を rnode->prev に格納しておく。lnode->cost には BOS からの最小累積コストが格納されている。単語の長さに応じて end_node_list に各ノードを格納する。

bool Viterbi::buildBestLattice(Lattice *lattice)

viterbi メソッドで構築したラティスの EOS ノードから prev を辿っていくことで最適パスを求める。prev は connect 関数でセットされた累積コストを最小とする一つ手前のノード。

N *Tokenizer<N, P>::lookup(const char *begin, const char *end, …)

指定された位置に対して候補となる全ての単語を sys.dic とユーザ辞書から取得する。
未知語処理もこのメソッドで行う。未知語のコストは unk.dic に登録されている値を使う。

おまけ 〜 Doxygen によるドキュメント生成〜

EXTRACT_PRIVATE = YES にすると、かなり詳細なクラス図が生成されるのでオススメです。

% brew install doxygen graphviz
% cd /path/to/mecab/mecab/src/
% doxygen -g
% cat <<EOF >> Doxyfile
heredoc> EXTRACT_ALL            = YES
heredoc> HAVE_DOT               = YES
heredoc> UML_LOOK               = YES
heredoc> EXTRACT_PRIVATE        = YES
heredoc> EOF
% doxygen
% open html/index.html