Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Fibonacci numbers, Lucas numbers and Huffman codes
Replies: 1   Last Post: Sep 12, 2004 1:01 AM

 Messages: [ Previous | Next ]
 Alex Vinokur Posts: 35 Registered: 12/8/04
Fibonacci numbers, Lucas numbers and Huffman codes
Posted: Sep 8, 2004 4:12 AM

Huffman codes are closely connected with Fibonacci and Lucas numbers.
Here are some aspects of such a connection.

Note. This message is an updated version of the message titled
"Huffman codes and Fibonacci numbers" at
* <a href="http://mathforum.org/discuss/sci.math/t/207334">http://mathforum.org/discuss/sci.math/t/207334</a>

####################### 1 #######################

1. Preface
==========

Definition 1.0. A strictly binary tree is a binary tree where
each non-terminal node (nonleaf) has exactly two children.

Further when we talk about binary trees, we mean strictly binary trees.

Definition 1.1. A binary tree size is number of its terminal nodes (leaves).

Definition 1.2. A number sequence size is number of its elements.

Let T(n) denote the binary tree of size n.
-------------------------------------

Let Q(n) denote the sequence of size n.
----------------------------------

Definition 1.3. The sequence Q(n) is called T(n)-Huffman sequence
if T(n) is binary Huffman tree for the sequence Q(n).

Let S(Q) denote Huffman cost of the sequence Q(n)
---------------------------------------------
(i.e., the weighted path length of the binary tree T(n)
for the sequence Q(n)).

Let M be some class of T(n)-Huffman sequences.
-----------------------------------------

Definition 1.4. T(n)-Huffman sequence Qmin(n) is called
a minimizing Huffman sequence (on T(n)) in class M
if S(Qmin) &lt;= S(Q) for any Q belonging to M.

Definition 1.5. T(n)-Huffman sequence Qmax(n) is called
a maximizing Huffman sequence (on T(n)) in class M
if S(Qmax) &gt;= S(Q) for any Q belonging to M.

Definition 1.6. A binary tree is called elongated
if at least one of any two sibling nodes is terminal.
An elongated binary tree is called left-sided
if the left node in each pair of sibling nodes is terminal.

Note. Elongated binary tree of size n has maximum height
among all binary trees of size n.

Let LEFT(n) denote the left-sided binary tree of size n.
---------------------------------------------------

Let F(n) denote n-th Fibonacci number, i.e., F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2) when n &gt; 2.
---------------------------------

Let L(n) denote n-th Lucas number, i.e., L(1) = 1, L(2) = 3, L(n) = L(n-1) + L(n-2) when n &gt; 2.
-----------------------------

-----------------------------------------------------------------
----------------- Example 1.1 -----------------------------------
----------------- Left-sided Huffman binary tree ----------------
----------------- for sequence {w(1), w(2), ..., w(n)} ----------
----------------- (n = 6) ---------------------------------------

s5 l(i) = the path length from the tree root
/\ to the i-th terminal node
/ s4 w(6) w(i) = the i-th terminal node weight
/ / \ n = size(T) = number of terminal nodes
s3 w(5) (Huffman code size)
/ / \ h(T) = max l(i), 1 &lt;= i &lt;= n
s2 w(4)
/ / \ E(T) = sum l(i), 1 &lt;= i &lt;= n
s1 w(3)
/ / \ S(T) = sum (w(i) * l(i)), 1 &lt;= i &lt;= n
w(1) w(2)

h(T) is the height of the binary tree T.

E(T) is the path length of the binary tree T.

S(T) is the weighted path length of the binary tree T
for the sequence {w(1), w(2), ..., w(n)},
i.e., S(T) is Huffman cost of T.

s1 = w(1) + w(2)
s2 = s1 + w(3)
s3 = s2 + w(4)
s4 = s3 + w(5)
s5 = s4 + w(6)

Tree 1.1 - Left-sided Huffman binary tree T

-----------------------------------------------------------------

####################### 2 #######################

2. Huffman codes (trees) and minimizing properties of Fibonacci and Lucas numbers.
==============================================================================

Let 1) B = {b1, b2, ..., b#n} be a non-decreasing sequence
of positive integers; size (B) = n.
2) C(B,k) = {c1, c2, ..., c#(n-k)} be a non-decreasing sequence
after k-th stage of the Huffman algorithm (k = 0, 1, ..., n-1);
size of (C(B,k)) = n-k.

Example.
B = 3, 4, 6, 9, 10, 20
C(B,1) = 6, (7), 9, 10, 20
C(B,2) = 9, 10, (13), 20
C(B,3) = (13), (19), 20
C(B,4) = 20, (32)
C(B,5) = (52)

Definition 2.1. A sequence B is called strict
if c2 &lt; c3 in each sequence C(B,k) (k = 1, ..., n-3)

Definition 2.2. A strict sequence B is called absolutely strict
if b2 &lt; b3.

Definition 2.3. A sequence B is called non-strict
if there is a sequence C(B,k) ( 1 &lt;= k &lt;= (k-3) )
in which c2 = c3.
Note. If B is not strict (according to Definition 2.1)
then B is non-strict (according to Definition 2.3).

Definition 2.4. A non-strict sequence B is called alternative
(or absolutely non-strict)
if c2 = c3 in every sequence C(B,k) ( 1 &lt;= k &lt;= (k-3) )
and b2 = b3.

Let 1) SET-OF-ABS-STRICT-SEQUENCES denote the set of such absolutely strict sequences
for which the binary Huffman tree is elongated;
2) SET-OF-STRICT-SEQUENCES denote the set of such strict sequences
for which the binary Huffman tree is elongated;
3) SET-OF-ALL-SEQUENCES denote the set of all (strict and non-strict) sequences
for which the binary Huffman tree is elongated.

Let Phi = (1+sqrt(5))/2.
-------------------

Theorem 2.1. * The Fibonacci sequence U(n) = {F(1), F(2), ..., F(n)} =
= {1, 1, 2, 3, 5, 8, ...}
is a minimizing Huffman sequence
on a left-sided binary tree LEFT(n)
in class SET-OF-ABS-STRICT-SEQUENCES
(See Definition 1.4 and Definition 2.2).
* The Huffman cost S(U(n)) = F(n+4) - (n+4).
* S(U(n)) asymptotic = (Phi^(n+4))/sqrt(5).

Theorem 2.2. * The double shifted Lucas sequence V(n) = {1, 1, L(1), ..., L(n-2)} =
= {1, 1, 1, 3, 4, 11, ...}
is a minimizing Huffman sequence
on a left-sided binary tree LEFT(n)
in class SET-OF-STRICT-SEQUENCES
(See Definition 1.4 and Definition 2.1).
* The Huffman cost S(V(n)) = F(n+4) - F(n) - (n+3).
* S(V(n)) asymptotic = ((Phi^n) * (Phi^4 - 1))/sqrt(5).

Theorem 2.3. * The shifted Fibonacci sequence Y(n) = {1, F(1), ..., F(n-1)} =
= {1, 1, 1, 2, 3, 5, ...}
is a minimizing Huffman sequence
on a left-sided binary tree LEFT(n)
in class SET-OF-ALL-SEQUENCES
(See Definition 1.4 and Definitions 2.1 - 2.3).
* The Huffman cost S(Y(n)) = F(n+3) - 3.
* S(Y(n)) asymptotic = (Phi^(n+3))/sqrt(5).

Corollary 2.1. The non-strict sequence Y(n) (See Theorem 2.3)
is alternative (See Definition 2.4).

Corollary 2.2. For the alternative sequence Y(n), n &gt;= 3
(See Theorem 2.3) there exist 2^(n-3) different
elongated binary Huffman trees
(one of them is left-sided).

-----------------------------------------------------------------
----------------- Example 2.1 -----------------------------------
----------------- Minimizing Huffman sequence -------------------
----------------- on a left-sided binary tree LEFT(n) -----------
----------------- in class SET-OF-ABS-STRICT-SEQUENCES ----------
----------------- (n = 6) ---------------------------------------
----------------- (See Theorem 2.1) -----------------------------

20 l(1) = 5, l(2) = 5, l(3) = 4.
/\ l(4) = 3, l(5) = 2, l(6) = 1
/ 12 8 w(1) = 1, w(2) = 1, w(3) = 2,
/\ w(4) = 3, w(5) = 5, w(6) = 8
/ 7 5 n = size(T) = 6
/ / \ h(T) = max l(i) = 5
4 3 i
/ / \ E(T) = sum l(i) = 20
2 2 i
/ / \ S(T) = sum (w(i) * l(i)) = 45
1 1 i

Note! S(T) = F(n+4) - (n+4) = F(10) - 10 = 55 - 10

Tree 2.1 - Left-sided Huffman binary tree
for minimizing Huffman sequence
in class SET-OF-ABS-STRICT-SEQUENCES

Huffman algorithm stages :
Source sequence U : 1, 1, 2, 3, 5, 8 u(2) &lt; u(3)
After stage#1 C(U,1) : 2, (2), 3, 5, 8 c(2) &lt; c(3)
After stage#2 C(U,2) : 3, (4), 5, 8 c(2) &lt; c(3)
After stage#3 C(U,3) : 5, (7), 8 c(2) &lt; c(3)
After stage#4 C(U,4) : 8, (12)
After stage#5 C(U,5) : (20)

-----------------------------------------------------------------

-----------------------------------------------------------------
----------------- Example 2.2 -----------------------------------
----------------- Minimizing Huffman sequence -------------------
----------------- on a left-sided binary tree LEFT(n) -----------
----------------- in class SET-OF-STRICT-SEQUENCES --------------
----------------- (n = 6) ---------------------------------------
----------------- (See Theorem 2.2) -----------------------------

17 l(1) = 5, l(2) = 5, l(3) = 4.
/\ l(4) = 3, l(5) = 2, l(6) = 1
/ 10 7 w(1) = 1, w(2) = 1, w(3) = 1,
/\ w(4) = 3, w(5) = 4, w(6) = 7
/ 6 4 n = size(T) = 6
/ / \ h(T) = max l(i) = 5
3 3 i
/ / \ E(T) = sum l(i) = 20
2 1 i
/ / \ S(T) = sum (w(i) * l(i)) = 38
1 1 i

Note! S(T) = F(n+4) - F(n) - (n+3) = F(10) - F(6) - 9 = 55 - 8 - 9

Tree 2.2 - Left-sided Huffman binary tree
for minimizing Huffman sequence
in class SET-OF-STRICT-SEQUENCES

Huffman algorithm stages :
Source sequence V : 1, 1, 1, 3, 4, 7 v(2) = v(3)
After stage#1 C(V,1) : 1, (2), 3, 4, 7 c(2) &lt; c(3)
After stage#2 C(V,2) : 3, (3), 4, 7 c(2) &lt; c(3)
After stage#3 C(V,3) : 4, (6), 7 c(2) &lt; c(3)
After stage#4 C(V,4) : 7, (10)
After stage#5 C(V,5) : (17)

-----------------------------------------------------------------

-----------------------------------------------------------------
----------------- Example 2.3.1 ---------------------------------
----------------- Minimizing Huffman sequence -------------------
----------------- on a left-sided binary tree LEFT(n) -----------
----------------- in class SET-OF-ALL-SEQUENCES -----------------
----------------- (n = 6) ---------------------------------------
----------------- (See Theorem 2.3) -----------------------------

13 l(1) = 5, l(2) = 5, l(3) = 4.
/\ l(4) = 3, l(5) = 2, l(6) = 1
/ 8 5 w(1) = 1, w(2) = 1, w(3) = 1,
/\ w(4) = 2, w(5) = 3, w(6) = 5
/ 5 3 n = size(T) = 6
/ / \ h(T) = max l(i) = 5
3 2 i
/ / \ E(T) = sum l(i) = 20
2 1 i
/ / \ S(T) = sum (w(i) * l(i)) = 31
1 1 i

Note! S(T) = F(n+3) - 3 = F(9) - 3 = 34 - 3

Tree 2.3.1 - Left-sided Huffman binary tree
for minimizing Huffman sequence
in class SET-OF-ALL-SEQUENCES

Huffman algorithm stages :
Source sequence Y : 1, 1, 1, 2, 3, 5 y(2) = y(3)
After stage#1 C(Y,1) : 1, (2), 2, 3, 5 c(2) = c(3)
After stage#2 C(Y,2) : 2, (3), 3, 5 c(2) = c(3)
After stage#3 C(Y,3) : 3, (5), 5 c(2) = c(3)
After stage#4 C(Y,4) : 5, (8)
After stage#5 C(Y,5) : (13)

Note. Compare with Example 2.3.2.

-----------------------------------------------------------------

-----------------------------------------------------------------
----------------- Example 2.3.2 ---------------------------------
----------------- Non-minimizing Huffman sequence ---------------
----------------- on a left-sided binary tree LEFT(n) -----------
----------------- in class SET-OF-ALL-SEQUENCES -----------------
----------------- (n = 6) ---------------------------------------

14 l(1) = 5, l(2) = 5, l(3) = 4.
/\ l(4) = 3, l(5) = 2, l(6) = 1
/ 8 6 w(1) = 1, w(2) = 1, w(3) = 1,
/\ w(4) = 2, w(5) = 3, w(6) = 6
/ 5 3 n = size(T) = 6
/ / \ h(T) = max l(i) = 5
3 2 i
/ / \ E(T) = sum l(i) = 20
2 1 i
/ / \ S(T) = sum (w(i) * l(i)) = 32
1 1 i

Tree 2.3.2 - Left-sided Huffman binary tree
for non-minimizing Huffman sequence
in class SET-OF-ALL-SEQUENCES

Huffman algorithm stages :
Source sequence X : 1, 1, 1, 2, 3, 6 x(2) = x(3)
After stage#1 C(X,1) : 1, (2), 2, 3, 6 c(2) = c(3)
After stage#2 C(X,2) : 2, (3), 3, 6 c(2) = c(3)
After stage#3 C(X,3) : 3, (5), 6 c(2) &lt; c(3)
After stage#4 C(X,4) : 6, (8)
After stage#5 C(X,5) : (14)

Note. Compare with Example 2.3.1.

-----------------------------------------------------------------

####################### 3 #######################

3. Huffman codes (trees) and maximizing properties of Fibonacci numbers.
====================================================================

Definition 3.1. A sequence P = {p1, p2, ..., p#n} of positive numbers
is called a non-decreasing normalized sequence
if sum (p#i) = 1, i = {1, 2, ..., n}; size (P) = n.

Let SET-OF-NORM-SEQUENCES denote the set
of all non-decreasing normalized sequences (of positive numbers)
for which the binary Huffman tree is elongated.

Theorem 3.1. * The sequence Z(n) =
= {1/F(n+1), F(1)/F(n+1), F(2)/F(n+1), ..., F(n-1)/F(n+1)}
is a maximizing Huffman sequence
on a left-sided binary tree LEFT(n) in class SET-OF-NORM-SEQUENCES
(See Definition 1.5).
* The Huffman cost S(Z(n)) = 2 + (F(n) - 3)/F(n+1).
* S(Z(n)) asymptotic = (3 + sqrt(5))/2 = 2.6180

-----------------------------------------------------------------
----------------- Example 3.1.1 ---------------------------------
----------------- Maximizing Huffman sequence -------------------
----------------- on a left-sided binary tree LEFT(n) -----------
----------------- in class SET-OF-NORM-SEQUENCES ----------------
----------------- (n = 6) ---------------------------------------
----------------- (See Theorem 3.1) -----------------------------

* l(1) = 5, l(2) = 5, l(3) = 4.
/\ l(4) = 3, l(5) = 2, l(6) = 1
/ * 5/13 w(1) = 1/13, w(2) = 1/13, w(3) = 1/13,
/\ w(4) = 2/13, w(5) = 3/13, w(6) = 5/13
/ * 3/13 n = size(T) = 6
/ / \ h(T) = max l(i) = 5
* 2/13 i
/ / \ E(T) = sum l(i) = 20
* 1/13 i
/\ 31
/ \ S(T) = sum (w(i) * l(i)) = -- = 2.3846
1/13 1/13 i 13

Note! S(T) = 2 + (F(n) - 3)/F(n+1) = 2 + (F(6) - 3)/F(7) = 2 + (8 - 3)/13.

Tree 3.1.1 - Left-sided Huffman binary tree
for maximizing Huffman sequence
in class SET-OF-NORM-SEQUENCES

Huffman algorithm stages : See Example 2.3.1

Note. Compare with Example 3.1.2.

-----------------------------------------------------------------

-----------------------------------------------------------------
----------------- Example 3.1.2 ---------------------------------
----------------- Non-maximizing Huffman sequence ---------------
----------------- on a left-sided binary tree LEFT(n) -----------
----------------- in class SET-OF-NORM-SEQUENCES ----------------
----------------- (n = 6) ---------------------------------------

* l(1) = 5, l(2) = 5, l(3) = 4.
/\ l(4) = 3, l(5) = 2, l(6) = 1
/ * 6/14 w(1) = 1/14, w(2) = 1/14, w(3) = 1/14,
/\ w(4) = 2/14, w(5) = 3/14, w(6) = 6/14
/ * 3/14 n = size(T) = 6
/ / \ h(T) = max l(i) = 5
* 2/14 i
/ / \ E(T) = sum l(i) = 20
* 1/14 i
/\ 32
/ \ S(T) = sum (w(i) * l(i)) = -- = 2.2857
1/14 1/14 i 14

Tree 3.1.2 - Left-sided Huffman binary tree
for non-maximizing Huffman sequence
in class SET-OF-NORM-SEQUENCES

Huffman algorithm stages : See Example 2.3.2

Note. Compare with Example 3.1.1.

-----------------------------------------------------------------

####################### 4 #######################

4. Huffman codes (trees) and contrast properties of Fibonacci numbers.
===================================================================

By Theorem 2.3, The integer sequence Y(n) = {1, F(1), F(2), ..., F(n-1)}
is minimizing integers Huffman sequence of size n
on a left-sided binary tree LEFT(n).
(See Example 2.3.1 and Example 2.3.2).

When the the sequence Y(n) is normalized, i.e., each of its elements
is divided by the sum of all elements (equal to F(n+1)),
its extremal properties are reversed:
By Theorem 3.1, the normalized sequence Z(n) =
= {1/F(n+1), F(1)/F(n+1), F(2)/F(n+1), ..., F(n-1)/F(n+1)}
is maximizing normalized Huffman sequence of size n
on a left-sided binary tree LEFT(n).
(See Example 3.1.1 and Example 3.1.2).

#################################################

For more details please see :
1. Vinokur A.B., Huffman trees and Fibonacci numbers
// Kibernetika (Kiev). - 1986. - No. 6. - pp. 9-12; -
Translated into English - pp. 692-696.
2. Vinokur A.B., Huffman codes and maximizing properties of Fibonacci numbers
// Kibernetika i Systemyi Analiz (Kiev). - 1992. - No. 3. - pp. 10-15; -
Translated into English - pp. 329-334.

#################################################

--
Alex Vinokur
<a href="http://mathforum.org/library/view/10978.html">http://mathforum.org/library/view/10978.html</a>
<a href="http://sourceforge.net/users/alexvn">http://sourceforge.net/users/alexvn</a>

Date Subject Author
9/8/04 Alex Vinokur
9/12/04 Alex Vinokur