Prefix code: Difference between revisions

Revision as of 09:29, 4 April 2016

Revision as of 09:37, 4 April 2016

Line 26:

==Related concepts==

A '''suffix code''' is a set of words none of which is a suffix of any other; equivalently, a set of words which are the reverse of a prefix code. As with a prefix code, the representation of a string as a concatenation of such words is unique. A '''bifix code''' is a set of words which is both a prefix and a suffix code.<ref name=BPR58>Berstel et al (2010) p.58</ref>

An '''optimal prefix code''' is a prefix code with minimal average length. That is, assume an alphabet of {{mvar|n}} symbols with probabilities {{<math|>p(A_i)}}</math> for a prefix code {{mvar|C}}. If {{mvar|C'}} is another prefix code and <math>λ_{i}^{1}\lambda'_i</math> are the lengths of the codewords of {{mvar|C'}}, then <math>\sum_{i=1}^n { \lambda_i p(A_i) } \leq \sum_{i=1}^n { \lambda'_i p(A_i) } \!</math>.<ref>McGill COMP 423 Lecture notes[http://www.cim.mcgill.ca/~langer/423/lecture2.pdf]</ref>

<math>\sum_{i=1}^n { y_i^2 }\!</math>

{{math|{{!}}''x''{{!}}}} of a [[real number]]&nbsp;{{mvar|x}}

==Prefix codes in use today==