ダウンロード ソースコード (6.8 KB)
ダウンロード バイナリファイル (51.6 KB)
本記事では大規模なデータを扱うためのデータ構造であるwavelet tree（WT）を紹介します。WTは文字列が与えられた時、文字cのi番目の出現位置や、文字cの位置pまでの出現回数を定数時間で答えるデータ構造です。作業領域量は元テキストの約2倍です。WTはsucBVの延長上にあるデータ構造であり、WTを用いることで圧縮索引やsuccinct data structureなどを実装できます。
※印刷用ページ表示機能はメンバーのみが利用可能です（登録無料）。
この記事は参考になりましたか？
- この記事の著者
-
岡野原 大輔（オカノハラ ダイスケ）
データ圧縮やデータ構造、またそれらの応用としての自然言語処理、機械学習に興味があります。http://hillbig.cocolog-nifty.com/(blog)
※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
