Fast parameterized pattern matching algorithms based on data compression

基于数据压缩的快速参数化模式匹配算法

• 批准号: 23700022
• 负责人: INENAGA Shunsuke
• 金额: $ 2.66万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23700022/
• 关键词: アルゴリズム; 文字列処理; データ圧縮; 文字列情報処理; データ構造

A sequence of characters or symbols is called a string. Many digital data can be regarded as a string. In order to process and utilize large-scale data, we proposed efficient string processing algorithms that are both fast and memory efficient. In particular, we developed efficient algorithms that work on strings given as straight-line programs (SLPs). We achieved fast and memory efficient solutions by an approach called compressed string processing, where given compressed data is not explicitly decompressed. The results of our work have been published in internal journals/proceedings, and presented in international/domestic conferences.

字符或符号的序列称为字符串。许多数字数据可以被视为一个字符串。为了处理和利用大规模的数据，我们提出了高效的字符串处理算法，该算法既快速又节省内存。特别是，我们开发了高效的算法，可以处理以直线程序(SLP)形式给出的字符串。我们通过一种称为压缩字符串处理的方法实现了快速和内存高效的解决方案，其中给定的压缩数据不会显式解压缩。我们的工作成果已发表在内部期刊/论文集上，并在国际/国内会议上发表。

项目成果

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

Shortest Unique Substrings Queries in Optimal Time

最优时间最短唯一子串查询

• DOI: 10.1007/978-3-319-04298-5_44
• 发表时间: 2014
• 期刊: Proc. the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), Lecture Notes in Computer Science
• 作者: Kazuya Tsuruta;Shunsuke Inenaga;Hideo Bannai;and Masayuki Takeda
• 通讯作者: and Masayuki Takeda

Permuted Pattern Matching on Multi-track Strings

多轨字符串上的排列模式匹配

• DOI: 10.1007/978-3-642-35843-2_25
• 发表时间: 2013
• 期刊: Proc. SOFSEM 2013
• 作者: Yagi T;Ito D;Okada Y;Akamatsu W;Nihei Y;Yoshizaki T;Yamanaka S;Ok ano H;Suzuki N;Takashi Katsura
• 通讯作者: Takashi Katsura

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