Results 1 to 1 of 1

Thread: Paq mixer theory

  1. #1
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,267
    Thanks
    200
    Thanked 985 Times in 511 Posts

    Paq mixer theory

    Suppose we have two bit sources with static probabilities
    p1 and p2, and a switching scheme added to that (static too) -
    bits are taken from 1st or 2nd source with a probability w.

    Then, let's say, we have N0 zeros and N1 ones in
    the already processed data, so:

    N01 = N0*w; N02 = N0*(1-w)
    N11 = N1*w; N12 = N1*(1-w)
    p1^N01 * p2^N02 * (1-p1)^N11 * (1-p2)^N12

    is a probability of a bit string like that appearing
    from switching sources with p1,p2,w as parameters.
    (aka "likelihood" of these parameters)

    (p1^w * p2^(1-w))^N0 * ((1-p1)^w * (1-p2)^(1-w))^N1

    and, supposing we'd add another bit to the string:

    l0 = (p1^w * p2^(1-w))^(N0+1) * ((1-p1)^w * (1-p2)^(1-w))^N1
    l1 = (p1^w * p2^(1-w))^N0 * ((1-p1)^w * (1-p2)^(1-w))^(N1+1)

    Thus,

    P(bit==0) = l0/(l0+l1) =
    p1^w * p2^(1-w) / (p1^w * p2^(1-w) + (1-p1)^w * (1-p2)^(1-w))

    which can be rewritten as

    1/(1 + (p1/(1-p1))^-w * p2/(1-p2)^(-1+w) )

    ...which is what paq mixer does.

    Edit: also that - http://nishi.dreamhosters.com/u/stems5.png -
    is how the paq mixer update can be derived.
    Last edited by Shelwien; 22nd November 2009 at 02:18.

Similar Threads

  1. PAQ turns up in the most unlikely places
    By willvarfar in forum Data Compression
    Replies: 0
    Last Post: 27th May 2010, 10:19
  2. Spec for portable PAQ
    By Matt Mahoney in forum Data Compression
    Replies: 40
    Last Post: 7th February 2009, 19:05
  3. M01 - Order 01 context mixer
    By toffer in forum Data Compression
    Replies: 58
    Last Post: 17th June 2008, 18:29
  4. Mixer vs 2D SSE
    By Shelwien in forum Forum Archive
    Replies: 26
    Last Post: 8th March 2008, 12:58
  5. can someone help me compiling paq by myself?
    By noshutdown in forum Forum Archive
    Replies: 4
    Last Post: 4th December 2007, 09:49

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •