第11回(12/11) トライ構造
    ・単語辞書の登録
    ・文の入力〜単語抽出〜属性の出力

■ トライ構造
日本語文から単語を取り出すことは、英語文からの場合と異なり、単語の間にスペースの区切が無いことから、手間がかかる。そこで単語辞書のデータ構造を工夫しなければならない。

そのためのデータ構造の1つに、トライ構造がある。トライ構造は、一種のツリー構造で、ノードが単語の品詞、アークが単語を構成する字面、となっている。そして、特徴は、アークを作る際、単語の先頭からの共通字面を束ねた形になっていることである。

たとえば、「鳥取大学」、「鳥取大砂丘」、「鳥取空港」、「賀露港」、「彼」、「は」、「に」、「行く」という単語をトライ構造にすると以下のようになる。

(root)┬→()─→()┬→()┬→(noun)
      │鳥   取   │大  │学
      │          │    └→()─→(noun)
      │          │     砂    丘
      │          └→()─→(noun)
      │           空    港
      ├→()─→()─→(noun)
      │賀   露    港
      ├→(noun)
      │彼
      ├→(p)
      │は
      ├→(p)
      │に
      └→()─→(verb)
        行   く

トライを用いて「彼は鳥取大学に行く」を解析する過程は以下のようになる。まず、先頭字面「彼」は(root)から見ると、(noun)に辿りつき、品詞が名詞であるとわかる。次の字面「は」は(root)から見ると、(p)に辿りつき、助詞であるとわかる。次の字面「鳥」は(root)から見るとアークを辿ることができる。次の字面「取」は辿った所から見るとさらにアークを辿ることができる。これを繰り返すと、(noun) と書いたノードに辿りつき、名詞であることがわかる。同様にして「に」や「行く」も解析できる。

この解析結果は、「noun,p,noun,p,verb」となる。

★ 以上は、わかりやすさのために、2バイト文字（漢字）を1アークに割り当てて説明した。しかし、実装では1バイトごとにアークを作る。すなわち、
    (root)┬─────→()─────→()─────→()─────→…
          │鳥1バイト目   鳥2バイト目   取1バイト目   取2バイト目
となる。

■ トライ構造の作り方
● トライノードのデータ構造
トライ構造を扱うクラスを定義しよう。
まず、ノードを表す TRYnode クラスを定義する。@data と @arc というインスタンス変数をアクセサから読み書きできるようにする。initialize メソッドでは、@data に nil を初期値として与え、@arc には 256 サイズの配列（Array.new(256.nil)）を与える。

class TRYnode
    @data へのアクセサの定義
    @arc へのアクセサの定義

    def initialize
        @data の初期化
        @arc の初期化
    end
end

● トライクラス・その1、単語登録
次に、本体となる TRY クラスを定義する。initialize メソッドでは、@root というインスタンス変数に初期値として TRYnode のインスタンスを与える。これが、トライのルートノード(root)となる。単語登録のメソッド entry_word は、単語と品詞という2つの引数があり、以下の擬似コードのとおり処理をする。

class TRY
  def initialize
        ルートノードの初期化
  end

  def entry_word( 単語, 品詞 )
    n = TRYのルートノード
    単語.size.times{|i|
        hlc = 単語コード列の i 番目要素とする（iバイト目）（hlc は0〜255の整数）
        もし、  nの arc の hlc 番目を参照し、辿れるノードが無い（nil）ならば、
            そこに、TRYnode のインスタンスを配置する
        n = 辿り先のノード（nの arc の hlc 番目のノード）とする
    }
    n.data に意味を登録する（元データをdupしたものを登録すること）
  end
end

● 単語辞書
単語辞書のデータは、以下のようにスペースあるいはタブ区切形式のテキストファイルとする。
┌  dictionary1.dic   ┐
│鳥取大学        noun│
│鳥取大砂丘      noun│
│鳥取空港        noun│
│賀露港          noun│
│彼              noun│
│は              p   │
│に              p   │
│行く            verb│
└──────────┘
● トライクラス・その2、辞書の読み込み
辞書ファイルを読み込むメソッド load_dictionary の引数は、辞書ファイル名である。以下の擬似コードのとおり処理をする。

class TRY
  - - - 
  def load_dictionary( filename )
    fp = File::open(filename,'r')
    fpの各行（line）について以下を行う。
      もし、正規表現を使って、line から単語部分と品詞部分を抽出できたならば、
          entry_word で単語と意味を登録する。
  end
end

※ 正規表現は /^([^\s]+)\s+([^\n]+)$/ とすればよい

● トライクラス・その3、辞書の表示
辞書内容を表示するプログラムは以下のとおりである。

class TRY
  - - -
  def show( n = @root, str = "" )
      if n.data != nil
          print str+","+n.data+"\n"
      else
          for i in 0...256 do
             if n.arc[i] != nil
                tmp = str + " "
                tmp[str.size] = i
                show( n.arc[i], tmp )
             end
          end
      end
  end
end

メインルーチンの例：
  dic = TRY.new
  dic.load_dictionary('dictionary1.dic')
  dic.show
辞書ファイルと順序が変っていても、コンマ区切りで同内容であれば正解。
⇒ prac1101.rb

■ トライ構造の使い方
トライ構造を使って文を解析するために、トライ構造を辿り始める場所を指定するルーチン（文解析ルーチンと呼ぶ）と、トライ構造を辿るルーチン（トライ探索ルーチンと呼ぶ）を作る。

●トライ探索ルーチン（最短一致）
トライ探索ルーチンは、トライクラスのメソッド search として実装する。引数は、文 sentence と解析位置 p である。たとえば、sentence = "彼は鳥取大学に行く" のうち「鳥」から解析をするのであれば、p = 4 となる。

class TRY
   - - -
  def search( 文sentence, 位置p )
    トライ構造の注目ノード n を root とする。
    辿った深さのカウンタ d = 0 とする。
    文の位置 p の文字コードを n のアークの配列番号に指定し、アークが nil でない（※1）間以下を行う。
        深さカウンタを 1つ増やす。
        もし、品詞登録がされている（※2）ならば、
            品詞と深さを返す。（成功終了）
        文の位置を1つ進める
    nil と 1 を返す。（失敗終了）
  end
end

※1 sentence[p] で位置pの文字コードが得られる。n.arc[文字コード] != nil でその文字のアークがあるかどうかがわかる。
※2 品詞登録がされているかどうかは、n.data != nil で調べることができる。

メインルーチンの例：
  dic = TRY.new
  dic.load_dictionary('dictionary1.dic')

  hinshi,depth = dic.search("鳥取大学",0)
  print hinshi," ",depth,"\n"
※ もし単語辞書中に「鳥取」があると、
    (root)┬→()─→(noun)┬→()┬→(noun)
          │鳥   取       │大  │学
となる。その場合、上述の最短一致のアルゴリズムでは不具合がある。ただし、今回の演習では、大目に見てよい。（もちろん、できる人は、最長一致のアルゴリズムを実現しても良い）
⇒ prac1102.rb

●文解析ルーチン
文解析ルーチンを関数 parse で実現する。引数は文と辞書である。返り値は、解析結果であり、品詞の配列とする。

def parse( 文, 辞書 )
   ans = 空の配列
   max = 文のサイズ
   p = 文の注目位置、初期値は 0
   p が max より小さい間、以下を行う。
       品詞と深さが、トライ探索の結果得られる。
       もし、品詞が nil ならば、
           ans に "*" を追加する
       そうでなければ、
           ans にその品詞を追加する
       p を深さだけ進める。
  ans を返す
end

メインルーチンの例：
  dic = TRY.new
  dic.load_dictionary('dictionary1.dic')
  print "["+parse("彼は鳥取大学に行く",dic).join(",")+"]\n"
  print "["+parse("彼は鳥取空港に行く",dic).join(",")+"]\n"
  print "["+parse("彼は鳥取に行く",dic).join(",")+"]\n"
⇒ prac1103.rb

■ 宿題
（必須問題）
・prac1103.rb まで完成させること。プログラムリストを印刷し、手書きで各行にコメントを書き、最後の実行結果の載せて、提出せよ。
（自由問題）
  [梅] parse 関数を文字列クラスのメソッドに追加するように改造せよ。
  [竹] 最長一致で単語辞書を検索するプログラムを作れ。
（自由研究）
  256サイズの配列で次ノードを表すことを止め、ハッシュで表わした場合についてプログラムを作り、考察せよ。大量辞書をロードしたときのメモリ効率、動作速度などはどうか？