完備辞書とはなにか
完備辞書というものがある。 詳細な解説は他のサイト や 書籍 を参照してほしいが、簡単にいうとビット列に対する操作が高速、 かつ省メモリに行えるデータ構造である。
ビット列の操作が速いと何が嬉しいのかというと、それを元にした様々なデータ構造があるからだ。 例えばLOUDSといって、 木構造をノード数×2ビットで表現できるデータ構造がある。 これに完備辞書を使うことで、 メモリ使用量を大きく抑えつつ木に対する様々な操作が定数時間でできたりする。 自分はそういう小さいのが大好きなので、まずは完備辞書を書いてみることにした。
O(log N) の select
日本語の範囲で調べてみると$\mathrm{select}$の実装は$\mathrm{O}(\log N)$のものしか見つからなかった。 とりあえず$\mathrm{rank}$は実装してみたが、やはり$\mathrm{select}$も$\mathrm{O}(1)$にしてみたい。 そこでよく参考文献として取り上げられている 高速文字列解析の世界 という本を読んでみたが、やはりそこにも$\mathrm{select}$が$\mathrm{O}(1)$になる方法は書いていなかった。
そこで、元論文にあたってみることにした。 少し探すとオリジナルらしき論文を見つけることができたので、 それを印刷して読んでみることにした。 英語論文をしっかり読んだことはあまりなかったのだが、意外とすんなり読むことができた。 論文の大まかなフォーマットを知っていて話の流れを予測できたからか、論文が優しく書かれていたか、 もしくはその両方だろう。
メンタルの問題
しかしそろそろ自分の知りたかった情報にたどり着くといったところで、 いろいろと生活に変化があってしばらく作業を中断してしまった。 落ち着いた頃には、すっかり気力が抜けてしまっていた。
最近こういうことが続いている。 ある程度以上に大きなものを作ろうとすると、 その途中で気分の上下が激しくなってきて中途半端なところで放棄してしまう。 そういう状態はよく認識していて、それでは良くないともおもっていたため、 とりあえず完備辞書を最後まで完成させることにした。 論文は最後まで読み終わっていないため、$\mathrm{select}$の時間計算量は$\mathrm{O}(\log N)$である。
kotet/fully-indexable-dictionary
そういうわけで最近とても落ち込んでいる。 今年の夏休みはいろんなものを作って、 このブログもその作ったものたちについての記事で充実するはずだった。 自己評価がとても低い。 自分はもうなにも作り出せない気さえする。
思うに、自分はハードルを高く設定しすぎているのではないか。 もう少し地道にやっていくようにしたほうがいいかもしれない。 もうひとつには、気分が変わらないうちに手早く作ってしまうという方法がある。 実装速度は競技プログラミングでもすれば上がるだろうか?