拡張ハッシュ法における部分文字列検索の設計と実現

概要

論文の詳細を見る
ハッシュ関数とファイル構造を局所的に再構成し,あふれを解消する拡張ハッシュ法は,ハッシュ法の検索の高速性を維持し,キー総数が予想できない分野にも応用できるが,任意の文字列を部分文字列として含むキーの検索を効率的に行うことはできない.本論文では,拡張ハッシュ法でこの部分文字列検索を実現するために,まず,特徴ベクトルと呼ばれるビット列をハッシュ値として用いて,トライを構成する.次に,アクセスすべきバケットを決定するための疑似ベクトルを定義し,トライ上で疑似ベクトルに対応した枝のみを走査する限定深さ優先探索法を提案する.さらに,キー数の増加に対応したトライをコンパクトに構成するために,均整ベクトルを導入し,そのベクトルを増進的に生成する手法を提案する.これにより,キーの取扱いに必要なビット数をおさえつつ,限定深さ優先探索法をより効率的に行うことができる.また,探索後に参照されるバケット数を抑制するためにディスクリプタを利用する.本手法は,約10万語の日本語キー集合と約8万語の英語キー集合に対する実験結果より,ディスクリプタだけを利用した拡張ハッシュ法に比べ,読み込みバケット数が60〜90%減少し,検索時間が2〜10倍高速となることが分かった.
一般社団法人情報処理学会の論文
1997-02-15

拡張ハッシュ法における部分文字列検索の設計と実現

スポンサーリンク

概要

著者

関連論文

スポンサーリンク