itoa on steroids

Function itoa implemented with SSE instructions is about 3 times faster then scalar CPU version. Read more.

Embedded in Academia

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

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
correctly.

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;
}

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

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.

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 = {
 ...
};

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

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


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

 class_type_dsc.tp_as_sequence = &class_seq;

 ...
}

pyahocorasick

Python module implementing Aho-Corasick algorithm has been released. C extension (for Py3k) and pure python code are available.

Internal memory fragmentation

In previous post I've advertised my text about trie representations.

Depending on particular representation internal memory fragmentation vary from 25% to 46% (in GNU libc). In other words if trie should occupy 100MB then in the worst case real memory usage is around 200MB. I've never suppose that fragmentation could be so significant.

When quite simple memory pools were used, then internal fragmentation has been cut down to 1-2%! Impressive.

Efficient trie representation

While implementing Aho-Corasick algorithm I've checked several trie representations.

Python3: import antigravity

Works fine!

Grafika komputerowa I

Całkiem udany skrypt do grafiki komputerowej autorstwa Przemysława Kiciaka udostępnił UW w ramach swojego portalu z materiałami dydaktycznymi. Obszerna tematyka, więc miejscami skrótowo i ogólnikowo, ale ogólnie wygląda zachęcająco.