Optimal Prefix Free Code: word-RAM Linear and Algebraic Instance Optimal

Details Optimal Prefix Free Code: word-RAM Linear and Algebraic Instance Optimal Optimal Prefix Free Code: word-RAM Linear and Algebraic Instance Optimal

2012-04-26

arxiv.org/abs/1204.5801v1

Computer Science

Data Structures and Algorithms

Preliminary draft

Scientific paper

We describe a new technique to compute an optimal prefix-free code over $\alphabetSize$ symbols from their frequencies $\{\frequency_1,..,\frequency_\alphabetSize\}$. This technique yields an algorithm running in linear time in the $\Omega(\lg \alphabetSize)$-word RAM model when each frequency holds into $\Oh(1)$ words, hence improving on the $\Oh(\alphabetSize\lg\lg\alphabetSize)$ solution based on sorting in the word RAM model. In a more restricted model, this yields also an algorithm performing $\Oh(\alphabetSize(1{+}\entropy(\alphabetSize_1,...,\alphabetSize_\nbCodeLengths))) \subset\Oh(\alphabetSize(1{+}\lg\nbCodeLengths)) \subset\Oh(\alphabetSize\lg\alphabetSize)$ algebraic operations, where $\nbCodeLengths$ is the number of distinct code lengths optimally assigned, $\alphabetSize_i$ is the number of frequencies assigned to the $i$-th code length, and $\entropy(\alphabetSize_1,..,\alphabetSize_\nbCodeLengths)=\alphabetSize\lg \alphabetSize-\sum\alphabetSize_i\lg\alphabetSize_i$ is the entropy of $(\alphabetSize_1,...,\alphabetSize_\nbCodeLengths)$. The first complexity is optimal in the word-RAM model, while the latter complexity is instance optimal over all input order oblivious algorithms in the algebraic decision tree model, and improves over both the traditional $O(\alphabetSize\lg\alphabetSize)$ algorithm from Huffman and the $O(\alphabetSize\nbCodeLengths)$ adaptive algorithm from Belal and Elmasry.

Affiliated with

Also associated with

No associations

Rating

Optimal Prefix Free Code: word-RAM Linear and Algebraic Instance Optimal does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Prefix Free Code: word-RAM Linear and Algebraic Instance Optimal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Prefix Free Code: word-RAM Linear and Algebraic Instance Optimal will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-313393