Skip to content

Instantly share code, notes, and snippets.

View mreid's full-sized avatar

Mark Reid mreid

100 followers · 10 following
View GitHub Profile
@mreid
mreid / arithmetic.py
Last active August 29, 2015 14:07
Toy implementation of arithmetic coding as described in Cover & Thomas §13.3
# Example implementation of simple arithmetic coding in Python (2.7+).
#
# USAGE
#
# python -i arithmetic.py
# >>> m = {'a': 1, 'b': 1, 'c': 1}
# >>> model = dirichlet(m)
# >>> encode(model, "aabbaacc")
# '00011110011110010'
#
@mreid
mreid / huffman.py
Last active September 25, 2021 12:22
Example implementation of Huffman coding in Python
# Example Huffman coding implementation
# Distributions are represented as dictionaries of { 'symbol': probability }
# Codes are dictionaries too: { 'symbol': 'codeword' }
def huffman(p):
'''Return a Huffman code for an ensemble with distribution p.'''
assert(sum(p.values()) == 1.0) # Ensure probabilities sum to 1
# Base case of only two symbols, assign 0 or 1 arbitrarily
if(len(p) == 2):
@mreid
mreid / keybase.md
Created July 15, 2014 01:46

Keybase proof

I hereby claim:

  • I am mreid on github.
  • I am mreid (https://keybase.io/mreid) on keybase.
  • I have a public key whose fingerprint is 0290 8892 E023 A876 460B D320 2B84 F83F 283D 58D8

To claim this, I am signing this object:

@mreid
mreid / received.txt
Created November 6, 2013 02:50
The resulting file `received.txt` when the command `cat message.txt | python python lz78-encode.py | python h74-encode.py | python channel.py 7 0.8 > received.txt` is run.
101110000011111111001001101101001010101001110011010000110100010111100111000000010111110000110101011011100000110000000101101100000101111010001001111000000000111000000011
@mreid
mreid / channel.py
Created October 29, 2013 00:18
A simple noisy channel that flips a single bit in a block of N with probability P.
# A command-line noisy channel
#
# USAGE: python channel.py BLOCK_SIZE FLIP_PROBABILITY
#
# EXAMPLE:
# $ echo "0000000" | python channel.py 7 0.8
# 0000100
#
# AUTHOR: Mark Reid <mark.reid@anu.edu.au>
# CREATED: 2013-10-21
@mreid
mreid / h74-encode.py
Created October 29, 2013 00:17
Python implementation of Hamming (7,4) encoding.
# Hamming (7,4) Coding
#
# Reads binary stream from standard input and outputs Hamming (7,4) encoded
# version to standard output.
#
# USAGE: python h74-encode.py
#
# EXAMPLE:
# $ echo "0001" | python h74-encode.py
# 1000101
@mreid
mreid / lz78-encode.py
Last active December 26, 2015 20:18
Python implementation of a simple version of LZ78 encoding.
# LZ78 Encoding
#
# Performs LZ78 encoding on the standard input and writes result to standard output
# using algorithm described in MacKay textbook.
#
# Note:
# - All input symbols are encoded using 7-bit ASCII.
# - Pointer index is encoded using logarithmically increasing number of bits
#
# USAGE: python lz78-encode.py
@mreid
mreid / lz77-encode.py
Last active July 21, 2019 02:59
A simple implementation of the LZ77 algorithm, as described in §13.4 of Cover and Thomas' "Information Theory" book. (Note: python is not my first choice of language so this code is probably non-idiomatic).
# LZ77 Encoding
#
# Simple implementation of Lempel-Ziv 77 (a.k.a. "Sliding Window") coding
# as described in Section 13.4 of Cover & Thomas' "Information Theory".
#
# USAGE: python encode.py INPUT_STREAM
#
# EXAMPLE (from lectures):
# $ python encode.py abbababbababbab
# (0,a)
@mreid
mreid / INSTALL-VW-OSX.md
Created January 29, 2012 21:59
Install Vowpal Wabbit on Mac OS X Lion

The INSTALL instructions that come with Vowpal Wabbit appear not to work on Mac OS X Lion. Here's what I did to get it to compile. You will need the developer tools that come with the XCode installation.

The only dependency VW has is the boost C++ library. So first, download and install Boost

To install Boost, do the following:

$ cp ~/Downloads/boost_1_48_0.tar.bz2 ./
@mreid
mreid / haskell-woes.txt
Created March 30, 2011 11:12
Running Snow Leopard 10.6.7 on a 2.66 GHz Intel Core 2 Duo iMac.
Installed XCode 4 from the App Store (previous had XCode 3 installed under 10.5).
----
$ uname -a
Darwin iMac.local 10.7.0 Darwin Kernel Version 10.7.0: Sat Jan 29 15:17:16 PST 2011; root:xnu-1504.9.37~1/RELEASE_I386 i386
$ gcc --version
i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5666) (dot 3)