1 files changed, 27 insertions, 0 deletions
diff --git a/sqlglot/trie.py b/sqlglot/trie.py
new file mode 100644
index 0000000..a234107
--- /dev/null
+++ b/sqlglot/trie.py
@@ -0,0 +1,27 @@
+def new_trie(keywords):
+    trie = {}
+
+    for key in keywords:
+        current = trie
+
+        for char in key:
+            current = current.setdefault(char, {})
+        current[0] = True
+
+    return trie
+
+
+def in_trie(trie, key):
+    if not key:
+        return (0, trie)
+
+    current = trie
+
+    for char in key:
+        if char not in current:
+            return (0, current)
+        current = current[char]
+
+    if 0 in current:
+        return (2, current)
+    return (1, current)