拡張ハッシュ法による効率的な辞書検索法に関する研究

本研究は,拡張ハッシュ法の索引部を成す2進木構造の効率的な圧縮手法の考案を目的としていた.従来の手法は,2進木構造を先行順走査に従ってコンパクトなビット列(先行順ビット列と呼ぶ)に圧縮するものであるが,大規模なキ-集合に対しては先行順ビット列が非常に長くなり,ビット列の後方に位置するキ-に対する各種処理の時間効率が悪化する,そこで,本研究では上記の問題点を解決するため,本研究の実施計画として,1.2進探索木の最適な分割手法の考案,2.分割深さと各種処理時間との比較および検討,の2点を計画していた.まず,1に関しては,2進木構造を一定の深さ(分割深さ)毎に分割し,分割された各木構造をポインターで連結することにより,木構造を階層的に管理する手法を考案した.このように,2進木構造を階層化すれば,処理すべきビット数を分割深さに対応した一定の値に抑制できる.また,検索キ-,即ちハッシュ値の1ビット分が2進木構造の一つの深さと対応しているため,2進木構造と同様に検索キ-も容易に分割・管理できる.次に,2に関しては,各種キ-集合に対する具体的実験結果から,分割深さが10前後が最も適していることが明らかになった.これは,次の2点からも明白である.まず,検索処理に関しては,分割深さが大きくなると走査する必要のないノード数が増加するため,検索時間は指数関数的に増加する.一方,更新処理に関しては,分割深さが小さ過ぎると木構造の分割が頻繁に起こるため,更新時間が増加し,逆に,分割深さが大き過ぎるとバスケット分割の際に単位木を挿入するコストが悪影響を及ぼす.本研究により,先行順ビット列の時間効率の改善が実現できた.しかしながら,空間効率にはまだ改善の余地があるため,今後は,よりコンパクトなビット列に圧縮する手法を考案する計画である.

本研究は,拡張ハッシュ法の索引部を成す2進木構造の効率的な圧縮手法の考案を目的としていた.従来の手法は,2進木構造を先行順走査に従ってコンパクトなビット列(先行順ビット列と呼ぶ)に圧縮するものであるが,大規模なキ-集合に対しては先行順ビット列が非常に長くなり,ビット列の後方に位置するキ-に対する各種処理の時間効率が悪化する,そこで,本研究では上記の問題点を解決するため,本研究の実施計画として,1.2進探索木の最適な分割手法の考案,2.分割深さと各種処理時間との比較および検討,の2点を計画していた.まず,1に関しては,2進木構造を一定の深さ(分割深さ)毎に分割し,分割された各木構造をポインターで連結することにより,木構造を階層的に管理する手法を考案した.このように,2進木構造を階層化すれば,処理すべきビット数を分割深さに対応した一定の値に抑制できる.また,検索キ-,即ちハッシュ値の1ビット分が2進木構造の一つの深さと対応しているため,2進木構造と同様に検索キ-も容易に分割・管理できる.次に,2に関しては,各種キ-集合に対する具体的実験結果から,分割深さが10前後が最も適していることが明らかになった.これは,次の2点からも明白である.まず,検索処理に関しては,分割深さが大きくなると走査する必要のないノード数が増加するため,検索時間は指数関数的に増加する.一方,更新処理に関しては,分割深さが小さ過ぎると木構造の分割が頻繁に起こるため,更新時間が増加し,逆に,分割深さが大き過ぎるとバスケット分割の際に単位木を挿入するコストが悪影響を及ぼす.本研究により,先行順ビット列の時間効率の改善が実現できた.しかしながら,空間効率にはまだ改善の余地があるため,今後は,よりコンパクトなビット列に圧縮する手法を考案する計画である.