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

# in some cases you might want to adjust your compiler (the same is applicable for `poetry install`)
CC='gcc' CFLAGS='-march=native' pip install trie-again

Usage

# create an instance
from trie_again import Trie

# if you want to use faster version
from trie_again import CyTrie

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 (adjust compiler options if needed)
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.3.tar.gz (5.7 kB view details)

Uploaded Source

File details

Details for the file trie_again-0.2.3.tar.gz.

File metadata

  • Download URL: trie_again-0.2.3.tar.gz
  • Upload date:
  • Size: 5.7 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: poetry/1.3.2 CPython/3.10.9 Darwin/21.6.0

File hashes

Hashes for trie_again-0.2.3.tar.gz
Algorithm Hash digest
SHA256 58540414d20bbba4ef342b4d20a61a7ce56a331710f90542805567e0d020969b
MD5 98095cd674457a9fa959f635456712d9
BLAKE2b-256 5a3210d0d2f54a5284df96ade5c3b969c9e8f6999b9dbc04f6add1ddd059e4d1

See more details on using hashes here.

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