# 38.3 Shannon-Fano Codes

Shannon-Fano codes are an approach to create prefix-free codes based on a set of symbols/characters and their probabilities. The main idea is that we want shorter prefix-free codes for more popular characters, and longer codes for lesser used characters.

The algorithm is: 

* Count relative frequencies of all characters in a text.
* Split into ‘left’ and ‘right halves’ of roughly equal frequency.
  * Left half gets a leading zero. Right half gets a leading one.
  * Repeat.

At the end, you will get a tree as shown below, with shorter paths for characters with a higher frequency, and longer paths for characters with a lower frequency.

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2F9D5OVxQfZUCbTv0pBzif%2FScreen%20Shot%202023-04-24%20at%206.06.15%20PM.png?alt=media&#x26;token=1ca46da8-df1e-4bff-ba42-2f564d571a21" alt=""><figcaption></figcaption></figure>

However, Shannon-Fano coding is NOT optimal, so it is not used very often.