The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
62 views

Existence of incremental algorithm for (canonical) prefix-free codes

Short version Given the $N$ code lengths of an optimal prefix-free code $L[1..N]$ for $N$ unknown weights $W[1..N]$ of known sum $S$, and $N'$ new weights $W'[1..N']$ all larger than the weights ...
8
votes
2answers
190 views

How do I construct an optimal affix code?

An affix code is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in ...
1
vote
1answer
508 views

Definition of a prefix-free Turing machine

A prefix-free function is one whose domain is prefix-free. Similarly, a prefix-free (Turing) machine is one whose domain is prefix-free. It is usual to consider such a machine as being ...
5
votes
0answers
147 views

What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?

In the algebraic decision tree, the result is clear: Elmasry and Belal (Verification Of Minimum Redundancy Prefix Codes)'s lower bound shows that the worst case complexity of computing an optimal ...