DAWG 0.1

DAWG

This package provides DAWG-based dictionary-like read-only objects for Python (2.x and 3.x).

String data in a DAWG may take up to 50x less memory than in a standard Python dict; the raw lookup speed is comparable; DAWG also provides fast advanced methods like prefix search.

Based on dawgdic C++ library.

Installation

pip install DAWG

Usage

There are several DAWG classes in this package:

• dawg.DAWG - basic DAWG wrapper; it can store unicode keys and do exact lookups;

• dawg.CompletionDAWG - dawg.DAWG subclass that supports key completion and prefix lookups (but requires more memory);

• dawg.BytesDAWG - dawg.CompletionDAWG subclass that maps unicode keys to lists of bytes objects.

• dawg.RecordDAWG - dawg.BytesDAWG subclass that maps unicode keys to lists of data tuples. All tuples must be of the same format (the data is packed using python struct module).

• dawg.IntDAWG - dawg.DAWG subclass that maps unicode keys to integer values.

>>> import dawg
>>> words = [u'foo', u'bar', u'foobar']
>>> base_dawg = dawg.DAWG(words)
>>> completion_dawg = dawg.CompletionDAWG(words)

>>> u'foo' in base_dawg
True
>>> u'baz' in completion_dawg
False

>>> completion_dawg.keys(u'foo')
>>> [u'foo', u'foobar']

>>> data = [(u'key1', b'value1'), (u'key2', b'value2'), (u'key1', b'value3')]
>>> bytes_dawg = dawg.BytesDAWG(data)

>>> bytes_dawg[u'key1']
[b'value1, b'value3']

>>> bytes_dawg[u'key2']
[b'value2']

>>> bytes_dawg.get(u'foo', None)
None

>>> format = ">HHH"

>>> keys = [u'foo', u'bar', u'foobar', u'foo']
>>> values = [(1, 2, 3), (2, 1, 0), (3, 3, 3), (2, 1, 5)]
>>> data = zip(keys, values)
>>> record_dawg = RecordDAWG(format, data)

>>> record_dawg['foo']
[(1, 2, 3), (2, 1, 5)]
>>> record_dawg['foobar']
[(3, 3, 3)]

>>> data = [ (u'foo', 1), (u'bar', 2) ]
>>> int_dawg = dawg.IntDAWG(data)

>>> int_dawg[u'foo']
1

>>> with open('words.dawg', 'wb') as f:
...     d.write(f)

>>> d.save('words.dawg')

>>> d = dawg.RecordDAWG(format_string)
>>> with open('words.record-dawg', 'rb') as f:
...     d.read(f)

>>> d = dawg.DAWG()
>>> d.load('words.dawg')

>>> import pickle
>>> data = pickle.dumps(d)
>>> d2 = pickle.loads(data)

Benchmarks

For a list of 3000000 (3 million) Russian words memory consumption with different data structures (under Python 2.7):

• dict(unicode words -> word lenghts): about 600M

• list(unicode words) : about 300M

• marisa_trie.RecordTrie : 11M

• marisa_trie.Trie: 7M

• dawg.DAWG: 8M

• dawg.CompletionDAWG: 10M

• dawg.IntDAWG: 11M

• dawg.RecordDAWG: 16M

Benchmark results (100k unicode words, integer values (lenghts of the words), Python 3.2, macbook air i5 1.8 Ghz):

dict __getitem__ (hits):        4.102M ops/sec
DAWG __getitem__ (hits):        not supported
BytesDAWG __getitem__ (hits):   1.558M ops/sec
RecordDAWG __getitem__ (hits):  0.950M ops/sec
IntDAWG __getitem__ (hits):     2.835M ops/sec
dict get() (hits):              3.053M ops/sec
DAWG get() (hits):              not supported
BytesDAWG get() (hits):         1.340M ops/sec
RecordDAWG get() (hits):        0.882M ops/sec
IntDAWG get() (hits):           2.370M ops/sec
dict get() (misses):            3.250M ops/sec
DAWG get() (misses):            not supported
BytesDAWG get() (misses):       2.483M ops/sec
RecordDAWG get() (misses):      2.249M ops/sec
IntDAWG get() (misses):         2.806M ops/sec

dict __contains__ (hits):           4.068M ops/sec
DAWG __contains__ (hits):           3.065M ops/sec
BytesDAWG __contains__ (hits):      2.627M ops/sec
RecordDAWG __contains__ (hits):     2.613M ops/sec
IntDAWG __contains__ (hits):        3.021M ops/sec
dict __contains__ (misses):         3.471M ops/sec
DAWG __contains__ (misses):         3.537M ops/sec
BytesDAWG __contains__ (misses):    3.381M ops/sec
RecordDAWG __contains__ (misses):   3.361M ops/sec
IntDAWG __contains__ (misses):      3.540M ops/sec

dict items():       58.754 ops/sec
DAWG items():       not supported
BytesDAWG items():  15.914 ops/sec
RecordDAWG items(): 10.699 ops/sec
IntDAWG items():    not supported

dict keys():        214.499 ops/sec
DAWG keys():        not supported
BytesDAWG keys():   23.929 ops/sec
RecordDAWG keys():  23.726 ops/sec
IntDAWG keys():     not supported

RecordDAWG.keys(prefix="xxx"), avg_len(res)==415:       6.057K ops/sec
RecordDAWG.keys(prefix="xxxxx"), avg_len(res)==17:      130.680K ops/sec
RecordDAWG.keys(prefix="xxxxxxxx"), avg_len(res)==3:    507.355K ops/sec
RecordDAWG.keys(prefix="xxxxx..xx"), avg_len(res)==1.4: 745.566K ops/sec
RecordDAWG.keys(prefix="xxx"), NON_EXISTING:            3032.758K ops/sec

Please take this benchmark results with a grain of salt; this is a very simple benchmark on a single data set.

Current limitations

• The library is not tested under Windows;

• IntDAWG is currently a subclass of DAWG and so it doesn’t support keys() and items() methods;

• read() method reads the whole stream (DAWG must be the last or the only item in a stream if it is read with read() method) - pickling doesn’t have this limitation;

• iterator versions of methods are not always implemented;

• there are keys() and items() methods but no values() method.

• prefixes() method for getting all prefixes of a given work is not implemented yet;

Contributions are welcome!

Contributing

Development happens at github and bitbucket:

• https://github.com/kmike/DAWG

• https://bitbucket.org/kmike/DAWG

The main issue tracker is at github: https://github.com/kmike/DAWG/issues

Feel free to submit ideas, bugs, pull requests (git or hg) or regular patches.

If you found a bug in a C++ part please report it to the original bug tracker.

$ tox

$ tox -c bench.ini

License

Wrapper code is licensed under MIT License. Bundled dawgdic C++ library is licensed under BSD license. libb64 is Public Domain.