ストリーム処理のための文字列組合せ論

用于流处理的字符串组合

• 批准号: 16J04105
• 负责人: 中島 祐人
• 金额: $ 0.83万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2016
• 资助国家: 日本
• 起止时间: 2016-04-22 至 2018-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16J04105/
• 关键词: 文字列組合せ論; 反復分解; LZ77分解; Lyndon分解

文字列の組合せ的性質の究明を目標に，文字列の特徴的な分解構造に着目し研究を行った．本研究では，文字列の反復分解，LZ77分解，そしてLyndon分解の3つの分解について以下に説明する二つの主な成果を得ている．一つ目は反復分解についての成果である．文字列の反復分解とは，文字列を反復とよばれる繰り返し構造の列への分解のことをいう．繰り返し構造は，文字列の特徴を捉える指標として最も基本的な構造の一つである．近年，様々な繰り返し構造による分解を考え，それらを計算する効率的なアルゴリズムの研究などの成果が公表されている．一つの文字列における反復分解は一般に複数存在する．本研究成果では，与えられた文字列の反復分解のサイズ（分解の項の数）が最大および最小となる反復分解を効率的に計算するアルゴリズムを提案した．本研究成果は，国際会議PSC 2016 に採択され発表済みである．さらに，反復分解とフィボナッチ文字列とよばれる特徴的な文字列との関係について新たな知見を得ており，公表に向けて準備中である．二つ目の成果では，LZ77分解とLyndon分解のサイズの関係を示した．LZ77分解は，理論，実用の両面から見ても良い圧縮率として知られるLZ77圧縮のもとになっている分解であり，そのような観点から，盛んに研究が行われている．一方で，Lyndon分解は文字列の辞書式順序に基づいた分解であり，近年その応用に関する研究が注目を集めている．LZ77分解は圧縮表現であるのに対し，Lyndon分解は圧縮表現ではないが，どちらの分解も最小文法のサイズの下界になっていることが知られており，文法圧縮分野において重要な指標である．本研究成果は，二つの分解に初めて直接的な関係を与えた結果である．また本研究成果は，国際会議STACS 2017 に採択され発表済みである．

The research on the properties of the combination of text columns and the decomposition structure of the characteristics of text columns are focused on the research of lines. In this study, the repeated decomposition of text string, LZ77 decomposition, Lyndon decomposition and 3 decomposition are described below. The result of repeated decomposition of a single eye. Text column repeatedly decomposes into text column. The most basic structure of a character string is the most basic structure of a character string. In recent years, the research results of structural analysis and calculation of the rate of structural analysis have been published. A character string is repeatedly decomposed into a general plurality. The results of this study are as follows: (1) the maximum and minimum of the repeated decomposition rate of the character string are calculated according to the number of decomposition terms. The results of this research are presented at the International Conference PSC 2016. In this case, it is necessary to repeatedly decompose the character string and the characteristic character string and the relationship between the new knowledge and the public table. LZ77 decomposition and Lyndon decomposition and the relationship between them are shown. LZ77 decomposition and theory are used to study the relationship between LZ77 decomposition and Lyndon decomposition. On the one hand, Lyndon decomposition of character string lexicographical order in the middle of the decomposition, in recent years, the use of relevant research focus on the focus. LZ77 decomposition and compression performance in the middle of the Lyndon decomposition and compression performance, the decomposition of the minimum syntax and the lower bound of the syntax and compression field in the middle of the important indicators. The results of this study are: the direct relationship between the initial decomposition and the results. The results of this research were presented at the international conference STACS 2017.

项目成果

Longest Common Abelian Factors and Large Alphabets

最长公共阿贝尔因子和大字母

• DOI: 10.1007/978-3-319-46049-9_24
• 发表时间: 2016
• 期刊: Lecture Notes in Computer Science
• 作者: Golnaz Badkobeh;Travis Gagie;Szymon Grabowski;Yuto Nakashima;Simon J. Puglisi and Shiho Sugimoto
• 通讯作者: Simon J. Puglisi and Shiho Sugimoto

Lyndon < 2×LZ77 Theorem

林登 < 2×LZ77 定理

• 发表时间: 2017
• 作者: Juha Karkkainen;Dominik Kempa;Yuto Nakashima;Simon J. Puglisi and Arseny M. Shur
• 通讯作者: Simon J. Puglisi and Arseny M. Shur

Minimum Suffix Array の逆問題

最小后缀数组的逆问题

• 发表时间: 2016
• 作者: 中島 祐人;稲永 俊介;坂内 英夫;竹田 正幸
• 通讯作者: 竹田 正幸

Computing Smallest and Largest Repetition Factorizations in O(n log n) time

在 O(n log n) 时间内计算最小和最大重复因式分解

• 发表时间: 2016
• 期刊: Proc. PSC 2016
• 作者: Hiroe Inoue;Yoshiaki Matsuoka;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;and Masayuki Takeda
• 通讯作者: and Masayuki Takeda

Lyndon分解とLZ分解の関係性

Lyndon分解与LZ分解的关系

• 发表时间: 2016
• 作者: Juha Karkkainen;Dominik Kempa;Yuto Nakashima;Simon J. Puglisi and Arseny M. Shur
• 通讯作者: Simon J. Puglisi and Arseny M. Shur