Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Sardinas–Patterson algorithm
Summary
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. 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.
Consider the code . This code, which is based on an example by Berstel, 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 and such that is a prefix of , that is,
for some "dangling suffix" . If one tries first and , the dangling suffix is . If we manage to find two sequences and of codewords such that
then we are finished: For then the string can alternatively be decomposed as , 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 , and the sequence 1 is a codeword. We can thus also continue with w'=0 as the new dangling suffix.
The algorithm is described most conveniently using quotients of formal languages.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.