sobota, 16 kwietnia 2011

Embedded in Academia

New link in blogroll -- blog of prof. John Regehr: low level code, bugs in C compilers and beautiful photos.

środa, 13 kwietnia 2011

Regular expressions derivatives

Have you ever heard about "regular expression derivatives"? No? Me too. This is very interseting idea, that have pratical usage in pattern matching.

Matthew Might wrote a sample program using the idea: A regular expression matcher in Scheme using derivatives. There is also a detailed paper on this topic: Regular-expression derivatives re-examined by Owens, Reppy and Turon.

Traversing DAGs

If DAG has got one component, then the simplest traversing
method is depth-first-search, which could be easily implemented
recursively (using implicit stack).

struct DAGNode {
        // user data
        bool    visited;        // after construction = 0

void DFS_aux(DAGNode* node, const bool val) {
        if (node->visited != val) {
                // visit node

                node->visited = val;
                for (n in node.connected)
                        DFS_aux(n, val)

void DFS(DAGNode node) {
        static val = true;
        DFS_aux(node, val);
        val = not val;

On every call of DFS() variable val is switched, and visited member is marked alternately with true or false.

There is just one problem — what if traversing method stop execution before visiting all nodes? Of course in such situation we have to visit DAG twice: on first pass reset (possibly many times) visited member to false, and then visit once each node.

But usually bool have at least 8 bits, so numbers could be used instead of boolean values 0 or 1. On each call of DFS() a reference number is incremented, thanks that even if previous call stopped in the middle procedure will work

The only moment when visited markers have to be cleared is wrapping a reference numbers to zero. This happen every 256 calls if 8-bit values used; for wider counters (16, 32 bits)
max value is greater.

void DFS(DAGNode node) {
        static unsigned int val = 1;
        if (val == 0) {
                // set visited member of all nodes to 0
                val += 1;
        DFS_aux(node, val);
        val += 1;

sobota, 9 kwietnia 2011

DAWG as dictionary? Yes!

If you read Wikipedia entry about DAWG, then you find following sentence:
Because the terminal nodes of a DAWG can be reached by multiple paths, a DAWG is not suitable for storing auxiliary information relating to each path, e.g. a word's frequency in the English language. A trie would be more useful in such a case.
This isn't true!

There is a quite simple algorithm, that allow to perform two-way minimal perfect hashing (MPH), i.e. convert any path representing a word to a unique number, or back --- a number to a path (word). Values lie in range 1..n, where n is number of distinct words saved in DAWG.

The algorithm is described in Applications of Finite Automata Representing Large Vocabularies, by Claudio Lucchiesi and Tomasz Kowaltowski (preprint is freely available somewhere online).

The main part of the algorithm is assigning to each node a number of reachable words from a node; this can be easily done in one pass. Then these numbers are used to perform perfect hashing. Hashing algorithm is fast and simple, translation from pseudocode presented in the paper is straightforward.

Algorithm requires additional memory for numbers in each node and a table of size n to implement dictionary lookups.

I've updated pyDAWG to support MPH.


pyDAWG is a python module implementing Directed Acyclic Word Graph, that allow to store set of words in a compacted way. DAWGs are much smaller then tries, while sharing the main advantage of tries - linear time to check if word is present in a set.

The main module is a C extension, there is also a pure python code.

piątek, 8 kwietnia 2011

Python: C extensions - sequence-like object

If class have to support standard len() function or operator in, then must be a sequence-like. This require variable of type PySequenceMethods, that store addresses of proper functions. Finally address of this structure have to be assigned to tp_as_sequence member of main PyTypeObject variable.

Here is sample code:

static PySequenceMethods class_seq;

static PyTypeObject class_type_dsc = {

classmeth_len(PyObject* self) {
 if (not error)
  return sequence_size;
  return -1;

classmeth_contains(PyObject* self, PyObject* value) {
 if (not error) {
  if (value in self)
   return 1;
   return 0;
  return -1;

PyInit_module() {
 class_seq.sq_length   = classmeth_len;
 class_seq.sq_contains = classmeth_contains;

 class_type_dsc.tp_as_sequence = &class_seq;