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. 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.
- Comment
- enIn 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.
- Has abstract
- enIn 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.
- Hypernym
- Algorithm
- Is primary topic of
- Sardinas–Patterson algorithm
- Label
- enSardinas–Patterson algorithm
- Link from a Wikipage to an external page
- www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html
- Link from a Wikipage to another Wikipage
- Arto Salomaa
- Block code
- Cambridge University Press
- Category:Algorithms
- Category:Coding theory
- Category:Data compression
- Coding theory
- Correctness (computer science)
- Donald Knuth
- Empty word
- Formal language
- Institute of Radio Engineers
- Kraft's inequality
- NL (complexity)
- NL-complete
- Nondeterministic Turing machine
- Polynomial time
- Prefix (computer science)
- Prefix code
- Quotient of a formal language
- Recursive definition
- Robert G. Gallager
- Robert W. Floyd
- Suffix (computer science)
- Suffix tree
- Timeline of information theory
- Variable-length code
- Wikt:terminate
- SameAs
- 4uRiX
- Algorithme de Sardinas-Patterson
- m.06znp8
- Q7423792
- Subject
- Category:Algorithms
- Category:Coding theory
- Category:Data compression
- WasDerivedFrom
- Sardinas–Patterson algorithm?oldid=1110849198&ns=0
- WikiPageLength
- 9053
- Wikipage page ID
- 23632960
- Wikipage revision ID
- 1110849198
- WikiPageUsesTemplate
- Template:Citation
- Template:Cite book
- Template:Cite journal
- Template:Sfnp