Skip to content

Instantly share code, notes, and snippets.

Avatar

Mark Reid mreid

View GitHub Profile
@mreid
mreid / huffman.py
Last active Sep 25, 2021
Example implementation of Huffman coding in Python
View huffman.py
# 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 / h74-encode.py
Created Oct 29, 2013
Python implementation of Hamming (7,4) encoding.
View h74-encode.py
# 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 / lz77-encode.py
Last active Jul 21, 2019
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).
View lz77-encode.py
# 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 Jan 29, 2012
Install Vowpal Wabbit on Mac OS X Lion
View INSTALL-VW-OSX.md

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 / received.txt
Created Nov 6, 2013
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.
View received.txt
101110000011111111001001101101001010101001110011010000110100010111100111000000010111110000110101011011100000110000000101101100000101111010001001111000000000111000000011
@mreid
mreid / channel.py
Created Oct 29, 2013
A simple noisy channel that flips a single bit in a block of N with probability P.
View channel.py
# 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 / lz78-encode.py
Last active Dec 26, 2015
Python implementation of a simple version of LZ78 encoding.
View lz78-encode.py
# 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
View haskell-woes.txt
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)
View Tally.java
package demo;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
@mreid
mreid / crossval.sh
Created Jul 21, 2009
Bash script for doing cross validation
View crossval.sh
#!/usr/bin/perl -w
# -*-perl-*-
# $Id: crossval,v 1.1.1.1 2003/04/02 02:06:05 mreid Exp $
#
# NAME
# crossval - Run Aleph on a collection of cross validation sets.
#
# SYNOPSIS
# crossval [--aleph ALEPH] [--yap YAP] [--param ALEPH_SETTING] [--set ALEPH_SETTING]
# EXP_BASE BACKGROUND DATA_PATTERN