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

情報処理学会 Web Site 被引用文献2件 参考文献18件

書誌事項

タイトル別名
  • カクチョウ ハッシュホウ ニ オケル ブブン モジレツ ケンサク ノ セッケイ
  • The Design and Implementation of a Substring Search in Extendible Hashing
  • テキスト処理

この論文をさがす

抄録

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

An extendible hashing scheme resolves bucket overflows by reorganizing the hash function and file structure locally, so it is very suitable for fast key retrievals of dynamic key sets. How-ever, it can't search keys that contain a given string as substrings efficiently. In this paper, in order to design this substring search in extendible hashing, signature vectors are introduced as hash values, and a trie structure as an extendible hash table, where each vector is composed by a bit stream. Pseudo signature vectors are defined to identify the buckets, and a con-strained depth-first search is presented to traverse the arcs of the trie structure. To construct a compact trie despite of an increase in the number of keys, uniform signature vectors are introduced, and the method for an incremental expansion of the hash table is proposed. This approach can restrict the size of the bit stream for each key, making constrained depth-first search efficient. From simulation results by applying the presented schemes to Japanese and English key sets, it was shown that the number of accessed buckets decreased from 60 to 90%in comparison with the traditional extendible hashing for which only descriptors were used. In addition, the searching time cost of the presented approach is 2 to 10 times faster.

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (18)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ