| 大会名称 |
|---|
| 2010年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2010 |
| 発行日 |
| 2010/8/20 |
| セッション番号 |
| 5A |
| セッション名 |
| アルゴリズム・コンピュテーション(2) |
| 講演日 |
| 2010/09/08 |
| 講演場所(会議室等) |
| A会場（総合学習プラザ1F 第5講義室） |
| 講演番号 |
| A-023 |
| タイトル |
| 接尾辞木に対する二分木化と簡潔データ構造による圧縮 |
| 著者名 |
| 馬場 雅大, 小野 廣隆, 定兼 邦彦, 山下 雅史, |
| キーワード |
| 接尾辞木, 簡潔データ構造, 二分木 |
| 抄録 |
|
接尾辞木はテキストに対する文字列検索や極大対の発見など多くの機能を備えたデータ構造である。一方で接尾辞木はデータ構造の大きさがネックになっており、サイズの圧縮が求められている。 圧縮接尾辞木(CST)は圧縮接尾辞配列(CSA)に木構造や木の枝長に関連する情報を加えたものである。このときCSAに付加するデータ構造のサイズは、テキストの長さをnとしたとき、最大で6n+o(n)ビットである。 本稿では接尾辞の二分木化により圧縮する方法を示す。この方法でCSAに付加するデータ構造のサイズは4n+o(n)ビットであり、また単純な文字列検索の場合などは既存手法と同じ計算量で行うことができる。 |
| 本文pdf |
| PDF download (186.4KB) |