## 1 Introduction  
The problem of _Compressed Pattern Matching_, introduced by [PERSON] and [PERSON] [1], is of performing pattern matching directly in a compressed text without any decompressing. More formally, for a given text \(T\), pattern \(P\) and complementing encoding and decoding functions \(\mathcal{E}\) and \(\mathcal{D}\), respectively, our aim is to search for \(\mathcal{E}(P)\) in \(\mathcal{E}(T)\), rather than the usual approach which searches for the pattern \(P\) in the decompressed text \(\mathcal{D}(\mathcal{E}(T))\). This paper is an extended version of [2]. Most research efforts in compressed matching were invested in what could be called \"classical\" texts. These are texts written generally in some natural language, and which have been compressed by one of a variety of known compression techniques, such as Huffman coding [3] or various variants of the Lempeland Ziv (LZ) methods, including LZW [4; 5; 6], gzip, DoubleSpace and many others [7; 8; 9]. Note, however, that these methods are of general purpose and not restricted to the compression of natural language texts only. We suggest to extend the problem to the search of patterns in the compressed form of _structured files_. The idea is that the raw texts form only a (sometimes, small) part of what needs to be stored in an Information Retrieval system to allow also efficient access to the data. Since the search on large scale systems is not performed by a linear scan, auxiliary files are adjoined, which are generally built in a preprocessing stage, but then permit very fast access during the production stage. These files include dictionaries, concordances, thesauri, bitmaps, signature files, grammatical files and many others, and their combined sizes are of the order of magnitude of the text they are based on. Obviously, these auxiliary files create a storage problem on their own, and thus are kept in compressed form. However, due to their special internal structure, which is known in advance, custom tailored compression techniques may be more effective than general purpose compressors. Compression of structured data has been suggested in the past, though not in the context of compressed matching. For example, database compression techniques require the ability to retrieve arbitrary records even when compression is used. [PERSON] and [PERSON] [10] explore the compression of large statistical databases and propose techniques for organizing the compressed data so that standard database operations such as retrievals, inserts, deletes and modifications are supported. Another example is compressing XML files, as suggested in [PERSON] and [PERSON] [11], by separating the document structure from its data. Various XML compression methods exist, such as the offline compressor XMill[12], so called container-based compression, that is, the data is partitioned into containers depending on the element names, and the containers are then compressed using Gzip. The structure is encoded as a sequence of numeric tokens that represent both the XML markup (start-tags, end-tags, _etc._) and the references to data containers. XMill achieves better compression than Gzip and runs at about the same speed. Another known online compressor is XMLPPM [13], based on a modification of the PPM2 compression scheme. It compresses better than XMill, but runs considerably slower, in part because of the use of arithmetic coding. XGrind[14] is another XML compressor which makes it possible to query compressed data by using Huffman coding. XMLZip[15] breaks the structural tree of the document at a specified depth, and compresses the resulting components using traditional dictionary compression techniques. A further example of structured files compression is _table compression_, _i.e._, collections of fixed length records (unlike databases that might contain intermixed fixed and variable length fields).