« 日テレ月曜 7 時の困窮 | トップページ | 交通安全教育の方向性 »

2008年11月21日 (金)

Yash 2 その 77

行編集機能、キー入力を受け取る処理の設計。

入力は一バイトづつ受け取った後、それが特殊なキー (割込みキー、カーソルキー、F1 キー等) を表す文字列かどうかを調べる。特殊なキーは対応する規定のワイド文字列に変換する。そうでないものはそのままワイド文字列に変換する。ワイド文字列に変換したら、それがカーソル移動等に割り当てたキー操作かどうかを調べる。何も割当たっていなければ行内に入力する。

ここで問題となるのはこれらの文字列が特殊なキーやキー操作を表す文字列になっているかどうかを調べるマッチング処理である。これは登録済みの多数の文字列の中から一致するものを探し出す処理になるが、入力された文字列全体がちょうど一致するとは限らないので、文字列の先頭から一文字づつ一致する可能性のある候補を絞ってゆくことになる。

このような処理にはハッシュ表よりもトライ (trie) が向いている。しかし単純にトライの各ノードに文字列の値をインデックスとする配列を持たせると、一ノード当たり 256 × sizeof(struct X*) バイトものメモリを食ってしまうため、ノードの構造を工夫する必要があると感じている。また、各ノードのデータサイズがバラバラの場合、多くのノードを配列上に一気に確保することが難しくなる点も考慮しなければならない。各ノードを個別に malloc するということは、メモリアクセスの空間的局所性が薄れるということを意味する。

|

« 日テレ月曜 7 時の困窮 | トップページ | 交通安全教育の方向性 »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/169172/43185149

この記事へのトラックバック一覧です: Yash 2 その 77:

« 日テレ月曜 7 時の困窮 | トップページ | 交通安全教育の方向性 »