OFFSET
0,2
COMMENTS
The Ziv-Lempel encoding scans the sequence from left to right and inserts a comma when the current phrase is an extension by one bit of an earlier phrase. In any case the scan ends with a comma. The phrases are the segments between the commas.
Equivalent sequences necessarily have the same Hamming weight.
REFERENCES
J. Ziv and A. Lempel, A universal algorithm for sequential data compression. IEEE Trans. Information Theory IT-23 (1977), 337-343.
LINKS
G. Seroussi, On universal types, Preprint, 2004.
G. Seroussi, On the number of t-ary trees with a given path length, Algorithmica 46(3), 557-565, 2006; arXiv:cs/0509046 [cs.DM], 2005-2007.
FORMULA
Seroussi shows that a(n) is asymptotically 2^{2cn/log_2(n)(1+o(1))}, where c = 0.11... is the inverse entropy function of 1/2.
EXAMPLE
The Ziv-Lempel encodings of the strings of lengths 1 through 3 are:
0,
1, so a(1)=2;
0,0,
0,1,
1,0, (same phrases as in previous line)
1,1, so a(2)=3;
0,00,
0,01,
0,1,0,
1,0,0, (same phrases as in previous line)
0,1,1,
1,0,1, (same phrases as in previous line)
1,10,
1,11, so a(3)=6; ...
PROG
(Tcl)
proc compress_phrases {vec} {set cur []; foreach v $vec {lappend cur $v
if {![info exists phrases($cur)]} {set phrases($cur) 1; set cur []}}
set plist [array names phrases]; if {[llength $cur]} {lappend plist $cur}
return [lsort $plist]}
proc enum {n vec} {if {$n == 0} {global phraselists
set phraselists([compress_phrases $vec]) 1} else {incr n -1
enum $n [concat $vec [list 0]]; enum $n [concat $vec [list 1]]}}
proc doit {} {global phraselists; set n 0; while {1} {array unset phraselists
enum $n []; puts -nonewline "[array size phraselists], "; flush stdout; incr n}}
doit
CROSSREFS
KEYWORD
nonn,hard
AUTHOR
N. J. A. Sloane, Aug 23 2005
EXTENSIONS
Terms from a(6) onwards from David Applegate, Aug 29 2005
Terms a(0)-a(20) confirmed and a(21)-a(25) added by John W. Layman, Sep 20 2010
STATUS
approved