Да вы что!

thesz — 13.10.2025 https://arxiv.org/abs/1403.4445

"In this paper we present a really simple linear-time algorithm constructing a context-free grammar of size O(g log (N/g)) for the input string, where N is the size of the input string and g the size of the optimal grammar generating this string... The here presented algorithm computes the LZ77 factorisation and transforms it in phases to a grammar..."

Фактически, это показывает, что gzip с его deflate это способ вычисления наименьшей грамматики. ;)

И ладно бы это был LZ78, где (как я понимаю) два фрагмента текста, обнаруженных ранее, объединяются в один (как в sequitur), так они LZ77 используют, где никаких попарных объединений нет!

Удивительно.

PS
Я в прошедшую субботу написал алгоритм PPM*, что вычисляет наиболее длинный контекст поиском а-ля LZ77, с ограничением по количеству попыток поиска по истории. Он довольно точен, надо сказать.

Оставить комментарий

Популярные посты:

• Архив