Skip to main content

DAWG2-Python

Python tests Coverage Status

This pure-python package provides read-only access for files created by dawgdic C++ library and DAWG python package.

This package is not capable of creating DAWGs. It works with DAWGs built by dawgdic C++ library or DAWG Python extension module. The main purpose of DAWG-Python is to provide access to DAWGs without requiring compiled extensions. It is also quite fast under PyPy (see benchmarks).

Installation

pip install DAWG2-Python

Usage

The aim of DAWG2-Python is to be API- and binary-compatible with DAWG when it is possible.

First, you have to create a dawg using DAWG module:

import dawg

d = dawg.DAWG(data)
d.save('words.dawg')

And then this dawg can be loaded without requiring C extensions:

import dawg_python

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

Please consult DAWG docs for detailed usage. Some features (like constructor parameters or save method) are intentionally unsupported.

Benchmarks

Benchmark results (100k unicode words, integer values (lengths of the words), PyPy 1.9, macbook air i5 1.8 Ghz):

dict __getitem__ (hits):        11.090M ops/sec
DAWG __getitem__ (hits):        not supported
BytesDAWG __getitem__ (hits):   0.493M ops/sec
RecordDAWG __getitem__ (hits):  0.376M ops/sec

dict get() (hits):              10.127M ops/sec
DAWG get() (hits):              not supported
BytesDAWG get() (hits):         0.481M ops/sec
RecordDAWG get() (hits):        0.402M ops/sec
dict get() (misses):            14.885M ops/sec
DAWG get() (misses):            not supported
BytesDAWG get() (misses):       1.259M ops/sec
RecordDAWG get() (misses):      1.337M ops/sec

dict __contains__ (hits):           11.100M ops/sec
DAWG __contains__ (hits):           1.317M ops/sec
BytesDAWG __contains__ (hits):      1.107M ops/sec
RecordDAWG __contains__ (hits):     1.095M ops/sec

dict __contains__ (misses):         10.567M ops/sec
DAWG __contains__ (misses):         1.902M ops/sec
BytesDAWG __contains__ (misses):    1.873M ops/sec
RecordDAWG __contains__ (misses):   1.862M ops/sec

dict items():           44.401 ops/sec
DAWG items():           not supported
BytesDAWG items():      3.226 ops/sec
RecordDAWG items():     2.987 ops/sec
dict keys():            426.250 ops/sec
DAWG keys():            not supported
BytesDAWG keys():       6.050 ops/sec
RecordDAWG keys():      6.363 ops/sec

DAWG.prefixes (hits):    0.756M ops/sec
DAWG.prefixes (mixed):   1.965M ops/sec
DAWG.prefixes (misses):  1.773M ops/sec

RecordDAWG.keys(prefix="xxx"), avg_len(res)==415:       1.429K ops/sec
RecordDAWG.keys(prefix="xxxxx"), avg_len(res)==17:      36.994K ops/sec
RecordDAWG.keys(prefix="xxxxxxxx"), avg_len(res)==3:    121.897K ops/sec
RecordDAWG.keys(prefix="xxxxx..xx"), avg_len(res)==1.4: 265.015K ops/sec
RecordDAWG.keys(prefix="xxx"), NON_EXISTING:            2450.898K ops/sec

Under CPython expect it to be about 50x slower. Memory consumption of DAWG-Python should be the same as of DAWG.

Current limitations

  • This package is not capable of creating DAWGs;
  • all the limitations of DAWG apply.

Contributions are welcome!

Contributing

Feel free to submit ideas, bugs or pull requests.

Running tests and benchmarks

Make sure pytest is installed and run

$ pytest .

from the source checkout. Tests should pass under python 3.8, 3.9, 3.10, 3.11 and PyPy3 >= 7.3.

In order to run benchmarks, type

$ pypy3 -m bench.speed

This runs benchmarks under PyPy (they are about 50x slower under CPython).

Authors & Contributors

The algorithms are from dawgdic C++ library by Susumu Yata & contributors.

License

This package is licensed under MIT License.

Changes

0.8.0 (2023-09-27)

  • Allow more flexible char substitutes by @bt2901
  • minimal Python version changed to 3.8 by @insolor
  • setup.py building changed to poetry by @insolor

0.7.2 (2015-04-18)

  • minor speedup;
  • bitbucket mirror is no longer maintained.

0.7.1 (2014-06-05)

  • Switch to setuptools;
  • upload wheel to pypi;
  • check Python 3.4 compatibility.

0.7 (2013-10-13)

IntDAWG and IntCompletionDAWG are implemented.

0.6 (2013-03-23)

Use less shared state internally. This should fix thread-safety bugs and make iterkeys/iteritems reentrant.

0.5.1 (2013-03-01)

Internal tweaks: memory usage is reduced; something is a bit faster, something is a bit slower.

0.5 (2012-10-08)

Storage scheme is updated to match DAWG==0.5. This enables the alphabetical ordering of BytesDAWG and RecordDAWG items.

In order to read BytesDAWG or RecordDAWG created with versions of DAWG < 0.5 use payload_separator constructor argument:

>>> BytesDAWG(payload_separator=b'\xff').load('old.dawg')

0.3.1 (2012-10-01)

Bug with empty DAWGs is fixed.

0.3 (2012-09-26)

  • iterkeys and iteritems methods.

0.2 (2012-09-24)

prefixes support.

0.1 (2012-09-20)

Initial release.

Metadata

Release files for DAWG2-Python 0.8.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for DAWG2-Python 0.8.0
File Size Uploaded Provenance Actions
dawg2_python-0.8.0.tar.gz 10.0 kB Without provenance Details for dawg2_python-0.8.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for DAWG2-Python 0.8.0
File Interpreter ABI Platform Actions
dawg2_python-0.8.0-py3-none-any.whl Python 3 none any Details for dawg2_python-0.8.0-py3-none-any.whl

Total release size: 18.9 kB

Release files / dawg2_python-0.8.0.tar.gz

Download URL dawg2_python-0.8.0.tar.gz
Size 10.0 kB
Tags Source
SHA-256 checksum
How to use checksums
fe766ba9d63fa42a99bcb45b9c15694fb32fc92528f66c68b9acffaaa068ceee
BLAKE2b-256 checksum
How to use checksums
a116dc4360640ac9846f89fe0517b3816271d6a8c13e6fedb863f81dd6991ede
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via poetry/1.6.1 CPython/3.10.12 Linux/6.2.0-1011-azure

Release files / dawg2_python-0.8.0-py3-none-any.whl

Download URL dawg2_python-0.8.0-py3-none-any.whl
Size 8.8 kB
Tags Python 3
SHA-256 checksum
How to use checksums
aea16490e51320c44a4632a8b7848950a9dc8a293b8f52a49ac013227869c060
BLAKE2b-256 checksum
How to use checksums
3a08b12f423b5914220aac343357714d72777cfb7e0d4da65cdc3bb247688cf1
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via poetry/1.6.1 CPython/3.10.12 Linux/6.2.0-1011-azure

Security for DAWG2-Python 0.8.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page