473,320 Members | 2,110 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

creating very small types

I was thinking to code the huffman algorithm and trying to compress
something with it, but I've got a problem.
How can I represent for example a char with only 3 bits??
I had a look to the compression modules but I can't understand them much...

Thank you very much
Any good link would be appreciated of course :)
Jul 19 '05 #1
7 1420
On Wed, 27 Apr 2005 22:17:07 +0200, andrea wrote:
I was thinking to code the huffman algorithm and trying to compress
something with it, but I've got a problem.
How can I represent for example a char with only 3 bits??
I had a look to the compression modules but I can't understand them much...

Thank you very much
Any good link would be appreciated of course :)


I think the answer to this question very much depends on why you want to
do this. Easy and fast are pretty opposed in this particular domain in
Python (IMHO anyways, it's an easy bit-bashing language but it's slow
for that), and you're in one of the rare domains where it matters.

The answers strongly vary if you're trying to create something performant,
or just for your learning purposes. Or homework purposes... ;-)

Jul 19 '05 #2
Jeremy Bowers wrote:
On Wed, 27 Apr 2005 22:17:07 +0200, andrea wrote:
I was thinking to code the huffman algorithm and trying to compress
something with it, but I've got a problem.
How can I represent for example a char with only 3 bits??
I had a look to the compression modules but I can't understand them much...

Thank you very much
Any good link would be appreciated of course :)


I think the answer to this question very much depends on why you want to
do this. Easy and fast are pretty opposed in this particular domain in
Python (IMHO anyways, it's an easy bit-bashing language but it's slow
for that), and you're in one of the rare domains where it matters.

The answers strongly vary if you're trying to create something performant,
or just for your learning purposes. Or homework purposes... ;-)

No it's not for homework but for learning purposes...
I understand I can't do it easily in python, but maybe I could define a
new type in C and use it to do those dirty works, what do you think?
Jul 19 '05 #3
andrea wrote:
I was thinking to code the huffman algorithm and trying to compress
something with it, but I've got a problem.
How can I represent for example a char with only 3 bits?? I had a look to the compression modules but I can't understand them much...
.... I understand I can't do it easily in python, but maybe I could define a
new type in C and use it to do those dirty works, what do you think?


Why do you need to create 'very small types'?

You only need actual bit-twiddling when you do the encoding/de-coding right?
If you create an encoding map 'codes' as a dict of strings of '1' and '0',
encoding might look like (untested):
def encode(stream):
outchar = count = 0
for char in stream:
for bit in codes[char]:
(outchar << 1) | (bit == "1")
count +=1
if count ==8:
yield chr(outchar)
outchar = count = 0
if count:
yield chr(outchar)
HTH
Michael

Jul 19 '05 #4
Michael Spencer wrote:
andrea wrote:
I was thinking to code the huffman algorithm and trying to compresssomething with it, but I've got a problem.
How can I represent for example a char with only 3 bits??I had a look to the compression modules but I can't understand
them much...
...
I understand I can't do it easily in python, but maybe I could
define a new type in C and use it to do those dirty works, what do you

think?
Why do you need to create 'very small types'?

You only need actual bit-twiddling when you do the encoding/de-coding right? If you create an encoding map 'codes' as a dict of strings of '1' and '0', encoding might look like (untested):

def encode(stream):
outchar = count = 0
for char in stream:
for bit in codes[char]:
(outchar << 1) | (bit == "1")
count +=1
if count ==8:
yield chr(outchar)
outchar = count = 0
if count:
yield chr(outchar)


I wrote some Huffman compression code a few years ago, with

class BitWriter(object):
# writes individual bits to an output stream
def __init__(self, outputStream):
self.__out = outputStream
self.__bitCount = 0 # number of unwritten bits
self.__currentByte = 0 # buffer for unwritten bits
def write(self, bit):
self.__currentByte = self.__currentByte << 1 | bit
self.__bitCount += 1
if self.__bitCount == BYTE_SIZE:
self.__out.write(chr(self.__currentByte))
self.__bitCount = 0
self.__currentByte = 0
def flush(self):
while self.__bitCount > 0:
self.write(0)

class BitReader(object):
# reads individual bits from an input stream
def __init__(self, inputStream):
self.__in = inputStream
self.__bits = [] # buffer to hold incoming bits
def readBit(self):
if len(self.__bits) == 0:
# read the next byte
b = ord(self.__in.read(1))
# unpack the bits
self.__bits = [(b & (1<<i)) != 0 for i in range(BYTE_SIZE-1,
-1, -1)]
return self.__bits.pop(0)

Jul 19 '05 #5
On Wed, 27 Apr 2005 15:54:54 -0700, Michael Spencer <ma**@telcopartners.com> wrote:
andrea wrote:
I was thinking to code the huffman algorithm and trying to compress
something with it, but I've got a problem.
How can I represent for example a char with only 3 bits??I had a look to the compression modules but I can't understand them much...
...
I understand I can't do it easily in python, but maybe I could define a
new type in C and use it to do those dirty works, what do you think?


Why do you need to create 'very small types'?

You only need actual bit-twiddling when you do the encoding/de-coding right?
If you create an encoding map 'codes' as a dict of strings of '1' and '0',
encoding might look like (untested):
def encode(stream):
outchar = count = 0
for char in stream:
for bit in codes[char]:
(outchar << 1) | (bit == "1")
count +=1
if count ==8:
yield chr(outchar)
outchar = count = 0
if count:

outchar <<= 8-count # make last bit field big-endian like others? yield chr(outchar)

I think I prefer little-endian bit streams though, e.g. (just hacked, not tested beyond
what you see and not recommended as efficient either way, esp the decode, but it might
be illustrative of something for Andrea ;-)

----< trivcodec.py >------------------------------------------------
#trivcodec.py
def encode(stream):
outchar = count = 0
for char in stream:
#print '%r code: %r'%(char, codes[char])
bits, width = codes[char]
outchar |= (bits<<count)
count += width
while count >= 8:
yield chr(outchar%0xff)
outchar >>= 8
count -= 8
if count:
yield chr(outchar)

def decode(stream):
codebuf = count = 0
width = 1
for codebyte in stream:
codebyte = ord(codebyte)
codebuf |= (codebyte<<count)
count += 8
if width>count:
continue
while width <= count:
code = (codebuf&((1<<width)-1), width)
if code not in chars:
width += 1
continue
yield chars[code]
codebuf >>= width
count -= width
width = 1
width = 1

#trivial encoding dict: a=0 b=01 C=0011 D=0111 E=1011 F=1111
codes = {'a':(0x00,1), 'b':(0x01,2),
'C':(0x3+0x4*0,4), 'D':(0x3+0x4*1,4),
'E':(0x3+0x4*2,4), 'F':(0x3+0x4*3,4)}
chars = dict([(v,k) for k,v in codes.items()]) # reverse

def test(*tests):
if not tests: tests = ['abaFECbaabbDF']
for charstream in tests:
print
codestream = ''.join(list(encode(charstream)))
print '%r [%s] -(encode)-> %r [%s]' % (
charstream, len(charstream), codestream, len(codestream))
recovered = ''.join(list(decode(codestream)))
print '%r [%s] -(decode)-> %r [%s]' % (
codestream, len(codestream), charstream, len(charstream))

if __name__ == '__main__':
import sys
test(*sys.argv[1:])
--------------------------------------------------------------------

Result:

[22:02] C:\pywk\clp>py24 trivcodec.py

'abaFECbaabbDF' [13] -(encode)-> '\xf2;Q\xf7' [4]
'\xf2;Q\xf7' [4] -(decode)-> 'abaFECbaabbDF' [13]

[22:02] C:\pywk\clp>py24 trivcodec.py a b C D E F

'a' [1] -(encode)-> '\x00' [1]
'\x00' [1] -(decode)-> 'a' [1]

'b' [1] -(encode)-> '\x01' [1]
'\x01' [1] -(decode)-> 'b' [1]

'C' [1] -(encode)-> '\x03' [1]
'\x03' [1] -(decode)-> 'C' [1]

'D' [1] -(encode)-> '\x07' [1]
'\x07' [1] -(decode)-> 'D' [1]

'E' [1] -(encode)-> '\x0b' [1]
'\x0b' [1] -(decode)-> 'E' [1]

'F' [1] -(encode)-> '\x0f' [1]
'\x0f' [1] -(decode)-> 'F' [1]

[22:02] C:\pywk\clp>py24 trivcodec.py

'abaFECbaabbDF' [13] -(encode)-> '\xf2;Q\xf7' [4]
'\xf2;Q\xf7' [4] -(decode)-> 'abaFECbaabbDF' [13]

[22:02] C:\pywk\clp>py24 trivcodec.py aaaaaaaa bbbb CC DD EE FF

'aaaaaaaa' [8] -(encode)-> '\x00' [1]
'\x00' [1] -(decode)-> 'aaaaaaaa' [8]

'bbbb' [4] -(encode)-> 'U' [1]
'U' [1] -(decode)-> 'bbbb' [4]

'CC' [2] -(encode)-> '3' [1]
'3' [1] -(decode)-> 'CC' [2]

'DD' [2] -(encode)-> 'w' [1]
'w' [1] -(decode)-> 'DD' [2]

'EE' [2] -(encode)-> '\xbb' [1]
'\xbb' [1] -(decode)-> 'EE' [2]

'FF' [2] -(encode)-> '\x00' [1]
'\x00' [1] -(decode)-> 'FF' [2]

[22:03] C:\pywk\clp>py24 trivcodec.py aaaaaaaabbbbCCDDEEFF

'aaaaaaaabbbbCCDDEEFF' [20] -(encode)-> '\x00U3w\xbb\x00' [6]
'\x00U3w\xbb\x00' [6] -(decode)-> 'aaaaaaaabbbbCCDDEEFF' [20]
Regards,
Bengt Richter
Jul 19 '05 #6
andrea wrote:
No it's not for homework but for learning purposes...
Bengt wrote: I think I prefer little-endian bit streams though,
good point: should lead to easier decoding via right-shifts

e.g. (just hacked, not tested beyond what you see
Yep, yours looks better. Pretty soon there isn't going to be much learning left
in this for Andrea ;-)

and not recommended as efficient either way, esp the decode,

I expect that decoding by walking the coding tree is cleaner (not sure about
faster).
but it might be illustrative of something for Andrea ;-)


Michael

Jul 19 '05 #7
On Thu, 28 Apr 2005 05:07:34 GMT, bo**@oz.net (Bengt Richter) wrote:

.... some not quite correct code ;-/
(I copy/pasted and created an illusion. My code dict has no EOS, so
I decode pad zero bits as code that a single zero stands for ('a' in this case)
so that was an oversight. I should have extended the coding some more or reserved
perhaps 'F' as EOString, and tested for EOS in the decode stream.
This is revised, sorry.
You can make a 'way more efficient decoder as an exercise ;-)
Hint: if you make a dict of all the 2**width integers as keys where
width is your widest code (4 here for 2**4), then you can do a single
mask of 2**width-1 and look up the translation to (char, codewidth) directly,
according to the codewidth least significant bits, if you make all the states
of the other bits into keys that map to the same (char,codewidth).
So for example all the even values of out 2**16 would have to map to ('a', 1)
and all the values with 2 LSBs of 01 (of which there are 4) would map to ('b',2)
and so forth. Thus the incrementing of width and trying one thing after
another is not necessary. I think that will work ...

Well, now Andrea has something to do ;-)----< trivcodec.py >------------------------------------------------ #trivcodec.py
EOS = ''
import itertools
def encode(stream):
outchar = count = 0
for char in itertools.chain(stream, [EOS]):
bits, width = codes[char]
outchar |= (bits<<count)
count += width
while count >= 8:
yield chr(outchar&0xff)
outchar >>= 8
count -= 8
if count:
yield chr(outchar)

def decode(stream):
codebuf = count = 0
width = 1; char = None
for codebyte in stream:
codebyte = ord(codebyte)
codebuf |= (codebyte<<count)
count += 8
if width>count:
continue
while width <= count:
code = (codebuf&((1<<width)-1), width)
if code not in chars:
width += 1
continue
char = chars[code]
if char == EOS: break
yield char
codebuf >>= width
count -= width
width = 1
if char == EOS: break
width = 1

#trivial encoding dict: a=0 b=01 C=0011 D=0111 E=1011 EOS=1111
codes = {'a':(0x00,1), 'b':(0x01, 2),
'C':(0x3+0x4*0,4), 'D':(0x3+0x4*1,4),
'E':(0x3+0x4*2,4), EOS:(0x3+0x4*3,4)}
chars = dict([(v,k) for k,v in codes.items()]) # reverse

def test(*tests):
if not tests: tests = ['abaDECbaabbD']
for charstream in tests:
print
codestream = ''.join(list(encode(charstream)))
print '%r [%s] -(encode)-> %r [%s]' % (
charstream, len(charstream), codestream, len(codestream))
recovered = ''.join(list(decode(codestream)))
print '%r [%s] -(decode)-> %r [%s]' % (
codestream, len(codestream), recovered, len(recovered))

if __name__ == '__main__':
import sys
test(*sys.argv[1:])--------------------------------------------------------------------

Result: Not really. Tack enough a's on the recovered chars to account for zero fill
of the last encoded byte ;-/
[22:02] C:\pywk\clp>py24 trivcodec.py

'abaFECbaabbDF' [13] -(encode)-> '\xf2;Q\xf7' [4]
'\xf2;Q\xf7' [4] -(decode)-> 'abaFECbaabbDF' [13]
Fine, because the [4] bytes were totally filled.
[22:02] C:\pywk\clp>py24 trivcodec.py a b C D E F

'a' [1] -(encode)-> '\x00' [1]
'\x00' [1] -(decode)-> 'a' [1] Not so fine. There is no character serving as EOS mark.
'b' [1] -(encode)-> '\x01' [1]
'\x01' [1] -(decode)-> 'b' [1]

'C' [1] -(encode)-> '\x03' [1]
'\x03' [1] -(decode)-> 'C' [1]

'D' [1] -(encode)-> '\x07' [1]
'\x07' [1] -(decode)-> 'D' [1]

'E' [1] -(encode)-> '\x0b' [1]
'\x0b' [1] -(decode)-> 'E' [1]

'F' [1] -(encode)-> '\x0f' [1]
'\x0f' [1] -(decode)-> 'F' [1]


That really produced:

[ 8:03] C:\pywk\clp>py24 trivcodec.py a b C D E F

'a' [1] -(encode)-> '\x00' [1]
'\x00' [1] -(decode)-> 'aaaaaaaa' [8]

'b' [1] -(encode)-> '\x01' [1]
'\x01' [1] -(decode)-> 'baaaaaa' [7]

'C' [1] -(encode)-> '\x03' [1]
'\x03' [1] -(decode)-> 'Caaaa' [5]

'D' [1] -(encode)-> '\x07' [1]
'\x07' [1] -(decode)-> 'Daaaa' [5]

'E' [1] -(encode)-> '\x0b' [1]
'\x0b' [1] -(decode)-> 'Eaaaa' [5]

'F' [1] -(encode)-> '\x0f' [1]
'\x0f' [1] -(decode)-> 'Faaaa' [5]

So we need to assign a code as the EOS.
And probably translate that to '' as the return char,
and end on that.

So now it does (having given up 1111 for EOS instead of F):

[10:22] C:\pywk\clp>py24 trivcodec.py

'abaDECbaabbD' [12] -(encode)-> 'r;Q\xf7' [4]
'r;Q\xf7' [4] -(decode)-> 'abaDECbaabbD' [12]

[10:22] C:\pywk\clp>py24 trivcodec.py a b C D E

'a' [1] -(encode)-> '\x1e' [1]
'\x1e' [1] -(decode)-> 'a' [1]

'b' [1] -(encode)-> '=' [1]
'=' [1] -(decode)-> 'b' [1]

'C' [1] -(encode)-> '\xf3' [1]
'\xf3' [1] -(decode)-> 'C' [1]

'D' [1] -(encode)-> '\xf7' [1]
'\xf7' [1] -(decode)-> 'D' [1]

'E' [1] -(encode)-> '\xfb' [1]
'\xfb' [1] -(decode)-> 'E' [1]

Goes to show you, eh? Slice and dice similar lines carefully ;-)

Regards,
Bengt Richter
Jul 19 '05 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Altramagnus | last post by:
I have 30 - 40 type of different window. For each type I need about 20 instances of the window. When I try to create them, I get "Error creating window handle" My guess is there is a maximum...
2
by: Iain Miller | last post by:
Now this shouldn't be hard but I've been struggling on the best way as to how to do this one for a day or 3 so I thought I'd ask the assembled company..... I'm writing an application that tracks...
8
by: Nanda | last post by:
hi, I am trying to generate parameters for the updatecommand at runtime. this.oleDbDeleteCommand1.CommandText=cmdtext; this.oleDbDeleteCommand1.Connection =this.oleDbConnection1;...
12
by: Mats Lycken | last post by:
Hi, I'm creating a CMS that I would like to be plug-in based with different plugins handling different kinds of content. What I really want is to be able to load/unload plugins on the fly without...
3
by: John Devlon | last post by:
Hi, I would like to create a small application that creates a new PDF-File, using an excisting PDF-file as background template, adding some text and a unique barcode. I would like to create my...
19
by: Tony | last post by:
I'm working on project that plays movies using Windows Media Player and I'm controlling everything with JavaScript. Per the client I only need to support IE 6 or greater which happens to make...
26
by: nyathancha | last post by:
Hi, How Do I create an instance of a derived class from an instance of a base class, essentially wrapping up an existing base class with some additional functionality. The reason I need this is...
169
by: JohnQ | last post by:
(The "C++ Grammer" thread in comp.lang.c++.moderated prompted this post). It would be more than a little bit nice if C++ was much "cleaner" (less complex) so that it wasn't a major world wide...
11
by: breal | last post by:
I have three lists... for instance a = ; b = ; c = ; I want to take those and end up with all of the combinations they create like the following lists
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.