拡張ハッシングにおけるディレクトリの圧縮アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
今日,データベースのようにたくさんのキー(情報)からなるファイルを扱う処理の必要性が高くなっている.そのファイルの保守のためには,情報の検索・挿入・削除といった処理を行わなければならない.これらの処理を行うアルゴリズムの一つとして,静的(static)ハッシュ法,動的(dynamic)ハッシュ法が用いられている.静的ハッシュ法は,ハッシュ表やハッシュ関数をあらかじめ定義するので,キー集合の性質(最大個数,構成文字など)が予測できる分野に対して高速な検索が実現できる.しかし,この性質が予知できない分野では,ハッシュ表の大きさによって,記憶領域の無駄の発生や,衝突(あふれ)の頻発による検索効果の低下が起こる.一方,動的ハッシュ法は,キーの性質が予測できない環境においても,ハッシュ関数とファイル構造を局所的に再構成する事によりハッシュ法の高速検索を維持させようとする手法である.本稿では,この動的ハッシュ法の一つであるコンパクト2進木(Compact Binary Trees,CB-Trees)と呼ばれる手法の改良法(以下,本手法と略記する)を述べる.以下,2.でCB-Treeと,そのもととなった2進デジタル検索木(Binary Digital Search Trees,BDS-Trees)について概要を示し,3.で本手法についての解説を行う.4.5.では本手法の評価および,今後の課題について記す.
- 一般社団法人情報処理学会の論文
- 1992-09-28
著者
関連論文
- 各個人のプロファイルを用いたメイル文書のフィルタリング手法
- 分野連想語の出現位置に基づく話題分野の特定手法
- 転置ファイルによる大規模 n-gram データの検索システム
- 転置ファイルによる大規模 n-gram データの検索システム
- 文書レイアウトにおける自動図表配置手法
- ストリングパターンマッチングマシンにおける検索キー追加方法
- LRパーサを用いた文字列置換アルゴリズム
- HTML形式の表構造に対する一索引化手法
- 定型表現を利用した効率的な形態素解析の実現
- 二つのトライを用いた自然言語辞書検索技法
- 知識表現モデルMERMにおける心理現象の一表現法
- ダブル配列による有限状態機械の記憶アルゴリズム
- 分類知識表現を用いたキー検索アルゴリズムの決定法
- 拡張ハッシングにおけるディレクトリの圧縮アルゴリズム