Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1196

Re: how to combine the probability of disjoint symbol models?

Show all headers | View raw

Input stream: 10011010100010

It is 14 bits long.
The minimum symbol size for an alphabet in which no symbol is used more than once with in the input stream is 3 bits.

Thus the starting alphabet consits of 8 symbols:

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

so for each "symbol" in the input:

** Step 1 **

Remaining input 10011010100010
input Symbol: 100

Symbol Table:

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Bits needed per symbol: 3

output symbol index: 4

output stream: 4


** Step 2 **

Remaining input 11010100010
input Symbol: 110

Symbol Table:

0 000
1 001
2 010
3 011
4 101
5 110
6 111

Bits needed per symbol: 2.81

output symbol index: 5

output stream: 4 5


** Step 3 **

Remaining input 10100010
input Symbol: 101

Symbol Table:

0 000
1 001
2 010
3 011
4 101
5 111

Bits needed per symbol: 2.58

output symbol index: 4

output stream: 4 5 4



** Step 4 **

Remaining input 00010
input Symbol: 000

Symbol Table:

0 000
1 001
2 010
3 011
4 111

Bits needed per symbol: 2.32

output symbol index: 0

output stream: 4 5 4 0




This totals 10.71 bits to encode the output + the remaining 2 bits = 12.71 bits

This example does of course not include the overhead of storing the size of the input symbols. But for larger input stream sizes I expect that the cost of storing the symbol size will be overcome by the saving.

On reflection, there is no need to indicate when the remainder bits are to be copied as this is readily determined when we reach EOF without reading in a complete input symbol.

This should give the idea of what i am proposing.

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 05:35 -0700
  Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 05:36 -0700
  Re: how to combine the probability of disjoint symbol models? biject <biject.bwts@gmail.com> - 2012-03-22 07:36 -0700
    Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 17:48 -0700
  Re: how to combine the probability of disjoint symbol models? Thomas Richter <thor@math.tu-berlin.de> - 2012-03-22 17:04 +0100
    Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 20:02 -0700
      Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 21:02 -0700
        Re: how to combine the probability of disjoint symbol models? biject <biject.bwts@gmail.com> - 2012-03-22 21:29 -0700
          Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 22:38 -0700
  Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-23 05:42 -0700

csiph-web