Skip to content

Commit 6713404

Browse files
committed
Updated LZ complexity estimation with speed bump and integer typing
- The function entropy.lziv_complexity now converts all valid input types to arrays of type np.uint32 for fast computation with Numba. - For strings and list of strings, utf-8 numeric representations are used for integer arrays using built-in ord - Normalization uses np.bincount instead of set on numpy arrays, significant speedup on large arrays. A major reason for using 32-bit and not 64-bint uints as np.bincount can't work with uint64 safely. Several open issues about this: numpy/numpy#17760 numpy/numpy#823 numpy/numpy#4384
1 parent d8d3575 commit 6713404

1 file changed

Lines changed: 51 additions & 48 deletions

File tree

‎antropy/entropy.py‎

Lines changed: 51 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -659,117 +659,117 @@ def sample_entropy(x, order=2, metric='chebyshev'):
659659
return -np.log(np.divide(phi[1], phi[0]))
660660

661661

662-
@jit('u8(unicode_type)', nopython=True)
662+
@jit("uint32(uint32[:])", nopython=True)
663663
def _lz_complexity(binary_string):
664664
"""Internal Numba implementation of the Lempel-Ziv (LZ) complexity.
665-
666665
https://github.com/Naereen/Lempel-Ziv_Complexity/blob/master/src/lziv_complexity.py
666+
- Updated with strict integer typing instead of strings
667+
- Slight restructuring based on Yacine Mahdid's notebook:
668+
https://github.com/BIAPT/Notebooks/blob/master/features/Lempel-Ziv%20Complexity.ipynb
667669
"""
668-
u, v, w = 0, 1, 1
669-
v_max = 1
670-
length = len(binary_string)
670+
# Initialize variables
671671
complexity = 1
672-
while True:
673-
if binary_string[u + v - 1] == binary_string[w + v - 1]:
674-
v += 1
675-
if w + v >= length:
676-
complexity += 1
677-
break
672+
prefix_len = 1
673+
len_substring = 1
674+
max_len_substring = 1
675+
pointer = 0
676+
677+
# Iterate until the entire string has not been parsed
678+
while prefix_len + len_substring <= len(binary_string):
679+
680+
# Given a prefix length, find the largest substring
681+
if (
682+
binary_string[pointer + len_substring - 1]
683+
== binary_string[prefix_len + len_substring - 1]
684+
):
685+
len_substring += 1 # increase the length of the substring
678686
else:
679-
v_max = max(v, v_max)
680-
u += 1
681-
if u == w:
687+
688+
max_len_substring = max(len_substring, max_len_substring)
689+
pointer += 1
690+
691+
# Since all pointers have been scanned, pick largest as the jump size
692+
if pointer == prefix_len:
693+
694+
# Increment complexity
682695
complexity += 1
683-
w += v_max
684-
if w >= length:
685-
break
686-
else:
687-
u = 0
688-
v = 1
689-
v_max = 1
690-
else:
691-
v = 1
696+
697+
# Set prefix length to the max substring size found so far (jump size)
698+
prefix_len += max_len_substring
699+
700+
# Reset pointer and max substring size
701+
pointer = 0
702+
max_len_substring = 1
703+
704+
# Reset length of current substring
705+
len_substring = 1
706+
707+
# Check if final iteration occurred in the middle of a substring
708+
if len_substring != 1:
709+
complexity += 1
710+
692711
return complexity
693712

694713

695714
def lziv_complexity(sequence, normalize=False):
696715
"""
697716
Lempel-Ziv (LZ) complexity of (binary) sequence.
698-
699717
.. versionadded:: 0.1.1
700-
701718
Parameters
702719
----------
703720
sequence : str or array
704721
A sequence of character, e.g. ``'1001111011000010'``,
705722
``[0, 1, 0, 1, 1]``, or ``'Hello World!'``.
706723
normalize : bool
707724
If ``True``, returns the normalized LZ (see Notes).
708-
709725
Returns
710726
-------
711727
lz : int or float
712728
LZ complexity, which corresponds to the number of different
713729
substrings encountered as the stream is viewed from the
714730
beginning to the end. If ``normalize=False``, the output is an
715731
integer (counts), otherwise the output is a float.
716-
717732
Notes
718733
-----
719734
LZ complexity is defined as the number of different substrings encountered
720735
as the sequence is viewed from begining to the end.
721-
722736
Although the raw LZ is an important complexity indicator, it is heavily
723737
influenced by sequence length (longer sequence will result in higher LZ).
724738
Zhang and colleagues (2009) have therefore proposed the normalized LZ,
725739
which is defined by
726-
727740
.. math:: \\text{LZn} = \\frac{\\text{LZ}}{(n / \\log_b{n})}
728-
729741
where :math:`n` is the length of the sequence and :math:`b` the number of
730742
unique characters in the sequence.
731-
732743
References
733744
----------
734745
* Lempel, A., & Ziv, J. (1976). On the Complexity of Finite Sequences.
735746
IEEE Transactions on Information Theory / Professional Technical
736747
Group on Information Theory, 22(1), 75–81.
737748
https://doi.org/10.1109/TIT.1976.1055501
738-
739749
* Zhang, Y., Hao, J., Zhou, C., & Chang, K. (2009). Normalized
740750
Lempel-Ziv complexity and its application in bio-sequence analysis.
741751
Journal of Mathematical Chemistry, 46(4), 1203–1212.
742752
https://doi.org/10.1007/s10910-008-9512-2
743-
744753
* https://en.wikipedia.org/wiki/Lempel-Ziv_complexity
745-
746754
* https://github.com/Naereen/Lempel-Ziv_Complexity
747-
748755
Examples
749756
--------
750-
>>> from antropy import lziv_complexity
757+
>>> from entropy import lziv_complexity
751758
>>> # Substrings = 1 / 0 / 01 / 1110 / 1100 / 0010
752759
>>> s = '1001111011000010'
753760
>>> lziv_complexity(s)
754761
6
755-
756762
Using a list of integer / boolean instead of a string:
757-
758763
>>> # 1 / 0 / 10
759764
>>> lziv_complexity([1, 0, 1, 0, 1, 0, 1, 0, 1, 0])
760765
3
761-
762766
With normalization:
763-
764767
>>> lziv_complexity(s, normalize=True)
765768
1.5
766-
767769
This function also works with characters and words:
768-
769770
>>> s = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
770771
>>> lziv_complexity(s), lziv_complexity(s, normalize=True)
771772
(26, 1.0)
772-
773773
>>> s = 'HELLO WORLD! HELLO WORLD! HELLO WORLD! HELLO WORLD!'
774774
>>> lziv_complexity(s), lziv_complexity(s, normalize=True)
775775
(11, 0.38596001132145313)
@@ -780,11 +780,14 @@ def lziv_complexity(sequence, normalize=False):
780780
sequence = np.asarray(sequence)
781781
if sequence.dtype.kind in 'bfi':
782782
# Convert [True, False] or [1., 0.] to [1, 0]
783-
sequence = sequence.astype(int)
784-
# Convert to a string, e.g. "10001100"
785-
s = ''.join(sequence.astype(str))
783+
s = sequence.astype("uint32")
784+
else:
785+
# Treat as numpy array of strings
786+
# Map string characters to utf-8 integer representation
787+
s = np.fromiter(map(ord, "".join(sequence.astype(str))), dtype="uint32")
788+
# Can't preallocate length (by specifying count) due to string concatenation
786789
else:
787-
s = sequence
790+
s = np.fromiter(map(ord, sequence), dtype="uint32")
788791

789792
if normalize:
790793
# 1) Timmermann et al. 2019
@@ -799,7 +802,7 @@ def lziv_complexity(sequence, normalize=False):
799802
# return _lz_complexity(s) / _lz_complexity(s_shuffled)
800803
# 2) Zhang et al. 2009
801804
n = len(s)
802-
base = len(''.join(set(s))) # Number of unique characters
805+
base = sum(np.bincount(s) > 0) # Number of unique characters
803806
base = 2 if base < 2 else base
804807
return _lz_complexity(s) / (n / log(n, base))
805808
else:

0 commit comments

Comments
 (0)