2進ディジタル探索木を用いた辞書検索法とその応用に関する研究

本論文は，キー検索技法の中で特に2進ディジタル探索木(BinaryDigital Search
Tree : BDS木と呼ぶ)を用いた辞書検索法に関する研究の成果をまとめたものであ
り，次の6章より構成される.
まず，第l章では，緒論として，本研究の目的ならびにその工学上の意義を述べ
ることで，本研究の意義および位置づけを明確にする.更に，本研究によって得ら
れた諸成果を概説する.
次に，第2章では，キー検索技法の歴史的背景を述べると共に，各種キー検索技
法の中でも，特に2分探索木法，多分探索木法，ハッシュ法，トライ法についての
構成法を紹介し，各技法の特徴および問題点について解説する.
そして，第3章では，本研究の基となるBDS木を用いたトライハッシュ法の構成
法を説明する. トライハッシュ法は，ハッシュ法の特徴である高速な検索能力を継
承しつつ，従来のハッシュ法では困難であった順検索を可能にする手法である. し
かしながら，登録キー数が多くなると，ハッシュ法の索引部を形成するBDS木のサ
イズが大きくなり， BDS木全体を主記憶上に格納できなくなる.この問題点を解決
するため，JongeらはBDS木を先行順ビット列と呼ばれるコンパクトなビット列に圧
縮する手法を提案した.そこで，本章ではJongeらの提案した圧縮手法について解説
した後，先行順ビット列上でのキーの検索・追加アルゴリズムを示す.
第4章では，第3章で紹介した先行順ビット列の時間的および空間的な問題点を
明確にした後，先行順ビット列により表現されたBDS木の時間効率および空間効率
を改善する手法をそれぞれ提案する.まずキー集合が大規模になると，先行順ビ
ット列が非常に長くなり，その結果，ビット列の後方に位置するキーに対する処理
の時間効率が悪化する.この時間的な問題点に対して，本論文では，BDS木の構造
を階層的に分割管理し，不必要な部分木に対する処理を削減することにより，大規
模なキー集合に対しても時間効率の悪化を防ぐ手法を提案する.また，先行順ビッ
ト列上でキーの検索・追加を実現するためには，BDS木のすべてのノードが2本の
枝を有する必要がある.従来の手法では，1本の枝しか持たないノードに対してダ
ミーリーフと呼ばれる擬似的な葉を持たせていた. しかしながら，大規模なキー集
合に対しては，ダミーリーフ数が非常に多くなり，その結果，ビット列が非常に長
くなる. この空間的な問題点に対して，本論文では，ダミーリーフを用いずに，よ
りコンパクトなビット列に圧縮する手法を提案する.更に，それぞれの提案手法の
理論的評価，及び実験による具体的評価を与え，本手法の有効性を確かめる.
また，第5章では，第4章で提案した2進ディジタル探索木を用いた辞書検索法
の文書処理への応用として，2進ディジタル探索木で構成された片仮名辞書と片仮
名変換ルールを用いた効率的な片仮名異表記生成手法および2進木構造で構築さ
れた文書構造データベースを用いた自動図表配置手法について述べる.
最後に，第6章では，本研究で得られた諸成果の統括を行い，今後の研究課題に
ついて述べる.

画像データは国立国会図書館から提供(2011/9/26。JPEG2000形式を本学でpdfに変換して公開)