Почему после алкоголя тяжело дышать ночью: причины, что делать и когда обращаться к врачу Когда эрефяне жалуются, что "в капиталистическом государстве никто не может диктовать режиссерам,какие фильмы снимать", имея в виду засилье таких "шедевров", как фильмы про бандитов, они очень сильно лукавят. Давно известно,что тот, кто хочет что то сделать, ищет возможность. Кто не ...
Да вы что!
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, с ограничением по количеству попыток поиска по истории. Он довольно точен, надо сказать.
Сохранено
|
|
</> |
Оставить комментарий
Популярные посты:
Архив записей в блогах:
Если бы «Сплит» снимали в России: Дмитрий Нагиев и его перевоплощения в сериале «Осторожно, модерн!» Как вам перевоплощения? Убедителен брутальный Нагиева в роли этаких сексуальных дам? Дмитрий говорил, что играть женщин – это еще ничего, а вот переодеваться для ролей – ...
Номер 18 (305) газеты "За науку" от 23 мая 1969 года, обратная сторона - та, что с человеческим лицом (кликабельно, 2000х2805 точек): Вся полоса - под рубрикой "Даешь каждый день первое апреля" "РФ-газета" меняет редакцию - окончание статьи с обложки. Факультетская хроника - ...
Как из великого блага делают БАБУ ЯГУ Кто в современном мире будет опаривать бесценное благо - интернет? Хочешь пообщаться-один клик-пожалуйста! Хочешь найти новости - в ленте всё на блюдечке с голубой каёмочкой. Хочешь перевести деньги-один момент и ты выручил родного человека, друга, ...
С НАЧАЛОМ ЗИМЫ! ************************** Есть древнее тайное учение, такого же возраста, как человеческий род; оно передается из уст в уста и до наших дней, но лишь немногие знают это. Наши предки умели создавать расположение планет, ...
