📦 Lempel-Ziv Complexity, fast implementations with 🐍 Python (naive, Numba or Cython for speedup), Open-Source (MIT) 👍
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
doc
src
.gitignore
LICENSE
Makefile
README.md
README.rst
Short_study_of_the_Lempel-Ziv_complexity.ipynb
_config.yml

README.md

Python implementation of Lempel-Ziv Complexity

This repository contains a small, simple and efficient implementation of the Lempel-Ziv complexity algorithm.

Examples

Simple usage

If the lempel_ziv_complexity.py file is accessible in your PATH or in Python's path:

>>> from lempel_ziv_complexity import lempel_ziv_complexity
>>> s = '1001111011000010'
>>> lempel_ziv_complexity(s)  # 1 / 0 / 01 / 1110 / 1100 / 0010
6

Documentation

See this file.

If you are really interested about the details of how the algorithm works, please see this GIF screencast from PythonTutor.com.

With the C extension

If the lempel_ziv_complexity.so file is accessible in your PATH or in Python's path:

Small benchmark

There is also a Cython version, to have a faster implementation:

$ ipython
...
>>> s = '1001111011000010'
>>> %timeit lempel_ziv_complexity(s)
6.1 µs ± 33.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit lempel_ziv_complexity_cython(s)
132 ns ± 2.55 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

The speedup is typically between ×50 and ×100.

Demo on a Jupyter notebook

See this notebook: on nbviewever, which also compares with the Julia version.


Install and build

Manually ?

Easy!

Clone this repository, go in the folder, compile, test, and if it works, install it.

cd /tmp/
git clone https://GitHub.com/Naereen/Lempel-Ziv_Complexity
cd Lempel-Ziv_Complexity/src/
make build
make test     # should pass
make install  # mv the build/lib*/*.so files where you need them

Be sure to include the dynamic library when you need it, or in a folder accessible by your Python interpreter (somewhere in sys.path). The file is lempel_ziv_complexity_cython.so (for Python 2) or the lempel_ziv_complexity_cython.cpython-35m-x86_64-linux-gnu.so (for Python 3.5, or higher, adapt the name).

With pip ?

This project is hosted on the Pypi package repository.

sudo pip install lempel_ziv_complexity
# test it
python -c "from lempel_ziv_complexity import lempel_ziv_complexity; print(lempel_ziv_complexity('1001111011000010') == 6)"  # test

lempel_ziv_complexity in pypi PyPI implementation PyPI pyversions


Julia implementation ?

I was curious and wanted to write the same algorithm in Julia. Here it is: lempel_ziv_complexity.jl. See this part of the notebook for a benchmark between Julia and Python.

The Julia package is published here: Naereen/LempelZiv.jl, and see here for its documentation.


About

Language?

Python v2.7+ or Python v3.1+.

  • Numba can be used to speed up the pure Python version.
  • Cython is needed to build the C extension (faster).

📜 License ? GitHub license

MIT Licensed (file LICENSE). © Lilian Besson, 2017.

Maintenance Ask Me Anything ! Analytics

ForTheBadge uses-badges ForTheBadge uses-git

forthebadge made-with-python ForTheBadge built-with-science