Lisp: PATRICIA


This article describes an implementation of the PATRICIA trie search algorithm (“Practical Algorithm To Retrieve Information Coded in Alphanumeric”, devised by Donald D. Morrison in 1968) in the Lisp programming language.

Please see TAOCP, vol. III, Section 6.3, Algorithm P, as well as the answer to the excercise 15 of that section for an excellent description and analysis of the algorithm.

The distribution package is signed with my PGP key having the fingerprint of D853 E6A9 F0D1 E01C 4833 DF59 75F7 BBFB 009E 3949.

PATRICIA Dictionary

TRIE &key (key #'identity)
Create an empty PATRICIA trie. key is a designator for a function of one argument that is used for obtaining strings of text which is being indexed.
EMPTY-P trie
T if trie is empty.
SEARCH trie k &key (prefix t)
Search for k in trie. prefix of T specifies a prefix search, i.e. a search for all strings that begin with K.
INSERT trie obj
Insert obj into trie.
GRAPH trie path
Output a Graphviz graph that depicts trie into a file that is specified by path.

Usage

The following is a demonstration of PATRICIA with the example that can be found in TAOCP:

The following is a vizualisation of the trie created in the previous example. The graph is produced using PATRICIA:GRAPH:

The following is a demonstration of PATRICIA's Unicode compliance:

Performance

The following demonstrates the speed of 240,000 searches per second for a prefixed search in a trie with 99,171 entries. The numbers were obtained using the Clozure Common Lisp version 1.11 under Debian GNU/Linux version 8.7 running on an Intel Core i7 CPU @2.93GHz.

Vadim Penzin, January 27th, 2017


I hereby place this article along with the accompanying source code into the public domain.
You are welcome to contact me by writing to dmcrypt at this domain.
I publish this information in the hope that it will be useful, but without ANY WARRANTY.
You are responsible for any and all consequences that may arise as the result of using this information.