Skip to main content
Python Software Foundation 20th Year Anniversary Fundraiser  Donate today!

Hashed Trie data structure for faster memory efficient and fast keyword indexing and lookup

Project description

Hash trie


Hash trie is an enhanced Trie data structure stores keyword indexes for faster keyword lookup. The storage is done in such a way that it does efficient memory usage and faster lookup.


Importing and instantiating

from pyhtrie.htrie import Trie
trie = Trie()


Syntax : trie.index_text(data, keyword_to_index)

data : Data can be any data to index keyword_to_index : Keyword associated with the data indexed

trie.index_text('Batman', 'batman')
trie.index_text('Bash', 'bash')

Prefix match

Syntax : trie.prefix_match(prefix_text_to_search)

The function returns all data matching the prefix text

prefix_text_to_search : Will be the prefix text on which the search will be performed. If there are no nodes matching the route of the prefix text then it will return an empty array


Pattern match

Syntax : trie.pattern_match(pattern_text_to_search)

This function returns all data associated with the text pattern. When compared to the prefix_match function, this function need not necessarily require the pattern_text_to_search to match with the prefix of the keyword to be searched for. The pattern_text_to_search can appear anywhere within the keyword

pattern_text_to_search : Is the text pattern to be searched.


Storage details

The keywords to be indexed are stored in a Trie data structure as can be seen in the image below. However for faster indexing of pattern match within keywords, each node in the trie is added to the hash-map with the letter corresponding to the node being the key.


So if you need to search for any words beginning with 'ca', then prefix_match('ca') will return [cat, car, cast] as in a regular trie. However, if you want to search for any words with 'at' in them, you can use the function pattern_match('as') that will return [cat, batman]. The prefix match is done with the help of the hash-map. When a prefix match of 'at' is done, the hash-map is checked for the letter 'a' in 'at'. This returns a list of three a nodes [a,a,a] each pointing to a correspinding 'a' node in the tries as shown in the figure above. Then each of them are traversed to see which of them have the next node as 't' of 'at'. The result will be the 't' of 'cat' and the 't' preceding 'm' in 'batman'. Then the algorithm performs a collection operation from each of these 't's returned to retrieve keywords stored under those t's. The result, as can be inferred from the figure above, will be [cat, batman]

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for pyhtrie, version 1.0.0
Filename, size File type Python version Upload date Hashes
Filename, size pyhtrie-1.0.0-py2-none-any.whl (4.3 kB) File type Wheel Python version py2 Upload date Hashes View
Filename, size pyhtrie-1.0.0.tar.gz (2.8 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page