パトリシアトライを用いた効果的な全文検索法に関する研究

基于Patricia Try的有效全文检索方法研究

• 批准号: 09780387
• 负责人: 獅々堀 正幹
• 金额: $ 1.34万
• 依托单位: The University of Tokushima
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09780387/
• 关键词: 全文検索; パトリシアトライ; Pa-CB-tree; 2進木構造; 情報検索; CB-tree

効率的な全文検索エンジンを構成するためには,よりコンパクトで,かつ,高速な検索が可能な索引部分を用いることが鍵となる.そこで,本研究ではパトリシアトライ構造により索引部を構成し,パトリシアトライの高速な検索機能は保持しつつ,そのデータ構造を圧縮する手法の考案を目的としていた.そこで,本研究では上記の目的を実現するため,本研究の実施計画として,まず1年目にはパトリシアトライの基本圧縮アルゴリズムの考案,2年目には圧縮型のパトリシア構造から形成される索引部を有する全文検索エンジンを構築し,大規模文書データベースに対する実験評価を予定していた.まず,1年目の研究実績として,パトリシアトライをPaCB-treeと呼ばれるコンパクトなビット列に圧縮する手法を考案した.通常の2進木トライの圧縮方法であるCB-treeと比較すると,PaCB-treeの方が従来のCB-treeよりも40〜60%圧縮率を向上できた.また,パトリシアトライの代表的な圧縮型データ構造であるPAT arrayと比較すると,コンパクト性ではPAT arrayの方が有利であるが,検索効率の面でディスクアクセス数が多くなるというPAT arrayの欠点を解消し,パトリシアトライが本来持つ検索効率を保持したまま圧縮が行えた.次に,2年目の研究実績としては,1年目で考案したPaCB-treeから形成される索引部を有する全文検索エンジンを構築した.従来のパトリシアトライ型の検索エンジンと比較した結果,同じサイズの索引部を用いた場合でも,本手法の検索エンジンの方が数多くの検索対象文書を索引部に格納することができ,実用的に優れていることを明らかにした.以上,本研究により,パトリシアトライの圧縮率を向上することができ,より実用性に富んだパトリシアトライ型の全文検索エンジンを実現できた.今後,本研究成果を曖昧検索や類似検索が行える全文検索に応用する計画である.

The full text search of efficiency is composed of two parts, namely, three parts, namely, two parts, namely, three parts, namely, three parts, four parts In this study, the index part of the structure is composed, and the high-speed search function of the structure is maintained. The purpose of this study is to achieve the above goals. The implementation plan of this study is to examine the basic compression of compression in the first year, to construct the index part of compression in the second year, and to evaluate the large-scale document in the second year. The results of this study over the past year have been reviewed in detail. Usually, the CB-tree compression ratio of 40 ~ 60% is higher than the CB-tree compression ratio of 40 ~ 60%. The PAT array is advantageous in comparison with the PAT array structure, which is representative of the compression type. The PAT array has a large number of defects in the search efficiency, and the original search efficiency is maintained. In the second half of this year, the research achievements of the first half of this year were compared with those of the second half of this year, and the results of the first half of this year were compared with those of the third half of this year. In the case where the index part of the search object is used, the search object of the method has a plurality of search objects, and the index part of the search object is used. Above, this study aims to explore the possibility of increasing the compression ratio of the product and realizing the full text search of the product. In the future, the results of this study will be discussed in detail.

项目成果

Masami Shishibori: "An Efficient Compression Method for the Patricia Trie" Proceedings of 1997 IEEE International Conference on Systems,Man and Cybernetics. Florida U.S.A.415-420 (1997)

Masami Shishibori：“Patricia Trie 的高效压缩方法”1997 年 IEEE 国际系统、人与控制论会议论文集。

Masami Shishibori: "Design of a Compact Data Structure for the Patricia Trie" IEICE Transactions on Information and Systems. (発表予定).

Masami Shishibori：“Patricia Trie 的紧凑数据结构的设计”IEICE Transactions on Information and Systems（即将出版）。

Masami Shishibori: "Robust Human-Computer Interface Systems Using the Generalized LR Raring" Proc.of the 2nd IEEE International Conference on Intelligent Processing Systems. Sydney,Australia. 62-66 (1998)

Masami Shishibori：“使用广义 LR Raring 的鲁棒人机接口系统”，第二届 IEEE 智能处理系统国际会议论文集。

Masami Shishibori: "The Design of a Compact Data Structure for Binary tries" Proceedings of the 17th International Conference on Computer Processing of Oriental Languages. Kowloon Hong Kong. 606-611 (1997)

Masami Shishibori：“二进制尝试的紧凑数据结构的设计”第 17 届东方语言计算机处理国际会议论文集。

Masami Shishibori: "Two Improved Access Methods on Compact Binary(CB) trees" International Journal of Information Processing & Management. (発売予定).

Masami Shishibori：“紧凑二叉树（CB）的两种改进的访问方法”国际信息处理与管理杂志（待发布）。