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.

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.


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 27th, 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.