.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/communications/information/plot_06_huffman_code.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_communications_information_plot_06_huffman_code.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_communications_information_plot_06_huffman_code.py:


Huffman's minimum-redundancy code (1952)
========================================

In Robert Fano's information theory class at MIT, David Huffman was offered
a term paper instead of a final exam: find the most efficient binary code.
Shannon and Fano's top-down splitting was good but not always optimal.
Huffman worked bottom-up. He merged the two least likely symbols into one,
and repeated until a single node remained. The resulting prefix code
(:func:`~engineeringkit.communications.huffman_code`) has the least average
length of any symbol-by-symbol code, within one bit of the entropy
(:func:`~engineeringkit.communications.entropy`), and reaches it exactly
when every probability is a power of one half.

.. GENERATED FROM PYTHON SOURCE LINES 17-22

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from engineeringkit.communications import entropy, huffman_code








.. GENERATED FROM PYTHON SOURCE LINES 23-27

Coding the letters of English
-----------------------------

Approximate single-letter frequencies of English text (space excluded).

.. GENERATED FROM PYTHON SOURCE LINES 27-46

.. code-block:: Python


    letters = "ETAOINSHRDLCUMWFGYPBVKJXQZ"
    freq = np.array(
        [12.7, 9.1, 8.2, 7.5, 7.0, 6.7, 6.3, 6.1, 6.0, 4.3, 4.0, 2.8, 2.8, 2.4, 2.4, 2.2, 2.0, 2.0, 1.9, 1.5, 1.0, 0.8, 0.15, 0.15, 0.1, 0.07]
    )
    p = freq / freq.sum()
    code = huffman_code(p)
    for letter, word in list(zip(letters, code.codewords))[:6]:
        print(f"{letter}: {word}")
    summary = code.summary()
    print(f"entropy {summary['entropy']:.3f} bit, Huffman {summary['average_length']:.3f} bit, fixed-length 5 bit")
    assert code.entropy <= code.average_length < code.entropy + 1
    assert np.isclose(sum(2.0**-code.lengths), 1)

    message = "HUFFMAN"
    bits = code.encode([letters.index(ch) for ch in message])
    assert "".join(letters[k] for k in code.decode(bits)) == message
    print(f"'{message}' takes {bits.size} bits instead of {5 * len(message)}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    E: 100
    T: 000
    A: 1110
    O: 1101
    I: 1011
    N: 1010
    entropy 4.177 bit, Huffman 4.206 bit, fixed-length 5 bit
    'HUFFMAN' takes 32 bits instead of 35




.. GENERATED FROM PYTHON SOURCE LINES 47-49

A dyadic source is coded exactly at its entropy
-----------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 49-63

.. code-block:: Python


    dyadic = huffman_code([0.5, 0.25, 0.125, 0.0625, 0.0625])
    print("dyadic codewords:", dyadic.codewords)
    assert np.isclose(dyadic.average_length, entropy([0.5, 0.25, 0.125, 0.0625, 0.0625]))

    fig, axes = plt.subplots(1, 2, figsize=(12, 3.8), gridspec_kw={"width_ratios": [3, 1]})
    code.plot(ax=axes[0])
    axes[0].set_xticks(np.arange(len(letters)), list(letters), rotation=0)
    axes[0].set(xlabel="letter", title="Huffman lengths follow $-\\log_2 p$")
    axes[1].bar(["entropy", "Huffman", "fixed"], [code.entropy, code.average_length, 5.0], color=["C2", "C0", "C7"])
    axes[1].set(ylabel="bit per letter")
    fig.tight_layout()

    plt.show()



.. image-sg:: /api/gallery/communications/information/images/sphx_glr_plot_06_huffman_code_001.png
   :alt: Huffman lengths follow $-\log_2 p$
   :srcset: /api/gallery/communications/information/images/sphx_glr_plot_06_huffman_code_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    dyadic codewords: ('0', '10', '110', '1110', '1111')





.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.184 seconds)


.. _sphx_glr_download_api_gallery_communications_information_plot_06_huffman_code.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/communications/information/plot_06_huffman_code.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_06_huffman_code.ipynb <plot_06_huffman_code.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_06_huffman_code.py <plot_06_huffman_code.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_06_huffman_code.zip <plot_06_huffman_code.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_