byte-prefix-tree


Namebyte-prefix-tree JSON
Version 0.3.1 PyPI version JSON
download
home_pageNone
SummaryTries with byte sequences as keys for Python and Rust
upload_time2025-01-21 14:57:08
maintainerNone
docs_urlNone
authorNone
requires_python>=3.10
licenseNone
keywords utilities trie byte rust python patricia art radix
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            ## 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"
}
        
Elapsed time: 0.65803s