[LRUG] How would you turn a bit stream into a character stream?

[James Coglan]

On 11 June 2012 13:56, James Coglan <jcoglan at gmail.com> wrote:

> I have a problem I'm not sure how to solve, more of a general programming
> problem than a Ruby thing. Basically, say you have an indefinite stream of
> random bits:
>
> 1100111001110110101100000110101011011110110011111001101000001000111000100000011001111110100010000001000001111110100010010100111111011101110110011111001101010101101111111011101111111000010001001001100100100101011100001001000001110101011101101101010011100111
> ...
>
> and you want to turn it into a stream of characters from an arbitrary-size
> list of characters, let's say the 26 letters from A to Z. You want the
> letters to be evenly distributed in the output; each letter should have an
> equal probability of appearing.
>

As an illustration, my current approach is to pop as many bits as I can off
the front of the stream such that they give a number up to the size of the
set. This produces a bias where some characters are 3x as likely to appear
as others:

{ '0': 3102,
  '1': 3160,
  '2': 3094,
  '3': 3070,
  '4': 3167,
  '5': 3185,
  '6': 3118,
  '7': 3197,
  '8': 3230,
  '9': 3096,
  '10': 3109,
  '11': 3072,
  '12': 3087,
  '13': 9375,
  '14': 9362,
  '15': 9291,
  '16': 3137,
  '17': 3166,
  '18': 3134,
  '19': 3190,
  '20': 3102,
  '21': 3060,
  '22': 3109,
  '23': 3176,
  '24': 3049,
  '25': 3162 }
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20120611/6ccfa2da/attachment-0003.html>