Python で構文木を端末に描画してみる

研究

巷にある構文解析器には，解析結果を木構造で端末に表示する機能がある．あった方が良いだろうなと思いつつ，自分で実装するのはいかにも面倒そうだと感じて，今まで後回しにしていた．いい加減そろそろ無いと困ると感じるようになってきたので，先日の通勤電車の中で暇つぶしに書いたら，思いの外あっけなく実装できたので，メモ代わりに残しておく．最初 Ruby でワンライナーで書けないかなと思ったが，流石に難しかったので，練習も兼ねて Python で実装してみた．

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Usage: lattice_to_tree.py < in.KNP
#   translate parser output into human-readable dependency tree structure
import sys

# customizable parameters
indent = 4          # for one dependency arc
offset = 2          # offset from the left
color  = "\033[31m" # color (red) for incorrect dependency arc

class Binfo:
    """ bunsetsu infomation """
    def __init__ (self, *args):
        self.id, self.head, self.ok, self.gold = args
        self.morph, self.depth, self.first_child = "", 0, -1
    def len    (self)        : return len (unicode (self.morph, 'utf-8'))
    def offset (self, width) : return width - self.len () - self.depth

binfo  = []
for line in sys.stdin:
    if line[0] == '#':
        sys.stdout.write (line)
        binfo = []
    elif line[0] == 'E': # EOS
        for c in reversed (binfo[:-1]):
            c.depth = binfo[c.head].depth + indent
            binfo[c.head].first_child = c.id
        width = offset + max (b.len () + b.depth for b in binfo) # tree width
        for b in binfo:
            if b.head == -1:
                sys.stdout.write ("% 3d:%s%s" % (b.id, "　" * b.offset (width),
                                                 b.morph))
            else:
                output = "" if b.ok else color
                output += "% 3d:%s%s" % (b.id, "　" * b.offset (width), b.morph)
                h = binfo[b.head]
                output += "━" * (b.depth - h.depth - 1) # ─
                output += "┓" if b.id == h.first_child else "┫" # ┐ ┤
                output += "" if b.ok else "%-4s\033[0m" % b.gold
                while h.head != -1: # draw arcs spanning from x < b to y > h
                    c, h = h, binfo[h.head]
                    output += "　" * (c.depth - h.depth - (1 if b.ok else 3))
                    output += "┃" if h.first_child < b.id else "　" # │
                    b.ok = True
                sys.stdout.write (output + "\n")
        sys.stdout.write (line)
    elif line[0] == '*':
        h, g = (line[:-1] + "#-1D").split (' ')[2].split('#')[:2]
        binfo.append (Binfo (len (binfo), int (h[:-1]),
                             g[:-1] == "-1" or h[:-1] == g[:-1], g))
    else:
        surface, feature = line[:-1].split('\t')
        binfo[-1].morph += surface

Python にはあまり慣れていないので，実装としてはあまり良くないかも知れないし，もっと短く書けるような気もするが（書き方の作法なども分からないので，載せるにあたって変数名を直すぐらいしかしていない），手続き的にはまあこんなものだろう．人が実際に見るものなので，スクリプト言語の実装でも速度的には十分実用的に使えそうだけど，C++ でもし書くとしたら，文字の幅を調べるのが無駄に面倒そうだ（けど知らないだけで簡単かもしれない）．しかし，sys.stdout.write が長過ぎて，しかも大量にあるので読み辛い・・・print は改行や空白など余計なものをつけてくれるし（end= を使っても長い），どうしたらすっきり書けるのだろうか． 文字列にまとめてから出力するようにした．
手続き的に厄介なのは，出力しようとする文節 i とその係り先 j に対して，x < i かつ j < y で x->y となるような係り先がある場合だが（右側の適切な位置にその arc（の一部）を描画しなければいけない），これは再帰的に主辞 (head) を辿って一番左の係り元 (first_child として記録) を調べれば ok．
というわけで，先日の日記から「より分かりやすく伝達する手段が他にあるのであれば（それを示すのはなかなか厄介だけど）その手段と言語を組み合わせる方法もある．」という文を選んで手元の解析器にかけた出力を描画してみた（解析誤りを強調する機能のテストのため，正解らしき係り先を追加で付与; 例は後で変えるかも）．

# S-ID: 1
* 0 1D#1D
より	副詞,*,*,*,より,より,代表表記:より
* 1 2D#2D
分かり	動詞,*,子音動詞ラ行,基本連用形,分かる,わかり,代表表記:分かる
やすく	接尾辞,形容詞性述語接尾辞,イ形容詞アウオ段,基本連用形,やすい,やすく,*
* 2 3D#3D
伝達	名詞,サ変名詞,*,*,伝達,でんたつ,代表表記:伝達
する	動詞,*,サ変動詞,基本形,する,する,付属動詞候補（基本） 代表表記:する
* 3 5D#5D
手段	名詞,普通名詞,*,*,手段,しゅだん,代表表記:手段
が	助詞,格助詞,*,*,が,が,*
* 4 5D#5D
他	名詞,普通名詞,*,*,他,た,漢字読み:音 修飾（ニ格） 代表表記:他
に	助詞,格助詞,*,*,に,に,*
* 5 15D#15D
ある	動詞,*,子音動詞ラ行,基本形,ある,ある,補文ト 代表表記:有る
のであれば	助動詞,*,ナ形容詞,デアル列基本条件形,のだ,のであれば,*
* 6 7D#7D
（	特殊,括弧始,*,*,（,（,*
それ	指示詞,名詞形態指示詞,*,*,それ,それ,*
を	助詞,格助詞,*,*,を,を,*
* 7 9D#9D
示す	動詞,*,子音動詞サ行,基本形,示す,しめす,代表表記:示す
の	名詞,形式名詞,*,*,の,の,*
は	助詞,副助詞,*,*,は,は,*
* 8 9D#9D
なかなか	副詞,*,*,*,なかなか,なかなか,修飾（ニ格） 代表表記:なかなか
* 9 13D#13D
厄介だ	形容詞,*,ナ形容詞,基本形,厄介だ,やっかいだ,代表表記:厄介だ
けど	助詞,接続助詞,*,*,けど,けど,*
）	特殊,括弧終,*,*,）,）,*
* 10 11D#11D
その	指示詞,連体詞形態指示詞,*,*,その,その,*
* 11 12D#12D
手段	名詞,普通名詞,*,*,手段,しゅだん,代表表記:手段
と	助詞,格助詞,*,*,と,と,*
* 12 13D#13D
言語	名詞,普通名詞,*,*,言語,げんご,代表表記:言語
を	助詞,格助詞,*,*,を,を,*
* 13 14D#14D
組み合わせる	動詞,*,母音動詞,基本形,組み合わせる,くみあわせる,代表表記:組み合わせる
* 14 15D#15D
方法	名詞,普通名詞,*,*,方法,ほうほう,代表表記:方法
も	助詞,副助詞,*,*,も,も,*
* 15 -1D
ある	動詞,*,子音動詞ラ行,基本形,ある,ある,補文ト 代表表記:有る
．	特殊,句点,*,*,．,．,*
EOS

を入力すると，

# S-ID: 1
  0:　　　　より━━━┓　　　　　　　　　　　　　　　　
  1:　　　　分かりやすく━━━┓　　　　　　　　　　　　
  2:　　　　　　　　　　伝達する━━━┓　　　　　　　　
  3:　　　　　　　　　　　　　　　手段が━━━┓　　　　
  4:　　　　　　　　　　　　　　　　他に━━━┫　　　　
  5:　　　　　　　　　　　　　　　あるのであれば━━━┓
  6:　　（それを━━━┓　　　　　　　　　　　　　　　┃
  7:　　　　　　示すのは━━━┓　　　　　　　　　　　┃
  8:　　　　　　なかなか━━━┫　　　　　　　　　　　┃
  9:　　　　　　　　厄介だけど）━━━┓　　　　　　　┃
 10:　　　　その━━━┓　　　　　　　┃　　　　　　　┃
 11:　　　　　　　手段と━━━┓13D 　┃　　　　　　　┃
 12:　　　　　　　　　　　言語を━━━┫　　　　　　　┃
 13:　　　　　　　　　　　　組み合わせる━━━┓　　　┃
 14:　　　　　　　　　　　　　　　　　　　方法も━━━┫
 15:　　　　　　　　　　　　　　　　　　　　　　　ある．EOS

という出力が得られる（ブラウザ上での表示のため，line-height を多少修正; 11文節目の表示がずれるのはフォント描画の問題で，Migu 1M などだときれいに表示される）．やはり木構造で見る方が抜群に読みやすい．可視化に限らず GUI なプログラムは全く書けないのだけど，端末でテキストを駆使して描画するものなら，すいすいと書けそうなので，今後は積極的に書くようにしよう．