sileのブログsileのブログ読者になるsileのブログこの広告は、90日以上更新していないブログに表示しています。algorithm前回に作成したLOUDS(LOUDS++)を用いたtrieの改良を試みる。できるであろう)箇所は結構沢山ある。(二分探索、その他を場合に応じて使い分けてはどうか)上位nノードまでのselect1/rank1の結果はメモ化しておいても良いのでは?などなど。実用の場面で使えるものを作ろうとするなら、こういった(云わば実装の細部に関する)改良も必要だと思う。今回は、このような実装の細部に関わる修正は置いておいて、trieの構造自体の変更を試してみようと思う。(とはいってもそう大したことをするわけでもないが)TAIL配列では、実際にはどうするかというと、TAIL配列*1を使う。大雑把に云えば、trieの各キーで共有がある先頭部分の文字列は普通にノードとして保持し、残りの各キーにユニークな末尾部分の最初の一文字以外は(そのためのノードを設けるのではなく)TAILという配列にまとめて入れてしまおう、といったような方法。キーセットに対応する木構造。TAIL配列を用いた場合。下にあるのがTAIL配列さらにTAIL配列の中で包含する文字列をまとめた場合。上の図に比べてTAIL配列が若干短くなっている図を見てもらえば分かると通り、TAIL配列使ってキーのユニークな末尾部分を管理するようにすると、trieのノード数を減らすことが可能となる(上の例では20個から9個に減っている)。その分はTAIL配列に移動しているので、実質的な総数は変わらないが、(前回のLOUDSによるtrie実装では)ノード一つ当たりには最大14bit*2の領域が必要なのに対し、TAIL配列では(要素は単なるchar型なので)一文字当たり8bit、と大きければ半分近く節約出きることになる。最後の図にあるようにTAIL配列中で包含関係にある末尾文字列同士をまとめることで、さらに使用領域を削ることができる。加えて、TAIL配列を使用すれば、前回のtrieでキー検索時にユニークな末尾部分を辿る際にも呼び出していた(ある意味無駄な)select1/rank1を省くことも可能となる(strcmp関数の一回の呼び出しに置換可能)。select1/rank1呼び出しのコストが低くはないことを考えると、これは結構重要なことのように思える。TAIL配列の概要と、そのメリット(と思われること)は大体以上。デメリット一応思いつくデメリットも書いておく。TAIL配列内の各末尾文字列を区切るためにヌル文字を使用する必要がある各キーごとに8bit余計に必要になる。末尾文字列を包含する他の文字列がある場合は不要TAIL配列内の文字列の開始位置を示すインデックスが必要インデックスのサイズを4byteとすれば、キー数*4byteの領域が必ず必要となるユニークな末尾部分が僅かにしかないようなキーセットの場合は、サイズ的/処理的なオーバヘッドの方が大きくなる(多分)trie構築が若干面倒かつ非効率になる上のような理由から、キー数が少ない場合やユニークな末尾文字列が僅かにしかないキーセットの場合は、TAIL配列を使用するオーバーヘッドの大きくなる可能性もあると思う。LOUDSが重宝するような大量のキーを扱うケースでは、これらのデメリットよりもTAIL配列を使うことで節約可能な領域およびselect1/rank1呼び出しによるメリットの方が大きいように思うが、その辺りは全然調査していないので現時点では'思う'としか云えない。残りは、TAIL配列を用いたtrieの実装。大半の部分は前回と同じ。変更がないソースファイルは割愛することにする。TAIL配列用のID。0;}TAIL配列の圧縮(包含関係にある末尾文字列の併合)を行っているクラスの定義。これは、Doarで使用しているものをほぼそのまま持ってきている。&tind;};#endif次は読み込み/検索部分。TAIL配列};#endifメイン関数。include文とクラス名が変わるくらい。データは前回作成したものを用いる。検索は少し速くなっているuser0m0.476ssys0m0.000s以上。IPA辞書のようなキーセット)では、TAIL配列の有無でそれほど結果が変わることはなかった。データ数を増やしての比較はまた今度。6最新記事RustでMD5ハッシュを計算するRustとSBCLでのDAWG構築性能の比較メモEmacsのファイル保存時に自動的にrustfmtが適用されるようにする現在時刻をUNIXタイムスタンプ形式で取得するloglevelとseverityの使い分けメモ注目記事ブクログqiitasileのtips人気エントリーはてなブログをはじめよう!sileさんは、はてなブログを使っています。ブログを報告する引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。