Fibonacci connection between Huffman codes and Wythoff array

From: Alex Vinokur (alexvn_at_big-foot.com)
Date: 10/08/04 

Date: Fri, 8 Oct 2004 14:57:28 +0200

Fibonacci connection between non-decreasing sequences of positive integers
producing maximum height Huffman trees and the Wythoff array has been proved.

http://arxiv.org/abs/cs.DM/0410013

                         Abstract
                         --------
   A non-decreasing sequence of positive integer weights
                P ={p[1], p[2],..., p(n-i)[n]}
is called k-ordered if an intermediate sequence
                P(i) ={p(i)[1], p(i)[2],..., p[n]}
of weights produced by Huffman algorithm for initial sequence P on i-th step
satisfy the following conditions:
                p(i)[2] = p(i)[3], 0 <= i <= k;
                p(i)[2] < p(i)[3], k+1 <= i <= n-3.
Let T be a binary tree of size n and M=M(T) be a set of such sequences of
positive integer weights that the tree T is the Huffman tree of P (|P|=n).
A sequence Pmin of n positive integer weights is called a minimizing sequence
of the binary tree T in the class M, if Pmin produces the minimal Huffman cost
of the tree T over all sequences from M.
   Fibonacci related connection between minimizing k-ordered sequences of
the maximum height Huffman tree and the Wythoff array [Sloane, A035513:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=035513,
http://www.research.att.com/~njas/sequences/classic.html]
has been proved.
   Let M[n,k] ( 0 <= k <= n-3) denote the set of all k-ordered sequences of size n for which the Huffman
tree has maximum height. Let F(i) denote i-th Fibonacci number.
Theorem: A minimizing k-ordered sequence of the maximum height Huffman tree
in the class M[n,k] is Pmin[n,k] = {p[1],..., p[n]} where
                p[1] = 1,
                p[2] = F(1),
                p[3] = F(2),
                ...,
                p[k+2] = F(k+1),
                p[k+3] = F(k+2) = w[F(k+2),0],
                p[k+4] = w[F(k+2),1],
                p[k+5] = w[F(k+2),2],
                ...,
                p[n] = w[F(k+2),n-k-3],
where w[i,j] is (i,j)-th element of the Wythoff array. The cost of Huffman
trees for those sequences has been computed. Several examples of minimizing
ordered sequences for Huffman codes are shown. 

-- 
 Alex Vinokur
     email: alex DOT vinokur AT gmail DOT com
     http://mathforum.org/library/view/10978.html
     http://sourceforge.net/users/alexvn

Relevant Pages

  • Re: Part 1 (of 3): What are major aspects of evolutionary theory?
    ... We see various sequences with various differences ... But when we reconstruct the states of the internal nodes of our ... Now if we construct an unrooted parsimony tree for those sequences, ... Now let's reconstruct the internal nodes by majority rule: ...
    (talk.origins)
  • Re: A few bonobo & chimp genes more related to our own
    ... In 453 of their sequences, ... What you get from homologous stretches of DNA from different species is a gene tree. ... This is usually pretty similar to the underlying species tree, but there are a variety of processes which can cause them to diverge. ... The gene tree has been incorrectly determined: that is, phylogenetic analysis has produced an estimated tree that doesn't match the true gene tree. ...
    (talk.origins)
  • Re: Part 1 (of 3): What are major aspects of evolutionary theory?
    ... We see various sequences with various differences ... By rooting the tree, or by assuming a molecular clock that roots the ... >>>What about duplications followed by later divergence of the copies? ... > clade of sponges becomes eumetazoans, the unrooted tree should look ...
    (talk.origins)
  • Re: Weirdos Irony Meter Just had a Blowout.
    ... organisms - which is what a phylogeny is SUPPOSED TO DO. ... trees are generated from sequences that ... I never said it was a phylogenetic tree'. ... above infinite tree of. ...
    (talk.origins)
  • Re: An uncountable countable set
    ... binary sequences, i.e ., infinite sequences whose terms were from a set ... And my tree shows that the complete set can be listed in form of a ... It is only the set of individualy infinite paths in that tree that are ...
    (sci.math)