Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
# -*- coding: utf-8 -*-
#author: rex
#created: 2010-08-01 20:24
#source uri:
# escape bug fix by fcicq @ 2012.8.19
# python3 compatible by EricDuminil @ 2017.03.
import re
class Trie():
"""Regexp::Trie in python. Creates a Trie out of a list of words. The trie can be exported to a Regexp pattern.
The corresponding Regexp should match much faster than a simple Regexp union."""
def __init__(self): = {}
def add(self, word):
ref =
for char in word:
ref[char] = char in ref and ref[char] or {}
ref = ref[char]
ref[''] = 1
def dump(self):
def quote(self, char):
return re.escape(char)
def _pattern(self, pData):
data = pData
if "" in data and len(data.keys()) == 1:
return None
alt = []
cc = []
q = 0
for char in sorted(data.keys()):
if isinstance(data[char], dict):
recurse = self._pattern(data[char])
alt.append(self.quote(char) + recurse)
q = 1
cconly = not len(alt) > 0
if len(cc) > 0:
if len(cc) == 1:
alt.append('[' + ''.join(cc) + ']')
if len(alt) == 1:
result = alt[0]
result = "(?:" + "|".join(alt) + ")"
if q:
if cconly:
result += "?"
result = "(?:%s)?" % result
return result
def pattern(self):
return self._pattern(self.dump())
if __name__ == '__main__':
t = Trie()
for w in ['foobar', 'foobah', 'fooxar', 'foozap', 'fooza']:
#=> "foo(?:ba[hr]|xar|zap?)"
Copy link

heytitle commented Aug 6, 2019

Hi Eric,

I'm currently working on a project and using this gist. Comparing to other Tries libraries, yours is quite minimal and sufficient for our work.

It would be good if we could import your gist as a module instead of this snippet.

Would you mind creating a pip module for this snippet? I could also do that if you don't have time and later transfer to your Github.


Copy link

EricDuminil commented Aug 6, 2019

Copy link

ddelange commented Apr 9, 2020

@EricDuminil I took the liberty and mentioned you in the MIT License!

cc @heytitle

Copy link

EricDuminil commented Apr 9, 2020

@ddelange: Thank you very much. The project looks good!

Copy link

Yoric commented Dec 11, 2020

Trying to port this code to Rust :)

What is q, exactly?

Copy link

ddelange commented Dec 11, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment