B木に基づく類名表記機能ファイルシステムの構成法
スポンサーリンク
概要
- 論文の詳細を見る
データベースシステムからキーを用いてデータを探索する場合,入力キー,あるいは,データベース中のキーが誤っていて,一致するキーがないときでも,類似したキーを列挙したり,最も類似したキーを検索できることが望ましい.本論文では,入力キーに類似したキーを列挙できる,あるいは最も類似したキーを探索できるファイルの構成法,および,操作法について述べる.基本的アイデアは,B木のもつキーの検索・挿入・削除の効率の良さと,類名表記を用いた階層ファイルのもつ類似したキーを探索する能力を融合した点である.そのため,B木では行えない類似したキーの探索や,類名表記を用いた階層ファイルでは考慮されていないキーの挿入・削除を行うことができる.文字はa〜m,n〜zの2類に分け,長さ6〜10の英単語16,561語を用いて実験を行った.キーの検索・挿入・削除の間に行われる2次記憶からの読込み回数は約3回,挿入・削除の間に行われる2次記憶への書込み回数は約1回であった.類似したキーの探索は,正しいキーを探索するときに比べ,約7.3〜8.5倍の読込みが必要である,検索率は一つの誤り(置換・挿入・脱落)に対して約85〜99%であった.また,記憶利用率は約70%になった.
- 社団法人電子情報通信学会の論文
- 1994-12-25
著者
関連論文
- 根がなく巡回的順序がある木の間の距離とその計算法
- 木の距離の並列計算法
- ハッシュ法を用いた類似キー検索ファイル (メディア統合および環境統合のための高機能データベースシステム、および一般)
- 一般化LR法に基づく文脈自由言語の誤り訂正アルゴリズム
- 根がなく順序がない木の距離とその計算法
- 大型データベースのための最長共通部分列の一高速抽出法
- 大型データペースのための最長共通部分列の一高速抽出法
- 木構造図の描写アルゴリズムの効率化
- 空間に埋め込まれた木のグラフ理論的距離とその計算法
- 空間に埋め込まれた木の距離とその計算法
- 構成文字ハッシュ法に基づく綴り誤りの高速訂正法
- 根がなく巡回的順序のある木の距離の逐次および並列計算法
- 類似データ検索のためのファイル構成法
- 線図形の類似度の計算法
- B木に基づく類名表記機能ファイルシステムの構成法
- 平面に埋め込まれた木の最大類似部分を求めるアルゴリズム
- 誤ったキーでも検索できるファイル構成法