構文解析 - 静かなる名辞

【python】cabochaのpythonバインディングの変な挙動

Fri, 23 Mar 2018 07:51:40 +0900

環境

　ubuntu 14.04
　cabocha 0.69
　cabocha-python 0.69

問題の概要

　変な挙動だった。というか率直に言ってバグなのでは？

>>> import CaboCha
>>> cparser = CaboCha.Parser()
>>> tree1 = cparser.parse("吾輩は猫である。")
>>> print(tree1.toString(CaboCha.FORMAT_TREE))
    吾輩は-D
  猫である。
EOS

>>> tree2 = cparser.parse("吾輩は猫ではない。")
>>> print(tree1.toString(CaboCha.FORMAT_TREE))
      吾輩は-D
  猫ではない。
EOS

　これはおかしい。CaboChaはこわれている。

　いや、「これで仕様通り動いてる。おまえの使い方が間違ってるんだ」て言われたら反論できないけど。詳細なドキュメントを見かけたことがないので、もしかしたらアホなこと（Parserのインスタンスの使い回し）をやっているのかもしれない。

回避するために試したこと

CaboCha.Parser("")する（コンストラクタに空文字列を渡す）

　効果なし。

一度空文字列に対してparseを呼ぶ

　ここを参考に「もしかしたら効くかも」と思ってやってみた。
MeCabのparseToNodeのひどいバグ - 北野坂備忘録
　効果なし。

文字列を変数に入れる、encodeする

　ここを参考に（以下略）。
MeCabをPythonから使う注意点とか
　効果なし。encodeに至ってはやったら落ちた。

仕方がないのでCaboCha.Parser()を毎回作る

>>> tree = CaboCha.Parser().parse("吾輩は猫である。")
>>> tree.toString(CaboCha.FORMAT_TREE)
Segmentation fault (コアダンプ)

　たぶん本体のメモリ管理とpythonの接合が上手く行っていないのだろうけど、さて困った。

>>> parser1 = CaboCha.Parser()
>>> parser2 = CaboCha.Parser()
>>> tree1 = parser1.parse("吾輩は猫である。")
>>> tree2 = parser2.parse("吾輩は猫ではない。")
>>> tree1.toString(CaboCha.FORMAT_TREE)
'    吾輩は-D\n  猫である。\nEOS\n'

　一応回避できることはわかった。これで書くと極めて非python的なプログラミングを強いられるという問題はあるが、たぶんなんとかなる。

　ちなみに、ParserのインスタンスがGCに回収されると treeだけ残っててもtoStringできないようです（Segmentation faultを吐いてくれる）。どんな作りになってるのかなんとなくわかってきたけど、率直に言って○○。

def parse(sentences):
    """
    sentencesは一文ずつに区切られた文のリストとして扱う
    """
    trees = []
    plist = []
    for s in sentences:
        parser = CaboCha.Parser()
        trees.append(parser.parse(s))
        plist.append(parser)

　このようなものを書いてあげれば、後からtreeを使うことができることがわかった。率直に言ってまったく嬉しくない。

問題原因の切り分け

　は、できてないです。
　

うちの環境固有の問題
cabocha-pythonの特定のバージョンの問題
cabocha-python固有の問題
cabocha固有の問題

　とりあえず逃げれることはわかったので、僕はやらない（明言）。

対策

　たぶん解析結果のtreeオブジェクトを使いまわそうという発想が間違っていて、cabochaのtreeオブジェクトを使わないで初手でXMLか何かに変換して取り扱うのが楽だと思います。そんなことを強いるバインディングって何よ？　って気がしますが。

　もう面倒くさいから、JUMAN/KNPに鞍替えしようかなと思う今日この頃。

日本語モダリティ解析器 Zundaを試す

Thu, 22 Mar 2018 13:34:36 +0900

　日本語のモダリティを解析できるらしい。「文中のイベント（動詞や形容詞など）に対して、その真偽判断（イベントが起こったかどうか）、仮想性（仮定の話かどうか）などを解析します」とのこと。

　公式ページはたぶんここ。

jmizuno.github.io

環境

　ubuntu14.04

インストール

　CaboCha (>=0.60)と、Boost Library (>=1.41)を予め入れおく必要がある。CaboChaは入ってたけどBoost Libraryはなかったので、apt-getで入れた。

$ sudo apt-get install libboost-all-dev

　後はtarballを落としてきてmakeで入れろと公式に書いてある。どんなエラーが出てくるかとびくびくしながらやったけど、まったく問題なく入った。

$ ./configure
$ make
$ sudo make install

試してみる

　こうやって使うらしい。

$ echo -e "次郎は大阪に行った。\n太郎は東京には行かず地元に残ろうとした" | zunda
#EVENT0	4	wr:筆者	非未来	0	叙述	成立	0	0
* 0 2D 0/1 -2.249829
次郎	名詞,固有名詞,人名,名,*,*,次郎,ジロウ,ジロー
は	助詞,係助詞,*,*,*,*,は,ハ,ワ
* 1 2D 0/1 -2.249829
大阪	名詞,固有名詞,地域,一般,*,*,大阪,オオサカ,オーサカ
に	助詞,格助詞,一般,*,*,*,に,ニ,ニ
* 2 -1D 0/1 0.000000
行っ	動詞,自立,*,*,五段・カ行促音便,連用タ接続,行く,イッ,イッ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
。	記号,句点,*,*,*,*,。,。,。
EOS

#EVENT0	5	wr:筆者	未来	0	叙述	不成立	0	0
#EVENT1	9	wr:筆者	未来	0	意志	高確率	ポジティブ	0
#EVENT2	12	wr:筆者	非未来	0	叙述	成立	0	0
* 0 4D 0/1 -1.650377
太郎	名詞,固有名詞,人名,名,*,*,太郎,タロウ,タロー
は	助詞,係助詞,*,*,*,*,は,ハ,ワ
* 1 2D 0/2 0.320510
東京	名詞,固有名詞,地域,一般,*,*,東京,トウキョウ,トーキョー
に	助詞,格助詞,一般,*,*,*,に,ニ,ニ
は	助詞,係助詞,*,*,*,*,は,ハ,ワ
* 2 4D 0/1 -1.650377
行か	動詞,自立,*,*,五段・カ行促音便,未然形,行く,イカ,イカ
ず	助動詞,*,*,*,特殊・ヌ,連用ニ接続,ぬ,ズ,ズ
* 3 4D 0/1 -1.650377
地元	名詞,一般,*,*,*,*,地元,ジモト,ジモト
に	助詞,格助詞,一般,*,*,*,に,ニ,ニ
* 4 -1D 3/4 0.000000
残ろ	動詞,自立,*,*,五段・ラ行,未然ウ接続,残る,ノコロ,ノコロ
う	助動詞,*,*,*,不変化型,基本形,う,ウ,ウ
と	助詞,格助詞,引用,*,*,*,と,ト,ト
し	動詞,自立,*,*,サ変・スル,連用形,する,シ,シ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

　公式ページには改行すれば別の文として扱われると書いてあるが、echoに-eオプションを渡さないと改行文字は改行として出力されないので注意。

　それはそうと、この結果の見方だが、

#EVENT0	4	wr:筆者	非未来	0	叙述	成立	0	0」

　という結果は4番目の形態素がどんなモダリティなのかを表す。つまり「行っ動詞,自立,*,*,五段・カ行促音便,連用タ接続,行く,イッ,イッ」に対応する。単純だけどわかりやすいかどうかは微妙かもしれない。

色々なことを試す

　とりあえず、もうちょっと色々な文を入れてみる。

$ echo "遊びに行きたいな" | zunda
#EVENT0	2	wr:筆者	未来	0	欲求	0	ポジティブ	0
* 0 1D 0/1 0.000000
遊び	名詞,一般,*,*,*,*,遊び,アソビ,アソビ
に	助詞,格助詞,一般,*,*,*,に,ニ,ニ
* 1 -1D 0/2 0.000000
行き	動詞,自立,*,*,五段・カ行促音便,連用形,行く,イキ,イキ
たい	助動詞,*,*,*,特殊・タイ,基本形,たい,タイ,タイ
な	助詞,終助詞,*,*,*,*,な,ナ,ナ
EOS

　なるほど。

$ echo -e "吾輩は猫である。\n名前はまだない。" | zunda
* 0 1D 0/1 0.000000
吾輩	名詞,代名詞,一般,*,*,*,吾輩,ワガハイ,ワガハイ
は	助詞,係助詞,*,*,*,*,は,ハ,ワ
* 1 -1D 0/2 0.000000
猫	名詞,一般,*,*,*,*,猫,ネコ,ネコ
で	助動詞,*,*,*,特殊・ダ,連用形,だ,デ,デ
ある	助動詞,*,*,*,五段・ラ行アル,基本形,ある,アル,アル
。	記号,句点,*,*,*,*,。,。,。
EOS

#EVENT0	3	wr:筆者	非未来	0	叙述	成立	0	0
* 0 2D 0/1 -2.377508
名前	名詞,一般,*,*,*,*,名前,ナマエ,ナマエ
は	助詞,係助詞,*,*,*,*,は,ハ,ワ
* 1 2D 0/0 -2.377508
まだ	副詞,助詞類接続,*,*,*,*,まだ,マダ,マダ
* 2 -1D 0/0 0.000000
ない	形容詞,自立,*,*,形容詞・アウオ段,基本形,ない,ナイ,ナイ
。	記号,句点,*,*,*,*,。,。,。
EOS

　ふーん。

　まあ、勝手はなんとなくわかった。それはそうと、zundaにはpythonバインディングなんて親切なものはないらしい。zundaオリジナルなのは#から始まる行だけで、その下はcabochaの-f 1フォーマットがそのまま出てるだけなので、プログラミングで使う側としてはテキスト処理でゴリ押して使うことになるだろう。

　その際は、コマンドラインオプションで何百kbも受け渡しするのは流石にアレなので、まとめてファイルを処理させるか、立ち上げておいて標準入出力でやりとりするかのどちらかになる。

【python】CKY法をpythonで実装

Mon, 19 Feb 2018 04:44:52 +0900

　構文解析アルゴリズムのCKY法の実装について説明する。参考にしたテキストはこれ。

自然言語処理の基礎

作者: 奥村学
出版社/メーカー: コロナ社
発売日: 2010/10/15
メディア: 単行本（ソフトカバー）
購入: 8人クリック: 379回
この商品を含むブログ (11件) を見る

理論
問題設定
実装
結果
感想
付録　ソースコード

理論

　教科書読めばぜんぶ書いてあります（ちゃんと解説しようとすると大変なので、自分で説明したくない）。

　ネット上の解説としては、

　この3つを読めば理解できると思います。プログラムとして実装する前に、紙とペンで一回やってみるべきです。

　CKY法は理屈が簡単な割に、プログラムに書き起こすのが面倒くさいタイプのアルゴリズムです（だと思う）。頭でちゃんと理解してから挑むことが望ましい。

問題設定

　教科書のToy problemで行きます。次の文を構文解析するというものです。

astronomers saw stars with ears

　文法は次のように与えられています。

S→NP VP:1.0
PP→P NP:1.0
VP→V NP:0.7
VP→VP PP:0.3
NP→NP PP:0.4
P→with:1.0
V→saw:1.0
NP→astronomers:0.1
NP→ears:0.18
NP→saw:0.04
NP→stars:0.18
NP→telescope:0.1

　コロンの後の数字は文法規則が適用される確率です。今回の例文には多義性があるので（複数の構文解析結果が出て来る）、この確率を使ってもっともらしい結果を選ぼうという訳です。

実装

　書いたソースコードは記事の最後に丸ごと載せてます。以下では実装方法を簡単に解説します。

　とりあえず何も考えず、上記例文と文法をグローバル変数として定義。

example_sentence = "astronomers saw stars with ears"

grammar_text = """S→NP VP:1.0
PP→P NP:1.0
VP→V NP:0.7
VP→VP PP:0.3
NP→NP PP:0.4
P→with:1.0
V→saw:1.0
NP→astronomers:0.1
NP→ears:0.18
NP→saw:0.04
NP→stars:0.18
NP→telescope:0.1"""

　CKYクラスを作ることにする。CKYクラスインスタンスのparseメソッドを呼べば、然るべき型で結果を返してくれるように作る方針で行こう。

class CKY:
    def __init__(self, grammar_text):
        self.grammar_dict = defaultdict(set)
        for line in grammar_text.split("\n"):
            rule, p = line.split(":")
            l, r = rule.split("→")
            self.grammar_dict[r].add((l, float(p)))

        self.cky_array = None

　文法の情報はクラス内で持ってないと困るので、defaultdict(set)で格納。解析の過程を考えると、文法の右側の要素から左側の要素（あと確率）が取り出せると嬉しいので、そうする。今回、keyは"astronomers"みたいな終端記号を表す文字列か、"P NP"みたいな非終端記号のペアを表す文字列にしている。非終端記号のペアはtupleにして……とか考えるとかえって面倒くさい。

　なんでsetにするのか？　右が同じだけど左が異なるパターンがあるから。「V→saw:1.0」と「NP→saw:0.04」とかですね。

　self.cky_arrayはとりあえずNoneにしておく。文の長さが決まらないとinitializeできない。ということは、initializeするメソッドも作っておく必要がある（別にメソッドにしないでparseメソッド内でやっても良いんだが）。

　このcky_array、CKYテーブル、詰まるところ三角行列をどう実装するかは悩みどころで、適当に作るとインデックスでエラく苦労する。とりあえず、今回は多義性がある文を解析するので、行列の一つのセルに複数の要素が入るので、三重リストみたいなものにしないといけない。

　という訳で、単語数*単語数*空リストの三重リストとして実装する。こうすると下半分が無駄にメモリを食うけど、大した実害はない。ちょっと無駄っぽいけど。

    def _init_cky_array(self, length):
        self.cky_array = [[[] for _ in range(length)]
                          for i in range(length)]
        return self.cky_array

　あとは空リストに適当に値を突っ込んでいけば、CKYテーブルは作れる。適当に、と書いたけど、ここが一番つらい。とりあえずparseメソッドを書き始める。

    def parse(self, text):
        words = text.split()
        self.length = len(words)
        self._init_cky_array(self.length)

　まず行列の対角成分（NT→Tの文法の部分）を埋める。

        for i, word in enumerate(words):
            for l, p in self.grammar_dict[word]:
                self.cky_array[i][i].append((l, word, p))

　テーブルのセルに入れる値は、(左辺値(str), 単語(str), 確率(float))の形のtuple。対角成分以外では、(左辺値(str), (右辺の左のindex(tuple), 右辺の右のindex(tuple)), 確率(float))とする方針。こういうところに独自定義のオブジェクトを入れたがる人がたまにいるが、経験上かえって面倒くさくなることが多い。CKY以外のクラスは定義しないで書く。

　そして謎のfor文で一気にCKY配列を埋める。コメントを書いたので頑張って理解して。

        # 対角成分の1つ右,2つ右,...と処理を回すループ
        for d in range(1, self.length):
            
            # 斜め下に進んでいくループ
            # i,jでどのセルを処理対象とするか決める
            for i in range(self.length - d):
                j = i + d
                
                # セルの中身を埋めるループ
                for k in range(i, j):

                    # 右辺の可能な組み合わせを列挙してる
                    for a, b in product(
                            range(len(self.cky_array[i][k])),
                            range(len(self.cky_array[k+1][j]))):

                        # 辞書のキーを作る
                        s = "{0} {1}".format(
                            self.cky_array[i][k][a][0],
                            self.cky_array[k+1][j][b][0])
                        
                        # キーに合致する文法をぜんぶ出す
                        for l,p in self.grammar_dict[s]:

                            # セルに中身を入れる
                            self.cky_array[i][j].append(
                                (l, ((i,k,a), (k+1,j,b)), p))

　なんとforループが5つもある。五重のforと名付けよう。なお、CKY法はのアルゴリズムである。一番内側の2つのループは基本的に定数項で、計算量には効かない。

　このforループが終わると、CKYテーブルはすでに完成している。後は、これを辿って構文木を出力するだけだ。セルにindexを入れたことがここで効いてくる。なお、紙とペンでやるときはNP1とか通し番号を振り、NP1(astronomers)とかPP1(P1, NP2)みたいに書くと混乱が少ない。
　
　構文木を辿る方法は、当然再帰である。indexを見て次のセルに飛べば良い。indexを表現するtupleではなく、終端記号を表現するstrが格納されていたら、再帰の終了条件を満たしたとみなす。

　構文木の出力形式は、XMLで行く。僕はlxmlを使って処理するのに慣れているので、今回も使うことにする。

　以上の方針を決めた上で、次のコードを書き足す。

        # parseの最後
        return self._gen_xml_etree_list()

    def _traverse_tree(self, index=(0,0,0)):
        # 構文木を辿る
        i,j,k = index
        node = self.cky_array[i][j][k]
        elem = etree.Element(node[0])
        child = node[1]
        p = node[2]
        elem.attrib["p"] = str(p)

        if type(child) == str:
            elem.text = child
            return elem
        else:
            l, r = child
            elem.append(self._traverse_tree(index=l))            
            elem.append(self._traverse_tree(index=r))
            return elem

    def _gen_xml_etree_list(self):
        # 再帰呼出しを開始する
        lst = []
        for i, s in enumerate(self.cky_array[0][self.length - 1]):
            if s[0] != "S":
                pass
            else:
                # etreeのまま返すことにしよう...
                lst.append(self._traverse_tree((0,4,i)))
        return lst

　お疲れ様でした。これでCKYクラスの実装はおしまいです。あとはmainを書くだけです。mainは確率の総乗を計算し、またetreeを文字列に変換して表示します。

def main():
    cky = CKY(grammar_text)
    lst = cky.parse(example_sentence)
    for xml_tree in lst:
        p = 1
        for elem in xml_tree.iter():
            p *= float(elem.attrib["p"])
        print(p)
        print(
            etree.tostring(xml_tree, pretty_print=True).decode())

　あとはmainの呼び出しを書けば終了です。import等はここでは省略しました。記事末尾のソースコードには載せています。

結果

　実行結果を見せます。

0.0009071999999999998
<S p="1.0">
  <NP p="0.1">astronomers</NP>
  <VP p="0.7">
    <V p="1.0">saw</V>
    <NP p="0.4">
      <NP p="0.18">stars</NP>
      <PP p="1.0">
        <P p="1.0">with</P>
        <NP p="0.18">ears</NP>
      </PP>
    </NP>
  </VP>
</S>

0.0006803999999999998
<S p="1.0">
  <NP p="0.1">astronomers</NP>
  <VP p="0.3">
    <VP p="0.7">
      <V p="1.0">saw</V>
      <NP p="0.18">stars</NP>
    </VP>
    <PP p="1.0">
      <P p="1.0">with</P>
      <NP p="0.18">ears</NP>
    </PP>
  </VP>
</S>

　まあ、良いのでは。「天文学者は耳と一緒の星を見た」と「天文学者は耳で星を見た」の二通りの解析結果があり、前者の方が良い感じ、みたいな結果・・・だと思います。

感想

　やっぱりアルゴリズムが簡単な割に書くのが大変だった。特にindexの範囲をミスると簡単に死ねるので、自分で実装するときはindexを随時printして（あるいはデバッガで確認して）正しい値が出ているか確認しながらやるのが良いです。

付録　ソースコード

▶ソースコード全体（クリックで展開）

# coding: UTF-8

from collections import defaultdict
from itertools import product

from lxml import etree

example_sentence = "astronomers saw stars with ears"

grammar_text = """S→NP VP:1.0
PP→P NP:1.0
VP→V NP:0.7
VP→VP PP:0.3
NP→NP PP:0.4
P→with:1.0
V→saw:1.0
NP→astronomers:0.1
NP→ears:0.18
NP→saw:0.04
NP→stars:0.18
NP→telescope:0.1"""

class CKY:
    def __init__(self, grammar_text):
        self.grammar_dict = defaultdict(set)
        for line in grammar_text.split("\n"):
            rule, p = line.split(":")
            l, r = rule.split("→")
            self.grammar_dict[r].add((l, float(p)))

        self.cky_array = None

    def _init_cky_array(self, length):
        self.cky_array = [[[] for _ in range(length)]
                          for i in range(length)]
        return self.cky_array

    def parse(self, text):
        words = text.split()
        self.length = len(words)
        self._init_cky_array(self.length)

        for i, word in enumerate(words):
            for l, p in self.grammar_dict[word]:
                self.cky_array[i][i].append((l, word, p))
        
        # 対角成分の1つ右,2つ右,...と処理を回すループ
        for d in range(1, self.length):
            
            # 斜め下に進んでいくループ
            # i,jでどのセルを処理対象とするか決める
            for i in range(self.length - d):
                j = i + d
                
                # セルの中身を埋めるループ
                for k in range(i, j):

                    # 右辺の可能な組み合わせを列挙してる
                    for a, b in product(
                            range(len(self.cky_array[i][k])),
                            range(len(self.cky_array[k+1][j]))):

                        # 辞書のキーを作る
                        s = "{0} {1}".format(
                            self.cky_array[i][k][a][0],
                            self.cky_array[k+1][j][b][0])
                        
                        # キーに合致する文法をぜんぶ出す
                        for l,p in self.grammar_dict[s]:

                            # セルに中身を入れる
                            self.cky_array[i][j].append(
                                (l, ((i,k,a), (k+1,j,b)), p))

        # parseの最後
        return self._gen_xml_etree_list()

    def _traverse_tree(self, index=(0,0,0)):
        # 構文木を辿る
        i,j,k = index
        node = self.cky_array[i][j][k]
        elem = etree.Element(node[0])
        child = node[1]
        p = node[2]
        elem.attrib["p"] = str(p)

        if type(child) == str:
            elem.text = child
            return elem
        else:
            l, r = child
            elem.append(self._traverse_tree(index=l))            
            elem.append(self._traverse_tree(index=r))
            return elem

    def _gen_xml_etree_list(self):
        # 再帰呼出しを開始する
        lst = []
        for i, s in enumerate(self.cky_array[0][self.length - 1]):
            if s[0] != "S":
                pass
            else:
                # etreeのまま返すことにしよう...
                lst.append(self._traverse_tree((0,4,i)))
        return lst

def main():
    cky = CKY(grammar_text)
    lst = cky.parse(example_sentence)
    for xml_tree in lst:
        p = 1
        for elem in xml_tree.iter():
            p *= float(elem.attrib["p"])
        print(p)
        print(
            etree.tostring(xml_tree, pretty_print=True).decode())

if __name__ == "__main__":
    main()