圧縮文字列上の高速パターン列挙に関する基盤技術開発

压缩字符串高速模式枚举基础技术开发

• 批准号: 12J06417
• 负责人: 井 智弘
• 金额: $ 1.28万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12J06417/
• 关键词: 圧縮文字列処理; 文字列中の規則性発見; 文字列パターン列挙

本年度は, 本研究テーマの一つの集大成として, 圧縮された文字列データから規則性をもった部分文字列を高速に計算・列挙する手法を開発した. 繰り返し構造や回文構造といった文字列の規則性の発見は文字列処理の基礎であり, また, ゲノムデータの解析などに応用出来る. 圧縮文字列処理では展開文字列長に比例する計算資源を用いないことを目標としており, そのため圧縮文字列を全て展開せずに処理しなければいけないという難しさがあるが, 解の列挙においてはさらに出力の仕方も問題になる. 単純に出力すると出力サイズに比例する時間を避ける事ができず, 今回の出力である繰り返し構造や回文構造の数は展開文字列長に比例するためである. 本手法では, 圧縮された文字列を展開する事無く処理を行い, かつ, 出力の圧縮表現を計算することでこの問題を回避した. これにより, ゲノムデータなどの大規模文字列データも, それが良く圧縮されているならば省領域かつ高速に規則性を発見することが出来る. この結果は38th International Symposium on Mathematical Foundations of Computer Science (MFCS2013)に採択され発表を行った.また, 圧縮された文字列上の組み合わせ的性質を探る研究として圧縮文字列とLyndon文字列との関連性を探った. Lyndon文字列およびそれを基にしたLyndon分解は代数学と深く関連しており古くから知られているが, 近年はアルゴリズムへの応用も注目されている. 申請者らは24th Annual Symposium on Combinatorial Pattern Matching (CPM2013)と20th Symposium on String Processing and Information Retrieval (SPIRE 2013)において圧縮文字列からLyndon分解を効率的に求めるアルゴリズムを開発した. その過程において, Lyndon分解の項数が文法圧縮サイズの下界になっているという興味深い知見を得ている.

In this year's study, the results of this study are as follows: in this year, the whole process of this study has been completed, and some of the text columns of high-speed calculation have been successfully implemented. Please read the palindromes to make the text column standard. See the text column. Please read the text column. The text column will be expanded, the text column will be expanded, the calculation of resources will be completed, and the full text column will be opened, so as to solve the problem of how to contribute to the government. The company has made an effort to reduce the number of palindromes. This time, we have made an effort to create the number of palindromes and expand the length of the text column. In this method, the text list is displayed, and you can make an effort to show that you are calculating how to solve problems. In order to improve the performance of the large-scale model text, we need to know how to improve the performance of the large-scale model text. The results show that 38th International Symposium on Mathematical Foundations of Computer Science (MFCS2013) does not show any changes in the table. A study of the properties of a combination of Lyndon text columns. The Lyndon text column is based on Lyndon decomposition, algebra, deep knowledge, knowledge and knowledge. In recent years, people have paid attention to it. The applicant uses 24th Annual Symposium on Combinatorial Pattern Matching (CPM2013) 20th Symposium on String Processing and Information Retrieval (SPIRE 2013) to determine the Lyndon decomposition rate of the text column. In the course of the process, Lyndon decomposes the number of items, grammar, grammar, and the lower bound. You have a lot of knowledge.

项目成果

Computing Convolution on Grammar-Compressed Text

• DOI: 10.1109/dcc.2013.53
• 发表时间: 2013-03
• 期刊: 2013 Data Compression Conference
• 作者: Toshiya Tanaka;I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda

Compressed automata for dictionary matching

用于字典匹配的压缩自动机

• DOI: 10.1016/j.tcs.2015.01.019
• 发表时间: 2015
• 期刊: Theor. Comput. Sci.
• 作者: Tomohiro I;Takaaki Nishimoto;Shunsuke Inenaga ;Hideo Bannai; Masayuki Takeda
• 通讯作者: Masayuki Takeda

General Algorithms for Mining Closed Flexible Patterns under Various Equivalence Relations

• DOI: 10.1007/978-3-642-33486-3_28
• 发表时间: 2012-09
• 作者: I. Tomohiro;Yuki Enokuma;H. Bannai;M. Takeda

Faster Lyndon factorization algorithms for SLP and LZ78 compressed text

• DOI: 10.1016/j.tcs.2016.03.005
• 发表时间: 2016-12
• 期刊: Theor. Comput. Sci.
• 作者: I. Tomohiro;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda

Computing Reversed Lempel-Ziv Factorization Online

在线计算逆 Lempel-Ziv 分解

• 发表时间: 2013
• 期刊: Proc. The Prague Stringology Conference 2013 (PSC 2013)
• 作者: Shiho Sugimoto;Tomohiro I;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
• 通讯作者: Masayuki Takeda