2012年1月3日火曜日

[python] 辞書型形態素解析器の作成

NLTK本12章に形態素解析のアルゴリズムが紹介されていたので、実装してみた。
12.2 日本語形態素解析

Web+DB vol.64にも、日本語かな漢字変換器の実装として、同様の手法が紹介されているが、
これだけ読んで、実装するのはちょっと骨にひびはいるかも。
ざっくりと概略つかむにはいい。
WEB+DB PRESS vol.64に日本語入力の記事を書いたよ


辞書型形態素解析の流れ


① 辞書に基づいた形態素分解
入力した文字列に対して可能な形態素分割をすべて求める。具体的には、入力文字列の頭から抽出できる文字列で辞書を引き、ヒットしたものを列挙する。次に、抽出開始位置を1文字進めて再度文字列を抽出し、辞書を引き、ヒットしたものを列挙する。たとえば、「くるま」なら、「く(区)」「く (九)」「くる(来る)」「くるま(車)」などの辞書エントリを列挙する。これは「共通接頭辞探索」とよばれ、このアルゴリズムに適した辞書のデータ構造として「トライ構造」が使われている。


② ラティス構造の作成
共通接頭辞探索を先頭から順に行う際、得られた形態素とその位置で終わる形態素との組み合わせを考え、接続したグラフ構造を作成する。この構造は「ラティス構造」と呼ばれる。このラティス構造を作成する際、つまり、形態素同士を接続する際、日本語の文法に正しいかどうかを確認し、間違っている場合は接続しない。このように連接可能な形態素同士が接続したラティス構造が作成される。


③ もっとも適切な解析結果の取得
ラティス構造を作成した段階で、日本語の文法的に正しい解析結果を得ることができる。より日本語らしい解析結果を上位に持ってくるための手法の一つとして、「コスト最小法」がある。この方法は、「形態素と形態素の結びつきやすさ/にくさ」(連接コスト)、「形態素自体の出現のしやすさ/しにくさ」(生起コスト)を各形態素ごとに割り当て、文全体で見たときのコストの総和を計算することで、日本語らしい解析結果を得る。

※ コストそのものの導出は、機械学習で作成したり、
統計的な手法(隠れマルコフモデルや条件付き確率場)を使って作成、推定するらしい。


辞書型形態素解析の実装


とりあえず雰囲気は出ている。
#!/usr/bin/python
# coding=utf-8

import sys
from collections import defaultdict
reload(sys)
sys.setdefaultencoding('utf-8')

# 辞書
dict_entries = [
    [u"かれ",     {'pos':'N',   'lemma':u"彼",    'cost':  0}],
    [u"の",       {'pos':'J-K', 'lemma':u"の",    'cost':  0}],
    [u"く",       {'pos':'N',   'lemma':u"区",    'cost':  0}],
    [u"くる",     {'pos':'V-S', 'lemma':u"来る",  'cost':  0}],
    [u"くる",     {'pos':'V-T', 'lemma':u"来る",  'cost':  0}],
    [u"くるま",   {'pos':'N',   'lemma':u"車",    'cost':  0}],
    [u"ま",       {'pos':'N',   'lemma':u"間",    'cost':  0}],
    [u"まで",     {'pos':'J-F', 'lemma':u"まで",  'cost':  0}],
    [u"で",       {'pos':'J-K', 'lemma':u"で",    'cost':  0}],
    [u"でま",     {'pos':'N',   'lemma':u"デマ",  'cost':  0}],
    [u"まつ",     {'pos':'N',   'lemma':u"松",    'cost':  0}],
    [u"まつ",     {'pos':'V-S', 'lemma':u"待つ",  'cost':  0}],
    [u"まつ",     {'pos':'V-T', 'lemma':u"待つ",  'cost':  0}],
    [u"つ",       {'pos':'N',   'lemma':u"津",    'cost':  0}],
    [u"こ",       {'pos':'SF',  'lemma':u"個",    'cost': 10}],
    [u"この",     {'pos':'T',   'lemma':u"この",  'cost': 10}],
    [u"ひ",       {'pos':'N',   'lemma':u"日",    'cost': 40}],
    [u"ひと",     {'pos':'N',   'lemma':u"人",    'cost': 40}],
    [u"ひとこと", {'pos':'N',   'lemma':u"一言",  'cost': 40}],
    [u"と",       {'pos':'J',   'lemma':u"と",    'cost': 10}],
    [u"こと",     {'pos':'N',   'lemma':u"事",    'cost': 10}],
    [u"で",       {'pos':'V-Z', 'lemma':u"出",    'cost': 40}],
    [u"で",       {'pos':'V-Y', 'lemma':u"出",    'cost': 40}],
    [u"で",       {'pos':'J',   'lemma':u"で",    'cost': 10}],
    [u"げんき",   {'pos':'N',   'lemma':u"元気",  'cost': 40}],
    [u"に",       {'pos':'J',   'lemma':u"に",    'cost': 10}],
    [u"になっ",   {'pos':'V-Y', 'lemma':u"担っ",  'cost': 40}],
    [u"なっ",     {'pos':'V-Y', 'lemma':u"なっ",  'cost': 40}],
    [u"た",       {'pos':'A',   'lemma':u"た",    'cost': 10}]
]

# Dic class
class Dic:
    """辞書クラス"""

    # トライの作成関数
    @staticmethod
    def insert(trie, key, value):
        """trie"""
        if key:
            first, rest = key[0], key[1:]
            if first not in trie:
                trie[first] = {}
            Dic.insert(trie[first], rest, value)
        else:
            if not 'value' in trie:
                trie['value'] = []
            trie['value'].append(value)

    # トライの作成
    @staticmethod
    def mktrie(dict_entries):
        matrie = {}
        for entry in dict_entries:
            entry[1]['length'] = len(entry[0])
            Dic.insert(matrie, entry[0].encode('utf-8'), entry[1])

        return matrie

# Node class
class Node:
    """ラティス構造を構築するためのノード"""
    def __init__(self, lemma, pos, node_cost, begin):
        self.lemma = lemma
        self.pos   = pos
        self.node_cost = node_cost
        self.length = len(lemma)
        self.next = []
        self.cost = 0
        self.begin = begin

# 形態素解析
def analyze(trie, sent, connect_func=lambda x,y: True, cost_func=lambda x,y: 0):

    # 共通接頭辞探索
    def common_prefix_search(trie, key):
        ret = []
        if 'value' in trie:
            ret += trie['value']
        if key:
            first, rest = key[0], key[1:]
            if first in trie:
                ret += common_prefix_search(trie[first], rest)
        return ret

    # 結果表示用
    def enum_solutions(node):
        results = []
        if node.lemma == u'EOS':
            return [[u'EOS']]
        for nnode in node.next:
            for solution in enum_solutions(nnode):
                results.append([node.lemma]+solution)
        return results


    # BOSノードの定義
    bos_node = Node('BOS', 'BOS', 0, -1)
    end_node_list = defaultdict(list)
    end_node_list[0].append(bos_node)


    # 文頭から
    for i in range(0, len(sent)+1):

        # 共通接頭辞探索
        if i < len(sent):
            cps_results = common_prefix_search(trie, sent[i:].encode('utf-8'))
        else:
            # EOS
            cps_results = [{'lemma':u'EOS','length':3,'pos':'EOS','cost':0}]

        # 各形態素の連接可能性、コストを計算
        for centry in cps_results:
            cnode = Node(centry['lemma'], centry['pos'], centry['cost'], i)
            min_cost = -1
            min_bnodes = []

            # 連接可能性を確認
            for bnode in end_node_list[i]:

                # 連接可能性を確認
                if connect_func(bnode, cnode):

                    # 生起コスト+連接コスト
                    cost = bnode.cost + cost_func(bnode, cnode)

                    # コストが最小のものを選択
                    if min_cost < 0 or cost < min_cost:
                        min_cost = cost
                        min_bnodes = [bnode]
                    elif cost == min_cost:
                        min_bnodes.append(bnode)

            if len(min_bnodes) > 0:
                for bnode in min_bnodes:
                    cnode.cost = min_cost
                    bnode.next.append(cnode)

                end_nodes = end_node_list[i + centry['length']]
                if not cnode in end_nodes: end_nodes.append(cnode)

    return enum_solutions(bos_node)

# main
def main():
    """main"""

    # 連接可能判定関数
    def is_connectable(bnode, cnode):
        """is_connectable"""
        ctable = set([
            ('BOS', 'N'),('BOS', 'V'),('BOS','T'),
            ('T', 'N'),('N', 'J'),('J','N'),('J','V'),
            ('V-T', 'N'),('V-T', 'J-F'),('V-Y', 'A'),
            ('V-S', 'EOS'),('A', 'EOS'),
        ])

        bpos = bnode.pos
        bpos_s = bpos.split('-')[0]
        cpos = cnode.pos
        cpos_s = cpos.split('-')[0]

        #return True
        return ((bpos, cpos) in ctable) or ((bpos_s, cpos) in ctable) \
            or ((bpos, cpos_s) in ctable) or ((bpos_s, cpos_s) in ctable)

    # 連接コスト計算関数
    def cost_minimum(bnode, cnode):
        ctable = {
            ('BOS', 'T'): 10,
            ('T', 'N'):   10,
            ('N', 'J'):   10,
            ('J', 'N'):   10,
            ('N', 'N'):   10,
            ('N', 'V-Z'): 40,
            ('N', 'V-Y'): 40,
            ('V-Z', 'N'): 40,
            ('V-Y', 'N'): 40,
            ('J', 'V-Z'): 10,
            ('J', 'V-Y'): 10,
            ('V-Y', 'A'): 10,
            ('A', 'EOS'): 10
        }
        pos_2gram = (bnode.pos, cnode.pos)
        return cnode.cost + (ctable[pos_2gram] if pos_2gram in ctable else 100)


    # 辞書のtrieを作成
    matrie = Dic.mktrie(dict_entries)

    # 解析
    res = analyze(matrie, u"かれのくるまでまつ", is_connectable, cost_minimum)
    print "解析1"
    print '\n'.join('/'.join(sent) for sent in res)
    print

    # 解析
    res = analyze(matrie, u"このひとことでげんきになった", is_connectable, cost_minimum)
    print "解析2"
    print '\n'.join('/'.join(sent) for sent in res)
    print

if __name__ == '__main__':
    main()

実行結果
[karino@localhost jisyo]$ python analyze_fix.py 
解析1
BOS/彼/の/車/で/待つ/EOS

解析2
BOS/この/一言/で/元気/に/なっ/た/EOS



コストをすべてゼロにした場合の実行結果。
考えられるすべての組み合わせが出力される。
解析1
BOS/彼/の/来る/間/で/間/津/EOS
BOS/彼/の/来る/間/で/松/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/出/間/津/EOS
BOS/彼/の/来る/間/出/松/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/出/間/津/EOS
BOS/彼/の/来る/間/出/松/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/で/間/津/EOS
BOS/彼/の/来る/間/で/松/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/デマ/津/EOS
BOS/彼/の/来る/まで/間/津/EOS
BOS/彼/の/来る/まで/松/EOS
BOS/彼/の/来る/まで/待つ/EOS
BOS/彼/の/来る/まで/待つ/EOS
BOS/彼/の/来る/間/で/間/津/EOS
BOS/彼/の/来る/間/で/松/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/出/間/津/EOS
BOS/彼/の/来る/間/出/松/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/出/間/津/EOS
BOS/彼/の/来る/間/出/松/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/出/待つ/EOS
BOS/彼/の/来る/間/で/間/津/EOS
BOS/彼/の/来る/間/で/松/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/で/待つ/EOS
BOS/彼/の/来る/間/デマ/津/EOS
BOS/彼/の/来る/まで/間/津/EOS
BOS/彼/の/来る/まで/松/EOS
BOS/彼/の/来る/まで/待つ/EOS
BOS/彼/の/来る/まで/待つ/EOS
BOS/彼/の/車/で/間/津/EOS
BOS/彼/の/車/で/松/EOS
BOS/彼/の/車/で/待つ/EOS
BOS/彼/の/車/で/待つ/EOS
BOS/彼/の/車/出/間/津/EOS
BOS/彼/の/車/出/松/EOS
BOS/彼/の/車/出/待つ/EOS
BOS/彼/の/車/出/待つ/EOS
BOS/彼/の/車/出/間/津/EOS
BOS/彼/の/車/出/松/EOS
BOS/彼/の/車/出/待つ/EOS
BOS/彼/の/車/出/待つ/EOS
BOS/彼/の/車/で/間/津/EOS
BOS/彼/の/車/で/松/EOS
BOS/彼/の/車/で/待つ/EOS
BOS/彼/の/車/で/待つ/EOS
BOS/彼/の/車/デマ/津/EOS

解析2
BOS/個/の/日/と/個/と/で/元気/に/なっ/た/EOS
BOS/個/の/日/と/個/と/で/元気/担っ/た/EOS
BOS/個/の/日/と/個/と/出/元気/に/なっ/た/EOS
BOS/個/の/日/と/個/と/出/元気/担っ/た/EOS
BOS/個/の/日/と/個/と/出/元気/に/なっ/た/EOS
BOS/個/の/日/と/個/と/出/元気/担っ/た/EOS
BOS/個/の/日/と/個/と/で/元気/に/なっ/た/EOS
BOS/個/の/日/と/個/と/で/元気/担っ/た/EOS
BOS/個/の/日/と/事/で/元気/に/なっ/た/EOS
BOS/個/の/日/と/事/で/元気/担っ/た/EOS
BOS/個/の/日/と/事/出/元気/に/なっ/た/EOS
BOS/個/の/日/と/事/出/元気/担っ/た/EOS
BOS/個/の/日/と/事/出/元気/に/なっ/た/EOS
BOS/個/の/日/と/事/出/元気/担っ/た/EOS
BOS/個/の/日/と/事/で/元気/に/なっ/た/EOS
BOS/個/の/日/と/事/で/元気/担っ/た/EOS
BOS/個/の/人/個/と/で/元気/に/なっ/た/EOS
BOS/個/の/人/個/と/で/元気/担っ/た/EOS
BOS/個/の/人/個/と/出/元気/に/なっ/た/EOS
BOS/個/の/人/個/と/出/元気/担っ/た/EOS
BOS/個/の/人/個/と/出/元気/に/なっ/た/EOS
BOS/個/の/人/個/と/出/元気/担っ/た/EOS
BOS/個/の/人/個/と/で/元気/に/なっ/た/EOS
BOS/個/の/人/個/と/で/元気/担っ/た/EOS
BOS/個/の/人/事/で/元気/に/なっ/た/EOS
BOS/個/の/人/事/で/元気/担っ/た/EOS
BOS/個/の/人/事/出/元気/に/なっ/た/EOS
BOS/個/の/人/事/出/元気/担っ/た/EOS
BOS/個/の/人/事/出/元気/に/なっ/た/EOS
BOS/個/の/人/事/出/元気/担っ/た/EOS
BOS/個/の/人/事/で/元気/に/なっ/た/EOS
BOS/個/の/人/事/で/元気/担っ/た/EOS
BOS/個/の/一言/で/元気/に/なっ/た/EOS
BOS/個/の/一言/で/元気/担っ/た/EOS
BOS/個/の/一言/出/元気/に/なっ/た/EOS
BOS/個/の/一言/出/元気/担っ/た/EOS
BOS/個/の/一言/出/元気/に/なっ/た/EOS
BOS/個/の/一言/出/元気/担っ/た/EOS
BOS/個/の/一言/で/元気/に/なっ/た/EOS
BOS/個/の/一言/で/元気/担っ/た/EOS
BOS/この/日/と/個/と/で/元気/に/なっ/た/EOS
BOS/この/日/と/個/と/で/元気/担っ/た/EOS
BOS/この/日/と/個/と/出/元気/に/なっ/た/EOS
BOS/この/日/と/個/と/出/元気/担っ/た/EOS
BOS/この/日/と/個/と/出/元気/に/なっ/た/EOS
BOS/この/日/と/個/と/出/元気/担っ/た/EOS
BOS/この/日/と/個/と/で/元気/に/なっ/た/EOS
BOS/この/日/と/個/と/で/元気/担っ/た/EOS
BOS/この/日/と/事/で/元気/に/なっ/た/EOS
BOS/この/日/と/事/で/元気/担っ/た/EOS
BOS/この/日/と/事/出/元気/に/なっ/た/EOS
BOS/この/日/と/事/出/元気/担っ/た/EOS
BOS/この/日/と/事/出/元気/に/なっ/た/EOS
BOS/この/日/と/事/出/元気/担っ/た/EOS
BOS/この/日/と/事/で/元気/に/なっ/た/EOS
BOS/この/日/と/事/で/元気/担っ/た/EOS
BOS/この/人/個/と/で/元気/に/なっ/た/EOS
BOS/この/人/個/と/で/元気/担っ/た/EOS
BOS/この/人/個/と/出/元気/に/なっ/た/EOS
BOS/この/人/個/と/出/元気/担っ/た/EOS
BOS/この/人/個/と/出/元気/に/なっ/た/EOS
BOS/この/人/個/と/出/元気/担っ/た/EOS
BOS/この/人/個/と/で/元気/に/なっ/た/EOS
BOS/この/人/個/と/で/元気/担っ/た/EOS
BOS/この/人/事/で/元気/に/なっ/た/EOS
BOS/この/人/事/で/元気/担っ/た/EOS
BOS/この/人/事/出/元気/に/なっ/た/EOS
BOS/この/人/事/出/元気/担っ/た/EOS
BOS/この/人/事/出/元気/に/なっ/た/EOS
BOS/この/人/事/出/元気/担っ/た/EOS
BOS/この/人/事/で/元気/に/なっ/た/EOS
BOS/この/人/事/で/元気/担っ/た/EOS
BOS/この/一言/で/元気/に/なっ/た/EOS
BOS/この/一言/で/元気/担っ/た/EOS
BOS/この/一言/出/元気/に/なっ/た/EOS
BOS/この/一言/出/元気/担っ/た/EOS
BOS/この/一言/出/元気/に/なっ/た/EOS
BOS/この/一言/出/元気/担っ/た/EOS
BOS/この/一言/で/元気/に/なっ/た/EOS
BOS/この/一言/で/元気/担っ/た/EOS

0 件のコメント:

コメントを投稿