Data Compression Using a Dictionary of Patterns

Abstract. Most modern lossless data compression techniques used today, are based in dictionaries. If some string of data being compressed matches a portion previously seen, then such string is included in the dictionary and its reference is included every time it occurs. A possible generalization of this scheme is to consider not only strings made of consecutive symbols, but more general patterns with gaps between its symbols. In this paper we introduce an off-line method based on this generalization. We address the main problems involved in such approach and provide a good approximation to its solution