パトリシアトライを用いた効果的な全文検索法に関する研究

効率的な全文検索エンジンを構成するためには,よりコンパクトで,かつ,高速な検索が可能な索引部分を用いることが鍵となる.そこで,本研究ではパトリシアトライ構造により索引部を構成し,パトリシアトライの高速な検索機能は保持しつつ,そのデータ構造を圧縮する手法の考案を目的としていた.そこで,本研究では上記の目的を実現するため,本研究の実施計画として,まず1年目にはパトリシアトライの基本圧縮アルゴリズムの考案,2年目には圧縮型のパトリシア構造から形成される索引部を有する全文検索エンジンを構築し,大規模文書データベースに対する実験評価を予定していた.まず,1年目の研究実績として,パトリシアトライをPaCB-treeと呼ばれるコンパクトなビット列に圧縮する手法を考案した.通常の2進木トライの圧縮方法であるCB-treeと比較すると,PaCB-treeの方が従来のCB-treeよりも40〜60%圧縮率を向上できた.また,パトリシアトライの代表的な圧縮型データ構造であるPAT arrayと比較すると,コンパクト性ではPAT arrayの方が有利であるが,検索効率の面でディスクアクセス数が多くなるというPAT arrayの欠点を解消し,パトリシアトライが本来持つ検索効率を保持したまま圧縮が行えた.次に,2年目の研究実績としては,1年目で考案したPaCB-treeから形成される索引部を有する全文検索エンジンを構築した.従来のパトリシアトライ型の検索エンジンと比較した結果,同じサイズの索引部を用いた場合でも,本手法の検索エンジンの方が数多くの検索対象文書を索引部に格納することができ,実用的に優れていることを明らかにした.以上,本研究により,パトリシアトライの圧縮率を向上することができ,より実用性に富んだパトリシアトライ型の全文検索エンジンを実現できた.今後,本研究成果を曖昧検索や類似検索が行える全文検索に応用する計画である.

効率的な全文検索エンジンを構成するためには,よりコンパクトで,かつ,高速な検索が可能な索引部分を用いることが鍵となる.そこで,本研究ではパトリシアトライ構造により索引部を構成し,パトリシアトライの高速な検索機能は保持しつつ,そのデータ構造を圧縮する手法の考案を目的としていた.そこで,本研究では上記の目的を実現するため,本研究の実施計画として,まず1年目にはパトリシアトライの基本圧縮アルゴリズムの考案,2年目には圧縮型のパトリシア構造から形成される索引部を有する全文検索エンジンを構築し,大規模文書データベースに対する実験評価を予定していた.まず,1年目の研究実績として,パトリシアトライをPaCB-treeと呼ばれるコンパクトなビット列に圧縮する手法を考案した.通常の2進木トライの圧縮方法であるCB-treeと比較すると,PaCB-treeの方が従来のCB-treeよりも40〜60%圧縮率を向上できた.また,パトリシアトライの代表的な圧縮型データ構造であるPAT arrayと比較すると,コンパクト性ではPAT arrayの方が有利であるが,検索効率の面でディスクアクセス数が多くなるというPAT arrayの欠点を解消し,パトリシアトライが本来持つ検索効率を保持したまま圧縮が行えた.次に,2年目の研究実績としては,1年目で考案したPaCB-treeから形成される索引部を有する全文検索エンジンを構築した.従来のパトリシアトライ型の検索エンジンと比較した結果,同じサイズの索引部を用いた場合でも,本手法の検索エンジンの方が数多くの検索対象文書を索引部に格納することができ,実用的に優れていることを明らかにした.以上,本研究により,パトリシアトライの圧縮率を向上することができ,より実用性に富んだパトリシアトライ型の全文検索エンジンを実現できた.今後,本研究成果を曖昧検索や類似検索が行える全文検索に応用する計画である.