誤ったキーでも検索できる情報検索システム

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文は,誤りを持つキーでも検索できる階層的ファイルの構成法について述べている.B-木あるいはそれを改良した階層的ファイルはよく知られているが,これらは正しく記憶されたデータを正しいキーで速く検索するものである.データが大量になると,データが誤って紀憶されることも避けられないし,検索者も常に正しいキーを使うとは限らない.このような事態にいかに対処するかはまだ手探りの状態であるが,最近,HL法が提案されている.本論文では,文字類の誤り傾向に基づいて文字をいくつかの類に分割し,その類名を用いてデータを分類し,階層的ファイルを作る.文字類が1つしかできないときは,適当に文字類を作る.このときは,他の類の文字に誤る(置換誤り)ことが起こりうる(類外置換).ファイルの大部分あるいはすべてを補助記憶に記憶する.キーがファイルにあるかどうかを調べる.キーがファイルにないとき,レーベンシュタイン距離の意味で最も近いキーを探す.3つの方法を提案し,長さ4〜8の1.66万語(辞書A)と10.4万語(辞書B)の上で,実験し,辞書Aの上で,HL法と比較した.キーの誤りは,類外置換,挿入,脱落は高々1つとし,実験では類外置換を含めて,誤り数は高々2としている.(a)すべての場合について,辞書の第1段を主記憶に置いた場合の方が,すべてを補助記憶に置いた場合より検索時間は短い.また,辞書Bの場合でも誤りのあるキーでの検索時間はそれほど低下しなかった。(b)誤りのないキーの検索時間は,HL法に比べて820〜1800倍速く,誤りのあるキーでは,70〜520倍速い.(c)挿入1,脱落1,脱落1+類内置換1の場合は,HL法が検索率がよく,他の5つの場合は本論文の検索率が高い.HL法はすべての場合について誤検索率が高い.

• 1989-11-15

著者

• 田中 栄一

  宇都宮大学工学部情報工学科

• 沼倉 覚

  宇都宮大学大学院工学研究科情報工学専攻

• 青木 晴海

  富士重工(株)

• 矢野目 毅

  シャープ(株)

• 矢吹 勉

  富士通(株)

• 田中 栄一

  宇都宮大学工学部

• 田中 栄一

  宇都宮大学

関連論文

• 誤ったキーでも検索できる情報検索システム
• 階層的ファイルを用いた中国語単語の検索法
• 誤りのある音素記号列訂正のための計算手数の軽減法
• グラフの部分整合アルゴリズム
• 機械処理のための中国語併音の調査
• 構文的パタン認識法は能率が悪い

スポンサーリンク