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!
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)
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
Algorithm | Hash digest | |
---|---|---|
SHA256 | 58540414d20bbba4ef342b4d20a61a7ce56a331710f90542805567e0d020969b |
|
MD5 | 98095cd674457a9fa959f635456712d9 |
|
BLAKE2b-256 | 5a3210d0d2f54a5284df96ade5c3b969c9e8f6999b9dbc04f6add1ddd059e4d1 |