Здравствуйте, Pavel Dvorkin, Вы писали: PD>Жду комментариев.
обычные алгоритмы сжатия типа LZ примерно так и работают. они выделяют встречающиеся подстроки, строят по ним словарь и передают вместо подстрок индексы. подстрока — просто последовательный кусок текста. может включать и несколько обычных слов.
алгоритм эффективней вашего вот почему
1. кодируются только строки встречающиеся в файле. обьем составляемого словаря много меньше вашего — универсального. таким образом индексы подстрок будут меньше. словари всегда "адаптированы" под данный файл. а не являются словарями какоего-то общего языка. в алгоритме lZ словарь не передается, а хитрым образом составляется так, что восстанавливается при разжатии из самого сжатого потока. насколько я помню, детали немного забыл.
2. алгоритм универсальный и жмет произвольные файлы.
3. строка может сожержать несколько обычных слов, чего нет у вас. и кодироваться всего байтом.
у вашего алгоритма совершенно нет шансов. даже в простешем базовом варианте LZ и вашего алгоритма, ваш проигрыш в среднем будет в 2-3 раза.
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Жду комментариев.
До идеи словаря ты додумался. Подкидываю следующие — упорядочить словарь по частоте встречаемости, и более частые элементы кодировать меньшим количеством бит, ограничить словарь только реально встречающимися словами, отдельно кодировать корни, приставки и суффиксы, если это выгодно.
Потом можно почитать про Huffman coding.
... <<RSDN@Home 1.2.0 alpha 4 rev. 1090 on Windows Vista 6.0.6001.65536>>
merk wrote:
> обычные алгоритмы сжатия типа LZ примерно так и работают. они выделяют > встречающиеся подстроки, строят по ним словарь и передают вместо > подстрок индексы. подстрока — просто последовательный кусок текста.
Кстати, если я правильно помню, там индексы переменной длины и тем короче, чем чаще встречается подстрока.
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
Алгоритм по сути своей эквивалентен алгоритмам сжатия группы LZ (только он гораздо деревяннее и тупее) с большим размером словаря. Который (словарь), замечу, строится в случае LZ адаптивно и динамически, и от "языка" не зависит. Кстати, указать, что HTTP будет сжат зипом очень просто — там аттрибут такой есть спицыальный. Например, так: Accept-Encoding: gzip,deflate.
This standards-based method of delivering compressed content is built into HTTP 1.1, and most modern browsers that support HTTP 1.1 support ZLIB inflation of deflated documents. In other words, they can decompress compressed files automatically, which saves time and bandwidth.
A>>3-6 раз для текста — это дело обычное: A>>http://www.maximumcompression.com/data/text.php (лидеры умудряются сжимать в 9 раз)
N>Что-то архиватор по имени "Дурилка 0.5" вызывает у меня сомнение.
Блин, точно! 5-м номером идёт! Может, специально под этот тестовый файл написали?
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, ., Вы писали:
.>merk wrote:
>> обычные алгоритмы сжатия типа LZ примерно так и работают. они выделяют >> встречающиеся подстроки, строят по ним словарь и передают вместо >> подстрок индексы. подстрока — просто последовательный кусок текста. .>Кстати, если я правильно помню, там индексы переменной длины и тем короче, чем чаще встречается подстрока.
в самом LZ этой идеи вроде нет, там кажется просто используются индексы переменной длины.
но LZ обычно дополняют сжатием по Хаффману, пропуская поток от LZ через этот вид сжатия — получается аббревиатура LZH. там как раз делается анализ частоты встречаемости.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Читайте внимательно. Про английский там сказано. Что же касается текстов на смеси русского, хинди и арабского — покажите мне такую страницу
Здравствуйте, VUspenskiy, Вы писали:
VU>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Читайте внимательно. Про английский там сказано. Что же касается текстов на смеси русского, хинди и арабского — покажите мне такую страницу
VU>http://ka.wikipedia.org/wiki/????
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Единственное слово на русском языке не считается куском русского текста. Таких страниц можно найти миллион. Навярняка многие страницы про Будду на русском языке содержат сноски на написание его имени и на многих языках. Ну, так это ж редкое исключение, которое на общее сжатие не влияет и кодируется, как есть, — без сжатия.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Lloyd, Вы писали:
L>Зачем, если можно использовать gzip?
Я не ответил вчера, хотел подумать.
Мне кажется, это разные вещи. В русском языке средняя длина слова 6 символов. Это не имеет отношения к информатике, так сложилось по иным причинам. Так что текст длиной в N букв занимает 6N байт (или 12N).
А предстваь себе, что в русском (или ином) языке средняя длина слова — 12 символов. При том же лексиконе. Тогда суммарная длина будет 12N (24N) байт при том. что передается та же информация.
Ты уверен, что gzip сожмет этот массив удвоенной длины до того же размера, что и одинарной длины ? Сомневаюсь.
Здравствуйте, Хитрик Денис, Вы писали:
ХД>Здравствуйте, Pavel Dvorkin, Вы писали:
ХД>Во-первых, вам ещё предстоит это доказать, что сжатие в 3 раза гарантировано или близко к этой цифре в вашей схеме.
Да.
ХД>Во-вторых, вопрос был в другом: так ли уж нужно сжимать именно русские тексты при передаче данных по сети? Чем это будет лучше того же gzip?
ХД>Я неточно выразился. Правильно ли я понимаю, что вы предлагаете кодировать только русские тексты, а английские, хинди и арабские передавать также как и сейчас?
Не совсем. Для русскоязычных страниц (которые могут, конечно, содержать вкрапления на других языках) — да. Для хиндиязычных страниц — кодировать только слова на хинди. И т.д. Английские слова можно кодировать на всех страницах, я об этом писал.
ХД>Не забудьте про префиксы, отличающие закодированное слово от буквы, они тоже место занимают.
Не забыл. Тут надо определить, с чем мы имеем дело. Если это форма ввода для магазина — лучше вообще не кодировать, префиксы больше места займут. Если это описание товара на 1-2 Кб — может , да, может, нет. Если это статья на литературную тему размером в 20 Кб — скорее да. Ну а если это глава из "Войны и Мира" — сам бог велел. Несмотря даже на наличие там французских вкраплений.
With best regards
Pavel Dvorkin
Re[4]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Mr.Cat, Вы писали:
MC>Как Вам уже сказали, идея не нова. ИМХО, тут надо двигаться, в ту же сторону, что и при сжатии звука и изображений — в сторону сжатия с потерями.
Тоже уже было такое. Например, в древнем финикийском письме при записи гласные опускались, оставлялись только согласные.
... << RSDN@Home 1.2.0 alpha rev. 778>>
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Mamut, Вы писали:
PD>>А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
M>Как отличить номер слова от переданной в тексте цифры?
А как отличают в UTF-8 однобайтный символ от двух или трех-байтного ? Примерно так же.
M>Как отличить номер слова от (не)юникодной последовательности слова на другом языке?
Так же.
M>Как кодировать падежи и спряжения?
Читай внимательно исходный постинг. Все слова считаются различными, если они отличаются хоть одной буквой. Формы склонений — различные слова, так что для каждого существительного будет в лексиконе от 1 до 6 слов.
With best regards
Pavel Dvorkin
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, Pavel Dvorkin.
DM>Вашу идею активно развивали еще в 1986 году (см. A locally adaptive data compression scheme — Bentley, Sleator et al. — 1986). DM>Кучу работ можете найти по ключевым словам Word-Based Text Compression. DM>А в оригинальном виде она наверняка была описана еще во времена римской империи.
Не сомневаюсь. Но вот реализаций не вижу.
With best regards
Pavel Dvorkin
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, merk, Вы писали:
M>Здравствуйте, Pavel Dvorkin, Вы писали: PD>>Жду комментариев.
M>обычные алгоритмы сжатия типа LZ примерно так и работают. они выделяют встречающиеся подстроки, строят по ним словарь и передают вместо подстрок индексы. подстрока — просто последовательный кусок текста. может включать и несколько обычных слов. M>алгоритм эффективней вашего вот почему M>1. кодируются только строки встречающиеся в файле. обьем составляемого словаря много меньше вашего — универсального. таким образом индексы подстрок будут меньше. словари всегда "адаптированы" под данный файл. а не являются словарями какоего-то общего языка. в алгоритме lZ словарь не передается, а хитрым образом составляется так, что восстанавливается при разжатии из самого сжатого потока. насколько я помню, детали немного забыл. M>2. алгоритм универсальный и жмет произвольные файлы. M>3. строка может сожержать несколько обычных слов, чего нет у вас. и кодироваться всего байтом.
M>у вашего алгоритма совершенно нет шансов. даже в простешем базовом варианте LZ и вашего алгоритма, ваш проигрыш в среднем будет в 2-3 раза.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Жду комментариев.
AVK>До идеи словаря ты додумался. Подкидываю следующие — упорядочить словарь по частоте встречаемости, и более частые элементы кодировать меньшим количеством бит, ограничить словарь только реально встречающимися словами, отдельно кодировать корни, приставки и суффиксы, если это выгодно. AVK>Потом можно почитать про Huffman coding.
Спасибо. Я Huffman_coding рассказывал студентам еще лет 10 так назад на лекциях.
А вот одно ты не понял. Хоть Хаффман, хоть LZH — слова исходного текста (в той или иной форме) в сжатом архиве хранятся. А у меня вообще нет.
Только подумай как следует. А если слова не 12, а 100 байт длину имеют, при том, что различных слов всего 100 тысяч. Тоже сожмешь до того же размера, что и русский текс ?
