<p>Which practical problem would benefit from a technique to compute optimal prefix free codes faster (say, faster than O(sigma log sigma) on sigma input symbols)?</p>

<p>When compressing a source of n symbols over al alphabet of size sigma, computing the Huffman code takes time within O(sigma log sigma), while compression and decompression takes time within O(n), typically much larger than sigma log sigma. So, is it useless to improve on this O(sigma log sigma) or are there applications where the running time of computing the optimal code does matter?</p>

<hr>

<h1>Background:</h1>

<h2>A new algorithm:</h2>

<p>In 2016, I describe (at the peer reviewed scientific conference CPM) a new (adaptive) algorithm for computing optimal prefix free codes (<a href="http://arxiv.org/abs/1602.00023" rel="noreferrer">http://arxiv.org/abs/1602.00023</a> Optimal Prefix Free Codes With Partial Sorting), inspired by van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with a relatively minor extension of Karp et al.'s Deferred Data Structure to partially sort a multiset accordingly to the queries performed on it (known since 1988). This algorithm is (optimally) taking advantage of some easy instances, such as when the frequencies cluster in a few groups of frequencies all within a factor of two of each other.</p>

<h2>Experimental Results:</h2>

<p>For the extended version, I implemented this algorithm in python (<a href="https://gitlab.com/FineGrainedAnalysis/PrefixFreeCodes" rel="noreferrer">https://gitlab.com/FineGrainedAnalysis/PrefixFreeCodes</a>) and tested it on word frequencies in English texts (from the Gutenberg project): I will update the arxiv version shortly with a description. The experiments suggest that the improvement cannot be by more than a constant factor.</p>

<h2>Negative comments:</h2>

<p>On the other hand, I am also told that the concept that "the problem of computing optimal prefix free codes faster is important because the Huffman code is used in main data compression standards" is "completely invalid", as <strong>none of implementations of standards contains routines for constructing Huffman codes</strong>, because <strong>Huffman codes are pre-constructed and are kept in the form of look-up tables</strong>.</p>

<h2>Partial answers:</h2>

<ol>
<li>Various people (e.g. van Leeuwen in 1976, Moffat and Turpin in 1988, Belal and Elmasry in 2016, etc.) in the past have worked on improving the computing time of optimal prefix free codes, so I am in good company in thinking the problem interesting, and I assumed that it meant that it had practical applications. </li>
<li>In 2000, Moura et al.~\cite{2000-TOIS-FastAndFlexibleWordSearchingOnCompressedText-MouraNavarroZivianiBaezaYates} studied the compression of natural texts via a Huffman code, taking words as input symbols, and showing that it lost a bit of compressibility but gained a lot in indexability.</li>
<li>In 1997 Takaoka showed that using the Huffman code tree to schedule the merging of sorted arrays yielded a faster version of merge sort (by detecting sorted runs, and merging in priority the shortest ones).</li>
</ol>

<p>I am unhappy with any of those answers, as those are all quite academic/theoretic: I am wondering about real practical applications.</p>

CC BY-SA 4.0
2019-12-19T14:21:43.473Z
There is something called [*adaptive Huffman coding*](https://en.wikipedia.org/wiki/Adaptive_Huffman_coding), where you assume that you have a source where the probability of the symbols changes, and you change the Huffman tree to keep pace with this changing probability. Calculating Huffman trees fast might make these coding protocols work faster.
Peter Shor 
CC BY-SA 4.0
2019-12-19T14:29:20.030Z
In jpeg, you are allowed to supply your own Huffman codes, although most implementations presumably use the pre-supplied Huffman code. So these people telling you that the use of it in data compression standards is "completely invalid" don't know what they're talking about. (On the other hand, the time needed for computing Huffman codes is undoubtedly a minuscule fraction of the time needed to encode an image in jpeg.)
Peter Shor 
CC BY-SA 4.0
2019-12-19T22:45:59.190Z
$O(|\Sigma| \log |\Sigma|)$ is close to linear in the input size already.  And if the symbols are given pre-sorted by frequency, Huffman Coding can be done in linear time.  On the surface, it doesn't seem like there's much room for improvement, either in theory or practice.
Neal Young
<huffman>
Are there any practical applications of a faster algorithm to compute Huffman codes?
J.y B.y
# Are there any practical applications of a faster algorithm to compute Huffman codes?

(Asked by: username_0 on 2019-12-19)

Which practical problem would benefit from a technique to compute optimal prefix free codes faster (say, faster than O(sigma log sigma) on sigma input symbols)?

When compressing a source of n symbols over al alphabet of size sigma, computing the Huffman code takes time within O(sigma log sigma), while compression and decompression takes time within O(n), typically much larger than sigma log sigma. So, is it useless to improve on this O(sigma log sigma) or are there applications where the running time of computing the optimal code does matter?

---

# Background:

## A new algorithm:

In 2016, I describe (at the peer reviewed scientific conference CPM) a new (adaptive) algorithm for computing optimal prefix free codes (<http://arxiv.org/abs/1602.00023> Optimal Prefix Free Codes With Partial Sorting), inspired by van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with a relatively minor extension of Karp et al.'s Deferred Data Structure to partially sort a multiset accordingly to the queries performed on it (known since 1988). This algorithm is (optimally) taking advantage of some easy instances, such as when the frequencies cluster in a few groups of frequencies all within a factor of two of each other.

## Experimental Results:

For the extended version, I implemented this algorithm in python (<https://gitlab.com/FineGrainedAnalysis/PrefixFreeCodes>) and tested it on word frequencies in English texts (from the Gutenberg project): I will update the arxiv version shortly with a description. The experiments suggest that the improvement cannot be by more than a constant factor.

## Negative comments:

On the other hand, I am also told that the concept that "the problem of computing optimal prefix free codes faster is important because the Huffman code is used in main data compression standards" is "completely invalid", as **none of implementations of standards contains routines for constructing Huffman codes**, because **Huffman codes are pre-constructed and are kept in the form of look-up tables**.

## Partial answers:

1. Various people (e.g. van Leeuwen in 1976, Moffat and Turpin in 1988, Belal and Elmasry in 2016, etc.) in the past have worked on improving the computing time of optimal prefix free codes, so I am in good company in thinking the problem interesting, and I assumed that it meant that it had practical applications.
2. In 2000, Moura et al.~\cite{2000-TOIS-FastAndFlexibleWordSearchingOnCompressedText-MouraNavarroZivianiBaezaYates} studied the compression of natural texts via a Huffman code, taking words as input symbols, and showing that it lost a bit of compressibility but gained a lot in indexability.
3. In 1997 Takaoka showed that using the Huffman code tree to schedule the merging of sorted arrays yielded a faster version of merge sort (by detecting sorted runs, and merging in priority the shortest ones).

I am unhappy with any of those answers, as those are all quite academic/theoretic: I am wondering about real practical applications.

**Tags:** huffman

> **Comments:**
> **username_1**: There is something called [*adaptive Huffman coding*](https://en.wikipedia.org/wiki/Adaptive_Huffman_coding), where you assume that you have a source where the probability of the symbols changes, and you change the Huffman tree to keep pace with this changing probability. Calculating Huffman trees fast might make these coding protocols work faster.  
> **username_1**: In jpeg, you are allowed to supply your own Huffman codes, although most implementations presumably use the pre-supplied Huffman code. So these people telling you that the use of it in data compression standards is "completely invalid" don't know what they're talking about. (On the other hand, the time needed for computing Huffman codes is undoubtedly a minuscule fraction of the time needed to encode an image in jpeg.)  
> **username_2**: $O(|\Sigma| \log |\Sigma|)$ is close to linear in the input size already.  And if the symbols are given pre-sorted by frequency, Huffman Coding can be done in linear time.  On the surface, it doesn't seem like there's much room for improvement, either in theory or practice.  

---

## 0 answers

