473,546 Members | 2,732 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

arithmetic coder

I was messing around with a project, trying out various
compression schemes. One of them was for arithmetic
coding. My implementation is .. novel ... because it
uses the Rational library for buring those CPU cycles.

Here's the output when you run it on the command-line
with the file itself as the training set and some text
from the file

% python arithmetic_code r.py arithmetic_code r.py "def for in tot R"
Orig. 136 bits, compr. 85 bits, ratio = 66%
242524315643209 44671345436
Was it 'def for in tot R'?
Guess so.

That second line is the compressed text * 2**85.

For funsies, here it is.

# A very slow arithmetic coder for Python.
#
# "Rationals explode quickly in term of space and ... time."
# -- comment in Rational.py (probably Tim Peters)
#
# Really. Don't use this for real work. Read Mark Nelson's
# Dr. Dobb's article on the topic at
# http://dogma.net/markn/articles/arith/part1.htm
# It's readable, informative and even includes clean sample code.
#
# Contributed to the public domain. (Like they would want it ;)
# Andrew Dalke < dalke @ dalke scientific . com >
import sys

import Rational, math
R = Rational.ration al

def train(text):
"""text -> 0-order probability statistics as a dictionary

Text must not contain the NUL (0x00) character because that's
used to indicate the end of data.
"""
assert "\x00" not in text
counts = {}
for c in text:
counts[c]=counts.get(c,0 )+1
counts["\x00"] = 1
tot_letters = sum(counts.valu es())

tot = 0
d = {}
prev = R(0)
for c, count in counts.items():
next = R(tot + count, tot_letters)
d[c] = (prev, next)
prev = next
tot = tot + count
assert tot == tot_letters

return d
def encode(text, probs):
"""text and the 0-order probability statistics -> longval, nbits

The encoded number is rational(longva l, 2**nbits)
"""
minval = R(0)
maxval = R(1)
for c in text + "\x00":
prob_range = probs[c]
delta = maxval - minval
maxval = minval + prob_range[1] * delta
minval = minval + prob_range[0] * delta

# I tried without the /2 just to check. Doesn't work.
# Keep scaling up until the error range is >= 1. That
# gives me the minimum number of bits needed to resolve
# down to the end-of-data character.
delta = (maxval - minval)/2
nbits = 0L
while delta < 1:
nbits = nbits + 1
delta = delta << 1
if nbits == 0:
return 0, 0
else:
avg = (maxval + minval)<<(nbits-1) # using -1 instead of /2
# Could return a rational instead ...
return avg.n/avg.d, nbits # the division truncation is deliberate
def decode(longval, nbits, probs):
"""decoe the number to a string using the given statistics"""
val = R(longval, 1L<<nbits)
letters = []
probs_items = [(c, minval, maxval) for (c, (minval, maxval))
in probs.items()]

while 1:
for (c, minval, maxval) in probs_items:
if minval <= val < maxval:
break
else:
raise AssertionError( "not found")

if c == "\x00":
break
letters.append( c)
delta = maxval - minval
val = (val - minval)/delta
return "".join(letters )

if __name__ == "__main__":
# getopt? optparse? What are they?
import sys
trainfilename = sys.argv[1] # must give a filename
phrase = sys.argv[2] # must give text to compress (slowly!)
probs = train(open(trai nfilename).read ())
n, nbits = encode(phrase, probs)
# +1 for the NUL terminator or equivalent
print "Orig. %d bits, compr. %d bits, ratio = %3.f%%" % (
(len(phrase)+1) *8, nbits, (100.*nbits) / (len(phrase)*8) )
print n
new_phrase = decode(n, nbits, probs)
print "Was it '%s'?" % (new_phrase,)
if phrase == new_phrase:
print "Guess so."
else:
print "Why not?!"

Jul 18 '05 #1
0 1111

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

Similar topics

20
1326
by: parametriceq | last post by:
Hello, I just realized there's only a "g" separating me from....me? Old Coder or Old Codger? Anyway, I haven't programmed since the late 80's. My experience then was with DEC PDP-11's and VAX's. Primarily Basic and RMS I've let myself get a decade+ behind. There's so much that I don't know that I get lost in getting started.
87
5125
by: ziliath | last post by:
I recently tried out the Google "top coder" contest, as a C++ coder. I noticed immediately that they expected me to know STL. To which I say, what the fuck?! I may be missing something, but at what point when learning C++ was I supposed to have picked up STL? I ask because at every job I've had, and every job interview for that matter,...
16
5104
by: TTroy | last post by:
Hello, I'm relatively new to C and have gone through more than 4 books on it. None mentioned anything about integral promotion, arithmetic conversion, value preserving and unsigned preserving. And K&R2 mentions "signed extension" everywhere. Reading some old clc posts, I've beginning to realize that these books are over-generalizing the...
43
26449
by: Mehta Shailendrakumar | last post by:
Hello, Can anyone suggest me operator to perform arithmetic shift in C? May it be for a perticular compiler. Thank you in advance. Regards, Shailendra
6
2274
by: Francois Grieu | last post by:
Are these programs correct ? #include <stdio.h> unsigned char a = {1,2}; int main(void) { unsigned char j; for(j=1; j<=2; ++j) printf("%u\n", *( a+j-1 )); return 0; }
4
1544
by: PDHB | last post by:
I'm sorry, but this is just the height of stupidity. I love the dot net framework. It has actually been sufficient to convert an anti-microsoft extremist (myself) to the windows camp. But not having numerical value types inherit from an interface to allow for arithmetic in generics, or in some other way allow arithmetic in generics without a...
23
442
by: Skybuck Flying | last post by:
Some coders don't need an obfuscator, they are the obfuscator. Bye, Skybuck =D
7
528
by: barikat | last post by:
int a; int *Ptr1, *Ptr2; Ptr1 = a; Ptr1++; Ptr2 = a; printf("Ptr1 : %p\n", Ptr1); printf("Ptr2 : %p\n\n", Ptr2);
26
3029
by: Bill Reid | last post by:
Bear with me, as I am not a "professional" programmer, but I was working on part of program that reads parts of four text files into a buffer which I re-allocate the size as I read each file. I read some of the items from the bottom up of the buffer, and some from the top down, moving the bottom items back to the new re-allocated bottom on...
0
7502
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7434
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7946
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
7791
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6026
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
5078
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3491
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3470
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1045
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

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.