fasterthanlime

Aug 09, 2019 27 min #compression · #golang · #entropy

Huffman 101

Let's play a game: your objective is to guess a word, but you can only ask yes or no questions. You should also aim to ask as few questions as possible.

You might have played a variant of this game before, guessing famous actors or musicians. You'd usually ask questions like "Are they alive?", or "Have they won an Oscar"? And that would allow you to narrow down the possibilities, until you finally resort to a list of direct guesses ("Is it Amy Adams?") or simply give up.

However, my version of the game is slightly harder. Firstly: you cannot give up. You can use as many questions as you need, but eventually you have to find the answer. Secondly: the words can be anything. They can be completely made up. You may have to guess "Sesquipedalian" (which is a real word), or you may have to guess "Bendified" (which is a made up word).

By now, you may be starting to realize your usual strategy may not be applicable. You can't even fall back to asking about every word in the dictionary, because there isn't a dictionary of all the made-up words.

What can you do? Well, made up or not, all the possible words are made up of a finite number of letters. And, in English, there's only 26 of those.

So, one possible strategy is to ask "Is the first letter of the word A?" - if not, try the next letter of the alphabet: "Is the first letter of the word B?". Once you get a positive answer, write down that letter and move on to guessing the next one. If you ask about the twenty six letters of the alphabet and none of them are it, then you'll know you've gotten all the letters.

For comparison's sake, and since we're going to be comparing strategies, let's agree on a notation. Let's say for each negative answer, we write down a 0, and for each positive answer, we write down a 1.

If we were guessing the word "axe", our answer sheet would look like:

In total, we had to ask 56 questions! For a three letter word. That's not very good. Let's think of ways to improve that.

Right now, every game will end with us asking 26 questions, all of which will be met with a negative answer. This is a high price to pay, especially for short words. Instead, after each letter we guess, we could ask "is that all?". Let's guess "axe" again with that strategy and the same notation:

This brings the total number of questions from 56 down to 33. Pretty good! Of course, this is just for that one word, "axe". To be sure it's a good method, we'd have to test it against, say, a list of the most commonly used English words.

And this is exactly what we're going to do. All we need is:

• A list of commonly used words (460 thousands should do)
• For each word, to count how many questions we'd have to ask with each strategy
• To export that data as CSV, import it somewhere and generate a graph for it.

We can make that happen with about a hundred lines of Go:

package main

import (
  "fmt"
  "io/ioutil"
  "strings"
)

type Measures struct {
  byLength map[int]ByLength
}

type ByLength struct {
  totalQuestions int64
  numWords       int64
}

func NewMeasures() *Measures {
  return &Measures{
    byLength: make(map[int]ByLength),
  }
}

func (m *Measures) Record(wordLength int, numQuestions int) {
  bl := m.byLength[wordLength]
  bl.numWords += 1
  bl.totalQuestions += int64(numQuestions)
  m.byLength[wordLength] = bl
}

type Strat struct {
  // Name of the strategy
  name string

  // Function that returns the number of questions
  // we need to ask to guess a given word
  f func(word string) int

  // Stats
  m *Measures
}

func main() {
  // (error handling is omitted here)
  payload, _ := ioutil.ReadFile("words.txt")

  // split the source file into an array of words.
  words := strings.Split(string(payload), "\n")
  for i := range words {
    words[i] = strings.TrimSpace(words[i])
  }

  strats := []Strat{
    Strat{name: "simplest", f: simplest, m: NewMeasures()},
    Strat{name: "whentostop", f: whentostop, m: NewMeasures()},
  }

  for _, w := range words {
    for i := range strats {
      numQuestions := strats[i].f(w)
      strats[i].m.Record(len(w), numQuestions)
    }
  }

  cols := []string{"word_length"}
  for _, strat := range strats {
    cols = append(cols, strat.name)
  }
  fmt.Printf("%s\n", strings.Join(cols, ","))

  // for words of length 1 to 20 (inclusive)
  for i := 1; i <= 20; i++ {
    // print word length
    fmt.Printf("%d", i)
    for _, strat := range strats {
      // ...and average number of questions for strategy
      if bl, ok := strat.m.byLength[i]; ok {
        fmt.Printf(",%.2f", float64(bl.totalQuestions)/float64(bl.numWords))
      } else {
        // except if we have no data, in which case, just print 0
        fmt.Printf(",0")
      }
    }
    fmt.Printf("\n")
  }
}

func simplest(word string) int {
  numQuestions := 0
  for _, c := range word {
    // index is the 0-based index of the letter
    // in the alphabet. A = 0, B = 1, C = 2, etc.
    index := int(c - 'a')
    // we have to ask 1 question for A, 2 questions for B, etc.
    numQuestions += index + 1
  }
  numQuestions += 26
  return numQuestions
}

func whentostop(word string) int {
  numQuestions := 0
  for _, c := range word {
    // same as 'simplest'
    index := int(c - 'a')
    numQuestions += index + 1
    // after each letter, we need to ask whether the word
    // is over
    numQuestions += 1
  }
  return numQuestions
}

The results are clear: using a question to determine whether the word is ended is better. It's much better for short words, and only becomes marginally better for longer words:

The vertical bars indicate "average number of questions to ask in order to guess a word of this length".

Now that we've run some tests against many words, I'm satisfied that this strategy change was indeed an improvement.

We can do better though! Some letters tend to appear more frequently than others in English words. Since we're asking about each letter one by one, we might be able to reduce the number of questions if we first ask about the most common letters!

Again, we can use our database of common English words, and a bit of Go code to measure that:

package main

import (
  "fmt"
  "io/ioutil"
  "strings"
)

func main() {
  // (error handling is omitted here)
  payload, _ := ioutil.ReadFile("words.txt")

  // split the source file into an array of words.
  words := strings.Split(string(payload), "\n")
  for i := range words {
    words[i] = strings.TrimSpace(words[i])
  }

  freqs := make([]int64, 26)
  var total int64
  for _, w := range words {
    for _, c := range w {
      freqs[int(c-'a')] += 1
      total += 1
    }
  }

  fmt.Printf("letter,frequency\n")
  for i := 0; i < 26; i++ {
    letter := 'a' + rune(i)
    freq := float64(freqs[i]) / float64(total)
    fmt.Printf("%v,%.5f\n", string([]rune{letter}), freq)
  }
}

And we end up with the following graph:

If our calculations are correct, this means the most common letters in the English alphabet are: 'e', 'i', 'a', and 'o'. No surprise there!

So what happens if we ask about letters starting with the most likely? Well, our answer sheet for the word "axe" now looks like this:

Notice that the top row is different! Instead of A, B, C, etc., we now have letters from most to least frequent. It turns out 'x' is in the exact same place as before. However, when guessing 'e', we now only have to ask one question instead of three.

We went from 56 to 33, down to 31 questions. Well, it's shorter! Time for mass production - we'll adjust our previous program to add this new strategy, and run it against our common words database to see if it's any improvement.

Our new strategy function can be implemented like this (it's not the only way, but it's a simple way that works):

var freqlet = "eiaonsrtlcupdmhgybfvkwxzqj"

func frequency(word string) int {
  numQuestions := 0
  for _, c := range word {
    for _, l := range freqlet {
      // ask about each letter, from most to least likely
      numQuestions += 1
      if c == l {
        break
      }
    }
    // after each letter, we need to ask whether the word
    // is over
    numQuestions += 1
  }
  return numQuestions
}

...and it is! It doesn't change much for very short words, but as words grow longer, it becomes a clear winner. We only need to ask 165 questions on average to guess twenty-letter words!

We've made great improvements to our initial strategy - however, we're still not making the most of our questioning powers. While we can stop early (when guessing "a", for example), we still only eliminate one letter per question.

If our word contains a 'j', we'll need 26 questions. And even though 'j' is the least common letter, words do contains the letter 'j' all the time!

Let's start with the basics - our alphabet has 26 letters, so any letter has to be either in the first half (from A to M) or the second half (from N to Z) of the alphabet, right? And "is the letter in the first half of the alphabet?" is definitely a yes and no question, so it's allowed!

Let's see what our answer sheet would look like if we were to guess, as usual, the word "axe".

Each question eliminates half of the remaining letters. The first question eliminates thirteen possible letters, the second eliminates six or seven, and so on until there's only one letter left.

With that strategy, guessing "axe" only requires 17 questions! In fact, each letter requires exactly five questions (+ 1 question per letter to know if the word is over).

Adding this to our little comparison plot is extremely easy, since we can now just multiply the length of the word by a constant:

func partition(word string) int {
  return (5 + 1) * len(word)
}

How well does it perform? Pretty freaking well:

We're down to 120 questions for 20-letter words.

But let's not stop there.

Our fourth attempt (partition) outperformed all the other strategies, but in some sense, it's a step back from the third. We did not use frequency at all there!

What we need is a way to:

1. Eliminate a large amount of letters with each question
2. Ask fewer than five questions for the most frequent letters

But first, let's add a rule to our little guessing game: the guesser and the guessee can share information beforehand, /as long as the word to be guessed cannot be deduced from that information/.

So, for example, they could share this decision tree:

Now, I made up this tree - I don't know yet if it's going to outperform our "partition" strategy, so let's try it out at a larger scale.

Our function to compute the number of questions will simply be:

func tree1(word string) int {
  numQuestions := 0
  for _, c := range word {
    // if the letter is 'i' or 'e', we only need two questions
    if c == 'i' || c == 'e' {
      numQuestions += 2
    } else {
      // otherwise, we need 6
      numQuestions += 6
    }
    // ask whether word is over
    numQuestions += 1
  }
  return numQuestions
}

And the results are in:

Note: I've omitted "simplest" and "whentostop", since they were so much worse.

For every word length, "tree1" performs slightly worse than "partition". This is actually good news! We went on a limb, and everything didn't go terribly wrong, only slightly.

In our defense, this is a pretty bad decision tree: the letter 'a' is almost as likely as the letter 'i', and yet we spend two questions on 'i' and six questions on 'a'. Even though we now spend six questions on most of the alphabet, the average number of questions is still, more or less, the same.

We could go all day coming up with trees and comparing their performance - but as it turns out, there is a way to come up with the optimal decision tree in our particular situation.

It goes like this:

• Make a 'node' out of each letter and the probability of it appearing in a word.
• Make a list of all our nodes
• Take the two least likely nodes and make a new node with it:
  • Its probability being the sum of the two nodes
  • It doesn't have a letter associated with it

Looking back at our letter frequency data, our two least likely letters are 'j' (0.16%) and 'q' (0.17%). So, let's make a new node out of them, which will have probability 0.32%.

This gives us part of our decision tree, like so:

Our next two nodes are 'x' (0.30%), and.. the node we just created (0.32%).

Now, our partly-built decision tree looks like this:

(I've switched to circles so it's a bit easier to visualize).

Instead of doing everything by hand, let's write a bit of code to do it for us. We're going to adjust the code we used to find the frequency of letters in common English words in the first place:

package main

import (
  "fmt"
  "io/ioutil"
  "sort"
  "strings"

  "github.com/disiqueira/gotree"
)

type Node struct {
  letters  []rune
  prob     float64
  children []*Node
}

func (n *Node) String() string {
  return fmt.Sprintf("%q (%.2f%%)", string(n.letters), n.prob*100)
}

func main() {
  // (error handling is omitted here)
  payload, _ := ioutil.ReadFile("words.txt")

  // split the source file into an array of words.
  words := strings.Split(string(payload), "\n")
  for i := range words {
    words[i] = strings.TrimSpace(words[i])
  }

  freqs := make([]int64, 26)
  var total int64
  for _, w := range words {
    for _, c := range w {
      freqs[int(c-'a')]++
      total++
    }
  }

  var leafs []*Node
  for i := 0; i < 26; i++ {
    letter := 'a' + rune(i)
    freq := float64(freqs[i]) / float64(total)
    leafs = append(leafs, &Node{
      letters:  []rune{letter},
      prob:     freq,
      children: nil,
    })
  }

  for len(leafs) > 1 {
    sort.Sort(ByAscendingProb(leafs))
    l := leafs[0]
    r := leafs[1]
    newNode := &Node{
      letters:  append(l.letters, r.letters...),
      prob:     l.prob + r.prob,
      children: []*Node{l, r},
    }
    leafs = append([]*Node{newNode}, leafs[2:]...)
  }

  tree := gotree.New(leafs[0].String())
  mktree(tree, leafs[0])

  fmt.Println(tree.Print())
}

func mktree(tree gotree.Tree, node *Node) {
  for _, n := range node.children {
    t := tree.Add(n.String())
    mktree(t, n)
  }
}

type ByAscendingProb []*Node

func (a ByAscendingProb) Len() int           { return len(a) }
func (a ByAscendingProb) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAscendingProb) Less(i, j int) bool { return a[i].prob < a[j].prob }

I've spent a few lines on visualization so that we could get this beautiful output:

"iygfwkhelmdtpursnobvzxjqca" (100.00%)
├── "iygfwkhelmd" (41.11%)
│   ├── "iygfwkh" (18.51%)
│   │   ├── "i" (8.96%)
│   │   └── "ygfwkh" (9.56%)
│   │       ├── "yg" (4.38%)
│   │       │   ├── "y" (2.02%)
│   │       │   └── "g" (2.36%)
│   │       └── "fwkh" (5.17%)
│   │           ├── "fwk" (2.53%)
│   │           │   ├── "f" (1.12%)
│   │           │   └── "wk" (1.41%)
│   │           │       ├── "w" (0.64%)
│   │           │       └── "k" (0.77%)
│   │           └── "h" (2.64%)
│   └── "elmd" (22.60%)
│       ├── "e" (10.77%)
│       └── "lmd" (11.83%)
│           ├── "l" (5.58%)
│           └── "md" (6.25%)
│               ├── "m" (3.01%)
│               └── "d" (3.24%)
└── "tpursnobvzxjqca" (58.89%)
    ├── "tpurs" (27.83%)
    │   ├── "tpu" (13.62%)
    │   │   ├── "t" (6.61%)
    │   │   └── "pu" (7.02%)
    │   │       ├── "p" (3.25%)
    │   │       └── "u" (3.76%)
    │   └── "rs" (14.21%)
    │       ├── "r" (7.04%)
    │       └── "s" (7.16%)
    └── "nobvzxjqca" (31.06%)
        ├── "no" (14.39%)
        │   ├── "n" (7.19%)
        │   └── "o" (7.20%)
        └── "bvzxjqca" (16.66%)
            ├── "bvzxjqc" (8.20%)
            │   ├── "bvzxjq" (3.82%)
            │   │   ├── "b" (1.83%)
            │   │   └── "vzxjq" (1.99%)
            │   │       ├── "v" (0.95%)
            │   │       └── "zxjq" (1.05%)
            │   │           ├── "z" (0.42%)
            │   │           └── "xjq" (0.62%)
            │   │               ├── "x" (0.30%)
            │   │               └── "jq" (0.32%)
            │   │                   ├── "j" (0.16%)
            │   │                   └── "q" (0.17%)
            │   └── "c" (4.38%)
            └── "a" (8.46%)

How does it work? Well, looking at the tree, assuming we're guessing the letter 'a', our first question would be:

• Is the letter one of i, y, g, f, w, k, h, e, l, m, or d?

We'd get a negative answer, so we can carry on to this part of the tree:

"tpursnobvzxjqca" (58.89%)
├── "tpurs" (27.83%)
│   ├── "tpu" (13.62%)
│   │   ├── "t" (6.61%)
│   │   └── "pu" (7.02%)
│   │       ├── "p" (3.25%)
│   │       └── "u" (3.76%)
│   └── "rs" (14.21%)
│       ├── "r" (7.04%)
│       └── "s" (7.16%)
└── "nobvzxjqca" (31.06%)
    ├── "no" (14.39%)
    │   ├── "n" (7.19%)
    │   └── "o" (7.20%)
    └── "bvzxjqca" (16.66%)
        ├── "bvzxjqc" (8.20%)
        │   ├── "bvzxjq" (3.82%)
        │   │   ├── "b" (1.83%)
        │   │   └── "vzxjq" (1.99%)
        │   │       ├── "v" (0.95%)
        │   │       └── "zxjq" (1.05%)
        │   │           ├── "z" (0.42%)
        │   │           └── "xjq" (0.62%)
        │   │               ├── "x" (0.30%)
        │   │               └── "jq" (0.32%)
        │   │                   ├── "j" (0.16%)
        │   │                   └── "q" (0.17%)
        │   └── "c" (4.38%)
        └── "a" (8.46%)

Our next question:

• Is the letter one of t, p, u, r, or s ?

Again, we'd get a no, so we'd carry on to this part of the tree:

"nobvzxjqca" (31.06%)
├── "no" (14.39%)
│   ├── "n" (7.19%)
│   └── "o" (7.20%)
└── "bvzxjqca" (16.66%)
    ├── "bvzxjqc" (8.20%)
    │   ├── "bvzxjq" (3.82%)
    │   │   ├── "b" (1.83%)
    │   │   └── "vzxjq" (1.99%)
    │   │       ├── "v" (0.95%)
    │   │       └── "zxjq" (1.05%)
    │   │           ├── "z" (0.42%)
    │   │           └── "xjq" (0.62%)
    │   │               ├── "x" (0.30%)
    │   │               └── "jq" (0.32%)
    │   │                   ├── "j" (0.16%)
    │   │                   └── "q" (0.17%)
    │   └── "c" (4.38%)
    └── "a" (8.46%)

To the question: "is the letter one of n, or o?" we'd also get a no (no pun intended):

"bvzxjqca" (16.66%)
├── "bvzxjqc" (8.20%)
│   ├── "bvzxjq" (3.82%)
│   │   ├── "b" (1.83%)
│   │   └── "vzxjq" (1.99%)
│   │       ├── "v" (0.95%)
│   │       └── "zxjq" (1.05%)
│   │           ├── "z" (0.42%)
│   │           └── "xjq" (0.62%)
│   │               ├── "x" (0.30%)
│   │               └── "jq" (0.32%)
│   │                   ├── "j" (0.16%)
│   │                   └── "q" (0.17%)
│   └── "c" (4.38%)
└── "a" (8.46%)

Finally, we can ask if the letter is one of b, v, x, z, j, q, or c - and when we get this no, we know the letter is a.

In total, we've spent four questions to guess the letter a - which is less than the five questions "partition" needs for any letter. This is good, because 'a' is in the top 3 most frequent letters.

If we were to guess x, by looking at the tree, we can see that we would be asking eight questions! However, for e, we'd only be asking three questions.

In total, to guess "axe", we'd be asking 4 + 8 + 3 = 15 questions, plus the three questions we need to know if the word is over, which adds up to 17 - exactly the same number of questions as with the "partition" method. However, this decision tree takes frequency into account, so it should perform better.

To test that out, we need to carry our decision tree from one program (the frequency measurement / tree building one) to the other (the "strategy efficiency comparator").

I'll simply use JSON for that. First, we add JSON tags to our Node data structure (this article is now a Go course):

// we need to make sure our fields are exported (start with an uppercase letter)
// otherwise they won't get marshalled.
type Node struct {
  Letters  []rune  `json:"letters"`
  Prob     float64 `json:"prob"`
  Children []*Node `json:"children"`
}

Then, once the tree is generated, we simply serialize it to a file, huff.json.

bs, _ := json.MarshalIndent(leafs[0], "", "  ")
_ = ioutil.WriteFile("huff.json", bs, 0644)

Here's a small excerpt from the resulting file:

{
    "letters": [
    121,
    103
    ],
    "prob": 0.04383930500372708,
    "children": [
    {
        "letters": [
        121
        ],
        "prob": 0.020195753849763715,
        "children": null
    },
    {
        "letters": [
        103
        ],
        "prob": 0.023643551153963365,
        "children": null
    }
    ]
}

Back to our benchmarking program, let's load it at startup, using an init() func:

var rootNode *Node

func init() {
  bs, _ := ioutil.ReadFile("huff.json")
  var node Node
  json.Unmarshal(bs, &node)
  // *not* a dangling pointer, all hail the garbage collecting gods!
  rootNode = &node
}

And finally, our "number of questions" function will look like this: (again, the slow, but somewhat-easy-to-follow way):

func tree2(word string) int {
  numQuestions := 0
  for _, wordLetter := range word {
    node := rootNode
    for len(node.Letters) > 1 {
    searchChild:
      for _, child := range node.Children {
        for _, nodeLetter := range child.Letters {
          if nodeLetter == wordLetter {
            node = child
            break searchChild
          }
        }
      }
      // every time we travel to a new node, that's a question!
      numQuestions++
    }

    // ask if the word is over
    numQuestions++
  }
  return numQuestions
}

So, how does it perform? Were our efforts worth it?

They were! The results are great - we're almost at 100 questions on average to guess a 20-letter word - which is much, much better.

What we have built here, is a Huffman code for the latin alphabet, suitable for compressing common English words. We know the tree we ended up with is the best tree possible (for those probabilities), because Huffman codes are optimal.

However, there is one more thing we can do.

We've learned how to construct a "decision tree" to minimize the number of questions to ask when guessing a word, and in particular, how to build the optimal tree for that.

But something's bothering me - between every letter, we need to ask whether the word is over, or if it keeps going. What if we decided that the nodes in our tree should not correspond only to "letters", but to symbols, which can be either:

• One of the 26 letters, from a to z, OR
• A signal for the end of the word

You can think of it as making up a new letter, so that we end up with a 27-letter alphabet. Only the 27th letter is only used to mark the end of a word.

First of all, we're going to need to measure the frequency of this new symbol. We can easily adjust our freq program.

  freqs := make([]int64, 27)
  var total int64
  for _, w := range words {
    for _, c := range w {
      freqs[int(c-'a')]++
      total++
    }
    // we've encountered the end of a word!
    // its frequency is at the 27th position,
    // so, 26 for 0-based indexing.
        freqs[26]++
        total++
  }

For the sake of visualization, I've decided that we'll use the real-world symbol '$' (dollar sign) to represent the end of a word.

Our new decision tree is as follows:

"$elmdtpursnobvzxjqcaiygfwkh" (100.00%)
├── "$elmdtpu" (42.33%)
│   ├── "$e" (19.32%)
│   │   ├── "$" (9.58%)
│   │   └── "e" (9.74%)
│   └── "lmdtpu" (23.01%)
│       ├── "lmd" (10.69%)
│       │   ├── "l" (5.04%)
│       │   └── "md" (5.65%)
│       │       ├── "m" (2.72%)
│       │       └── "d" (2.93%)
│       └── "tpu" (12.32%)
│           ├── "t" (5.97%)
│           └── "pu" (6.34%)
│               ├── "p" (2.94%)
│               └── "u" (3.40%)
└── "rsnobvzxjqcaiygfwkh" (57.67%)
    ├── "rsno" (25.86%)
    │   ├── "rs" (12.84%)
    │   │   ├── "r" (6.37%)
    │   │   └── "s" (6.48%)
    │   └── "no" (13.02%)
    │       ├── "n" (6.51%)
    │       └── "o" (6.51%)
    └── "bvzxjqcaiygfwkh" (31.81%)
        ├── "bvzxjqca" (15.07%)
        │   ├── "bvzxjqc" (7.42%)
        │   │   ├── "bvzxjq" (3.46%)
        │   │   │   ├── "b" (1.65%)
        │   │   │   └── "vzxjq" (1.80%)
        │   │   │       ├── "v" (0.86%)
        │   │   │       └── "zxjq" (0.95%)
        │   │   │           ├── "z" (0.38%)
        │   │   │           └── "xjq" (0.56%)
        │   │   │               ├── "x" (0.27%)
        │   │   │               └── "jq" (0.29%)
        │   │   │                   ├── "j" (0.14%)
        │   │   │                   └── "q" (0.15%)
        │   │   └── "c" (3.96%)
        │   └── "a" (7.65%)
        └── "iygfwkh" (16.74%)
            ├── "i" (8.10%)
            └── "ygfwkh" (8.64%)
                ├── "yg" (3.96%)
                │   ├── "y" (1.83%)
                │   └── "g" (2.14%)
                └── "fwkh" (4.68%)
                    ├── "fwk" (2.29%)
                    │   ├── "f" (1.02%)
                    │   └── "wk" (1.27%)
                    │       ├── "w" (0.58%)
                    │       └── "k" (0.69%)
                    └── "h" (2.39%)

We need to adjust our "number of questions" measurement function a bit. First, let's extract "letter cost estimation" into its own function:

// Calculate the number of questions required to guess
// a letter (or '$') using our latest tree
func letterCost(wordLetter rune) int {
  numQuestions := 0
  node := rootNode
  for len(node.Letters) > 1 {
  searchChild:
    for _, child := range node.Children {
      for _, nodeLetter := range child.Letters {
        if nodeLetter == wordLetter {
          node = child
          break searchChild
        }
      }
    }
    // every time we travel to a new node, that's a question!
    numQuestions++
  }
  return numQuestions
}

And now our word cost computation function is trivial:

func tree3(word string) int {
  numQuestions := 0
  for _, wordLetter := range word {
    // add the cost of each letter
    numQuestions += letterCost(wordLetter)
  }
  // and finally, our end of word marker
  numQuestions += letterCost('$')
  return numQuestions
}

Was it a good idea? Let's pit our three trees together: our naive one early on, our Huffman code with one explicit "end of word" question per letter, and our Huffman code that has an "end of word" symbol in its alphabet.

This time, I used a logarithmic scale for the Y axis, to make the graph more readable.

I want to take a moment to point out that I did not know what the results would be exactly when I started writing this article. All I had was a blind faith in David A. Huffman and the word "optimal", and a feeling of what would work well and what wouldn't.

I'm really excited to see that, yes, indeed, having "end of word" as a symbol is worth it.. for words of 4 letters and above. Below that, our eager "is it over yet?" strategy performs better.

Finally, let's pit all of our strategies against each other, from the very first one (asking about each letter of the alphabet in sequence) to the last one (a Huffman code with an "end of word" symbol).

And that's it for this post! I hope you enjoyed learning about Huffman codes in the most roundabout way possible. In the real world, they're used for data compresion, in formats like DEFLATE (PDF), which I might do another article on since it has a lot of interesting tidbits of its own!

This is hopefully the first of many articles sponsored by my patrons on Patreon, I look forward to write some more!

Thanks to my sponsors: xales, nyangogo, Shane Lillie, Josiah Bull, Jean-David Gadina, Jonathan Adams, henrique-pinto, Valentin Mariette, David White, Nikolai Vincent Vaags, Daniel Papp, Aalekh Patel, Philipp Gniewosz, Johan Saf, bbutkovic, Kamran Khan, Sindre Johansen, compwhizii, Chris Biscardi, Matt Jackson and 227 more xales, nyangogo, Shane Lillie, Josiah Bull, Jean-David Gadina, Jonathan Adams, henrique-pinto, Valentin Mariette, David White, Nikolai Vincent Vaags, Daniel Papp, Aalekh Patel, Philipp Gniewosz, Johan Saf, bbutkovic, Kamran Khan, Sindre Johansen, compwhizii, Chris Biscardi, Matt Jackson, Romet Tagobert, Thor Kamphefner, Xirvik Servers, Michael Mrozek, Andy Gocke, Tabitha, Matěj Volf, Blake Johnson, Brandon Piña, Chris Emery, David Cornu, Walther, Nicholas Bishop, Tom Forbes, Paul Horn, Makoto Nakashima, Lyssieth, genny, Andrew Neth, Benjamin Röjder Delnavaz, Dirkjan Ochtman, Romain Ruetschi, Paul Schuberth, Marie Janssen, Alex Krantz, Michael, Dimitri Merejkowsky, Aleksandre Khokhiashvili, Daniel Wagner-Hall, Cole Kurkowski, clement, Jack Duvall, Richard Pringle, Adam Gutglick, Johan Andersson, Aiden Scandella, Geoff Cant, Jacob Cheriathundam, Jean Manguy, Dennis Henderson, James Rhodes, Isak Sunde Singh, Lev Khoroshansky, Vincent, Boris Dolgov, Santiago Lema, Yves, David E Disch, Beth Rennie, Leo Shimonaka, Xavier Groleau, Raphaël Thériault, old.woman.josiah, Michał Bartoszkiewicz, Helge Eichhorn, Dylan Anthony, AdrianEddy, Horváth-Lázár Péter, Luke Konopka, Zoran Zaric, Marco Carmosino, Sarah Berrettini, Alan O'Donnell, Http 418, Zaki, avborhanian, James Brown, Lena Schönburg, Matt Heise, Michal Hošna, Zachary Thomas, Tyler Bloom, Lucille Blumire, Chris Thackrey, Andronik, Victor Song, Moritz Lammerich, Neil Blakey-Milner, Paige Ruten, callym, Jake Demarest-Mays, Borys Minaiev, Zeeger Lubsen, Mikkel Rasmussen, René Ribaud, Marcin Kołodziej, Mason Ginter, Yuriy Taraday, Torben Clasen, Marcus Griep, Rufus Cable, Scott Steele, Raine Tingley, Noel, C J Silverio, villem, Marty Penner, Paul Marques Mota, Eugene Bulkin, Sean Bryant, anichno, Mike Cripps, Steven McGuire, Senyo Simpson, ZacJW, joseph, Antoine Rouaze, Ben Mitchell, Lennart Oldenburg, Guy Waldman, Max Heaton, Integer 32, LLC, Sawyer Knoblich, Chris Walker, Berkus Decker, Peter Shih, Josh Triplett, WeblWabl, Dom, Henrik Tudborg, Ryan, Cass, std__mpa, jer, Foxie Solutions, Mattia Valzelli, Daniel Silverstone, Justin Ossevoort, Jelle Besseling, Scott Sanderson, Luiz Irber, Mario Fleischhacker, Ahmad Alhashemi, Christoph Grabo, Romain Kelifa, budrick, Garret Kelly, playest, SeniorMars, jatescher, Tobias Bahls, Nicolas Goy, Tyler Schmidtke, Sylvie Nightshade, Marcus Brito, Matthew T, notryanb, L0r3m1p5um, Sam, Niels Abildgaard, Enrico Zschemisch, Jörn Huxhorn, hgranthorner, Steven Pham, Chris, Ivo Murrell, Andy F, Diego Roig, Pete Bevin, David Souther, qrpth, Ramen, Marcus Griep, Manuel Hutter, Evan Relf, Ernest French, Herman J. Radtke III, John VanEnk, Tiziano Santoro, Jon Gjengset, you got maiL, Miguel Piedrafita, Ronen Ulanovsky, Geoffroy Couprie, Marky Mark, Jarek Samic, Max Bruckner, Marc-Andre Giroux, Matt Jadczak, prairiewolf, Radu Matei, Ross Williams, Theodore Rose, Gran PC, zaurask, Luke Yue, Yufan Lou, Tanner Muro, Timothée Gerber, Alex Doroshenko, Ben Wishovich, Richard Stephens, belzael, Astrid, Philipp Hatt, Morgan Rosenkranz, Corey Alexander, Ives van Hoorne, Guillaume Demonet, pinkhatbeard, Daniel Strittmatter, Chris Sims, Christian Bourjau, Colin VanDervoort, Olly Swanson, Joshua Roesslein, Michael Alyn Miller, Johnathan Pagnutti, Jan De Landtsheer, David Barsky, Yann Schwartz, Bob Ippolito, Max von Forell, Guillaume E, Kristoffer Winther Balling, Hadrien G., Julian Schmid, Braidon Whatley, Olivia Crain, Alejandro Angulo, Duane Sibilly, Mark Old, ofrighil, Chirag Jain, James Leitch, Ronen Cohen, Joonas Koivunen

Comment on /r/fasterthanlime

If you liked what you saw, please support my work!

Donate on GitHub Donate on Patreon

Here's another article just for you:

When rustc explodes

Jul 13, 2022

1 hour 23 min #rust · #tracing · #investigation

One could say I have a bit of an obsession with build times.

I believe having a "tight feedback loop" is extremely valuable: when I work on a large codebase, I want to be able to make small incremental changes and check very often that things are going as expected.

Especially if I'm working on a project that needs to move quickly: say, the product for an early-stage startup, or a side-project for which I only ever get to do 1-hour work bursts at most.

Read more