Вычисление сложности Лемпеля-Зива (LZ) (или сложности последовательности) двоичной строки
Мне нужно рассчитать 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
6 ответов
@Arash и @Sanchit Gupta: Возможно, вы запутались между сложностью LZ76 и сложностью LZ78. То, на что ссылается Араш, это сложность LZ76, а другая - сложность LZ78. Вы можете обратиться к разделу 3 статьи "Оценка скорости энтропии поездов с шипами с помощью сложности Лемпель-Зив".
1 0 01 11 10 110 00 010
Сложность последовательности составляет 8, потому что разделы 8 не 6 - 1/0/01/11/10/110/00/010
У Гильермо Валле есть реализация, которая дает правильные ответы (в отличие, например, от текущего кода Википедии).
Например,
Сложность 0001 равна 2: 0 001
Сложность 010 равна 3: 0 1 0
Ниже приведен краткий пример того, как вычислять 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;
}
Это может быть актуально для вас. Это параллельная реализация алгоритма LZMP, который вычисляет LZ-сложность в CUDA и работает на GPU nVidia.
Создайте двоичное дерево, где left равно 0, а right равно 1. Для каждого бита попытайтесь найти последовательность в дереве. Если он есть, соедините следующий бит, промойте, повторите. Если его там нет, добавьте его в дерево и продолжайте. Сложность LZ - это общее количество путей в дереве (а не только # конечных узлов).
Кстати, это homework?
Это должно сработать в 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()