アルゴリズム・サイエンスシリーズ 数理技法編 8 簡潔データ構造

本書は、計算機でプログラムを作成する際に必要なデータ構造の一種である、「簡潔データ構造」についての教科書です。簡潔データ構造は、データを圧縮したまま検索等の処理ができるようなデータ構造であり、大量のデータを効率良く処理する際に有益なものです。従来の圧縮手法では、データを圧縮したまま扱うことができません。データを使用する際にはまず復元する必要があり、圧縮前と同じ量の計算機のメモリが必要になってしまいます。一方、簡潔データ構造では必要な部分のみを復元することで、圧縮したままの処理が可能になっています。また、データが大量の場合、高速に検索するための「索引」と呼ばれるデータ構造を付加することがありますが、通常のデータ構造ではそのサイズが大きく、元のデータよりも大きくなることがあるため、索引の圧縮も必要となります。簡潔データ構造ではこの索引の圧縮もできます。
 
本書では、代表的な簡潔データ構造について、その構造と理論的な結果について説明しています。同じ機能を持つデータ構造については、最初に提案されたものではなく、後に提案された、より洗練されていて理解しやすいものを紹介するようにしています。その際、定理の厳密な証明も入れています。プログラムを書くだけならば証明は理解しなくても良いのですが、その場合は既に存在するライブラリを使うだけになり、自分の行いたい操作がサポートされていない場合には処理を行えません。その場合は自分で新しいデータ構造を作る必要がありますが、そのためには定理の証明を理解することが必要となります。興味を持たれた方はぜひ自分で新しい簡潔データ構造を開発してみてください。

簡潔データ構造の歴史としては、まず1989年にビットベクトルおよび木構造やグラフ構造が提案され、その後2000年に文字列検索のデータ構造が提案されてからは多くの研究が行われています。特に、8章のBW変換と4章のウェーブレット木は、それぞれ2000年、2003年に提案されたものですが、これらは最も重要な簡潔データ構造と言ってもよく、広く使われています。特に、DNA配列の検索では簡潔データ構造を利用したものが主流となっています。本書では、まず3章で最も基本的なビットベクトルの簡潔データ構造を説明し、次にそれを用いた様々な簡潔データ構造を説明します。データ構造間の依存関係も分かるように書いてあります。本書により、簡潔データ構造を俯瞰的にとらえることができると思います。
 

(紹介文執筆者: 情報理工学系研究科 教授 定兼 邦彦 / 2021)