Factorizing Strings into Combinatorial Objects
志穂 杉本 · Kyushu University Institutional Repository (QIR) (Kyushu University) · 2017
String factorization is a task of factorizing a string into a sequence of non-empty strings under given constraints.The size of factorization is defined to be the number of factors in it.For example, the Lyndon factorization has the constraints that each factor is a Lyndon word and the factors are arranged in the lexicographically non-increasing order.On the other hand, the Lempel-Ziv 77 (LZ77) factorization, the core of LZ77 compression, is a smallest-sized factorization such that each factor has a previous occurrence.It is known that the sizes of the Lyndon factorization and the LZ77 factorization of a string w are lower bounds on the size of grammar that generates w in the grammar-based compression.