Skip to content

Commit 40c7325

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 319d251 commit 40c7325

1 file changed

Lines changed: 51 additions & 27 deletions

File tree

‎entropy/entropy.py‎

Lines changed: 51 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -659,36 +659,57 @@ 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.
665665
666666
https://github.com/Naereen/Lempel-Ziv_Complexity/blob/master/src/lziv_complexity.py
667+
668+
- Updated with strict integer typing instead of strings
669+
- Slight restructuring based on Yacine Mahdid's notebook:
670+
https://github.com/BIAPT/Notebooks/blob/master/features/Lempel-Ziv%20Complexity.ipynb
667671
"""
668-
u, v, w = 0, 1, 1
669-
v_max = 1
670-
length = len(binary_string)
672+
# Initialize variables
671673
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
674+
prefix_len = 1
675+
len_substring = 1
676+
max_len_substring = 1
677+
pointer = 0
678+
679+
# Iterate until the entire string has not been parsed
680+
while prefix_len + len_substring <= len(binary_string):
681+
682+
# Given a prefix length, find the largest substring
683+
if (
684+
binary_string[pointer + len_substring - 1]
685+
== binary_string[prefix_len + len_substring - 1]
686+
):
687+
len_substring += 1 # increase the length of the substring
678688
else:
679-
v_max = max(v, v_max)
680-
u += 1
681-
if u == w:
689+
690+
max_len_substring = max(len_substring, max_len_substring)
691+
pointer += 1
692+
693+
# Since all pointers have been scanned, pick largest as the jump size
694+
if pointer == prefix_len:
695+
696+
# Increment complexity
682697
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
698+
699+
# Set prefix length to the max substring size found so far (jump size)
700+
prefix_len += max_len_substring
701+
702+
# Reset pointer and max substring size
703+
pointer = 0
704+
max_len_substring = 1
705+
706+
# Reset length of current substring
707+
len_substring = 1
708+
709+
# Check if final iteration occurred in the middle of a substring
710+
if len_substring != 1:
711+
complexity += 1
712+
692713
return complexity
693714

694715

@@ -780,11 +801,14 @@ def lziv_complexity(sequence, normalize=False):
780801
sequence = np.asarray(sequence)
781802
if sequence.dtype.kind in 'bfi':
782803
# 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))
804+
s = sequence.astype("uint32")
805+
else:
806+
# Treat as numpy array of strings
807+
# Map string characters to utf-8 integer representation
808+
s = np.fromiter(map(ord, "".join(sequence.astype(str))), dtype="uint32")
809+
# Can't preallocate length (by specifying count) due to string concatenation
786810
else:
787-
s = sequence
811+
s = np.fromiter(map(ord, sequence), dtype="uint32")
788812

789813
if normalize:
790814
# 1) Timmermann et al. 2019
@@ -799,7 +823,7 @@ def lziv_complexity(sequence, normalize=False):
799823
# return _lz_complexity(s) / _lz_complexity(s_shuffled)
800824
# 2) Zhang et al. 2009
801825
n = len(s)
802-
base = len(''.join(set(s))) # Number of unique characters
826+
base = sum(np.bincount(s) > 0) # Number of unique characters
803827
base = 2 if base < 2 else base
804828
return _lz_complexity(s) / (n / log(n, base))
805829
else:

0 commit comments

Comments
 (0)