Sardinas–Patterson algorithm

In coding theory, the Sardinas–Patterson algorithm is a classical algorithm for determining in polynomial time whether a given variable-length code is uniquely decodable, named after August Albert Sardinas and George W. Patterson, who published it in 1953.[1] The algorithm carries out a systematic search for a string which admits two different decompositions into codewords. As Knuth reports, the algorithm was rediscovered about ten years later in 1963 by Floyd, despite the fact that it was at the time already well known in coding theory.[2]

Idea of the algorithm

Consider the code { a ↦ 1 , b ↦ 011 , c ↦ 01110 , d ↦ 1110 , e ↦ 10011 } {\displaystyle \{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011\,\}} . This code, which is based on an example by Berstel,[3] is an example of a code which is not uniquely decodable, since the string

011101110011

can be interpreted as the sequence of codewords

01110 – 1110 – 011,

but also as the sequence of codewords

011 – 1 – 011 – 10011.

Two possible decodings of this encoded string are thus given by cdb and babe.

In general, a codeword can be found by the following idea: In the first round, we choose two codewords x 1 {\displaystyle x_{1}} and y 1 {\displaystyle y_{1}} such that x 1 {\displaystyle x_{1}} is a prefix of y 1 {\displaystyle y_{1}} , that is, x 1 w = y 1 {\displaystyle x_{1}w=y_{1}} for some "dangling suffix" w {\displaystyle w} . If one tries first x 1 = 011 {\displaystyle x_{1}=011} and y 1 = 01110 {\displaystyle y_{1}=01110} , the dangling suffix is w = 10 {\displaystyle w=10} . If we manage to find two sequences x 2 , … , x p {\displaystyle x_{2},\ldots ,x_{p}} and y 2 , … , y q {\displaystyle y_{2},\ldots ,y_{q}} of codewords such that x 2 ⋯ x p = w y 2 ⋯ y q {\displaystyle x_{2}\cdots x_{p}=wy_{2}\cdots y_{q}} , then we are finished: For then the string x = x 1 x 2 ⋯ x p {\displaystyle x=x_{1}x_{2}\cdots x_{p}} can alternatively be decomposed as y 1 y 2 ⋯ y q {\displaystyle y_{1}y_{2}\cdots y_{q}} , and we have found the desired string having at least two different decompositions into codewords.

In the second round, we try out two different approaches: the first trial is to look for a codeword that has w as prefix. Then we obtain a new dangling suffix w', with which we can continue our search. If we eventually encounter a dangling suffix that is itself a codeword (or the empty word), then the search will terminate, as we know there exists a string with two decompositions. The second trial is to seek for a codeword that is itself a prefix of w. In our example, we have w = 10 {\displaystyle w=10} , and the sequence 1 is a codeword. We can thus also continue with w'=0 as the new dangling suffix.

Precise description of the algorithm

The algorithm is described most conveniently using quotients of formal languages. In general, for two sets of strings D and N, the (left) quotient N − 1 D {\displaystyle N^{-1}D} is defined as the residual words obtained from D by removing some prefix in N. Formally, N − 1 D = { y ∣ x y ∈ D   and   x ∈ N } {\displaystyle N^{-1}D=\{\,y\mid xy\in D~{\textrm {and}}~x\in N\,\}} . Now let C {\displaystyle C} denote the (finite) set of codewords in the given code.

The algorithm proceeds in rounds, where we maintain in each round not only one dangling suffix as described above, but the (finite) set of all potential dangling suffixes. Starting with round i = 1 {\displaystyle i=1} , the set of potential dangling suffixes will be denoted by S i {\displaystyle S_{i}} . The sets S i {\displaystyle S_{i}} are defined inductively as follows:

S 1 = C − 1 C ∖ { ε } {\displaystyle S_{1}=C^{-1}C\setminus \{\varepsilon \}} . Here, the symbol ε {\displaystyle \varepsilon } denotes the empty word.

S i + 1 = C − 1 S i ∪ S i − 1 C {\displaystyle S_{i+1}=C^{-1}S_{i}\cup S_{i}^{-1}C} , for all i ≥ 1 {\displaystyle i\geq 1} .

The algorithm computes the sets S i {\displaystyle S_{i}} in increasing order of i {\displaystyle i} . As soon as one of the S i {\displaystyle S_{i}} contains a word from C or the empty word, then the algorithm terminates and answers that the given code is not uniquely decodable. Otherwise, once a set S i {\displaystyle S_{i}} equals a previously encountered set S j {\displaystyle S_{j}} with j < i {\displaystyle j<i} , then the algorithm would enter in principle an endless loop. Instead of continuing endlessly, it answers that the given code is uniquely decodable.

Termination and correctness of the algorithm

Since all sets S i {\displaystyle S_{i}} are sets of suffixes of a finite set of codewords, there are only finitely many different candidates for S i {\displaystyle S_{i}} . Since visiting one of the sets for the second time will cause the algorithm to stop, the algorithm cannot continue endlessly and thus must always terminate. More precisely, the total number of dangling suffixes that the algorithm considers is at most equal to the total of the lengths of the codewords in the input, so the algorithm runs in polynomial time as a function of this input length. By using a suffix tree to speed the comparison between each dangling suffix and the codewords, the time for the algorithm can be bounded by O(nk), where n is the total length of the codewords and k is the number of codewords.[4] The algorithm can be implemented using a pattern matching machine. [5] The algorithm can also be implemented to run on a nondeterministic Turing machine that uses only logarithmic space; the problem of testing unique decipherability is NL-complete, so this space bound is optimal.[6]

A proof that the algorithm is correct, i.e. that it always gives the correct answer, is found in the textbooks by Salomaa[7] and by Berstel et al.[8]

See also

  • Kraft's inequality in some cases provides a quick way to exclude the possibility that a given code is uniquely decodable.
  • Prefix codes and block codes are important classes of codes which are uniquely decodable by definition.
  • Timeline of information theory

Notes

  1. ^ Sardinas & Patterson (1953).
  2. ^ Knuth (2003), p. 2
  3. ^ Berstel et al. (2009), Example 2.3.1 p. 63
  4. ^ Rodeh (1982).
  5. ^ Apostolico & Giancarlo (1984).
  6. ^ Rytter (1986) proves that the complementary problem, of testing for the existence of a string with two decodings, is NL-complete, and therefore that unique decipherability is co-NL-complete. The equivalence of NL-completeness and co-NL-completeness follows from the Immerman–Szelepcsényi theorem.
  7. ^ Salomaa (1981)
  8. ^ Berstel et al. (2009), Chapter 2.3

References

  • Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001.
  • Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
  • Knuth, Donald E. (December 2003). "Robert W Floyd, In Memoriam". SIGACT News. 34 (4): 3–13. doi:10.1145/954092.954488. S2CID 35605565.
  • Rodeh, M. (1982). "A fast test for unique decipherability based on suffix trees (Corresp.)". IEEE Transactions on Information Theory. 28 (4): 648–651. doi:10.1109/TIT.1982.1056535..
  • Apostolico, A.; Giancarlo, R. (1984). "Pattern matching machine implementation of a fast test for unique decipherability". Information Processing Letters. 18 (3): 155–158. doi:10.1016/0020-0190(84)90020-6..
  • Rytter, Wojciech (1986). "The space complexity of the unique decipherability problem". Information Processing Letters. 23 (1): 1–3. doi:10.1016/0020-0190(86)90121-3. MR 0853618..
  • Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064.
  • Sardinas, August Albert; Patterson, George W. (1953), "A necessary and sufficient condition for the unique decomposition of coded messages", Convention Record of the I.R.E., 1953 National Convention, Part 8: Information Theory, pp. 104–108.
Further reading