Tries are special kind of search trees. It is mainly used for storing and retrieving strings.

approximate string matching

Technique of finding strings that match a pattern approximately. Examples are the Levenshtein distance, Hamming distance, Edit distance. When using tree data structures, like Trie Data Structure, we need to consider if we want to support fuzzy string matching (original name: Approximate string matching) when implementing the search function.

Implementation

this library is archived on github?

{shell} pip install pygtrie

from lorem_text import lorem
import pygtrie

long_string = lorem.words(20).split(" ")
t = pygtrie.StringTrie()

for word in long_string:
	t[word] = True

See https://pygtrie.readthedocs.io/en/stable/

Iterate through the trie:

Consider if iterating through the trie is really necessary. It kinda defeats the purpose of a trie structure if we need to manually iterate through it. Maybe there are some edge cases.

Modifications on the search functions

Hamming distance