Here are my outputs for the 4 files. If anyone wants to see my tables I will add them. For now I'll just output everything else my program generates.

Test file 1:

abababab
a converts to 0
b converts to 1
ab converts to 2
aba converts to 4
b converts to 1

<Table>
Number of input symbols(8) * 8 bits: 64 bits
There are 6 elements in the table.
To represent 6 elements we need at least 3 bits
There were 5 reductions.
5 reductions * 3 bits = 15 bits.
Compression ratio is 15 / 64 = 0.234375

Test file 2:

abbaabbaababbaaaabaabba
a converts to 0
b converts to 1
b converts to 1
a converts to 0
ab converts to 2
ba converts to 4
ab converts to 2
abb converts to 6
aa converts to 5
aa converts to 5
baa converts to 7
bb converts to 3
a converts to 0

<Table>

Number of input symbols(23) * 8 bits: 184 bits
There are 14 elements in the table.
To represent 14 elements we need at least 4 bits
There were 13 reductions.
13 reductions * 4 bits = 52 bits.
Compression ratio is 52 / 184 = 0.2826086956521739

Test file 3:

xxyyxyxyxxyyyxyxxyxxyyx
x converts to 0
x converts to 0
y converts to 1
y converts to 1
xy converts to 3
xyx converts to 6
xy converts to 3
yy converts to 4
xyxx converts to 7
yx converts to 5
xyy converts to 8
x converts to 0

<Table>

Number of input symbols(23) * 8 bits: 184 bits
There are 13 elements in the table.
To represent 13 elements we need at least 4 bits
There were 12 reductions.
12 reductions * 4 bits = 48 bits.
Compression ratio is 48 / 184 = 0.2608695652173913

Test file 4:

I'm not going to output the reductions for this one, its too long. I'll just show what I got for the last part.

Number of input symbols(1011) * 8 bits: 8088 bits
There are 256 elements in the table.
To represent 256 elements we need at least 8 bits
There were 602 reductions.
602 reductions * 8 bits = 4816 bits.
Compression ratio is 4816 / 8088 = 0.5954500494559841

-Todd

Test 1 Out:

The original input was:
abababab

Dictionary
 IntIndex       ByteIndex         String
-------------------------------------------------
|       0              0                a    |
|       1              1                b    |
|       2             10               ab    |
|       3             11               ba    |
|       4            100              aba    |
|       5            101             abab    |
-------------------------------------------------
In integer notation your input is compressed to:
0 1 2 4 1
In binary notation your input is compressed to:
000, 001, 010, 100, 001,

The compression ratio [15/64] is 0.234375

Test 2 out:

The original input was:
abbaabbaababbaaaabaabba

Dictionary
 IntIndex       ByteIndex         String
-------------------------------------------------
|       0              0                a    |
|       1              1                b    |
|       2             10               ab    |
|       3             11               bb    |
|       4            100               ba    |
|       5            101               aa    |
|       6            110              abb    |
|       7            111              baa    |
|       8           1000              aba    |
|       9           1001             abba    |
|      10           1010              aaa    |
|      11           1011              aab    |
|      12           1100             baab    |
|      13           1101              bba    |
-------------------------------------------------
In integer notation your input is compressed to:
00 01 01 00 02 04 02 06 05 05
07 03 00
In binary notation your input is compressed to:
0000, 0001, 0001, 0000, 0010,
0100, 0010, 0110, 0101, 0101,
0111, 0011, 0000,
The compression ratio [52/184] is 0.2826086956521739

Test 3 output:

The original input was:
xxyyxyxyxxyyyxyxxyxxyyx

Dictionary
 IntIndex       ByteIndex         String
-------------------------------------------------
|       0              0                x    |
|       1              1                y    |
|       2             10               xx    |
|       3             11               xy    |
|       4            100               yy    |
|       5            101               yx    |
|       6            110              xyx    |
|       7            111             xyxx    |
|       8           1000              xyy    |
|       9           1001              yyx    |
|      10           1010            xyxxy    |
|      11           1011              yxx    |
|      12           1100             xyyx    |
-------------------------------------------------
In integer notation your input is compressed to:
00 00 01 01 03 06 03 04 07 05
08 00
In binary notation your input is compressed to:
0000, 0000, 0001, 0001, 0011,
0110, 0011, 0100, 0111, 0101,
1000, 0000,
The compression ratio [48/184] is 0.2608695652173913

Test 4 output:

The compression ratio [5130/8088] is 0.634272997032641

Can someone else please upload their results so we can compare the output of test4 since the two of us got different answers...

-bort

My new Test4

The compression ratio [4560/8088] is 0.5637982195845698

my index was incrementing before it calculated the number of bits required... I believe that my answer is correct now

Ya I calculate the number of bits at the end, but its not dependent on the number of characters directly...

I am using a ceiling function on Log₂ of the number of dictionary indexes that there are.

Bits = Ceiling(Log₂(Total Number of Dictionary Entries))

I was getting the wrong number because at the end of one of my for loops on the last iteration I incremented the index even though I did not add anything to the dictionary...

So my answer was being multiplied by 9 bits instead of 8 bits...

cbort wrote:

My new Test4

The compression ratio [4560/8088] is 0.5637982195845698

.