Skip to main content

Trie data structure for prefix search and text completion

Project description

Trie Again: Python Trie implementation optimized for T9 completion

Installation

pip install trie-again

Usage

# create an instance
from trie_again import Trie

trie = Trie()

# insert a single word
trie.insert('boy')

# insert a list of words
trie.extend(['bondage', 'coverage'])

# insert a list of words with multipliers (useful when parsing json)
data = {
    'bondage': 10,
    'coverage': 20,
}
trie.extend(data.keys(), data.values())

# check key in trie
print('bondage' in trie)
# True

# list all keys, sorted by usage
print(list(trie))
# ['coverage', 'bondage', 'boy']

# complete simple, sorted by usage
print(list(trie.complete('b')))
# ['bondage', 'boy']

T9 Like completion

# complete with t9 like approach
print(list(trie.complete(['bc', 'o', 'vn'])))
# ['coverage', 'bondage']

How it works?


b o y
b o n d a g e
c o v e r a g e
^ ^ ^
1 2 3

We use these groups to complete: bc, o, vn. It means that at position 1 it the letter may be b or c, at position 2 only o, at position 3 v or n.

Test

# test behavior
poetry run pytest

# test performance
poetry run pytest --benchmark

Dev

# very start
poetry install

# install pre commit
poetry run pre-commit install

# lint
poetry run black .
poetry run flake8 .
poetry run mypy .

# coverage
poetry run coverage run -m pytest && poetry run coverage report -m

# build package: limiting to sdist to compile it on install
poetry build -f sdist

Read an article about the trie, friends!

https://blagovdaryu.hashnode.dev/ok-lets-trie-t9-in-python

Project details


Download files

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

Source Distribution

trie_again-0.2.0.tar.gz (6.3 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page