google / pygtrie Goto Github PK

View Code? Open in Web Editor NEW

811.0 18.0 133.0 140 KB

Python library implementing a trie data structure.

License: Apache License 2.0

Python 100.00%

pygtrie's Introduction

pygtrie

pygtrie is a Python library implementing a trie data structure.

Trie data structure, also known as radix or prefix tree, is a tree associating keys to values where all the descendants of a node have a common prefix (associated with that node).

The trie module contains Trie, CharTrie and StringTrie classes each implementing a mutable mapping interface, i.e. dict interface. As such, in most circumstances, Trie could be used as a drop-in replacement for a dict, but the prefix nature of the data structure is trie’s real strength.

The module also contains PrefixSet class which uses a trie to store a set of prefixes such that a key is contained in the set if it or its prefix is stored in the set.

Features

A full mutable mapping implementation.
Supports iterating over as well as deleting a subtrie.
Supports prefix checking as well as shortest and longest prefix look-up.
Extensible for any kind of user-defined keys.
A PrefixSet supports “all keys starting with given prefix” logic.
Can store any value including None.

Installation

To install pygtrie, run:

pip install pygtrie

Or download the sources and save pygtrie.py file with your project.

Upgrading from 0.9.x

The 1.0 release introduced backwards incompatibility in naming. The module has been renamed from trie to pygtrie. Fortunately, updating scripts using pygtrie should boil down to replacing:

from pytrie import trie

with:

import pygtrie as trie

pygtrie's People

Contributors

Stargazers

Watchers

Forkers

pombredanne uikit0 jiajie999 hellcoderz senseb hurricane1260 luffyhwl nervenxc snachx leo-unc eykd encorechow zhengtang1120 kleopatra999 jianyuwang hughku artoria2e5 linearregression mar29th datavizweb dimazest asksandipd shobhit sniranjan 7758285 john-g-g phord rajpratim21 foobarai argentumblack benjamesbabala bigrlab mrzysv5 pythagoraskitty decpaul wannaphong deuteron warenlg amit2014 hcheruku pymia chenghuige dfbblwd limingjin10 knarfzy dbl0null buddyhello mina86 ewaszyszka briantoliveira qiang841129 leostormrage sixzhang igormq keohaneindustries xiaorancs cmaxcy xxcharles kaizhao02 nikhilraju 2208abhinav feitianyiren anshulh opengenus karthicksanjeevi shengyfu andrewwhwang dkandalam bsll czgdp1807 eakman ashuein 4theh shinroo manthanchauhan gksinghjsr seahrh dirtyhands2 moqiguzhu qiaofeiw jacobwegner saonam mikuh suparek danilevy1212 barseghyanartur xinshu vienking ustclink denisonlinus ogking damielcowen yyht cslyc sunader benthem keruizhu seyifeyi pandorawang neotim

pygtrie's Issues

Include `version` attribute in main module

It would be helpful if the main module has a __version__ attribute like most modules. This might be tricky to reconcile with the current way of versioning this lib (i.e. via version.py), but I think it would be an overall improvement.

Provide "rightmost key at most" and "leftmost key at least" queries (feature request)

Given a Trie, I'd like to be able to search for a key k, and get either k or the closest thing on either side of k.

More precisely, the query would yield one of these:

k and its value, if k is in the trie,
the immediate lexicographical predecessor (or successor) of k if one exists, or
the fact that the trie has no values before (or after) k.
(When I say "lexicographical" I'm talking about the ordering given by the structure of the trie.)

Currently I can see how to implement it by iteratively calling has_node, or iteratively calling iterkeys (or iteritems), building up a larger and larger prefix and maybe handling KeyError exceptions to decide when to go forward. Or it could be implemented naively by traversing over all keys linearly (but that wouldn’t take advantage of the convenient structure of a trie). Finally, I’m half-sure it could be implemented by using traverse, but it’s not obvious how. The traverse function seems to work like foldr on the path to a key—which should be enough, as long as you also implement a "rightmost child" or "leftmost child" query.

All of these options (except the naive one) involve non-trivial work that deals with the structure of the tree, so I think these queries should be handled internally by the class.

BUG no correct trie

when i use the CHARTRIE en give it a dicitonary to make a trie of it false to do so corectly.
For example giving the trei the words "NPM" en "NPS", among others.
gives folowing path :

while the word "NVG" does get corectly indexed:

What is wrong?

cannot install current version using pip

ayr@DESKTOP-DPGQQFH:/mnt/p/downloads$ pip install pygtrie
Collecting pygtrie
Using cached https://files.pythonhosted.org/packages/3c/93/557455c974a21dd7ec0da309b9223952457c1999072bfe1f8f47f6091eab/pygtrie-2.4.1.tar.gz
Complete output from command python setup.py egg_info:
running egg_info
creating pip-egg-info/pygtrie.egg-info
writing pip-egg-info/pygtrie.egg-info/PKG-INFO
writing top-level names to pip-egg-info/pygtrie.egg-info/top_level.txt
writing dependency_links to pip-egg-info/pygtrie.egg-info/dependency_links.txt
writing manifest file 'pip-egg-info/pygtrie.egg-info/SOURCES.txt'
Traceback (most recent call last):
File "", line 1, in
File "/tmp/pip-build-EXlvog/pygtrie/setup.py", line 177, in
distutils.core.setup(**kwargs)
File "/usr/lib/python2.7/distutils/core.py", line 151, in setup
dist.run_commands()
File "/usr/lib/python2.7/distutils/dist.py", line 953, in run_commands
self.run_command(cmd)
File "/usr/lib/python2.7/distutils/dist.py", line 972, in run_command
cmd_obj.run()
File "/home/ayr/.local/lib/python2.7/site-packages/setuptools/command/egg_info.py", line 296, in run
self.find_sources()
File "/home/ayr/.local/lib/python2.7/site-packages/setuptools/command/egg_info.py", line 303, in find_sources
mm.run()
File "/home/ayr/.local/lib/python2.7/site-packages/setuptools/command/egg_info.py", line 534, in run
self.add_defaults()
File "/home/ayr/.local/lib/python2.7/site-packages/setuptools/command/egg_info.py", line 570, in add_defaults
sdist.add_defaults(self)
File "/home/ayr/.local/lib/python2.7/site-packages/setuptools/command/py36compat.py", line 34, in add_defaults
self._add_defaults_python()
File "/home/ayr/.local/lib/python2.7/site-packages/setuptools/command/sdist.py", line 135, in _add_defaults_python
build_py = self.get_finalized_command('build_py')
File "/usr/lib/python2.7/distutils/cmd.py", line 311, in get_finalized_command
cmd_obj = self.distribution.get_command_obj(command, create)
File "/usr/lib/python2.7/distutils/dist.py", line 846, in get_command_obj
cmd_obj = self.command_obj[command] = klass(self)
TypeError: object() takes no parameters

----------------------------------------

Command "python setup.py egg_info" failed with error code 1 in /tmp/pip-build-EXlvog/pygtrie/
ayr@DESKTOP-DPGQQFH:/mnt/p/downloads$

readthedocs badges are broken

The supported URLs have changed apparently.

Cannot pickle Trie

Since node uses slots and getstate is not implemented, a Trie cannot be pickled:
TypeError: a class that defines __slots__ without defining __getstate__ cannot be pickled

Documentation example not working for longest_prefix()

The documentation shows: https://pygtrie.readthedocs.io/en/stable/#pygtrie.Trie.longest_prefix

But when I try to run the same example, it does not has a readable output:

import pygtrie
trie = pygtrie.StringTrie()
trie['foo'] = 'Foo'
trie['foo/bar/baz'] = 'Baz'
print( trie.longest_prefix('foo/bar/baz/qux') )
print( trie.longest_prefix('does/not/exist') )
# -->
<pygtrie.Trie._Step object at 0x000002519E36C818>
<pygtrie.Trie._NoneStep object at 0x000002519C09D0D0>

Initializing PrefixSet with an iterable does not eliminate longer keys.

Hi there!
Initializing PrefixSet like so:

from pygtrie import PrefixSet

x = PrefixSet(["aaa", "aa"])
print(len(x))

outputs 2 even though I'd expect it to print 1

How can i save and load a trie?

Inconsistent names?

Just a minor stuff but the repo is named pytrie, the Pypi package pygtrie and the python module trie....
Could it be worth to have a single name, such as pygtrie?
Thank you for your kind consideration!

provide a method to view the CharTrie graphically (feature request)

It would be great if a graphical view can be implemented for CharTries. ie,
trie['hi'] = 5
trie['he'] = 6

HTML can be used to produce,

h i -> 5
e -> 6

This feature can be useful for debugging or applications where close interactions with the data structure is required.

Error: "No module named 'packaging'"

Hi Googlers

I noticed an error when building my solution today. We use pygtrie in our solution and it seems that the crash we experienced is related to the release of pygtrie 2.4.0.

This is corroborated by:

the error message;
the timing of the release of pygtrie 2.4.0 (yesterday), and
Reverting to pygtrie 2.3.3 seems to resolve the problem.

The full error description can be found below:

Collecting pygtrie
  Downloading pygtrie-2.4.0.tar.gz (35 kB)
    ERROR: Command errored out with exit status 1:
     command: /usr/local/bin/python -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-p_3v3rdq/pygtrie/setup.py'"'"'; __file__='"'"'/tmp/pip-install-p_3v3rdq/pygtrie/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' egg_info --egg-base /tmp/pip-pip-egg-info-yevdgn7f
         cwd: /tmp/pip-install-p_3v3rdq/pygtrie/
    Complete output (5 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/tmp/pip-install-p_3v3rdq/pygtrie/setup.py", line 5, in <module>
        import packaging.version
    ModuleNotFoundError: No module named 'packaging'
    ----------------------------------------
ERROR: Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.

Apache v2 license (only) is incompatible with GPLv2

Unfortunately the Apache v2 license is generally considered to be incompatible with the GPLv2 license, making this library unusable from many projects.

The standard workaround for this (very common in the Rust community) is to license projects as MIT OR Apache 2.0, which means that contributions invoke the Apache 2.0 protections but downstream users can choose which license they want to accept the code under.

It would be excellent if pygtrie did as well.

pygtrie-0.9.1.linux-x86_64.exe weirdly named Windows exe on Pypi

You released a pygtrie-0.9.1.linux-x86_64.exe weirdly named Windows exe on Pypi..

Michal Nazarewicz replied:
Now, if only I knew how PyPi works and how exactly did I release that file…

Iterator over internal node structure (feature request)

It would be nice if there was a builtin way to iterate over the internal nodes in the trie like this:

            def _iternodes(self):
                """
                Generates all nodes in the trie
                """
                stack = deque([[self._root]])
                while stack:
                    for node in stack.pop():
                        yield node
                        stack.append(node.children.values())

That would make it much easier to write the Shortest Unique Prefix algorithm:

def shortest_unique_prefixes(items):
    """
    The shortest unique prefix algorithm.

    Args:
        items (list of str): returned prefixes will be unique wrt this set

    Returns:
        list of str: a prefix for each item that uniquely identifies it
           wrt to the original items.

    References:
        http://www.geeksforgeeks.org/find-all-shortest-unique-prefixes-to-represent-each-word-in-a-given-list/
        https://github.com/Briaares/InterviewBit/blob/master/Level6/Shortest%20Unique%20Prefix.cpp

    Requires:
        pip install pygtrie

    Doctest:
        >>> from pysseg.fnameproc import *
        >>> items = ["zebra", "dog", "duck", "dove"]
        >>> shortest_unique_prefixes(items)
        ['z', 'dog', 'du', 'dov']

    Timeing:
        >>> # make numbers larger to stress test
        >>> # L = max length of a string, N = number of strings,
        >>> # C = smallest gaurenteed common length
        >>> # (the setting N=10000, L=100, C=20 is feasible we are good)
        >>> import random
        >>> def make_data(N, L, C):
        >>>     rng = random.Random(0)
        >>>     return [''.join(['a' if i < C else chr(rng.randint(97, 122))
        >>>                      for i in range(L)]) for _ in range(N)]
        >>> items = make_data(N=1000, L=10, C=0)
        >>> %timeit shortest_unique_prefixes(items)
        17.5 ms ± 244 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
        >>> items = make_data(N=1000, L=100, C=0)
        >>> %timeit shortest_unique_prefixes(items)
        141 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
        >>> items = make_data(N=1000, L=100, C=70)
        >>> %timeit shortest_unique_prefixes(items)
        141 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
        >>> items = make_data(N=10000, L=250, C=20)
        >>> %timeit shortest_unique_prefixes(items)
        3.55 s ± 23 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    """
    import pygtrie
    from collections import deque
    if len(set(items)) != len(items):
        raise ValueError('inputs must be unique')

    # construct tree
    tree = pygtrie.CharTrie.fromkeys(items, value=0)

    # Hack into the internal structure and insert frequencies at each node
    def _iternodes(self):
        """
        Generates all nodes in the trie
        """
        stack = deque([[self._root]])
        while stack:
            for node in stack.pop():
                yield node
                stack.append(node.children.values())

    # Set the value (frequency) of all (except the root) nodes to zero.
    for node in _iternodes(tree):
        if node is not tree._root:
            node.value = 0

    # For each item trace its path and increment frequencies
    for item in items:
        final_node, trace = tree._get_node(item)
        for key, node in trace[1:]:
            node.value += 1

    # Query for the first prefix with frequency 1 for each item.
    # This is the shortest unique prefix over all items.
    unique = []
    for item in items:
        freq = None
        for prefix, freq in tree.prefixes(item):
            if freq == 1:
                break
        assert freq == 1, 'item={} has no unique prefix'.format(item)
        unique.append(prefix)
    return unique

Pygtrie fails to install in linux with latest pip

System

Python 3.7.5
pip 21.3.1
Ubuntu 18.04.3

To replicate

# no cache dir in case it finds the wheel in cache
# 2.4.2 version as otherwise it backtracks to another version
pip install --no-cache-dir pygtrie==2.4.2

This throws

Collecting pygtrie==2.4.2
  Downloading pygtrie-2.4.2.tar.gz (35 kB)
  Preparing metadata (setup.py) ... error
  ERROR: Command errored out with exit status 1:
   command: /data/code/test/travis_bug/venv/bin/python3 -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-0wq_8vbs/pygtrie_62d541023f2d4328bfb177$
3cd0adcda/setup.py'"'"'; __file__='"'"'/tmp/pip-install-0wq_8vbs/pygtrie_62d541023f2d4328bfb17793cd0adcda/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if $
s.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __fi$
e__, '"'"'exec'"'"'))' egg_info --egg-base /tmp/pip-pip-egg-info-_u9evd_6
       cwd: /tmp/pip-install-0wq_8vbs/pygtrie_62d541023f2d4328bfb17793cd0adcda/
  Complete output (33 lines):
  running egg_info
  creating /tmp/pip-pip-egg-info-_u9evd_6/pygtrie.egg-info
  writing /tmp/pip-pip-egg-info-_u9evd_6/pygtrie.egg-info/PKG-INFO
  writing dependency_links to /tmp/pip-pip-egg-info-_u9evd_6/pygtrie.egg-info/dependency_links.txt
  writing top-level names to /tmp/pip-pip-egg-info-_u9evd_6/pygtrie.egg-info/top_level.txt
  writing manifest file '/tmp/pip-pip-egg-info-_u9evd_6/pygtrie.egg-info/SOURCES.txt'
  Traceback (most recent call last):
    File "<string>", line 1, in <module>
    File "/tmp/pip-install-0wq_8vbs/pygtrie_62d541023f2d4328bfb17793cd0adcda/setup.py", line 179, in <module>
      distutils.core.setup(**kwargs)
    File "/usr/lib/python3.7/distutils/core.py", line 148, in setup
      dist.run_commands()
    File "/usr/lib/python3.7/distutils/dist.py", line 966, in run_commands
      self.run_command(cmd)
    File "/usr/lib/python3.7/distutils/dist.py", line 985, in run_command
      cmd_obj.run()
    File "/data/code/test/travis_bug/venv/lib/python3.7/site-packages/setuptools/command/egg_info.py", line 299, in run
      self.find_sources()
    File "/data/code/test/travis_bug/venv/lib/python3.7/site-packages/setuptools/command/egg_info.py", line 306, in find_sources
      mm.run()
    File "/data/code/test/travis_bug/venv/lib/python3.7/site-packages/setuptools/command/egg_info.py", line 541, in run
      self.add_defaults()
    File "/data/code/test/travis_bug/venv/lib/python3.7/site-packages/setuptools/command/egg_info.py", line 578, in add_defaults
      sdist.add_defaults(self)
    File "/usr/lib/python3.7/distutils/command/sdist.py", line 226, in add_defaults
      self._add_defaults_python()
    File "/data/code/test/travis_bug/venv/lib/python3.7/site-packages/setuptools/command/sdist.py", line 113, in _add_defaults_python
      self._add_data_files(self._safe_data_files(build_py))
    File "/data/code/test/travis_bug/venv/lib/python3.7/site-packages/setuptools/command/egg_info.py", line 621, in _safe_data_files
      return build_py.get_data_files_without_manifest()
    File "/usr/lib/python3.7/distutils/cmd.py", line 103, in __getattr__
      raise AttributeError(attr)
  AttributeError: get_data_files_without_manifest
  ----------------------------------------
WARNING: Discarding https://files.pythonhosted.org/packages/a5/8b/90d0f21a27a354e808a73eb0ffb94db990ab11ad1d8b3db3e5196c882cad/pygtrie-2.4.2.tar.gz#sha256=43205559d28863358dbbf25
045029f58e2ab357317a59b11f11ade278ac64692 (from https://pypi.org/simple/pygtrie/). Command errored out with exit status 1: python setup.py egg_info Check the logs for full comman
d output.
ERROR: Could not find a version that satisfies the requirement pygtrie==2.4.2 (from versions: 0.9.1, 0.9.2, 0.9.3, 1.0, 1.1, 1.2, 2.0, 2.1, 2.2, 2.3, 2.3.2, 2.3.3, 2.4.0, 2.4.1,
2.4.2)
ERROR: No matching distribution found for pygtrie==2.4.2

Recursion error with deep trie on copy()

This is unfortunately a well known issue for copy, pickle and json when dealing with nested/recursive data structures. With this:

>>> from pygtrie import Trie
>>> from array import array
>>> t=Trie()
>>> for x in range(100):
...  y = array('h', range(x, 1000)).tostring()
...  t.update([(y,x,)])
... 
>>> t2=t.copy()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
[...]
  File "/home/pombreda/w421/scancode-toolkit-ref/local/lib/python2.7/site-packages/pygtrie.py", line 81, in iterate
    for step, node in sorted(self.children.iteritems()):
RuntimeError: maximum recursion depth exceeded while calling a Python object

There are two ways out IMHO:

a custom de/serialization function that flattens the trie (eventually slow)
a different non-nested data structure for the Trie such as an array/list-based structure (e.g. double array Trie)

method to convert CharTrie into a compact trie for space-optimized representation (feature request)

char_trie['he'] = 3
char_trie['him'] = 4

---h

    |__e: 3

    |__i

        |__m: 4

can be compressed as,
---h

|__e: 3

|__i m:4

since removing each redundant node saves atleast 56 bytes, this can provide high memmory optimisation to a data structure that is used for memmory optimized storage.

Provide trie traversal functions (feature request)

It would be great to have some functions similar in logic to os.walk e.g. top down, breadth first and bottom up depth first "postorder" traversal of the trie.

Install fails because version.get_version fails

pip install from pypi fails

$ mktmpenv
Using base prefix '/usr/local/Cellar/python3/3.5.2_3/Frameworks/Python.framework/Versions/3.5'
New python executable in /Users/muyloco/Dev/Envs/tmp-5c77e50baa5495b6/bin/python3.5
Also creating executable in /Users/muyloco/Dev/Envs/tmp-5c77e50baa5495b6/bin/python
Installing setuptools, pip, wheel...done.
This is a temporary environment. It will be deleted when you run 'deactivate'.
(tmp-5c77e50baa5495b6) muyloco at cambria in ~/Dev/Envs/tmp-5c77e50baa5495b6
$ pip install pygtrie
Collecting pygtrie
  Using cached pygtrie-2.0.tar.gz
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-build-ap34m_ri/pygtrie/setup.py", line 6, in <module>
        import version  # pylint: disable=relative-import
      File "/private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-build-ap34m_ri/pygtrie/version.py", line 128
        print get_version()
                        ^
    SyntaxError: invalid syntax
    
    ----------------------------------------
Command "python setup.py egg_info" failed with error code 1 in /private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-build-ap34m_ri/pygtrie/
(tmp-5c77e50baa5495b6) muyloco at cambria in ~/Dev/Envs/tmp-5c77e50baa5495b6

pip install from master branch fails

$ pip install git+https://github.com/google/pygtrie.git@master
Collecting git+https://github.com/google/pygtrie.git@master
  Cloning https://github.com/google/pygtrie.git (to master) to /private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-d79a4kzy-build
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-d79a4kzy-build/setup.py", line 8, in <module>
        release = version.get_version()
      File "/private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-d79a4kzy-build/version.py", line 122, in get_version
        raise ValueError('Cannot find the version number')
    ValueError: Cannot find the version number
    
    ----------------------------------------
Command "python setup.py egg_info" failed with error code 1 in /private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-d79a4kzy-build/

pip install from local repo fails

$ git clone https://github.com/google/pygtrie.git
Cloning into 'pygtrie'...
remote: Counting objects: 247, done.
remote: Compressing objects: 100% (27/27), done.
remote: Total 247 (delta 11), reused 0 (delta 0), pack-reused 220
Receiving objects: 100% (247/247), 150.25 KiB | 0 bytes/s, done.
Resolving deltas: 100% (135/135), done.
(tmp-5c77e50baa5495b6) muyloco at cambria in ~/Dev/Envs/tmp-5c77e50baa5495b6
$ cd pygtrie
$ git describe
v2.0-14-g2785d76
(tmp-5c77e50baa5495b6) muyloco at cambria in ~/Dev/Envs/tmp-5c77e50baa5495b6/pygtrie on master*
$ git describe --long --match 'v[0-9]*.*'                                                                                                                                                                                                   
v2.0-14-g2785d76
(tmp-5c77e50baa5495b6) muyloco at cambria in ~/Dev/Envs/tmp-5c77e50baa5495b6/pygtrie on master*
$ pip install .
Processing /Users/muyloco/Dev/Envs/tmp-5c77e50baa5495b6/pygtrie
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-573kfusl-build/setup.py", line 8, in <module>
        release = version.get_version()
      File "/private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-573kfusl-build/version.py", line 122, in get_version
        raise ValueError('Cannot find the version number')
    ValueError: Cannot find the version number
    
    ----------------------------------------
Command "python setup.py egg_info" failed with error code 1 in /private/var/folders/dm/nyn5y95d4mqbwvcz1jsgpg8w0000gn/T/pip-573kfusl-build/

Recursion error with deep trie on pickle

This is a follow up on #8 (Thanks ++ for fixing this)!
With this:

>>> from pygtrie import Trie
>>> from array import array
>>> t=Trie()
>>> for x in range(100):
...  y = array('h', range(x, 1000)).tostring()
...  t.update([(y,x,)])
... 
>>> import pickle
>>> x=pickle.dumps(t)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.7/pickle.py", line 1374, in dumps
    Pickler(file, protocol).dump(obj)
[...]
  File "/usr/lib/python2.7/pickle.py", line 286, in save
    f(self, obj) # Call unbound method with explicit self
  File "/usr/lib/python2.7/pickle.py", line 649, in save_dict
    self._batch_setitems(obj.iteritems())
  File "/usr/lib/python2.7/pickle.py", line 662, in _batch_setitems
    save(k)
  File "/usr/lib/python2.7/pickle.py", line 271, in save
    pid = self.persistent_id(obj)
RuntimeError: maximum recursion depth exceeded

This is also something where I cannot reasonably increase the recursion limit.

Can I merge two trie with pygtrie?

It seems update is just overwrite, same as dict.update

Install fail in windows

I using "pip install pygtrie" but it's fail in windows 10. python 3.6 64 bit

Collecting pygtrie
  Using cached pygtrie-2.1.tar.gz
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "C:\Users\WANNAP~1\AppData\Local\Temp\pip-build-553d519x\pygtrie\setup.py", line 17, in <module>
        readme = f.read()
      File "C:\Users\wannaphong\Anaconda3\lib\encodings\cp874.py", line 23, in decode
        return codecs.charmap_decode(input,self.errors,decoding_table)[0]
    UnicodeDecodeError: 'charmap' codec can't decode byte 0x99 in position 933: character maps to <undefined>

    ----------------------------------------
Command "python setup.py egg_info" failed with error code 1 in C:\Users\WANNAP~1\AppData\Local\Temp\pip-build-553d519x\pygtrie\