Tx
いつもプログラム作りっぱなしだったので、解説とマニュアルを書いてみました。Tx。省スペースなtrieです
とりあえず出すところまで行きたかったので最低限の実装と解説しか書いていませんが、これから少しずつ書き足していきます。
結局、これを使って今何ができるかというと、キー集合があったら、それらに(入力順ではないが)固有の番号を0から順に付けられて、Txを使って、キーの番号を引くことができる(もしないなら、NOTFOUNDが返ってくる)。
大体入力キーのトータルの長さの半分ぐらいのスペースでできます。
アプリケーションを作る場合は各キーに付随するデータをvectorとかにキーの数だけいれておいて、それらをTxを使って参照、操作することになります。その例も作らないと
loud (level-order unary tree)とよばれる木のsuccinct な表現を使ったアプリケーションを作ってみたかったことからやってみたのですが、double arrayなみに高速化できれば用途もでてくるかなぁと。今はselect操作を適当にさぼっているので遅いと思うのですが、きちんと実装すればキャッシュも効いてきて速くなるかな。
The comments to this entry are closed.
Comments