{
    "info": {
        "author": "Florian Leitner",
        "author_email": "florian.leitner@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 4 - Beta",
            "Intended Audience :: Developers",
            "Intended Audience :: Science/Research",
            "License :: OSI Approved :: Apache Software License",
            "Programming Language :: Python :: 2.7",
            "Programming Language :: Python :: 3",
            "Topic :: Scientific/Engineering :: Information Analysis",
            "Topic :: Software Development :: Libraries :: Python Modules",
            "Topic :: Text Processing :: Indexing"
        ],
        "description": "patricia-trie\n=============\n\nA pure Python 2.7+ implementation of a PATRICIA trie for effcient matching\nof string collections on text.\n\nNote that you probably first want to have a look at the Python wrapper\n`marisa-trie`_ or its `PyPi package <https://github.com/kmike/marisa-trie/>`_\nbefore using particia-trie; according to simple timeit comparisons, these\nwrappers for the C-based MARISA library are about twice as fast as this pure\nPython implementation.\n\n`patricia-trie`_ does have its merits, however - it is small, clear, and\nhas a very clean interface that imitates the `dict` API and works with Py3k.\n\nInstallation\n------------\n\n::\n\n  pip install patricia-trie\n\nUsage\n-----\n\n::\n\n    >>> T = trie('root', key='value', king='kong') # a root value and two pairs\n    >>> T['four'] = None # setting new values as in a dict\n    >>> '' in T # check if the value exits (note: the [empty] root is '')\n    True\n    >>> 'kong' in T # existence checks as in a dict\n    False\n    >>> T['king'] # get the value for an exact key ... as in a dict\n    'kong'\n    >>> T['kong'] # error from non-existing keys (as in a dict)\n    Traceback (most recent call last):\n        ...\n    KeyError: 'kong'\n    >>> len(T) # count keys (\"terminals\") in the tree\n    4\n    >>> sorted(T) # plus \"traditional stuff\": .keys(), .values(), and .items()\n    ['', 'four', 'key', 'king']\n    >>> # scanning a string S with key(S), value(S), and item(S):\n    >>> S = 'keys and kewl stuff'\n    >>> T.key(S) # report the (longest) key that is a prefix of S\n    'key'\n    >>> T.value(S, 9) # using offsets; NB: a root value always matches!\n    'root'\n    >>> del T[''] # interlude: deleting keys (here, the root)\n    >>> T.item(S, 9) # raise error if no key is a prefix of S\n    Traceback (most recent call last):\n        ...\n    KeyError: 'k'\n    >>> # info: the error string above contains the matched path so far\n    >>> T.item(S, 9, default=None) # avoid the error by specifying a default\n    (None, None)\n    >>> # iterate all matching content with keys(S), values(S), and items(S):\n    >>> list(T.items(S))\n    [('key', 'value')]\n    >>> T.isPrefix('k') # reverse lookup: check if S is a prefix of any key\n    True\n    >>> T.isPrefix('kong')\n    False\n    >>> sorted(T.iter('k')) # and get all keys that have S as prefix\n    ['key', 'king']\n\n*Deleting* entries is a \"half-supported\" operation only. The key appears\n\"removed\", but the trie is not actually changed, only the node state is\nchanged from terminal to non-terminal. I.e., if you frequently delete keys,\nthe compaction will become fragmented and less efficient. To mitigate this\neffect, make a copy of the trie (using a copy constructor idiom)::\n\n    T = trie(**T)\n\nIf you are only interested in scanning for the *presence* of keys, but do not\ncare about mapping a value to each key, using ``None`` as the value of your\nkeys and scanning with ``key(S, None, start=i)`` at every offset ``i`` in the\nstring ``S`` is perfectly fine (because the return value will be the key\nstring iff a full match was made and ``None`` otherwise)::\n\n    >>> T = trie(present=None)\n    >>> T.key('is absent here', None, start=3) # start scanning at offset 3\n    >>> T.key('is present here', None, start=3) # start scanning at offset 3\n    'present'\n\nAPI\n---\n\ntrie(``*value``, ``**branch``)\n    | Create a new tree node.\n    | Any arguments will be used as the ``value`` of this node.\n    | If keyword arguments are given, they initialize a whole ``branch``.\n    | Note that `None` is a valid value for a node.\n\ntrie.isPrefix(``prefix``)\n    | Return True if any key starts with ``prefix``.\n\ntrie.item(``string``, ``start=0``, ``end=None``, ``default=NULL``)\n    | Return the key, value pair of the longest key that is a prefix of ``string`` (beginning at ``start`` and ending at ``end``).\n    | If no key matches, raise a `KeyError` or return the `None`, ``default`` pair if any ``default`` value was set.\n\ntrie.items([``string`` [, ``start`` [, ``end`` ]]])\n    Return all key, value pairs (for keys that are a prefix of ``string``\n    (beginning at ``start`` (and terminating before ``end``))).\n\ntrie.iter(``prefix``)\n    Return an iterator over all keys that start with ``prefix``.\n\ntrie.key(``string``, ``start=0``, ``end=None``, ``default=NULL``)\n    | Return the longest key that is a prefix of ``string`` (beginning at ``start`` and ending at ``end``).\n    | If no key matches, raise a `KeyError` or return the ``default`` value if it was set.\n\ntrie.keys([``string`` [, ``start`` [, ``end`` ]]])\n    Return all keys (that are a prefix of ``string``\n    (beginning at ``start`` (and terminating before ``end``))).\n\ntrie.value(``string``, ``start=0``, ``end=None``, ``default=NULL``)\n    | Return the value of the longest key that is a prefix of ``string`` (beginning at ``start`` and ending at ``end``).\n    | If no key matches, raise a `KeyError` or return the ``default`` value if it was set.\n\ntrie.values([``string`` [, ``start`` [, ``end`` ]]])\n    Return all values (for keys that are a prefix of ``string``\n    (beginning at ``start`` (and terminating before ``end``))).\n\n\nHistory\n-------\n\n1. Initial release.\n2. *Update*: Full documentation and corrections.\n3. *Feature*: optional keyword parameters to indicate an offset ``start`` when\n   scanning a string with the methods key(), keys(), item(), items(), value(),\n   and values(), so it is not necessary to slice strings for each scan::\n\n       >>> # Old usage to scan 'string' in 'the string' was:\n       >>> T.keys('the string'[4:])\n       >>> # With the new optional keyword parameter:\n       >>> T.keys('the string', start=4)\n\n4. **Important API change**: item() now returns key, value pairs even when a\n   default value is given, using ``None`` as the \"key\"::\n\n       >>> # Old behaviour was:\n       >>> T.item('string', default=False)\n       False\n       >>> # While now, the same call produces:\n       >>> T.item('string', default=False)\n       None, False\n\n   *Improvement*: Switched from using dictionaries to two-tuple lists\n   internally (thanks to Pedro Gaio for the suggestion!) to improve the\n   overall performance a bit (about 20% faster on simple tests).\n5. *Bugfix*: When splitting edges while adding a new key that is shorter than\n   the current edge, a index error would have occurred.\n6. *Feature*: Added optional keyword parameter ``end`` to the methods key(),\n   keys(), item(), items(), value(), and values(), so it is not necessary to\n   scan within a window::\n\n       T.key('string', start=2, end=3, default=None)\n       T.keys('string', start=2, end=3)\n\n7. *Improvement*: Switched back to a very efficient internal dictionary\n   implementation; Runs about two- to three times as fast as the two-tuple\n   list from update 4 against the simple (and newly added) ``time_patricia.py``\n   \"benchmark\".\n8. *Bugfix*: Correct behavior when using a negative start index.\n   Added a comparison to `marisa-trie`_ - by now, it seems, patricia-trie\n   is roughly only a factor two slower than the marisa-trie PyPI version\n   wrapping a C library. Also makes it nice to compare the two usages.\n9. *Bugfix* (15/09/2014): Correct behaviour when using an exactly matching\n   prefix as query (issue described in #1 by @zachrahan). Also fixes\n   code-smells (PEP8, code complexity) and a failing test case code.\n10. *Bugfix* (14/12/2014): Added the missing README to PyPI package.\n    (MANIFEST.in)\n   \nCopyright\n---------\n\nCopyright 2013, Florian Leitner. All rights reserved.\n\nLicense\n-------\n\n`Apache License v2 <http://www.apache.org/licenses/LICENSE-2.0.html>`_\n\n.. _marisa-trie: https://code.google.com/p/marisa-trie/\n.. _patricia-trie: https://www.github.com/fnl/patricia-trie/",
        "description_content_type": null,
        "docs_url": null,
        "download_url": "UNKNOWN",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "http://www.github.com/fnl/patricia-trie",
        "keywords": null,
        "license": "Apache License v2",
        "maintainer": null,
        "maintainer_email": null,
        "name": "patricia-trie",
        "package_url": "https://pypi.org/project/patricia-trie/",
        "platform": "UNKNOWN",
        "project_url": "https://pypi.org/project/patricia-trie/",
        "project_urls": {
            "Download": "UNKNOWN",
            "Homepage": "http://www.github.com/fnl/patricia-trie"
        },
        "release_url": "https://pypi.org/project/patricia-trie/10/",
        "requires_dist": null,
        "requires_python": null,
        "summary": "A pure Python implementation of a PATRICIA trie.",
        "version": "10"
    },
    "last_serial": 1343322,
    "releases": {
        "1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "765584d56bc2ff1dd0ddcc6db80590ef",
                    "sha256": "03dca2b4391ec3f0487da0af0f1459f9a69ed351a6ff6e84fb2a890665af86fa"
                },
                "downloads": -1,
                "filename": "patricia-trie-1.tar.gz",
                "has_sig": false,
                "md5_digest": "765584d56bc2ff1dd0ddcc6db80590ef",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 3603,
                "upload_time": "2013-05-30T06:15:27",
                "url": "https://files.pythonhosted.org/packages/f9/dd/f7634eb4a26c3203556e0a130711dcaccccfac7e33abfe955a66a1b51c05/patricia-trie-1.tar.gz"
            }
        ],
        "10": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "ac92720655cb302f084e1651c7d204e3",
                    "sha256": "65a35219bf211b4e4b34bdd9e858c008e1699e23c43b3fb4542726c996966bae"
                },
                "downloads": -1,
                "filename": "patricia-trie-10.tar.gz",
                "has_sig": false,
                "md5_digest": "ac92720655cb302f084e1651c7d204e3",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6663,
                "upload_time": "2014-12-14T16:28:04",
                "url": "https://files.pythonhosted.org/packages/cf/bb/aa3e619457bf0c36d0867a25be958b274f5bf29b4e09eb715fc8fae7dc02/patricia-trie-10.tar.gz"
            }
        ],
        "2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "d3b3e86cc798ed1109603aa9f8cbd104",
                    "sha256": "467a537a4859dc717e3db592cdb525c97712122ea999c980ba219fdf7bc18f4a"
                },
                "downloads": -1,
                "filename": "patricia-trie-2.tar.gz",
                "has_sig": false,
                "md5_digest": "d3b3e86cc798ed1109603aa9f8cbd104",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 4030,
                "upload_time": "2013-05-30T07:31:23",
                "url": "https://files.pythonhosted.org/packages/74/5d/2216364d071f4a7e3a7aa843e4e404450af85763621b4aefffe2cc17699e/patricia-trie-2.tar.gz"
            }
        ],
        "5": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "da725e133b3a698af7e7802e35245506",
                    "sha256": "5484955e3f03a4013d163a1cdba52c8925fdfe240912169575b0e4cf7125385d"
                },
                "downloads": -1,
                "filename": "patricia-trie-5.tar.gz",
                "has_sig": false,
                "md5_digest": "da725e133b3a698af7e7802e35245506",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5005,
                "upload_time": "2013-06-06T15:02:08",
                "url": "https://files.pythonhosted.org/packages/87/78/c737526ed3c169f439c3c1ec1d7e038041e30df2943832b2e45fdaebb721/patricia-trie-5.tar.gz"
            }
        ],
        "7": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "a28107e21e79100ffad33083c334d56c",
                    "sha256": "edb0a2480d76170bfab1d99caba1bced2a8eecd07b03af5b66f6ac3aaa15463f"
                },
                "downloads": -1,
                "filename": "patricia-trie-7.tar.gz",
                "has_sig": false,
                "md5_digest": "a28107e21e79100ffad33083c334d56c",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5530,
                "upload_time": "2013-06-07T17:39:41",
                "url": "https://files.pythonhosted.org/packages/69/83/c55c2ecdfbe1d20f681105d01de4dabc406dd1c12e91d9b3166dcf871156/patricia-trie-7.tar.gz"
            }
        ],
        "8": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "0fbfa824977af80e2b9c8d477c61b415",
                    "sha256": "04bcc3e59438ee2970a77d2de7c8d226686f6487f6c1a5d8fe59f12a9e450b10"
                },
                "downloads": -1,
                "filename": "patricia-trie-8.tar.gz",
                "has_sig": false,
                "md5_digest": "0fbfa824977af80e2b9c8d477c61b415",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 5610,
                "upload_time": "2013-06-07T18:22:08",
                "url": "https://files.pythonhosted.org/packages/15/d9/d7dbc475fb4e89213059e9e3aca4dc5aab2355cd2d732b6e5a975e4ec4b5/patricia-trie-8.tar.gz"
            }
        ],
        "9": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "5a21bdd03be814274b87e9b691933fb6",
                    "sha256": "f8ba13a56b768eac8851edaeed091e0269d7e42856d52560856cefae85c0546f"
                },
                "downloads": -1,
                "filename": "patricia-trie-9.tar.gz",
                "has_sig": false,
                "md5_digest": "5a21bdd03be814274b87e9b691933fb6",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6090,
                "upload_time": "2014-09-15T10:21:44",
                "url": "https://files.pythonhosted.org/packages/97/57/4bb15317352c5d2b9578e8524f8e1cd3bba3de4b5a486eed5cbdc4851388/patricia-trie-9.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "ac92720655cb302f084e1651c7d204e3",
                "sha256": "65a35219bf211b4e4b34bdd9e858c008e1699e23c43b3fb4542726c996966bae"
            },
            "downloads": -1,
            "filename": "patricia-trie-10.tar.gz",
            "has_sig": false,
            "md5_digest": "ac92720655cb302f084e1651c7d204e3",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 6663,
            "upload_time": "2014-12-14T16:28:04",
            "url": "https://files.pythonhosted.org/packages/cf/bb/aa3e619457bf0c36d0867a25be958b274f5bf29b4e09eb715fc8fae7dc02/patricia-trie-10.tar.gz"
        }
    ]
}