{{ message }}

Instantly share code, notes, and snippets.

# Mark Reid mreid

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):
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
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)
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 ./
``````
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.
 101110000011111111001001101101001010101001110011010000110100010111100111000000010111110000110101011011100000110000000101101100000101111010001001111000000000111000000011
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 # CREATED: 2013-10-21
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
Created Mar 30, 2011