## Byte tries in Rust with Python bindings
### Installation
Install from PyPI (only built for Python 3.10+ on Linux)
```
pip install byte-prefix-tree
```
### Manual installation
Make sure you have Rust installed, then do the following:
```bash
git clone https://github.com/bastiscode/byte-trie.git
cd byte-trie
pip install maturin[patchelf]
maturin develop --release
```
### Usage
Currently implemented tries:
- Patricia trie
- Adaptive radix trie
Key needs to be a bytes object, value can be anything.
Make sure that the key never contains a 255 byte, as it is used as a terminator internally. For utf8-encoded text this is always the case, but for other types of data you might need to encode it in a way that ensures this.
```python
from byte_trie import PatriciaTrie, AdaptiveRadixTrie
pt = PatriciaTrie()
# add key-value pairs
pt.insert(b"hello", 1)
pt.insert(b"world", 2)
# delete key
print(pt.delete(b"hello")) # 1
# check for keys and prefixes
print(pt.contains(b"hello")) # False
print(pt.contains(b"world")) # True
print(pt.contains(b"wor")) # False
print(pt.contains_prefix(b"hel")) # False
print(pt.contains_prefix(b"wor")) # True
# get values
print(pt.get(b"hello")) # None
print(pt.get(b"world")) # 2
# overwrite
print(pt.insert(b"world", 3)) # 2
print(pt.get(b"world")) # 3
# continuations for prefix
print(pt.continuations(b"wo")) # [(b'world', 3)]
# prefixes of some key, returns list of (prefix length, value) tuples
key = b"world cup"
prefix_matches = pt.prefix_matches(key)
print(prefix_matches) # [(5, 3)]
print(
[(key[:length].decode(), value) for length, value in prefix_matches]
) # [('world', 3)]
# same for ART
art = AdaptiveRadixTrie()
art.insert(b"hello", 1)
art.insert(b"world", 2)
print(art.delete(b"hello")) # 1
print(art.contains(b"hello")) # False
print(art.contains(b"world")) # True
print(art.contains(b"wor")) # False
print(pt.contains_prefix(b"hel")) # False
print(pt.contains_prefix(b"wor")) # True
print(art.get(b"hello")) # None
print(art.get(b"world")) # 2
print(art.insert(b"world", 3)) # 2
print(art.get(b"world")) # 3
print(art.continuations(b"wo")) # [(b'world', 3)]
key = b"world cup"
prefix_matches = art.prefix_matches(key)
print(prefix_matches) # [(5, 3)]
print(
[(key[:length].decode(), value) for length, value in prefix_matches]
) # [('world', 3)]
```
Raw data
{
"_id": null,
"home_page": null,
"name": "byte-prefix-tree",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.10",
"maintainer_email": null,
"keywords": "utilities, trie, byte, rust, python, patricia, art, radix",
"author": null,
"author_email": "Sebastian Walter <swalter@cs.uni-freiburg.de>",
"download_url": null,
"platform": null,
"description": "## Byte tries in Rust with Python bindings\n\n### Installation\n\nInstall from PyPI (only built for Python 3.10+ on Linux)\n\n```\npip install byte-prefix-tree\n```\n\n### Manual installation\n\nMake sure you have Rust installed, then do the following:\n\n```bash\ngit clone https://github.com/bastiscode/byte-trie.git\ncd byte-trie\npip install maturin[patchelf]\nmaturin develop --release\n```\n\n### Usage\n\nCurrently implemented tries:\n- Patricia trie\n- Adaptive radix trie\n\nKey needs to be a bytes object, value can be anything.\nMake sure that the key never contains a 255 byte, as it is used as a terminator internally. For utf8-encoded text this is always the case, but for other types of data you might need to encode it in a way that ensures this.\n\n```python\nfrom byte_trie import PatriciaTrie, AdaptiveRadixTrie\n\npt = PatriciaTrie()\n\n# add key-value pairs\npt.insert(b\"hello\", 1)\npt.insert(b\"world\", 2)\n\n# delete key\nprint(pt.delete(b\"hello\")) # 1\n\n# check for keys and prefixes\nprint(pt.contains(b\"hello\")) # False\nprint(pt.contains(b\"world\")) # True\nprint(pt.contains(b\"wor\")) # False\nprint(pt.contains_prefix(b\"hel\")) # False\nprint(pt.contains_prefix(b\"wor\")) # True\n\n# get values\nprint(pt.get(b\"hello\")) # None\nprint(pt.get(b\"world\")) # 2\n\n# overwrite\nprint(pt.insert(b\"world\", 3)) # 2\nprint(pt.get(b\"world\")) # 3\n\n# continuations for prefix\nprint(pt.continuations(b\"wo\")) # [(b'world', 3)]\n\n# prefixes of some key, returns list of (prefix length, value) tuples\nkey = b\"world cup\"\nprefix_matches = pt.prefix_matches(key)\nprint(prefix_matches) # [(5, 3)]\nprint(\n [(key[:length].decode(), value) for length, value in prefix_matches]\n) # [('world', 3)]\n\n# same for ART\nart = AdaptiveRadixTrie()\n\nart.insert(b\"hello\", 1)\nart.insert(b\"world\", 2)\n\nprint(art.delete(b\"hello\")) # 1\n\nprint(art.contains(b\"hello\")) # False\nprint(art.contains(b\"world\")) # True\nprint(art.contains(b\"wor\")) # False\nprint(pt.contains_prefix(b\"hel\")) # False\nprint(pt.contains_prefix(b\"wor\")) # True\n\nprint(art.get(b\"hello\")) # None\nprint(art.get(b\"world\")) # 2\n\nprint(art.insert(b\"world\", 3)) # 2\nprint(art.get(b\"world\")) # 3\n\nprint(art.continuations(b\"wo\")) # [(b'world', 3)]\n\nkey = b\"world cup\"\nprefix_matches = art.prefix_matches(key)\nprint(prefix_matches) # [(5, 3)]\nprint(\n [(key[:length].decode(), value) for length, value in prefix_matches]\n) # [('world', 3)]\n```\n\n",
"bugtrack_url": null,
"license": null,
"summary": "Tries with byte sequences as keys for Python and Rust",
"version": "0.3.1",
"project_urls": {
"Github": "https://github.com/bastiscode/byte-trie"
},
"split_keywords": [
"utilities",
" trie",
" byte",
" rust",
" python",
" patricia",
" art",
" radix"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "bd612bc92fb8c3f421f95d38a41320210fa279573a958ef2e52fd66d96eaf89a",
"md5": "3f12b7e503f61f497d6634b09c2dd4e5",
"sha256": "921921bd46292ea3cab3151cce7b047b11745c97c9989f3f2c640c146720800b"
},
"downloads": -1,
"filename": "byte_prefix_tree-0.3.1-cp312-cp312-manylinux_2_34_x86_64.whl",
"has_sig": false,
"md5_digest": "3f12b7e503f61f497d6634b09c2dd4e5",
"packagetype": "bdist_wheel",
"python_version": "cp312",
"requires_python": ">=3.10",
"size": 238181,
"upload_time": "2025-01-21T14:57:08",
"upload_time_iso_8601": "2025-01-21T14:57:08.467064Z",
"url": "https://files.pythonhosted.org/packages/bd/61/2bc92fb8c3f421f95d38a41320210fa279573a958ef2e52fd66d96eaf89a/byte_prefix_tree-0.3.1-cp312-cp312-manylinux_2_34_x86_64.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-01-21 14:57:08",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "bastiscode",
"github_project": "byte-trie",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "byte-prefix-tree"
}