拡張ハッシュ法による検索技法の拡張 : 部分文字列検索と順検索への拡張

概要

論文の詳細を見る
拡張ハッシュ法は動的なキー集合に対して,高速な検索を実現する手法である.拡張ハッシュ法でキーの順検索を可能にするコンパクト2進木法がJongeらにより提案されているが,キーの検索時間が大きい.本稿では,キーの順検索特性を保存して従来の手法を改良することにより,キーの検索時間の改善方法を提案する.本手法を用いることで,検索速度が58倍高速になることが実験結果より確かめられた.また,これまでの提案方法では,与えられた任意の文字列を含むキーの検索(部分文字列検索)を効率的に行うことはできなかった.本稿では,部分文字列検索を効率的に行うため,特徴ベクトルと呼ばれるビット列を用いる方法を提案する.また,通常の拡張ハッシュ法では,複数のバケットを参照する必要が生じる.本稿では更に,その参照数の抑制のためにディスクリプタを利用してキーの処理時間の改善方法も提案する.本手法の有効性を確認するため実験を行った結果,通常の拡張ハッシュ法に比べ,40倍以上高速に検索できることがわかった.また,検索キーの長さが長くなるほど,高速に検索できることが確認できた.
一般社団法人情報処理学会の論文
1994-10-13