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

Question

Мне нужно вычислить LZ-сложность двоичной строки.LZ-сложность - это количество подстрок разности, встречающихся при просмотре потока от начала до конца.В качестве примера:

s = 1001111011000010

Маркировка в разных подстроках сложности последовательности c (s) = 6: s = 1/0/01/1110/1100/0010 /

Может ли кто-нибудь помочь мне найти простое решение для этого?Я уверен, что для этой хорошо известной проблемы должно быть несколько очень простых реализаций, но мне трудно их найти.Можно ли это сделать просто с помощью построения дерева суффиксов или чего-то подобного.Если да, то как именно?и что я должен делать?

кто-нибудь знает какой-либо исходный код на c / c ++ для выполнения задачи?

Заранее спасибо.

, чтобы уточнить конструкцию дерева, предложенного в ответах.Дерево выглядит так?

         o
       /   \
      o     o
     / \   / \
    o   o o   o
       /     /
      o     o

Answer 1

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

Answer 2

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

Answer 3

Ниже приведен краткий пример того, как вычислять 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;
}

Answer 4

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

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

Answer 5

Это должно сработать в Python (от: Каспар, Ф. Шустер, Х. Легко вычисляемая мера для сложности пространственно-временных моделей . Физический обзор A, том 36, № 2, стр. 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()

Answer 6

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

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