Computation of Prefix Free Codes with many repeated weight values in reduced space Does the code below respect Python programming conventions? (and if not, which one does it disrespect?) The objective would be to publish this code as part of a scientific article, as "reproducible research".

In 1998, Moffat and Turpin described in "Efficient Construction of Minimum Redundancy Codes for Large Alphabets" (which I reviewed here) how to compute prefix free codes from sorted weights with many repeated weight values in reduced space and time (once the weights are sorted). I am planning to reproduce and describe their first experiment (compressing some TREC data set) in a fully reproducible way, as an exercize in reproducible research. Their algorithm should be implementable (they did implement it and ran it for their experiment but did not share their code) but I found that I needed to make large modifications when programming it in Python, and I wonder if I am doing it properly (I am more of a mathematician than a programmer).

def assertEqual(x,y):
   assert x==y, str(x)+" should be "+str(y)

# A function to simulate one sorted list from two:
def sourceOfFirstOfTwo(leaves,graphs):
   """Given two lists of 4-uple, returns a pointer to the one with the list with the smallest first element, sorted by first value."""
   assert(len(leaves)&gt;0 or len(graphs)&gt;0)
   if len(leaves)==0:
      return graphs
   elif len(graphs)==0:
      return leaves
   else:
     (firstLeafWeight,firstLeafFrequency,firstLeafLeft,firstLeafRight) = leaves[0]
     (firstGraphWeight,firstGraphFrequency,firstGraphLeft,firstGraphRight) = graphs[0]
     if firstLeafWeight&lt;firstGraphWeight:
        return leaves
     else:
        return graphs
assertEqual(sourceOfFirstOfTwo([(1,1,0,0)],[]),[(1,1,0,0)])
assertEqual(sourceOfFirstOfTwo([],[(2,1,0,0)]),[(2,1,0,0)])
assertEqual(sourceOfFirstOfTwo([(1,1,0,0)],[(2,1,0,0)]),[(1,1,0,0)])
assertEqual(sourceOfFirstOfTwo([(2,1,0,0)],[(1,1,0,0)]),[(1,1,0,0)])


def Meld(leaves):
   assert(len(leaves)&gt;0)
   graphs = []
   source = leaves
   first = (firstWeight,firstFrequency,firstLeft,firstRight) = source[0]
   while firstFrequency&gt;1 or len(leaves)+len(graphs)&gt;1: 
      assert(len(graphs)&lt;5)
      if firstFrequency&gt;1:
         if firstFrequency %2 == 1:
            source[0] = (firstWeight, 1, firstLeft, firstRight)
         else:
            source.remove(first)
         graphs.append((2*firstWeight,firstFrequency // 2,first,first)) 
      else: #firstFrequency == 1 but len(leaves)+len(graphs)&gt;1
         source.remove(first)
         secondSource = sourceOfFirstOfTwo(leaves,graphs)
         second = (secondWeight,secondFrequency,secondLeft,secondRight) = secondSource[0]
         assert(secondFrequency&gt;0)
         if secondFrequency==1:
            secondSource.remove(second)
         else:
            secondSource[0] = (secondWeight,secondFrequency-1,secondLeft,secondRight)
         graphs.append((firstWeight+secondWeight,1,first,(secondWeight,1,secondLeft,secondRight)))
      source = sourceOfFirstOfTwo(leaves,graphs)
      first = (firstWeight,firstFrequency,firstLeft,firstRight) = source[0]
   return(sourceOfFirstOfTwo(leaves,graphs)[0])
assertEqual(Meld([(1,1,0,0)]),(1, 1, 0, 0))
assertEqual(Meld([(1,2,0,0)]),(2,1,(1, 2, 0, 0),(1, 2, 0, 0)))
assertEqual(Meld([(1,4,0,0)]),(4,1,(2,2,(1, 4, 0, 0),(1, 4, 0, 0)),(2,2,(1, 4, 0, 0),(1, 4, 0, 0))))
assertEqual(Meld([(1,2,0,0),(3,1,0,0)]),(5,1,(2,1,(1,2,0,0),(1,2,0,0)),(3,1,0,0)))
1. Comments on your code


The Python style guide (PEP8) recommends using 4 spaces for each indentation step, and lowercase_words_with_underscores for variable names and function names. You're not obliged to follow this guide, but it will make it easier for you to collaborate with other Python programmers if you do.
In answer to your question in comments, assert statements are fine. It's usually a good sign when code includes them, because it shows that the programmer has thought about what needs to be true at each step of the algorithm.
The assertEqual calls, on the other hand, are not quite in the right place. It's a good sign to see test cases. However, it's not a good idea to intermix the test suite with the code like this, because it means that every time your program gets run or your module gets loaded, the test suite gets run. That's harmless here because the test cases are so short, but if the test suite took a lot of time to run, you'd normally prefer not to run it every time.

So I would suggest reorganizing the test code so that it uses the facilities in the unittest module. Which includes its own assertEqual method, saving you the need to write your own. See below for how you might do this.
The docstring of sourceOfFirstOfTwo seems confused. Python doesn't have "pointers" and it's best not to think in terms of pointers, but in terms of values. You should have written:

"""Given two lists of 4-tuples, return the one with the smallest first element."""


but in fact this doesn't completely describe the behaviour of the function because it doesn't say what happens if one of the lists is empty.
A confused or complicated docstring is often an indication that a function would profit from being simplified or generalized, and that's definitely the case here. The first thing to note is that sequences test true if they are non-empty, and false if they are empty, so the initial tests can be rewritten:

assert(leaves or graphs)
if not leaves:
    return graphs
elif not graphs:
    return leaves


Next, Python already compares tuples element-wise:

&gt;&gt;&gt; sorted([(2,3), (1,4), (2,1)])
[(1, 4), (2, 1), (2, 3)]


so there is no need to split up your 4-tuples into their components. Instead you can write:

if leaves[0] &lt; graphs[0]:
    return leaves
else:
    return graphs


which can be simplified to:

return min(leaves, graphs)


since lists compare element-wise too. But now that we've made these simplifications, there's nothing in this function that needs to know about leaves and graphs. Really, it's a function that takes two sequences, discards empty ones, and returns the smaller among the remaining ones. But you can see that there's nothing special about the number two here. So I would generalize this function in order to further simplify it, like this (just one line!):

def min_non_empty(*sequences):
    """Return the smallest of the non-empty sequences.
    Raise ValueError if all sequences are empty.

        &gt;&gt;&gt; min_non_empty([1,2],[2,3],[])
        [1, 2]
        &gt;&gt;&gt; min_non_empty([1,2],[1],[])
        [1]
        &gt;&gt;&gt; min_non_empty([], [])
        Traceback (most recent call last):
        ...
        ValueError: min() arg is an empty sequence

    """
    return min(s for s in sequences if s)


Notice how I've used the docstring to provide examples of how the function can be called. Python's doctest module is capable of running these mini-tests and checking their output. (This feature doesn't substitute for a proper test suite, but it's a useful way to check examples in documentation.)

Note also that there's no need for an assertion any more because min raises ValueError if you don't give it any arguments.

But having done all that, I don't think we actually need this function at all. See below.
A data structure with more than a couple of elements becomes unwieldy to manipulate if you represent it as a tuple. You have to refer to its elements by index (like x[1]) in which case it is not clear what that element means, or else you have to break it down into its components.

It would be better to refer to the elements of your data structure by name. You could do this by creating a class, but the simplest thing to do here is to use a named tuple:

Graph = namedtuple('Graph', 'weight frequency left right'.split())

Instead of using 0 as a placeholder meaning "no left/right child", it's conventional in Python to use None. That way there's no risk of confusing it for a weight or a frequency.
Your Meld function lacks a docstring. What does it do and how to call it?
Your Meld algorithm isn't the same as the one in your blog. (The original paper is hidden behind a paywall and IEEE want to charge me $31 just to read it, so I am basing this on your blog instead.) The differences are as follows: (i) you separate the graphs into two lists, leaves and graphs, whereas Moffat and Turpin just maintain a single list A; (ii) you set first to be the smaller of the initial elements of leaves and graphs, whereas Moffat and Turpin set t to be the first element of A; (iii) similarly for second and u.

This causes some of the prefix trees to come out in a different order. For example, you have

&gt;&gt;&gt; Meld([(1,2,0,0),(3,1,0,0)])
(5, 1, (2, 1, (1, 2, 0, 0), (1, 2, 0, 0)), (3, 1, 0, 0))


but I believe that Moffat and Turpin's algorithm would go through these steps:


A = [(1, 2), (3, 1)]
A = [(3, 1), (2, 1, (1, 2), (1, 2))]
A = [(5, 1, (3, 1), (2, 1, (1, 2), (1, 2)))]


I don't know if this difference is significant, but I thought I ought to mention it.

Update: you noted in comments that the reason for this difference is that the description of Moffat and Turpin's algorithm in your blog was incomplete in that the list A needs to be maintained in sorted order (or rather, it needs to be possible to efficiently fetch the smallest element from the list).

Maintaining a priority queue can be done efficiently in Python using the heapq module. I've revised my code below to show how to do this.
In the course of the algorithm you need to manipulate the list graphs by adding items at the right and removing items from the left. The latter operation is not efficient for ordinary Python lists: if you look at the TimeComplexity page on the Python Wiki you'll see that deleting an item from a list is O(n).

In order to modify a sequence at both ends efficiently, you need to use some other data structure. In many cases you could use the double-ended queue class collections.deque, but here since you need to be able to efficiently fetch the smallest item in the sequence, the heapq module is the one to use.
The meld function is not very useful by itself. As you comment in your blog post, any actual user will need a function that converts the list of weights into the (weight, frequency) pairs (collections.Counter would be a convenient and efficient tool to do this in Python), and a function that processes the resulting prefix tree into the codes. You'd probably want to add these functions to your code.


2. Rewrite

Putting all this together, here's how I'd write this code:

from collections import namedtuple
from heapq import heapify, heappush, heappop
from unittest import TestCase

Graph = namedtuple('Graph', 'weight frequency left right'.split())

def meld(graphs):
    """Given a non-empty list 'graphs' of Graph objects, return a
    minimum-redundancy prefix tree constructed using the algorithm of
    Moffat and Turpin (1998).

    """
    heapify(graphs)
    while True:
        t = graphs[0]
        if t.frequency &gt; 1:
            if t.frequency % 2 == 0:
                heappop(graphs)
            else:
                graphs[0] = Graph(t.weight, 1, t.left, t.right)
            heappush(graphs, Graph(2 * t.weight, t.frequency // 2, t, t))
        elif len(graphs) &gt; 1:
            assert(t.frequency == 1)
            heappop(graphs)
            u = graphs[0]
            if u.frequency == 1:
                heappop(graphs)
            else:
                graphs[0] = Graph(u.weight, u.frequency - 1, u.left, u.right)
            heappush(graphs, Graph(t.weight + u.weight, 1, t, u))
        else:
            assert(len(graphs) == 1 and t.frequency == 1)
            return t

class MeldTest(TestCase):
    def test(self):
        t = Graph(1, 1, None, None)
        self.assertEqual(meld([t]), t)

        u = Graph(1, 2, None, None)
        self.assertEqual(meld([u]), Graph(2, 1, u, u))

        v = Graph(1, 4, None, None)
        w = Graph(2, 2, v, v)
        self.assertEqual(meld([v]), Graph(4, 1, w, w))

        x = Graph(3, 1, None, None)
        self.assertEqual(meld([u, x]), Graph(5, 1, Graph(2, 1, u, u), x))


Notes:


There turned out to be no need for the sourceOfFirstOfTwo function.
The unit tests have been moved to a unittest.TestCase class. You can run all the unit tests from the command line like this:

$ python -munittest mymodule.py
.
----------------------------------------------------------------------
Ran 1 test in 0.000s

OK