ded_maxim: (Gottfried Wilhelm von Leibnitz)
[personal profile] ded_maxim
Известно, что алгоритм Лемпеля-Зива обладает свойством универсальности по сравнению с классом всех конечных автоматов: любую достаточно длинную последовательность символов, принимающих конечное число значений, алгоритм Лемпеля-Зива может сжать почти настолько же, насколько это можно сделать при помощи любого конечного автомата (включая любые КА, которые можно построить, зная последовательность наперед). Недавно появилась статья, в которой утверждается, что алгоритм Лемпеля-Зива не универсален по отношению к классу магазинных автоматов: авторы статьи построили последовательность, которую алгоритм Лемпеля-Зива практически не может сжать, но которая сжимается по крайней мере наполовину с помощью магазинного автомата.

Date: 2007-04-19 08:54 pm (UTC)
From: [identity profile] ygam.livejournal.com
Забавно. Ты об этом узнал из какого-то блога?

Date: 2007-04-19 08:58 pm (UTC)
From: [identity profile] ded-maxim.livejournal.com
Нет, просто я ежедневно слежу за постингами в http://arxiv.org/list/cs.IT/recent и http://arxiv.org/list/cs.LG/recent. Должен же я интересоваться, чем мои коллеги занимаются.

Date: 2007-04-19 10:30 pm (UTC)
From: [identity profile] juan-gandhi.livejournal.com
Wow! How obvious, and how refreshing!

Date: 2007-04-19 11:14 pm (UTC)
From: [identity profile] spamsink.livejournal.com
Ну да, а если LZ модифицировать так, чтобы он мог ссылаться и на строки задом наперед?

Например,

abcdcba обычным LZ совсем не сжимается, а модифицированным - abcd(1,-3). Здесь первое число в паре - отступ назад, а второе - длина. Отрицательные числа используются для "задом наперед".

Date: 2007-04-20 12:49 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
Верите ли, я уже обсуждал нечто подобное с разными людьми, вроде бы какие-то работы в этом направлении ведутся, но конкретных результатов вроде бы либо нет, либо очень мало.

Date: 2007-04-20 01:05 am (UTC)
From: [identity profile] spamsink.livejournal.com
Да кого бы сейчас LZ интересовал, особенно для таких источников, для которых описанное улучшение будет существенным? Хардверный LZ обычно вообще не 77, а 78 (LZW), а относительно нового софтвера, использующего LZ77, я и не назову...

Date: 2007-04-22 04:24 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
Теоретики до сих пор живо интересуются LZ. Во-первых, он поддается анализу, и на его основе изучают другие задачи -- была статья, например, где на основе LZ строился алгоритм для сжатия с потерями, причем обладающий свойством универсальности не только по отношению к статистической природе источника, но и по отношению к функции потерь. Во-вторых, LZ важен концептуально: идея вероятностного моделирования, в основе которой лежит контекстный парсинг последовательностей, распространяется на такие задачи, как оптимальное управление.

Date: 2007-04-22 01:53 am (UTC)

Profile

ded_maxim: (Default)
ded_maxim

December 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
2425 2627282930
31      

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 30th, 2025 04:49 am
Powered by Dreamwidth Studios