パターン照合に基づく情報検索・発見支援システムの開発

基于模式匹配的信息搜索与发现支持系统开发

• 批准号: 02J09184
• 负责人: 平尾 昌啓
• 金额: $ 1.28万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-02J09184/
• 关键词: パターン照合; 情報検索; 発見支援; 圧縮

本研究の目的は,インターネット上に氾濫するWEBファイル,研究者によって蓄積された実験データ等の電子化されたデータから,そこに内在するパターンを効率よく発見するためのアルゴリズムの開発を行い,それを実装して計算機実験を行うことを目的としている.ここで対称とするパターンの表現として,どのようなものを採用するかは,パターンの表現力とそれを探すアルゴリズムの実行時間のトレードオフになる重要な問題である.本年度は,可変長代入を許したワイルドカードを持つパターン(以後VLDCパターンと呼ぶ)に特に着目した.VLDCパターンは,これまでに行ってきた部分文字列パターンや部分列パターンの一般化であり,バイオインフォマティクスの分野でも自然に用いられているモチーフの表現に近い.まず,VLDCパターンの照合を高速化する必要があるので,そのためのデータ構造について,領域計算量と構築アルゴリズムについての考察を行った.その結果,部分文字列パターンや部分列パターンのように領域計算量を線形にすることはできないが,照合に関してはこれまでと同様にパターン長の線形時間で照合が行えることがわかった.また,パターン発見アルゴリズムに関しても,これまでのパターン発見アルゴリズムを拡張することによって,探索時間をそれほど増大させずに最適なパターンを発見できることがわかった.今後,このアルゴリズムを実装してそのパフォーマンスを評価していく予定である.

The purpose of this study is to develop a computer system that can be used to store data. The performance of the company is important to the company's performance and the company's ability to perform. This year, we can change the length of the text column to maintain the text column (later VLDC). In addition,VLDC's illumination and high speed are necessary to investigate the field calculation and construction of VLDC. As a result, part of the text column, part of the column. The search time is increased and the best search time is increased. From now on, the number of cases will be determined.

项目成果

M.Hirao, H.Hoshino, A.Shinohara, M.Takeda, S.Arikawa: "A practical algorithm to find the best subsequences patterns"Theoretical Computer Science. 292,2. 465-479 (2003)

M.Hirao、H.Hoshino、A.Shinohara、M.Takeda、S.Arikawa：“寻找最佳子序列模式的实用算法”理论计算机科学。