情報検索のためのコンパクトなデータ構造とその動的更新に関する研究

信息检索的紧凑数据结构及其动态更新研究

• 批准号: 15700002
• 负责人: 定兼 邦彦
• 金额: $ 1.28万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15700002/
• 关键词: 接尾辞配列; 圧縮接尾辞配列; 文字列検索; 文字列圧縮; 省スペース; 文書データベース; データ圧縮; 情報検索; アルゴリズム

大量データ処理のための領域効率のよいアルゴリズムとデータ構造の開発を行った.まず,文字列の高速検索を行うデータ構造として,すでに圧縮接尾辞配列が提案されているが,それを構築する省メモリなアルゴリズムを開発した.このアルゴリズムは定数サイズアルファベット上の文字列に関しては時間・領域ともに最適であり,定数サイズではない場合にも従来手法より高速である.具体的には,アルファベットサイズをΣ,文字列長をnとしたとき,O(n log Σ)領域,O(n log n)時間である.また,このアルゴリズムよりも時間はかかるが,圧縮率の高い文字列についてはさらに省スペースなアルゴリズムも考案した.計算量は,O(n log n)時間である(HOは文字列の次数0のエントロピー).次に,複数の文字列の検索が可能なデータ構造を提案した.これは文字列の挿入・削除を高速に実行でき,検索も高速である.また,文字列だけでなく,一般の数列を表現するデータ構造についても考察した.このデータ構造は,数字の更新(増加),数列の和,検索を効率よく行え,必要な領域はほぼ最適である.さらに,圧縮接尾辞配列のデータ構造として二次記憶での実装や分散環境に適したものを提案した.これにより,より大量のデータに対する検索を高速に行えるようになった.

A large number of data processing and domain efficiency of the development of data structure. The text column is constructed by a high speed search engine. The text column is constructed by a compression engine. The text on the text column is related to the time and field. The optimum time and field are related to the time and field. The optimum time and field are related to the speed and speed of the text. Specific, O(n log Σ) field,O (n log n) time. In addition, the number of times when the file is closed is reduced, and the number of times when the file is closed is reduced. Calculation quantity,O(n log n) time (HO). Second, the search for multiple character strings is possible with the proposed structure. The text line is inserted, removed, and the speed is high. The text column is divided into two parts, and the general sequence is divided into two parts. The structure of this problem, the update of the number (increase), the sum of the series, the search efficiency, the necessary field, the optimal field. In addition, the data structure of compressed tail word arrangement and secondary memory are suitable for distributed environment. A large number of high-speed vehicles are required.

项目成果

Breaking a time-and-space barrier in constructing full-text indices

• DOI: 10.1109/sfcs.2003.1238199
• 发表时间: 2003-10
• 期刊: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
• 作者: W. Hon;K. Sadakane;W. Sung

Compressed Index for Dynamic Text

动态文本的压缩索引

• 发表时间: 2004
• 期刊: Data Compression Conference, IEEE Computer Society
• 作者: W.K.Hon;T.W.Lam;Kunihiko Sadakane;W.K Sung;S.M Yiu
• 通讯作者: S.M Yiu

W.K.Hon, T.W.Lam, K.Sadakane, W.K.Sung: "Constructing Compressed Suffix Arrays with Large Alphabets"Proceedings of International Symposium on Algorithms and Computation(ISAAC). Vol.14. 240-249 (2003)

W.K.Hon、T.W.Lam、K.Sadakane、W.K.Sung：“Constructing compressed Suffix Arrays with Large Alphabets”国际算法与计算研讨会（ISAAC）论文集。

韓 永楷, 定兼 邦彦, 宋 永健: "全文索引構築のための省スペースなアルゴリズム"情報科学技術レターズ. Vol.2, No.LD-002. 67-68 (2003)

韩永凯、贞兼邦彦、宋永健：“构建全文索引的节省空间算法”，《信息科学与技术快报》，第 2 卷，No.LD-002 (2003)。

Constructing Compressed Suffix Arrays with Large Alphabets

• DOI: 10.1007/978-3-540-24587-2_26
• 发表时间: 2003-12
• 作者: W. Hon;T. Lam;K. Sadakane;W. Sung