вычисление сложности Лемпеля-Зива (LZ) (также известной как сложность последовательности) двоичной строки

Ниже приведен краткий пример того, как вычислить LZ-сложность с помощью дерева. Для удобства - мой; не ваш - этот код реализует предварительно выделенное дерево фиксированного размера и является ярким примером того, почему указатели void* уродливы в использовании и сложны в обслуживании. Дайте этот код как есть, и ваш лектор, скорее всего, выстрелит вам в лицо :)

#include <stdlib.h>
#include <stdio.h>

int LZComplexity(char *p_binarySequence, int p_maxTreeNodes)
{
 void **patternTree;
 void **currentNode;
 void **nextFreeNode;
 int nodeCount;
 int sequenceIndex;
 int currentDigit;

 nodeCount = 0;
 patternTree = malloc(sizeof(void*) * (p_maxTreeNodes << 1));
 currentNode = patternTree;
 nextFreeNode = patternTree + (sizeof(void*) << 1);
 currentNode[0] = NULL;
 currentNode[1] = NULL;
 sequenceIndex = 0;

 while (p_binarySequence[sequenceIndex])
 {
  currentDigit = p_binarySequence[sequenceIndex] - 48;
  if (NULL == currentNode[currentDigit])
  {
   currentNode[currentDigit] = nextFreeNode;
   nextFreeNode[0] = NULL;
   nextFreeNode[1] = NULL;
   nextFreeNode += (sizeof(void*) << 1);
   currentNode = patternTree;
   nodeCount++;
  }
  else
  {
   currentNode = currentNode[currentDigit];
  }
  sequenceIndex++;
 }

 free(patternTree);
 return nodeCount;
}


int main(int argc, char *argv[])
{
 printf("%u\n", LZComplexity("10100101001011101011", 1000));
 return 0;
}

1 0 01 11 10 110 00 010
Сложность последовательности равна 8, потому что разделов 8, а не 6 - 1/0/01/11/10/110/00/010

@Араш и @Санчит Гупта: Возможно, вы запутались между сложностью LZ76 и сложностью LZ78. Тот, о котором говорит Араш, — это сложность LZ76, а другой — сложность LZ78. Вы можете обратиться к разделу 3 статьи «Оценка уровня энтропии импульсных поездов с помощью сложности Лемпеля-Зива».

Guillermo Valle имеет реализацию, которая создает правильные ответы (в отличие, например, от текущего кода Википедии).

Например,

Сложность 0001 равна 2: 0 001

Сложность 010 равна 3: 0 1 0

Создайте бинарное дерево, где слева 0, а справа 1. Для каждого бита попытайтесь найти последовательность в дереве. Если он есть, соедините следующий бит, промойте, повторите. Если его там нет, добавьте его в дерево и продолжайте. LZ Сложность — это общее количество путей в дереве (а не только # листовых узлов).

Кстати, это homework?

Это может быть актуально для вас. Это параллельная реализация алгоритма LZMP, который вычисляет LZ-сложность в CUDA и работает на графическом процессоре nVidia.

http://www.ariel.ac.il/sites/ratsaby/Code/LZMP.zip

Это должно сработать в Python (из: Kaspar, F. Schuster, H. Легко вычисляемая мера сложности пространственно-временных паттернов. Physical Review A, vol 36, n. 2, p 842.)

#!/usr/bin/python


def lz_complexity(s):
    i, k, l = 0, 1, 1
    k_max = 1
    n = len(s) - 1
    c = 1
    while True:
        if s[i + k - 1] == s[l + k - 1]:
            k = k + 1
            if l + k >= n - 1:
                c = c + 1
                break
        else:
            if k > k_max:
               k_max = k
            i = i + 1
            if i == l:
                c = c + 1
                l = l + k_max
                if l + 1 > n:
                    break
                else:
                    i = 0
                    k = 1
                    k_max = 1
            else:
                k = 1
    return c


def main():
    lz = lz_complexity('1001111011000010')
    assert lz == 6 
    print lz


if __name__ == '__main__':

    main()