A picture is a two-dimensional counterpart of a string and it is represented by a rectangular array of symbols over a finite alphabet Σ. A set X of pictures over Σ is a code if every picture over Σ is tilable in at most one way with pictures in X. Recently, the definition of strong prefix code was introduced as a decidable family of picture codes, and a construction procedure for maximal strong prefix (MSP) codes was proposed. Unfortunately, the notion of completeness cannot be directly transposed from strings to pictures without loosing important properties. We generalize to pictures a special property satisfied by complete set of strings that allow to prove interesting characterization results for MSP codes. Moreover, we show an encoding algorithm for pictures using pictures from a MSP code. The algorithm is based on a new data structure for the representation of MSP codes.
Encoding pictures with maximal codes of pictures
Madonia, Maria
2018-01-01
Abstract
A picture is a two-dimensional counterpart of a string and it is represented by a rectangular array of symbols over a finite alphabet Σ. A set X of pictures over Σ is a code if every picture over Σ is tilable in at most one way with pictures in X. Recently, the definition of strong prefix code was introduced as a decidable family of picture codes, and a construction procedure for maximal strong prefix (MSP) codes was proposed. Unfortunately, the notion of completeness cannot be directly transposed from strings to pictures without loosing important properties. We generalize to pictures a special property satisfied by complete set of strings that allow to prove interesting characterization results for MSP codes. Moreover, we show an encoding algorithm for pictures using pictures from a MSP code. The algorithm is based on a new data structure for the representation of MSP codes.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.