Does the algorithm require testing infinitely many messages?

No. It explores residual suffix states derived from a finite codebook. Detecting that the reachable states are exhausted provides a finite stopping condition.

Does it construct the best compression code?

No. It tests a decodability property of a supplied code. Code design and average encoded length are separate questions.

Can it test alphabets other than binary?

Yes. The prefix and suffix comparisons apply to finite strings over other coding alphabets as well.

AI Glossary / MLOps and deployment / Intermediate

Sardinas - Patterson algorithm

Definition

The Sardinas - Patterson algorithm determines whether a finite set of variable-length codewords is uniquely decodable. It checks whether two different sequences of source symbols could produce exactly the same concatenated encoded string, assuming distinct source symbols have distinct, nonempty codewords.

What it means

Assigning a different bit pattern to every symbol is not enough for reliable decoding. Once those patterns are joined without separators, their boundaries can become ambiguous. Unique decodability means that every complete valid encoded message corresponds to only one source-symbol sequence.

Prefix-free codes avoid the problem by ensuring that no codeword starts with another complete codeword. However, some codes are uniquely decodable without being prefix-free. Sardinas - Patterson provides a more general test by systematically tracking the unmatched endings that competing interpretations could leave behind.

How it works

Compare codewords whenever one is a proper prefix of another. Remove the shorter prefix and collect the nonempty suffixes that remain. These suffixes represent differences between competing partial parses.

Next compare each residual suffix with every original codeword, in both directions: either the residual may begin with a codeword, or a codeword may begin with the residual. Remove matching prefixes and collect the new nonempty residuals. Continue this process.

In one standard formulation, finding a residual that is itself a codeword proves ambiguity. An equivalent formulation detects an empty residual when two competing parses finally meet. If no new residual states arise without such a collision, the finite code is uniquely decodable. A correct implementation must use one consistent stopping convention.

Three practical examples

1. Custom telemetry codes: an engineer proposes short bit patterns for common events. The algorithm can check whether concatenated event messages remain unambiguous before the codebook enters a protocol.

2. Encoding audits: a team inherits a non-prefix code and needs to distinguish a genuine ambiguity from merely delayed decoding. A complete residual test provides stronger evidence than a few successful sample decodes.

3. Computer-science education: students can compare instantaneous decoding with eventual unique decoding. Small examples make clear why checking only that individual codewords differ is insufficient.

Think of it this way

Think of two people reading a sentence with the spaces removed and disagreeing about where its words end. The algorithm keeps track of the unmatched tail after their interpretations overlap, then asks whether further words could make the interpretations line up exactly.

The analogy is limited: natural language uses meaning and context, whereas the algorithm applies exact string rules. It tests all finite concatenations permitted by the codebook, without relying on which messages sound plausible.

Worked example

Let three source symbols have codewords A→0, B→01 and C→10. The initial codeword set is {0,01,10}. Since 0 is a prefix of 01, removing it leaves the residual 1. No other proper-prefix comparison adds a different initial residual.

Now compare residual 1 with the original codewords. It is a prefix of 10, leaving residual 0. Because 0 is itself a codeword, the collision criterion is met: this code is not uniquely decodable.

An explicit witness confirms the result. The encoded string 010 can be split as 0|10, meaning AC, or as 01|0, meaning BA. Both are complete messages, so knowing where the overall message ends does not remove this ambiguity.

For comparison, consider only A→0 and B→01. The initial residual is again 1, but neither 0 nor 01 begins with 1, and neither is a prefix of 1. No further residual arises, so this smaller code is uniquely decodable, despite not being prefix-free. After receiving a zero, a decoder may need the next bit or message end to decide which symbol it has received.

Illustrative case study

Fictional case: BitCourier designs compact event messages. Its test suite encodes and decodes individual events successfully, and the team assumes that distinct bit patterns guarantee a safe format.

A protocol reviewer instead tests the complete codebook. The residual analysis produces a collision, and a short encoded message is shown to represent two different event sequences. The failure had been absent from the limited examples used in the earlier tests.

The team selects a prefix-free replacement and versions the changed format. It also retains an ambiguity witness as a regression test. This fictional case illustrates why validating individual entries and validating arbitrary concatenations are different responsibilities.

Common misconceptions and mistakes

“Distinct codewords guarantee unique decoding.” They guarantee only that a single known codeword identifies a symbol. Concatenation can introduce new ambiguities.

“Failing the prefix-free test means a code is ambiguous.” Some non-prefix codes remain uniquely decodable, although they can require lookahead or a message boundary.

“A probability model resolves the ambiguity.” Choosing the more likely interpretation does not make exact lossless decoding unique. The other interpretation remains possible under an unrestricted codebook.

“Passing this test proves error correction.” The algorithm concerns ambiguity in an intact encoded string. It does not establish recovery from changed, lost or inserted bits.

Business use

For organizations designing compact formats, Sardinas - Patterson is a specialized validation tool. It can identify a fundamental coding defect before an ambiguous representation spreads across devices or stored archives. It is especially useful when reviewing a proposed non-prefix code.

Keep the scope of the result clear. Passing says nothing by itself about compression efficiency, decoding delay, corruption detection or implementation security. If a protocol restricts valid message sequences or carries separate lengths, analyze those rules explicitly; do not silently assume they are part of the unrestricted codebook test. Prefer a clear, documented decoding contract that independent implementations can follow.

Check your understanding

A codebook is not prefix-free, but its residual exploration ends without a collision. Should it automatically be rejected as ambiguous?

Answer: No. Under the algorithm's assumptions it is uniquely decodable. The designer must still assess decoding delay and framing requirements.

Related terms

Prefix code
Lossless compression
Uniquely decodable code
variable-length code
Huffman coding
Kraft–McMillan inequality
finite-state search

Learn next

Learn prefix trees, then trace residual sets for small codebooks. Implement both collision detection and witness reconstruction, and compare the result with exhaustive decoding of short strings as a debugging aid rather than a substitute for the general test.

Sources

Primary teaching source: Sam Roweis, “Uniquely Decodable and Instantaneous Codes,” Lecture 2, states the Sardinas–Patterson residual-set criterion: https://cs.nyu.edu/home/people/in_memoriam/roweis/csc310-2005/notes/lec2x.pdf . The codebook walkthrough and fictional protocol review are original teaching examples.

Previous: Sampling with replacement Next: Sargan - Hansen test