Repository: JuliaDynamics/ComplexityMeasures.jl (julia)

Issue:
Lempel–Ziv complexity measure
New complexity measure:

https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv_complexity

The wiki website also has an implementation. This is really easy to implement as far as I can tell from the algorithm section at the end.

Pull request description:
Fixes #258.

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 62ff5a9c6..b80d2a38a 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,7 @@ Changelog is kept with respect to version 0.11 of Entropies.jl. From version v2.
 
 - New function `allprobabilities` that is like `probabilities` but also includes 0 entries for possible outcomes that were not present in the data.
 - `StatisticalComplexity` is now compatible with any normalizable `EntropyDefinition`.
+- Add the 1976 Lempel-Ziv complexity measure (`LempelZiv76`).
 - New entropy definition: identification entropy (`Identification`).
 - Minor documentation fixes.
 
diff --git a/docs/src/complexity.md b/docs/src/complexity.md
index 122e58c96..250c26088 100644
--- a/docs/src/complexity.md
+++ b/docs/src/complexity.md
@@ -39,8 +39,15 @@ ReverseDispersion
 ```
 
 ## Statistical complexity
+
 ```@docs
 StatisticalComplexity
 entropy_complexity
 entropy_complexity_curves
-```
\ No newline at end of file
+```
+
+## Lempel-Ziv complexity
+
+```@docs
+LempelZiv76
+```
diff --git a/src/complexity_measures/complexity_measures.jl b/src/complexity_measures/complexity_measures.jl
index 4aed83d27..5cef3ee36 100644
--- a/src/complexity_measures/complexity_measures.jl
+++ b/src/complexity_measures/complexity_measures.jl
@@ -2,4 +2,5 @@ include("sample_entropy.jl")
 include("approximate_entropy.jl")
 include("reverse_dispersion_entropy.jl")
 include("missing_dispersion.jl")
-include("statistical_complexity.jl")
\ No newline at end of file
+include("statistical_complexity.jl")
+include("lempel_ziv.jl")
diff --git a/src/complexity_measures/lempel_ziv.jl b/src/complexity_measures/lempel_ziv.jl
new file mode 100644
index 000000000..7fb627b3e
--- /dev/null
+++ b/src/complexity_measures/lempel_ziv.jl
@@ -0,0 +1,69 @@
+export LempelZiv76
+
+"""
+    LempelZiv76 <: ComplexityEstimator
+    LempelZiv76()
+
+The Lempel-Ziv, or `LempelZiv76`, complexity measure (Lempel & Ziv, 1976) [^LempelZiv1976],
+which is used with [`complexity`](@ref) and [`complexity_normalized`](@ref).
+
+For results to be comparable across sequences with different length, use the normalized
+version. Normalized LempelZiv76-complexity is implemented as given in Amigó et al.
+(2004)[^Amigó2004]. The normalized measure is close to zero for very regular signals, while
+for random sequences, it is close to 1 with high probability[^Amigó2004]. Note: the
+normalized LempelZiv76 complexity can be higher than 1[^Amigó2004].
+
+The `LempelZiv76` measure applies only to binary sequences, i.e. sequences with a
+two-element alphabet (precisely two distinct outcomes). For performance optimization,
+we do not check the number of unique elements in the input. If your input sequence is not
+binary, you must [`encode`](@ref) it first using one of the implemented [`Encoding`](@ref)
+schemes (or encode your data manually).
+
+[^LempelZiv1976]:
+    Lempel, A., & Ziv, J. (1976). On the complexity of finite sequences. IEEE Transactions
+    on information theory, 22(1), 75-81.
+[^Amigó2004]:
+    Amigó, J. M., Szczepański, J., Wajnryb, E., & Sanchez-Vives, M. V. (2004). Estimating
+    the entropy rate of spike trains via Lempel-Ziv complexity. Neural Computation, 16(4),
+    717-736.
+"""
+struct LempelZiv76 <: ComplexityEstimator end
+
+function complexity(est::LempelZiv76, x::AbstractArray{T, N}) where {T, N}
+    # The implementation here is taken directly from
+    # https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv_complexity
+    i = 0 # `i = p − 1`, `p is the pointer
+    c = 1 # The complexity counter
+    u = 1 # Length of the current prefix
+    v = 1 # Length of the current component for the current pointer `p``
+    vmax = v
+    n = length(x)
+    @inbounds while u + v <= n
+        if x[i + v] == x[u + v]
+            v += 1
+        else
+            vmax = max(v, vmax)
+            i += 1
+            if i == u  # all pointers have been treated
+                c += 1
+                u += vmax
+                v = 1
+                i = 0
+                vmax = v
+            else
+                v = 1
+            end
+        end
+    end
+    if v != 1
+        c += 1
+    end
+    return c
+end
+
+# Formula from Amigó et al. (2004)
+function complexity_normalized(est::LempelZiv76, x)
+    n = length(x)
+    c = complexity(est, x)
+    return c / (n / log2(n))
+end


Test patch:
diff --git a/test/complexity/complexity.jl b/test/complexity/complexity.jl
index 1fbf84198..9b108472b 100644
--- a/test/complexity/complexity.jl
+++ b/test/complexity/complexity.jl
@@ -4,4 +4,5 @@
     testfile("measures/entropy_approx.jl")
     testfile("measures/entropy_sample.jl")
     testfile("measures/statistical_complexity.jl")
+    testfile("measures/lempel_ziv.jl")
 end
diff --git a/test/complexity/measures/lempel_ziv.jl b/test/complexity/measures/lempel_ziv.jl
new file mode 100644
index 000000000..aa6c3c42e
--- /dev/null
+++ b/test/complexity/measures/lempel_ziv.jl
@@ -0,0 +1,24 @@
+using Random
+# Example from
+# Amigó, J. M., Szczepański, J., Wajnryb, E., & Sanchez-Vives, M. V. (2004). Estimating
+# the entropy rate of spike trains via Lempel-Ziv complexity. Neural Computation, 16(4),
+# 717-736.
+# This should give the subsequences: 0, 1, 011, 0100, 011011, 1001, 0, or 7 elements
+x = [0,1,0,1,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0]
+
+@test complexity(LempelZiv76(), x) == 7
+
+# A very regular signal should have normalized LempelZiv76-complexity close to zero.
+ts = sin.(0:0.5:100000)
+μ = mean(ts)
+x = [x <= μ ? 0 : 1 for x in ts]
+c = complexity_normalized(LempelZiv76(), x)
+@test 0 ≤ c ≤ 0.05
+
+# A random sequence should have normalized LempelZiv76-complexity close to 1
+rng = MersenneTwister(1234)
+ts = rand(10000)
+μ = mean(ts)
+x = [x <= μ ? 0 : 1 for x in ts]
+c = complexity_normalized(LempelZiv76(), x)
+@test 0.95 ≤ c ≤ 1.05