概要

未知語処理できるようになりました
次はkuromojiのsearch modeを模倣したい．ユーザー辞書も．
コードをgithubにこっそり上げてみました．golang の作法があんまりよく分からないのでコメントもらえると嬉しいです．

はじめに

未知語処理を実装して，それとなく動くところまで持って行くのが目標です．

未知語処理なし： (現状)

未知語処理あり： (目標)

こんな感じに，今は未知語の処理をしていないので，ラティスが末尾から先頭まで辿れなくなっているところをなんとかします．（トトロが辞書にないので，そこの連結がなくなってしまっています．）

前回までのあらすじ

Pure Go な形態素解析器で，辞書同梱のバイナリを作る
MeCab辞書を go ソースに変換してコンパイルした
ソース大きい & コンパイル遅い (手元の Mac:Core i7 2.9GHzで30分ほど)
実行バイナリのサイズは100MB程度になった
未知語処理が実装されていないので，ノードが連結しない場合がある ← ★今回これに対応する

参考

下記を参考にさせていただきました．

未知語処理の基本戦略

入力文字列を前から一つずつずらして CommonPrefixSearch して，その位置から始まる形態素をラティスのノードにしていきます．ある位置から始まる形態素が辞書に登録されていないとき，その位置から始まる文字列を文字種でグルーピングして未知語ノードとしてラティスに追加します．

MeCab-IPADIC の設定

MeCab の未知語関連の設定は，char.def と unk.def の2つのファイルです．

未知語処理を起動するタイミングの設定

char.def の頭の方に以下のような設定が書かれています．
左から

CATEGORY_NAME: カテゴリ名
INVOKE: 1 に設定されているカテゴリは常に未知語ノードを追加．そうでなければ，その位置から始まるノードがないときだけ追加．
GROUP: 先頭と同じ文字種の文字列をグルーピングして未知語とする．
LENGTH: 長さ 1 から n までのノードを追加する．

char.def[抜粋]

###################################################################################
#
#  CHARACTER CATEGORY DEFINITION
#
#  CATEGORY_NAME INVOKE GROUP LENGTH
#
#   - CATEGORY_NAME: Name of category. you have to define DEFAULT class.
#   - INVOKE: 1/0:   always invoke unknown word processing, evan when the word can be found in the lexicon
#   - GROUP:  1/0:   make a new word by grouping the same chracter category
#   - LENGTH: n:     1 to n length new words are added
#
DEFAULT        0 1 0  # DEFAULT is a mandatory category!
SPACE          0 1 0
KANJI          0 0 2
SYMBOL         1 1 0
NUMERIC        1 1 0
ALPHA          1 1 0
HIRAGANA       0 1 2
KATAKANA       1 1 2
KANJINUMERIC   1 1 0
GREEK          1 1 0
CYRILLIC       1 1 0

ふむふむ．記号とか来たら常に未知語処理が働くけど，漢字やひらがなの時はその位置から始まるノードが作れないときだけ未知語処理すればいいのね φ(．．)．

文字種の設定

char.def の残りの部分には，各文字がどの文字種に含まれるかが書いてあります．文字は UCS2 で表されています．UCS2 は golang でいえば rune にあたります．この表を rune を調べてどのカテゴリに当てはまるか分かればいいのですね．

char.def[抜粋]

###################################################################################
#
# CODE(UCS2) TO CATEGORY MAPPING
#

# SPACE
0x0020 SPACE  # DO NOT REMOVE THIS LINE, 0x0020 is reserved for SPACE
0x00D0 SPACE
0x0009 SPACE
0x000B SPACE
0x000A SPACE

# ASCII
0x0021..0x002F SYMBOL
0x0030..0x0039 NUMERIC
0x003A..0x0040 SYMBOL
0x0041..0x005A ALPHA
0x005B..0x0060 SYMBOL
0x0061..0x007A ALPHA
0x007B..0x007E SYMBOL

よく見ると，複数クラスにまたがる場合もあるようです．

char.def[抜粋]

# KANJI-NUMERIC (一 二 三 四 五 六 七 八 九 十 百 千 万 億 兆)
0x4E00 KANJINUMERIC KANJI
0x4E8C KANJINUMERIC KANJI
0x4E09 KANJINUMERIC KANJI
0x56DB KANJINUMERIC KANJI
0x4E94 KANJINUMERIC KANJI
0x516D KANJINUMERIC KANJI

未知語カテゴリのコスト

未知語のカテゴリ(ALPHA とか KANJI とか)について，unk.def に品詞や重みが定義されています．

unk.def[抜粋]

DEFAULT,5,5,4769,記号,一般,*,*,*,*,*
SPACE,9,9,8903,記号,空白,*,*,*,*,*
KANJI,1285,1285,11426,名詞,一般,*,*,*,*,*
KANJI,1283,1283,17290,名詞,サ変接続,*,*,*,*,*
KANJI,1293,1293,17611,名詞,固有名詞,地域,一般,*,*,*
KANJI,1292,1292,12649,名詞,固有名詞,組織,*,*,*,*
KANJI,1289,1289,17340,名詞,固有名詞,人名,一般,*,*,*
KANJI,1288,1288,15295,名詞,固有名詞,一般,*,*,*,*
SYMBOL,1283,1283,17585,名詞,サ変接続,*,*,*,*,*
NUMERIC,1295,1295,27386,名詞,数,*,*,*,*,*
ALPHA,1285,1285,13398,名詞,一般,*,*,*,*,*
ALPHA,1293,1293,18706,名詞,固有名詞,地域,一般,*,*,*
ALPHA,1292,1292,13835,名詞,固有名詞,組織,*,*,*,*
ALPHA,1289,1289,18188,名詞,固有名詞,人名,一般,*,*,*
ALPHA,1288,1288,15673,名詞,固有名詞,一般,*,*,*,*
ALPHA,3,3,15235,感動詞,*,*,*,*,*,*
HIRAGANA,1285,1285,13069,名詞,一般,*,*,*,*,*
HIRAGANA,1283,1283,20223,名詞,サ変接続,*,*,*,*,*
HIRAGANA,1293,1293,17882,名詞,固有名詞,地域,一般,*,*,*
HIRAGANA,1292,1292,14761,名詞,固有名詞,組織,*,*,*,*
HIRAGANA,1289,1289,18060,名詞,固有名詞,人名,一般,*,*,*
HIRAGANA,1288,1288,14787,名詞,固有名詞,一般,*,*,*,*
HIRAGANA,3,3,16989,感動詞,*,*,*,*,*,*
KATAKANA,1285,1285,9461,名詞,一般,*,*,*,*,*
KATAKANA,1293,1293,13661,名詞,固有名詞,地域,一般,*,*,*
KATAKANA,1292,1292,10922,名詞,固有名詞,組織,*,*,*,*
KATAKANA,1289,1289,13581,名詞,固有名詞,人名,一般,*,*,*
KATAKANA,1288,1288,10521,名詞,固有名詞,一般,*,*,*,*
KATAKANA,3,3,14138,感動詞,*,*,*,*,*,*
KANJINUMERIC,1295,1295,27473,名詞,数,*,*,*,*,*
GREEK,1285,1285,7884,名詞,一般,*,*,*,*,*
GREEK,1293,1293,12681,名詞,固有名詞,地域,一般,*,*,*
GREEK,1292,1292,8573,名詞,固有名詞,組織,*,*,*,*
GREEK,1289,1289,12697,名詞,固有名詞,人名,一般,*,*,*
GREEK,1288,1288,10029,名詞,固有名詞,一般,*,*,*,*
CYRILLIC,1285,1285,7966,名詞,一般,*,*,*,*,*
CYRILLIC,1293,1293,12600,名詞,固有名詞,地域,一般,*,*,*
CYRILLIC,1292,1292,8492,名詞,固有名詞,組織,*,*,*,*
CYRILLIC,1289,1289,12615,名詞,固有名詞,人名,一般,*,*,*
CYRILLIC,1288,1288,9866,名詞,固有名詞,一般,*,*,*,*

どうやって golang のコードに落とすか？

ある文字がふくすうのカテゴリに含まれる場合があるのが面倒です．これ，kuromoji ではどうやって処理してるんでしょうか？kuromoji のコードを見てみます．kuromoji は github にあがってるほうじゃなくて，lucene に含まれている方を参考にしました．

kuromoji(UnknownDictionaryBuilder.java)

  public void readCharacterDefinition(String filename, UnknownDictionaryWriter dictionary) throws IOException {
    FileInputStream inputStream = new FileInputStream(filename);
    InputStreamReader streamReader = new InputStreamReader(inputStream, encoding);
    LineNumberReader lineReader = new LineNumberReader(streamReader);

    String line = null;

    while ((line = lineReader.readLine()) != null) {
      line = line.replaceAll("^\\s", "");
      line = line.replaceAll("\\s*#.*", "");
      line = line.replaceAll("\\s+", " ");

      // Skip empty line or comment line
      if(line.length() == 0) {
        continue;
      }

      if(line.startsWith("0x")) {  // Category mapping
        String[] values = line.split(" ", 2);  // Split only first space

        if(!values[0].contains("..")) {
          int cp = Integer.decode(values[0]).intValue();
          dictionary.putCharacterCategory(cp, values[1]);
        } else {
          String[] codePoints = values[0].split("\\.\\.");
          int cpFrom = Integer.decode(codePoints[0]).intValue();
          int cpTo = Integer.decode(codePoints[1]).intValue();

          for(int i = cpFrom; i <= cpTo; i++){
            dictionary.putCharacterCategory(i, values[1]);
          }
        }
      } else {  // Invoke definition
        String[] values = line.split(" "); // Consecutive space is merged above
        String characterClassName = values[0];
        int invoke = Integer.parseInt(values[1]);
        int group = Integer.parseInt(values[2]);
        int length = Integer.parseInt(values[3]);
        dictionary.putInvokeDefinition(characterClassName, invoke, group, length);
      }
    }
  }

ふむふむφ(．．)．だいたいこんな感じか (意訳含む)

文字は UCS2 なので 65536 種類しかないので，65536 byte のバイト列を用意して，そこに文字カテゴリをセットする．
文字カテゴリは最初のカテゴリを記録．複数あっても無視 orz．
未知語処理の起動のタイミングはテーブルを作って記録しておく，

そうですか，カテゴリが複数指定してあっても関係ないのね・・・

ラティスを作ろう

処理はこんな感じ．

入力文字を先頭から一文字ずつ読みながら以下を繰り返す．
1. ユーザー辞書を引く (未実装)
2. 形態素辞書を引く
3. 未知語ノードを追加する．

ただし，(3) で未知語処理が起動するのは， (2)で辞書が引けなかった場合か，現在処理している文字が，未知語処理を常に起動する場合．

golang は文字列を byte でも rune でも表現できるので，その辺がこんがらがらないようにインデックスに気をつけてコードを書きます．コードはこんな感じになりました．char.def で未知語の最大長が設定されていたけど，kuromoji の処理を読んだら，その値は使われてなかったので，とりあえず無視 (^^ゞ．

lattice.go

func (this *Lattice) build(a_input *string) (err error) {
        this.input = []byte(*a_input)

        runeCount := utf8.RuneCount(this.input)
        this.list = make([][]Node, runeCount+2)

        this.list[0] = append(this.list[0], Node{id: BOSEOS, class: KNOWN, start: 0})
        this.list[len(this.list)-1] = append(this.list[len(this.list)-1], Node{id: BOSEOS, class: KNOWN, start: len(this.list) - 2})

        chPos := -1
        for bufPos, ch := range *a_input {
                chPos++

                // (1) TODO: USER DIC
                anyMatches := false
                if anyMatches {
                        continue
                }
                // (2) KNOWN DIC
                prefixs, ids := dic.Index.CommonPrefixSearchBytes(this.input[bufPos:])
                anyMatches = len(prefixs) > 0
                for key, substr := range prefixs {
                        id := ids[key]
                        c, ok := dic.Counts[id]
                        if !ok {
                                c = 1
                        }
                        for x := 0; x < c; x++ {
                                this.addNode(id+x, chPos, bufPos, bufPos+len(substr), KNOWN)
                        }
                }
                // (3) UNKNOWN DIC
                if !anyMatches || dic.InvokeList[dic.CharacterCategoryList[ch]] {
                        class := dic.CharacterCategoryList[ch]
                        endPos := bufPos + utf8.RuneLen(ch)
                        unkWordLen := 1
                        for i, w, size := endPos, 1, len(this.input); i < size; i += w {
                                var c rune
                                c, w = utf8.DecodeRune(this.input[i:])
                                if dic.CharacterCategoryList[c] != class {
                                        break
                                }
                                endPos += w
                                unkWordLen++
                                if unkWordLen >= _MAX_UNKNOWN_WORD_LENGTH {
                                        break
                                }
                        }
                        pair := dic.UnkIndex[class]
                        for i, w := bufPos, 0; i < endPos; i += w {
                                _, w = utf8.DecodeRune(this.input[i:])
                                end := i + w
                                for x := 0; x < pair[1]; x++ {
                                        this.addNode(pair[0]+x, chPos, bufPos, end, UNKNOWN)
                                }
                        }
                }
        }
        return
}

まとめ

未知語処理は細かい処理を端折ってしまっている気がしますが，とりあえず動くところまで来ました．ホントは，kuromojiのsearch modeを模倣したかったんですが，それは鋭意対応中です．search modeだと，関西国際空港と1形態素で解析された部分が関西国際空港と分割されて，全文検索のインデキシングの時に検索漏れが発生しにくくなります．あと，ユーザー辞書．これもなんとかしたい．とりあえず，出来てるところまでを github に上げておきました．

Pure Go な形態素解析器で実行バイナリに辞書埋め込んだヤツを作ってみた (2) 未知語処理編

概要

はじめに

前回までのあらすじ

参考

未知語処理の基本戦略

MeCab-IPADIC の設定

未知語処理を起動するタイミングの設定

文字種の設定

未知語カテゴリのコスト

どうやって golang のコードに落とすか？

ラティスを作ろう

まとめ