Data Compression on Multisets. Submultiset-Free Codes

Regular data compression converts a sequence of symbols into a sequence of strings (descriptions), assigning the shortest descriptions to the most frequent symbols produced by the data source. By contrast, here we consider the compression of a sequence of symbols to a sequence of multisets. This is relevant if the communication channel does not preserve order (positioning) of the transmitted letters, as is the case in many biological contexts; for example, if you regard the passage of a multiset of molecules through a blood vessel as an information transfer. We introduce the concept of submultiset-free codes, a counterpart to the existing concept of prefix-free codes. We derive a theorem about the structure of optimal submultiset codes for uniform random variables and we describe an algorithm for constructing them.