There is provided a method of interactive compression using multiple compression state information entries. The method comprises receiving a request for data from a communicating party; retrieving the data; identifying, for use in compressing the data, at least two compression state information entries shared between the parties to the communication; compressing the data with each of the at least two compression state information entries; determining, from the set of compression state information entries, a preferred compression state information entry that provides a greatest compression ratio; and transmitting the data, compressed in accordance with the preferred compression state information entry to the communicating party.