biais.org

I'm using nltk for a personal project. It's a great library providing many tools for natural language processing. It provides different kinds of tokenizers but these tokenizers only cut string into substring without keeping track of location or other useful metadata. I needed to have tokens location (line and column number of the token) in the original text so I wrote this simple tokenizer imitating the function nltk.wordpunct_tokenize:

import re
 
def wordpunct_tokenize_position(stream):
    """
    Tokenize and store location of tokens from a stream or a string
    >>> list(wordpunct_tokenize_position('nltk is great'))
    [('nltk', (0, 0)), ('is', (0, 5)), ('great', (0, 8))]
    >>> list(wordpunct_tokenize_position('nltk\\nis\\ngreat'))
    [('nltk', (0, 0)), ('is', (1, 0)), ('great', (2, 0))]
    >>> list(wordpunct_tokenize_position('nltk is nltk'))
    [('nltk', (0, 0)), ('is', (0, 5)), ('nltk', (0, 8))]
 
    """
    if isinstance(stream, basestring):
        sourceiterable = stream.splitlines() # not an iterator
    else:
        sourceiterable = stream.readlines()
    regex = re.compile(r'(\w+|[^\w\s]+)')
    for line_number, line in enumerate(sourceiterable):
        for match in regex.finditer(line):
            yield match.group(1), (line_number, match.start())
 
if __name__ == "__main__":
    import doctest
    doctest.testmod()

Reinteract is a good alternative to Python shell or IPython, watch the screencast. Excepting graphical and "GUI objects" inclusion, it's easy to reproduce the behavior with emacs + mode-python and the py-execute-region function.

You can get it from the git repository:

git clone git://git.fishsoup.net/reinteract

Blog post announce

I got a script running on this server that try to look for unusual referrers in my apache access.log, recently it found this line:

65.57.245.11 - - [xx/xx/xxxx:xx:xx:xx +0200] "GET /blog/data
/cv-maxime_biais-en.pdf HTTP/1.0" 200 54736 "http://www.googl
e.com/custom?q=intitle:(resume+OR+CV+OR+Vitae)+%22C%2B%2B%22+
%22Software+(Engineer+OR+Architect+OR+Programmer)%22+Python&h
l=en&client=pub-6116397745508461&cof=FORID:1%3BAH:left%3BCX:S
earch4Candidates%3BL:http://www.google.com/coop/images/google
_custom_search_sm.gif%3BLH:55%3BLP:1%3BGFNT:%23666666%3BDIV:%
23cccccc%3B&cx=003801465318207546779:5c5132mwnqy&adkw=AELymgW
0pVdk7NwNw7cXNIpOpKa3-mkuy3nVruyomR-uq_cmYbfti5RND-XpsliIWGfC
Ed_NEB3f--XthNt0VqWxOO4eTnZ5-Nc_XrqU_tmkWrslLS52BtRbBtRAgj_Dn
MTXeOGVw5_qjTNkBNF60wvDmXltsGdSSw&start=250&sa=N" "Mozilla/5.
0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.7) Gecko/20070
914 Firefox/2.0.0.7"

So what ?:

• The IP: 65.57.245.11 is the gateway of Google mountain view employees.
• The referrer is a custom search engine and it searches for webpages that contains (resume OR CV OR Vitae) in title, and C++ and Python and (Software Engineer OR Architect OR Programmer) in everything.

Try the referer url.

Now, you know what to write in your resume title if you want Google HR to find you.

A small but sufficient documentation to configure, run and use jablit.

I was looking for a good text mode jabber client to talk with my friends / distant co-worker. I only found centericq but I don't like the interface, so I begin to write a very small text mode client : jablit. The early first release is not documented but i'm using all day long, it's stable and perfectly fits my needs ( I hope it will fit your ).

A variant of the Viterbi Algorithm returning the less energy path of a matrix. Example:

 
M = [[4, 1, 3],
     [3, 4, 2],
     [2, 1, 4]]

This matrix M is projected to the following virtual trellis:

In this example, the path' energy from top to bottom [1, 1, 1] (passing the node 1 then 4 then 1) is 6 ( = abs(1-4) + abs(4-1)).

def viterbi(matrix):
    """Viterbi algorithm : find the best 8-connected path in a matrix.
    
    Example, here the best path from top to bottom is to follow the "4"s 
    (diagonal), the energy of the path is 0
    >>> viterbi([[4, 1, 3], \
                 [3, 4, 2], \
                 [2, 1, 4]])
    [0, 1, 2]
    
    On the next example, 2 best paths, only the first found is returned
    >>> viterbi([[1, 2, 2], \
                 [1, 1, 2], \
                 [1, 2, 1]])
    [0, 0, 0]
    
    A basic example. Best path energy: 1
    >>> viterbi([[1, 0], \
                 [4, 2]])
    [0, 1]
    """
    # init
    h = len(matrix) - 1
    w = len(matrix[0])
    k = 0
    S = {}      #Survivors
    L = {}      #Accumulate Length
    for i in range(w):
        L[(k, i)] = 0
 
    # recursion
    for k in range(h):
        for x in range(w):
            for dx in range(-1, 2):
                if (x + dx) < 0 or (x + dx) >= w:
                    continue
                tmpl = L[k, x] + abs(matrix[k][x] - matrix[k+1][x+dx])
                if (not (k+1, x+dx) in L) or (tmpl < L[(k+1, x+dx)]):
                    L[(k+1, x+dx)] = tmpl
                    S[(k+1, x+dx)] = x
 
    # look for the smallest
    tmp, idx = -1, -1
    for i in range(w):
        if L[(h, i)] < tmp or tmp == -1:
            tmp = L[(h, i)]
            idx = i
 
    # create the inversed path
    res = [idx]
    for k in range(h, 0, -1):
        idx = S[(k, idx)]
        res.append(idx)
 
    # reverse the path
    res.reverse()
    return res

Notes:

• You may use Numeric.Array to represent the matrix for better perfomances
• Download the source

I wanted to write a simple function in Caml, compile it and load it as a Python module, but it was a bit more complex that I thought. I tried to use pycaml or py2caml to avoid writing C code; without success. Then I read the Extending Python With C chapter in the Python doc and the Interfacing C with Objective Caml chapter from OCaml manual.

There is 4 main steps to write this example module:

1. Write the Caml function you want to use in your Python program (in the example file mop.ml)
2. Write the C code to wrap the Caml code (mop_mlwrapper.c)
3. Write the C code to declare the Python module (mop_module.c)
4. Compile all and link everything together (not the easiest when you're not familiar with Caml compilation process)

Caml code:

let square a =  a * a;;

(* declare square function as name "square" to call it from C code *)
let _ = Callback.register "square" square;;

C code to wrap the Caml function:

#include "caml/callback.h"
 
void initcaml(void)
{
  char *dummy[] = {0};
 
  // Initialize the Caml interpreter
  caml_startup(dummy);
}
 
int mlmop(int a)
{
  int res;
  static value *f = NULL;
  value r_caml;
 
  // Get a pointer on the caml code "square"
  f = caml_named_value("square");
  if (f == NULL)
    return -1;
  // Run the Caml function pointed by f
  r_caml = callback(*f, Val_int(a));
  // Convert the return value to an integer
  res = Int_val(r_caml);
  return res;
}

C code, Python extension:

#include "Python.h"
 
extern int mlmop(int);
extern void initcaml();
 
static PyObject *
testmop(PyObject *self, PyObject *args)
{
  int arg, res;
 
  if (!PyArg_ParseTuple(args, "i", &arg))
    return NULL;
 
  res = mlmop(arg);
  // convert to a Python int
  return Py_BuildValue("i", res);
}
 
static PyMethodDef MopMethods[] = {
  {"testmop", testmop, METH_VARARGS, "test function calling caml code"},
  {NULL, NULL, 0, NULL}        /* Sentinel */
};
 
 
// function needed to initialize the module and call the caml init
PyMODINIT_FUNC
initmop(void)
{
  (void) Py_InitModule("mop", MopMethods);
  initcaml();
}

The Makefile:

1. Compile the ml file in object file (-output-obj option)
2. Compile both C files in object files
3. Link all object files in a shared library. The library must be linked with dependency libraries : libcamlrun, libunix, libm, libcurses

PY_PREFIX=/usr
PY_VERSION=2.4

LIBS = -L/usr/lib/ocaml/3.09.2/ -L$(PY_PREFIX)/lib/python$(PY_VERSION)/config -lpython$(PY_VERSION) -lunix  -lcamlrun -lm -lcurses 
INCS = -I$(PY_PREFIX)/include/python$(PY_VERSION) -I/usr/lib/ocaml/3.09.2/

all: mop.so

mop_module.o: mop_module.c
	gcc -ggdb -Wall -c mop_module.c $(INCS) -o mop_module.o

mop_mlwrapper.o: mop_mlwrapper.c
	ocamlc -ccopt -Wall -c mop_mlwrapper.c

mop.o: mop.ml
	ocamlc -o mop.o -output-obj -ccopt -fPIC mop.ml

# Note: under MacOS X replace -shared by -dynlib
mop.so: mop_module.o mop_mlwrapper.o mop.o
	gcc -shared --whole-archive mop_mlwrapper.o mop.o mop_module.o $(LIBS) -o mop.so

test: mop.so
	python$(PY_VERSION) test.py

test2: mop.so
	python$(PY_VERSION) -c "import mop; print 'square(2) =', mop.testmop(2)"

clean:
	rm -rf *o *so *cmi *cmo

After the compilation process, when mop.so is built, you can run import it as a Python module:

import mop
 
for i in range(15):
    print mop.testmop(i)

Here is the archive of the Caml, C and Python code and Makefile.

Next step: the same example with pycaml or py2caml.

I started a new project called plotmoi, hosted by code.google: http://code.google.com/p/plotmoi/. The goal is to plot any formated or non formated data. After some hours of coding plotmoi can generate interesting svg without pain. For example, I extracted from a database the following table in tests/reallife_data_5.data:

   size   | count 
 ---------+-------
        1 | 73719
       17 | 58136
       21 | 51949
       19 | 47431
       16 | 47027
       15 | 46303
       24 | 44450
       25 | 44388
 ...
 (25673 rows)

Then run plotmoi:

$ python src/plotmoi.py tests/reallife_data_5.data plotmoi_loglog_example.svg

It generated this svg file (log/log scale). bitmap preview:

You can retrieve sources via subversion:

svn checkout http://plotmoi.googlecode.com/svn/trunk/ plotmoi

When I talk with other pythoners, then often argue that reduce, map and filter builtins + lambdas are faster than a classic for loop or list comprehensions.

Notes:

• mip3 is here to verify that you must use standard library functions when it's possible.
• profilteit is described here

@profileit(0)
def mip0(iterable):
    sum = 0
    for i in iterable:
        sum += i
    print sum
 
@profileit(0)
def mip1(iterable):
    print reduce(lambda x, y: x + y, iterable, 0)
 
import operator
@profileit(0)
def mip2(iterable):
    "Wrap a builtin in reduce will avoid heavy python function calls"
    print reduce(operator.add, iterable, 0)
 
@profileit(0)
def mip3(iterable):
    print sum(iterable)
 
for i in range(4):
    exec "mip%d(xrange(500000))" % i

$ python2.5 tips.py|grep CPU
         1 function calls in 0.555 CPU seconds
         500001 function calls in 2.072 CPU seconds
         1 function calls in 0.666 CPU seconds
         1 function calls in 0.430 CPU seconds

Even mip2 where reduce wrap operator.add (a C builtin) is not the fastest function. Of course, the sum builtin is the fastest way to sum a list ;), but the first, and I think, the most readable version, is a good choice when builtin doesn't exist.

A small snippet to measure profiling time:

from profileit import profileit
import operator
import time
timed = 0
 
def timemeth(func):
    def _inner(self, *args, **kw):
        start = time.time()
        res = func(self, *args, **kw)
        global timed
        timed = time.time() - start
        return res
    return _inner
 
@timemeth
@profileit(0)
def mip0(iterable):
    reduce(operator.add, iterable, 0)
 
@timemeth
@profileit(0)
def mip1(iterable):
    reduce(lambda x, y: x + y, iterable, 0)
 
mip0(xrange(100000))
print "timed %.3f seconds" % timed
 
mip1(xrange(100000))
print "timed %.3f seconds" % timed

Notes:

• profileit is described here.
• putting @timemeth before @profileit(0) will measure consumed time of profileit method call.
• swap @timemeth with @profileit(0) and you will profile the timemeth function
• read my last post to see why I used python2.5 and not python2.4

Outputs:

$ python2.5 reducecomp.py|grep seconds
         1 function calls in 0.097 CPU seconds
timed 0.109 seconds
         100001 function calls in 0.406 CPU seconds
timed 8.883 seconds

It's not a surprise, the profiler is time consuming when many functions are called.