Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」

大規模な文字列データの文字検索/カウントを効率的に行う

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2006/01/26 12:00

ダウンロード ソースコード (6.8 KB)
ダウンロード バイナリファイル (51.6 KB)

本記事では大規模なデータを扱うためのデータ構造であるwavelet tree(WT)を紹介します。WTは文字列が与えられた時、文字cのi番目の出現位置や、文字cの位置pまでの出現回数を定数時間で答えるデータ構造です。作業領域量は元テキストの約2倍です。WTはsucBVの延長上にあるデータ構造であり、WTを用いることで圧縮索引やsuccinct data structureなどを実装できます。

目次
※印刷用ページ表示機能はメンバーのみが利用可能です(登録無料)。
  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5