An Efficient Algorithm of Retrieving Example Sentences from Huge Text Data Bases

IPSJ Web Site 24 References

Bibliographic Information

Other Title
  • 大規模文書データに対する用例文の効率的検索アルゴリズム
  • ダイキボ ブンショ データ ニ タイスル ヨウ レイブン ノ コウリツテキ ケ
  • 文書データベース

Search this article

Description

大量の用例文データから複数の索引要求に共通する用例文を検索する手法は，実例に基づく機械翻訳，文書管理システムにおいて必要不可欠な技法となってきている．しかしながら，これまでの用例文検索の研究は類似のとらえ方の議論が主であり，検索と絞り込みアルゴリズムは，従来からある文番号を直接比較する方法を適用するにとどまっているので，大規模データベースに対する実用的検索技法は十分に議論されていないのが現状である．索引が指定する復数の文番号を文番号列とするとき，本論文では，多くの索引要求があり，しかも索引に対する文番号列が非常に長くなる場合でも，目的とする用例文を高速に絞り込めるアルゴリズムを提案する．本手法では，全用例文に対する文番号をビット位置に対応させた文番号ベクトルを構成し，このベクトルを多段階に圧縮して，検索と絞り込みを高速化する．本手法により，共通文番号の絞り込みは，複数の索引に対する必要な部分ベクトルのみを一括して論理演算するだけとなり，同時に大量の文番号列を補助記憶から転送する必要もなくなり，高速化が実現できる．本手法の有効性を確認するため，約45万件の用例文に対する索引数（10?100）の絞り込み実験を行った．その結果，従来法より約3?24倍高速になり，さらに約1億文のデータベースを想定したシミュレーションでは，6?88倍高速になることが分かった．

Storing and retrieving an useful example sentence efficiently is an important task in docu-ment management systems because text retrieval is the most time-consuming part of them.Inverted filing is well-known approach,but there are some problems when storing a huge number of sentences.It arises when the intersection is computed for large postings indexed by terms,or keywords.Moreover,disk access for postings also takes a lot of time in this situation.This paper presents a technique for the storing of multi-stages of postings and retrieving them partly in order to compute efficiently the intersection between postings for the requested terms.From the simulation results,it is shown that the algorithm presented is 3 to 88 times faster than the traditional approach.

Journal

References(24)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top