形態素解析のための語彙辞書を作る

前回でChaSen形式のコーパスリーダーを作ったので、続いてコーパス中に出てくる単語を集めて語彙辞書を作ります。この辞書を形態素解析器の単語知識のソースにする予定です。

語彙辞書のフォーマット

まず辞書のフォーマットを次のように決めておきます。
・1行につき1単語を書く
・1単語についての情報量と表現形式はChaSen形式を使う
・単語は重複しない（つまり、見出し形、読み、原形、品詞、活用種別・型が全て同じ単語は複数存在しない）
・五十音順は特に気にしない

辞書の一部の例を挙げれば以下のような感じです。

戦い    タタカイ    戦う    動詞-自立   五段・ワ行促音便    連用形
戦い    タタカイ    戦い    名詞-一般
闘い    タタカイ    闘い    名詞-一般
闘い    タタカイ    闘う    動詞-自立   五段・ワ行促音便    連用形
たたかい    タタカイ    たたかう    動詞-自立   五段・ワ行促音便    連用形

読みが同じだけど見出し形が異なる単語や、品詞が異なる単語は別単語として扱います。

プログラムの流れ

コーパスから単語を取り出して語彙辞書を作るプログラム全体の流れは次のようになります。
1. コーパスリーダーを使って、コーパスを1ファイル開く
2. コーパスリーダーからコーパスに含まれる単語を全てもらう
3. 単語を一つずつ見ていき、初出の単語であれば語彙リストに追加する
4. 全てのコーパスファイルについて1〜3を繰り返す
5. 語彙リストの内容をファイルに書き出す

5で出力されるファイルこそが欲しい語彙辞書そのものです。
1〜4の部分だけを素直に実装すると次のような感じですね。

vocabulary = []    # 語彙リスト
for corpus_file in corpus_file_paths:
    r = ChasenCorpusReader(corpus_file)    # コーパスから単語抽出
    for word in r.words:
        if word not in vocabulary:    # 語彙リストにまだない単語であれば
            vocabulary.append(word)   # 語彙リストに追加する

ぱっと見簡単そうですが、ひとつ大きな落とし穴があります。それはこの部分。

if word not in vocabulary:

ここでのvocabularyはただのlistなので、この処理はvocabularyに入ってる要素を一つずつwordと比較します。だから当然vocabularyの要素数に比例して処理時間が増えます。要素数が10とか100とかなら気にするほどでもないですが、語彙を集めるともなればその数は数万とか十数万とかになってしまいます。手元のcore i7(3GHz)マシンでざっと測ったところ、vocabularyの要素数が5000になると、上記のword比較の処理時間が1wordあたり平均1ミリ秒ぐらいかかりました。これが語彙数が増えるにつれて線形で長くなっていって、数千語のコーパスを1ファイルを処理するのに数分かかるようになった時点であきらめました。
このように語彙をlistで持つのは性能面で決定的に無理があるため、別のデータ構造を使う必要があります。自然言語処理の語彙を保持するのに適した伝統的なデータ構造としてTrie(トライ)というものがあるようですので、まずこのTrieを実装し、現実的な処理時間で辞書が作成できるように頑張ってみます。

Trieの実装

Trieはツリー構造の仲間です。Trieのイメージ図と詳しい説明はWikipediaを見るのが分かりやすいとして、今回の語彙辞書の作成にとってTrieが持つ一番重要な性質は、キーに対する高速な検索性能です。Trieでは検索にかかる時間は格納している要素数に依らず、検索キー文字列の長さで決まります。つまり何万語の語彙を格納しようが、listのように単語が既に存在するかどうかの判定が遅くなっていったりしないという都合の良い性質です。
Trieは語彙の保持以外にもいろんな用途に使えますが、今回は辞書作りに最低限必要な「要素の追加」操作と、保持している要素のダンプ機能だけを実装します。ちなみにTrieの実装形態としてはダブル配列、LOUDS、組み込みdictを使った方法など幾つかの選択肢があります。最初は人気のダブル配列で実装してみましたが、残念ながらまだ力不足のせいで、Trieへの動的な要素の追加でどうしても速度が出せませんでした。今回は組み込みdictを使って実装します。dict方式は一番見やすい上にそこそこ早いので最初はとっつきやすいです。近いうちにダブル配列にもリベンジ。

  1 class Trie(object):
  2     def __init__(self):
  3         self._root = {} # ルートノード
  4         
  5     # 新規要素を追加する
  6     def insert(self, key, value):
  7         node = self._root 
  8         for c in key:
  9             if c not in node:
 10                 node[c] = {} # 文字cに対応する子ノードを作成
 11             node = node[c] #子ノードへ移動
 12             
 13         # リーフノードに値を格納
 14         if 'value_list' not in node:
 15             node['value_list'] = [] # 同一キーに対する複数の異なる値の格納に対応
 16         for v in node['value_list']:
 17             if value == v: # キー、値共に同一の場合は何もしない
 18                 return
 19         node['value_list'].append(value)
 20         
 21     # 保持している全ての(Key, Value)のタプルのリストを返す
 22     def dump(self):
 23         return self._dump(self._root, [])
 24         
 25     def _dump(self, node, key):
 26         data = []
 27         if 'value_list' in node:
 28             k = key[:]
 29             for v in node['value_list']:
 30                 data.append((k, v))
 31                 
 32         for label, child_node in node.items():
 33             if label != 'value_list':
 34                 child_key = key[:]
 35                 child_key.append(label)
 36                 data += self._dump(child_node, child_key)
 37                 
 38         return data

動作はPython3.4で確認しています。
今回実装したTrieの特徴は、同じキーに対して複数の値を持てるようにしたところです。これにより、同音異義語や、同じ見出し形だけど別の品詞を持つ単語を単一のキーで格納することができます。ただしその代わり、単語を追加するときには同一キーで既に追加している単語全てと比較して、本当にまだ追加されていない同音異義語かどうかを判定する必要があります。そのためTrieが持つ、検索性能が既に格納している要素数によらないという性質が若干損なわれていますが、若干の性能低下と引き換えに使い勝手の方を優先します。

さっそくTrieを使って先ほどの語彙リスト生成処理を書き直します。

vocabulary = Trie() # 語彙リスト。listに代わりTrieを使用
    for corpus_file in corpus_file_paths:
        r = ChasenCorpusReader(corpus_file)
        for word in r.words:
            vocabulary.insert(word.lemma, word) # 見出し語をキーにして単語を追加。
　　　　　　　　　　　　　　　　　　　　　　　　        # 単語が既に登録済みかどうかはTrieの中でのキー検索により判定している。

語彙辞書を生成するスクリプト

Trieの実装によって語彙辞書を現実的な時間で作るめどがたったので、いよいよ今回の目的である語彙辞書を生成するプログラムを書いてみます。
このプログラムでは、前回作成したChasenCorpusReaderとChasenWordも使います。

  1 import sys
  2 import glob
  3 import os
  4 import argparse
  5 
  6 from chasen import ChasenCorpusReader, ChasenWord
  7 import Trie
  8 
  9 
 10 if __name__ == '__main__':
 11     # 起動パラメータ取得
 12     parser = argparse.ArgumentParser()
 13     parser.add_argument('-s', '--src_root_path', nargs=None, type=str, action='store') # コーパスファイルのフォルダを指定
 14     parser.add_argument('-f', '--file_pattern', nargs=None, type=str, action='store') # ファイル名パターンを指定
 15     args = parser.parse_args()
 16     
 17     # ChaSenコーパスファイルのパスを集める
 18     corpus_file_paths = []
 19     for dir_path, sub_dirs, file_names in os.walk(args.src_root_path):
 20         file_list = glob.glob(os.path.expanduser(dir_path) + '/' + args.file_pattern)
 21         for file in file_list:
 22             root, ext = os.path.splitext(file)
 23             if ext == ".chasen":
 24                 corpus_file_paths.append(file)
 25                 
 26     # コーパスから語彙を集めてTrieで保持
 27     vocabulary = Trie()
 28     for corpus_file in corpus_file_paths:
 29         print('extracting words form ' + corpus_file)
 30         
 31         r = ChasenCorpusReader(corpus_file)
 32         for word in r.words:
 33             vocabulary.insert(word.lemma, word)
 34             
 35     # 語彙をファイルに書き出す
 36     with open('.'.join(['out', 'vocab']), 'w') as f:
 37         for key_val in vocabulary.dump(): 
 38             word = key_val[1]
 39             if word.lemma in ['EOS', 'BOS']:
 40                 continue
 41             line = str(word) + '\n'
 42             f.write(line)

使い方は、

python make_vocabulary.py -s [コーパスファイルフォルダ] -f [ファイル名パターン]

[コーパスファイルフォルダ]で指定したフォルダ以下にある全てのchasenファイルから語彙を抽出し、語彙辞書を生成してout.vocabというファイル名で出力します。[ファイル名パターン]は特定のコーパスファイルだけをフィルタリングするために使いますが、普通は全てのファイルを表すワイルドカード「*」を指定します。
このスクリプトで作った語彙辞書ファイルを使えば、形態素解析のための語彙知識をコンピュータに与えることができるようになります。
次は単語同士の接続の仕方を定義する接続表の作成に取り組んでいく予定です。

[補足]ChasenWordクラスの拡張

話の流れの都合で後回しにしてましたが、実はChasenWordクラスにいくつかの機能を追加しないと上で作ったTrieと辞書生成スクリプトは正しく動きません。
追加する機能は、比較演算子__eq__()と、文字列変換の特殊関数である__str__()です。__eq__()はTrieの実装の17行目で呼ばれますが、ChaSen形式の単語を表すユーザー定義クラスであるChasenWordにとって、それらが等しいとはどういうことかを明示的に実装する必要があります。また、__str__()は語彙辞書生成スクリプトの41行目のstr(word)のところで呼ばれます。ChasenWordの__str__()ではChaSen形式の単語を表す文字列を返すのが自然です。

class ChasenWord(object):
    # 等値比較。見出し形、読み、原形、活用種別、活用形の全てが一致する場合に等値とする
    def __eq__(self, other):
        return ((self.lemma, self.pron, self.base, self.pos, self.conj_type, self.conj_form) ==
                (other.lemma, other.pron, other.base, other.pos, other.conj_type, other.conj_form))

    def __ne__(self, other):
        return not self.__eq__(other)

    # 以下は比較演算子の定義。見出し形で辞書順に並ぶように比較する
    def __lt__(self, other):
        return self.lemma < other.lemma

    def __le__(self, other):
        return self.lemma <= other.lemma

    def __gt__(self, other):
        return self.lemma > other.lemma

    def __ge__(self, other):
        return self.lemma >= other.lemma

    # 文字列変換。ChaSen形式の単語文字列を返す
    def __str__(self):
        _str = '\t'.join([self.lemma, self.pron, self.base, '-'.join(self.pos)])
        if self.conj_type:
            _str = '\t'.join([_str, self.conj_type])
        if self.conj_form:
            _str = '\t'.join([_str, self.conj_form])
        return _str

今回必要な拡張比較関数は__eq__だけですが、pep8の推奨に従って他の比較演算(__ne__, __lt__, __le__, __gt__, __ge__)も明示的に実装しています。
これで今回分の実装は一通りそろいました。