Linear-time off-line text compression by longest-first substitution

Abstract. Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text com-pression techniques of this type. Each compression scheme is categorized as being either off-line or on-line, according to how a text is processed. One representative tactics for off-line compression is to substitute the longest repeated factors of a text with a production rule. In this paper, we present an algorithm that compresses a text basing on this longest-first principle, in linear time. The algorithm employs a suitable index structure for a text, and involves technically efficient operations on the structure.