Compression and decompression of XML and other structured documents uses parameterized templates. A region of a serialized document is nominated as a template, information units are annotated as fixed or parameter values, and the template is recorded with a template identifier. A template invocation represents the nominated records. Nominated regions can be nested, and they do not necessarily correspond to XML elements or other well-formed portions of the original document. Templates may be defined on the fly, after compression has started.