Text Compression and Compressed String Mining
啓介 後藤, Keisuke Goto · Institutional Repositories DataBase (IRDB) · 2013
Due to the rapid advance in computer technology and global growth of computer networks, we can utilize a large amount of machine-readable data today.Most of such data can be seen as sequences of characters, or strings, and the demand for mining valuable information from them is increasing.To mine valuable information from them, efficient string mining algorithms applicable to large-scale string data are needed.In this thesis, we develop fast and space efficient string mining algorithms for enormous string data, using text compression as a core technology.We focus on compressed string processing, which is an approach that directly processes compressed data without explicit decompression.We present simple and efficient algorithms for calculating all frequencies of q-grams that occur in a string T represented in compressed form, namely, as a straight line program (SLP).Our algorithm runs in O(qn) time and space, where n is the size of the SLP.Computational experiments show that our algorithm and its variation are practical for small q, actually running faster on various real string data, compared to algorithms that work on the uncompressed text.We also discuss applications in data mining and classification of string data, for which our algorithms can be useful.We then improve the algorithm so that it can handle larger q.We propose an O(min{qn, Ndup(q, T )}) algorithm improving on our previous O(qn) algorithm when q = Ω(N/n), where N is the length of T and dup(q, T ) is a quantity that represents the amount of redundancy that the SLP captures with respect to q-grams in T .The algorithm is asymptotically always at least as fast and better in many cases compared to working on the uncompressed strings.We further consider the extended problem which computes non-overlapping occurrence frequency of all q-grams.The non-overlapping occurrence frequency of a string P in a string T is defined as the maximum number of non-overlapping occurrences of P in T .We present the first algorithm for calculating the non-overlapping occurrence frequency of all q-grams, that works for any q ≥ 2, and runs in O(q 2 n) time and O(qn) space.Since the runtime of compressed string processing algorithms depends on the size of an input SLP, it is important to develop algorithms to compute, from a given text, an SLP of small size that derives it.It is known that the computation of the smallest sized grammar of a string is NP-hard, and therefore several approximation algorithms have been proposed.Rytter proi I would like to thank everyone who supported me in my research and life at Kyushu University.First, I would express my appreciation to my supervisor, Professor Masayuki Takeda.He kindly directed me and taught many things to me, how to research, how to think, and so on.I will never forget