@@ -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 )
663663def _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
695714def 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