Incoding theory, theSardinas–Patterson algorithm is a classical algorithm for determining inpolynomial time whether a givenvariable-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. AsKnuth reports, the algorithm was rediscovered about ten years later in 1963 byFloyd, despite the fact that it was at the time already well known in coding theory.^[2]

Consider the code${\displaystyle \{\mathtt{\text{a}}\mapsto \mathtt{\text{1}},\mathtt{\text{b}}\mapsto \mathtt{\text{011}},\mathtt{\text{c}}\mapsto \mathtt{\text{01110}},\mathtt{\text{d}}\mapsto \mathtt{\text{1110}},\mathtt{\text{e}}\mapsto \mathtt{\text{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 bycdb andbabe.

In general, a codeword can be found by the following idea: In the first round, we choose two codewords${\displaystyle x_1}$ and${\displaystyle y_1}$ such that${\displaystyle x_1}$ is aprefix of${\displaystyle y_1}$, that is,${\displaystyle x_{1}w=y_1}$ for some "dangling suffix"${\displaystyle w}$. If one tries first${\displaystyle x_1=\mathtt{\text{011}}}$ and${\displaystyle y_1=\mathtt{\text{01110}}}$, the danglingsuffix is${\displaystyle \mathtt{\text{w}}=\mathtt{\text{10}}}$. If we manage to find two sequences${\displaystyle x_2,\dots ,x_p}$ and${\displaystyle y_2,\dots ,y_q}$ of codewords such that${\displaystyle x_2\cdots x_p=w{y}_2\cdots y_q}$, then we are finished: For then the string${\displaystyle x=x_1{x}_2\cdots x_p}$ can alternatively be decomposed as${\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 hasw as prefix. Then we obtain a new dangling suffixw, with which we can continue our search. If we eventually encounter a dangling suffix that is itself a codeword (or theempty 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 ofw. In our example, we have${\displaystyle w=\mathtt{\text{10}}}$, and the sequence1 is a codeword. We can thus also continue with${\displaystyle w=\mathtt{\text{0}}}$ as the new dangling suffix.

Example run
${\displaystyle C}$:
a	1
b	011
c	01110
d	1110
e	10011
${\displaystyle S_1}$:
F=a-1d	110
G=a-1e	0011
H=b-1c	10
${\displaystyle S_2}$:
H=a-1F	10
I=a-1H	0
b=H-1e	011
J=I-1b	11
K=I-1c	1110

The algorithm is described most conveniently usingquotients offormal languages. In general, for two sets of stringsD andN, the (left) quotient${\displaystyle N^{-1}D}$ is defined as the residual words obtained fromD by removing some prefix inN. Formally,${\displaystyle N^{-1}D=\{y\mid xy\in D\text{and}x\in N\}}$. Now let${\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${\displaystyle i=1}$, the set of potential dangling suffixes will be denoted by${\displaystyle S_i}$. The sets${\displaystyle S_i}$ are definedinductively as follows:

${\displaystyle S_1=C^{-1}C\setminus \{\epsilon \}}$. Here, the symbol${\displaystyle \epsilon }$ denotes theempty word.

${\displaystyle S_{i+1}=C^{-1}{S}_i\cup S_i^{-1}C}$, for all${\displaystyle i\ge 1}$.

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

See the left box for an example run of the algorithm on the given code; lower and upper case letters denote code and "dangling sugffix" strings, respectively. During the construction of${\displaystyle S_2}$, the code wordb is encountered (shown in red), and the algorithm stops. The right box indicates how the example string 1110011 can be shown to have multiple encodings (db,aae), using the equations that were collected during the algorithm run.

Since all sets${\displaystyle S_i}$ are sets of suffixes of a finite set of codewords, there are only finitely many different candidates for${\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 alwaysterminate. 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 inpolynomial time as a function of this input length. By using asuffix tree to speed the comparison between each dangling suffix and the codewords, the time for the algorithm can be bounded by O(nk), wheren is the total length of the codewords andk is the number of codewords.^[4] The algorithm can be implemented using apattern matching machine.^[5] The algorithm can also be implemented to run on anondeterministic Turing machine that uses onlylogarithmic space; the problem of testing unique decipherability isNL-complete, so this space bound is optimal.^[6]

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

• Kraft's inequality in some cases provides a quick way to exclude the possibility that a given code is uniquely decodable.
• Prefix codes andblock codes are important classes of codes which are uniquely decodable by definition.
• Timeline of information theory
• Post's correspondence problem is similar, yet undecidable.

• 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 theI.R.E., 1953 National Convention, Part 8: Information Theory, pp. 104–108.

Further reading

• Robert G. Gallager:Information Theory and Reliable Communication. Wiley, 1968

• Algorithms
• Coding theory
• Data compression