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.

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

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:

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 27^{th}, 2017

I hereby place this article along with the accompanying source code into the public 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.