This is a pre-production deployment of Warehouse, however changes made here WILL affect the production instance of PyPI.
Latest Version Dependencies status unknown Test status unknown Test coverage unknown
Project Description

vtrie

Trie structure supporting approximate string matching (substitutions only) for Python (2.x and 3.x).

Note

Only ascii strings are supported. Hence, Python 3 users should use ‘b’ prefix to insert strings into the trie.

Installation

pip install vtrie

Features

  • It is similar to a dict() in general usage, and supports much of the dict() interface:
    • __len__(): number of items in the trie
    • __contains()__
    • __getitem()__
    • __setitem()__
    • __delitem()__
    • __sizeof()__: size of the trie in bytes
    • __repr()__: dict-like output, showing contents of the trie
    • has_key()
    • setdefault()
    • get()
    • pop()
    • popitem()
    • keys()
    • values()
    • items()
    • iterkeys()
    • itervalues()
    • iteritems()
  • Trie-specific methods:
    • num_nodes(): number of nodes
    • longest_prefix(k): find longest key matching the beginning of k, returning (key, value) pair as a 2-tuple. None is returned if no match.
    • suffixes(k): iterate over all (suffix, value) pairs as 2-tuples, that have k as a prefix.
    • neighbors(key = k, maxhd = n): iterate over all (Hamming distance, key, value) triples, as 3 tuples, where key and k differ by at least 1, but maximally n characters. Note, one can only search for neighbors of existing keys.
    • pairs(keylen = l, maxhd = n): iterate over ALL (Hamming distance, key1, value1, key2, value2) 5-tuples where key1 and key2 differ by at least 1, but maximally n characters. Note, pairs() returns a dirty iterator, meaning that nodes in the trie are modified while the iterator is running. An exception will be thrown when iterating with more than one dirty iterator.
  • Pickling

Usage

Create a trie:

>>> from vtrie import Trie
>>> t = Trie()

Add strings to the trie. Currently, only ascii strings are supported:

>>> t[b"Hello"] = 123
>>> t[b"World"] = {"my": "dict"}
>>> t[b"foo"] = None

Check if “Hello” is in the trie:

>>> b"Hello" in t
True

Show all inserted strings sharing the same prefix:

>>> t[b"foo"] = 0
>>> t[b"foobar"] = 1
>>> t[b"fooo"] = 2
>>> t[b"hello"] = 3
>>> list(t.suffixes(b"fo"))
[('o', 0), ('obar', 1), ('oo', 2)]

Search for keys that differ by less than a given number of substitutions from the provided key. The results are tuples with first the Hamming distance between the given key and the found key, then the found key and its value:

>>> t[b"hello world"] = 0
>>> t[b"*ello world"] = "a"
>>> t[b"*ell* world"] = "b"
>>> t[b"*ell* w*rld"] = "c"
>>> t[b"hell* w*rl*"] = "d"
>>> list(t.neighbors(b"hello world", maxhd = 1))
[(1, '*ello world', 'a')]
>>> list(t.neighbors(b"hello world", maxhd = 2))
[(1, '*ello world', 'a'), (2, '*ell* world', 'b')]
>>> print("\n".join(map(str,list(t.neighbors(b"hello world", 3)))))
(3, 'hell* w*rl*', 'd')
(1, '*ello world', 'a')
(2, '*ell* world', 'b')
(3, '*ell* w*rld', 'c')

Search for all keys of a certain length that are within a certain Hamming of each other. The results are tuples with first the Hamming distance between the found keys, then the first key and its value, and then the second key and its value:

>>> print("\n".join(map(str,list(t.pairs(keylen = 11, maxhd = 2)))))
(1, 'hello world', 0, '*ello world', 'a')
(2, 'hello world', 0, '*ell* world', 'b')
(2, 'hell* w*rl*', 'd', '*ell* w*rld', 'c')
(1, '*ello world', 'a', '*ell* world', 'b')
(2, '*ello world', 'a', '*ell* w*rld', 'c')
(1, '*ell* world', 'b', '*ell* w*rld', 'c')
Release History

Release History

0.0.2

This version

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

0.0.1

History Node

TODO: Figure out how to actually get changelog content.

Changelog content for this version goes here.

Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit.

Show More

Download Files

Download Files

TODO: Brief introduction on what you do with files - including link to relevant help section.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
vtrie-0.0.2.tar.gz (34.3 kB) Copy SHA256 Checksum SHA256 Source Aug 25, 2016

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS HPE HPE Development Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting