転置ファイルとビット配列を用いた高速文字列あいまい照合アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, 文字ベースの転置ファイルとビット配列を用いた高速文字列あいまい照合アルゴリズムを提案し, 実験によってその有効性を示す. 文字列あいまい照合の代表的アルゴリズムに, WuとManberのアルゴリズム(以下「Bit-Arrayアルゴリズム」)がある. これは, 照合状況を示すビット配列に単純なシフト演算と論理演算を逐次的に施すことで, 長さnのテキストと長さmの検索文字列に対するk回以内の挿入/削除/置換を許した文字列あいまい照合を, ワード長がmビット以上の計算機においてO(nk)の計算量で実行できるという優れた特長を持つ. しかし, 照合のためにテキストの全文字を参照する必要があり, そのままで大量テキストのあいまい検索に適した方法とはいえない. これに対して本稿では, Bit-Arrayアルゴリズムの考え方を, 大量の固定的テキストの検索に有効な文字ベースの転置ファイルと組み合わせた, 「スキップ型Bit-Arrayアルゴリズム(SBAアルゴリズム)」を提案する. SBAアルゴリズムは転置ファイルを参照することで, 検索文字列の構成文字以外のテキスト位置でのビット配列計算をスキップする. 照合処理の計算量はO(kmn/|Σ|)であるが(|Σ|は文字セット規模), |Σ|に比べてmが十分小さければBit-Arrayアルゴリズムよりも高速な検索速度が得られる. 1000万文字の日本語テキストに対する検索実験(2≤m≤10, k≤m)では, 従来のBit-Arrayアルゴリズムと比べて, 照合処理時間が約1728〜約1/178に短縮され, SBAアルゴリズムの優位性を確認できた.
- 一般社団法人情報処理学会の論文
- 1999-04-15
著者
関連論文
- Web文書集合からの意見情報抽出と着眼点に基づく要約生成(Webマイニング)(テーマ:「Webマイニングによる情報活動と自然言語処理」その他一般)
- Web文書集合からの意見情報抽出と着眼点に基づく要約生成(Webマイニング)(テーマ:「Webマイニングによる情報活用と自然言語処理」その他一般)
- 意見抽出を目的とした機械学習による属性-評価値対同定(属性抽出)
- 仮説生成と検証の効率的組合せに基づく手書き文字列読み取り向け知識処理方式
- 転置ファイルとビット配列を用いた高速文字列あいまい照合アルゴリズム
- 認識知識処理 (認識と制御技術 特集)
- ボトムアップ/トップダウン処理を融合した手書き文字列読み取り知識処理
- 手書き文字列読み取りのための単語列探索アルゴリズム : 文字タグ法
- 手書き文字列読み取りのための単語連鎖制約に基づく効率的探索と棄却
- 効率的探索とトップダウン的検証を組み合わせた手書き住所読み取り知識処理
- 文字タグ法による手書き住所読み取りの評価
- A-4 テキストからの類義語抽出手法とその評価(概念と言語(I))
- 手書き文字列読み取りのための単語列探索アルゴリズム : 文字タグ法
- 手書き住所読取りのための町名検索アルゴリズム : 文字タグ法
- 手書き住所読取りにおけるパタン処理と連携した住所知識処理方式
- 共起類似性に基づく同義語の抽出
- D-2 Support Vector Machineを用いた地域情報ページの自動分類(Webコンテンツ処理,D.データベース)
- モバイルサーチエンジンWithAirの試作と評価
- モバイルサーチエンジンWithAirの試作と評価
- 情報検索システム評価用ベンチマークVer.1.0(BMIR-J1)について (メディア統合および環境統合のための高機能データベースシステム、および一般)
- 日本語情報検索システムのためのベンチマークの構築
- 意見抽出のための評価表現の収集
- インターネットからの評判情報検索(WWW上の情報の知的アクセスのためのテキスト処理)
- テキストマイニングによる評価現象の収集
- D-1 意見分析システムにおける意見抽出方式の検討と評価(Webコンテンツ処理,D.データベース)
- インターネットからの評判情報検索
- インターネットからの評判情報検索
- 文章解析アクセラレータ(2) : 接続検定マシンMONCの試作と評価
- 形態素抽出マシンMEX-IIの試作と評価
- 形態素抽出マシンMEX-IIの概要
- ア***ロセッサによる文脈自由言語の並列認識アルゴリズム
- 文章解析アクセラレータ(1) : 形態素抽出マシンの試作
- 多重照合型形態素抽出方式に関する検討
- 文字列検索LSIを用いた国語辞書システムの構築法
- 文構造を有する日本語テキストエディタJESS
- 日本語文章作成支援システムCOMET
- 辞書およびパターンマッチルールの増強と品質強化に基づく日本語固有表現抽出
- 予測ペン入力インタフェースとその手書き操作削減効果
- 大語彙かな漢字変換 : 未登録語と区切り誤りの減少
- 招待講演:新世代検索ポータル技術 (2001年情報学シンポジウム講演論文集--21世紀の情報化社会・ネットビジネスを支える情報学/情報技術) -- (セッション5:情報技術の視点から)
- WWWサーチエンジン (特集 情報検索)
- Webサーチエンジンの基本技術と最新動向（上）基本技術
- Webサーチエンジンの基本技術と最新動向（下）最新技術
- WWW情報検索技術と評価の問題(情報検索システムの力くらべ : テストコレクションによる評価)
- 農業情報の検索・ナビゲーション (特集 情報化がもたらす新しい農業・農村)
- 専用ハードウェアを用いた形態素解析器の開発
- 検索エンジンの仕組みと技術の発展(インターネット検索エンジン)
- モバイルユーザ向け情報選別配信技術
- 目的および個人に特化したサーチエンジンの開発 (「Webシステムにおける情報獲得支援技術」)
- 大語彙辞書を用いたかな漢字変換についての考察