本を読む

読書やコンピュータなどに関するメモ

うろ覚えでKanzenの辞書データ構造をまねてみる

発端

 twitterでつぶやいてみました。

 …じゃなかった、こっちこっち(↓)。

 KanzenはLispマシンのTAO/ELIS上で動く漢字入力システムで、SKKの原型です(実装はまったく別)。とりあえず、うろ覚えで、Emacs Lispを使ってデータ構造を再現してみます(うろおぼえ選手権的な意味で)。

データ構造

 こんな構造にしてみます。

("k"
 (("a"
   (("o" . "顔")
    ("n"
     (("j" "i" . "漢字")
      ("z" "e" "n" . "完全")))))
  ("u" "r" "u" "m" "a" . "車")))
  • 1文字ごとのTRIE構造
  • 文字列はcdr方向に伸びる
    • 各セルのcdrは:
      • 候補が1つなら、その文字
      • 候補が複数なら、候補ごとのTRIE構造のリスト
  • 最後のセルのcdrに変換後の文字列

 実は、実装よりデータ構造を考えるほうが悩みました。

やってみる

 というわけでサンプル実装。これを評価してから、*scratch*で以下のようにやってみます。

(setq r (trie-add nil "kao" "顔"))
(setq r (trie-add r "kanji" "漢字"))
(setq r (trie-add r "kuruma" "車"))
(setq r (trie-add r "kanzen" "完全"))

 これでrに上記のデータ構造が作られました。

作ってみてから

 ふと思い返してみれば、Kanzenの辞書はローマ字じゃなくてカナのTRIEだったような気がしてきました。

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://emasaka.blog65.fc2.com/tb.php/679-a23bc955

 | HOME | 

Categories

Recent Entries

Recent Comments

Recent Trackbacks

Appendix

emasaka

emasaka

フリーター。
連絡先はこのへん

Monthly


FC2Ad