木の高さの計り方

Lijun Feng+ "A Comparison of Features for Automatic Readability Assessment"
の実装をしようとしていた時の疑問。

このpaperの中では、木の高さ（Tree height）が素性として使われる。
じゃあ、コードにする時には木の高さをどうするのさ？という話。

たぶん、「一番Rootから離れたノードがRootに到達するまでのパスの数」と解釈できるのではないかと。

例えばStanford Parserのdemoにある式ならば
※　http://nlp.stanford.edu:8080/parser/

(ROOT
  (S
    (NP (PRP$ My) (NN dog))
    (ADVP (RB also))
    (VP (VBZ likes)
      (S
        (VP (VBG eating)
          (NP (NN sausage)))))
    (. .)))

があるが、この場合だと一番ひくい所にあるノードはNN sausageだろう。

では、NN sausageがRootに到達するまでのパス数は？

図を書いて確かめてみたのだが、おそらく７になるはずだ。

では、この式だけ見て、どのように高さを計るか？それは、「NN sausageがいくつの括弧に囲まれているか？」になるかと思う。
NN sausageを囲んでいる括弧の数を数えてみると、８つになる。
で、このうち( . . )は自己完結しているので、−１。つまり７つの括弧になる。

ということで、コードにするときは、

・一番、内側にあるものを探しにいく
・いくつの括弧に囲まれているか？を数字にする（自己完結しているのは除く）

ということになるかなと。

上のやり方はStanford Parserでの出力の話。
Charniak Parserなら、また別の出力をするので、Charniak Parser用に考えなくてはいけないだろう。....めんどくさ

ーそれからー
アルゴリズムを考えてもらった。

開きカッコがある度に、カッコ変数を+1、閉じカッコがある度にカッコ変数を-1する。
さらに、現時点での最深の変数を用意して、深さを記録しておく。

こうすれば、ちゃんと高さのカウントができるはず
pythonでは以下の感じになるはず

#! /usr/bin/python
# -*- coding:utf-8 -*-

#------------------------------------------------------------------------
#単純に木の深さを数字にするコード @2013/1/8
#------------------------------------------------------------------------
import sys

f = open('testSent_for_python','r')
lines = f.readlines()

for line in lines:
    # open_pa:木の一時的な深さを保存 depth:木の最深数を保存
    open_pa = 0
    depth = 0
    
    for char in line:
        
        if char == '(':
            open_pa = open_pa + 1

        elif char == ')':
            open_pa = open_pa - 1

            # open_paとdepthを比較してopen_paの方が大きかったら木の最深数を更新
            if open_pa > depth:
                depth = open_pa

    print 'depth is:',depth
    # open_paは最後には0になってないとおかしいので、その時は以下を表示
    if not open_pa == 0:
        print "something wrong"