Вот такая странная идея пришла мне в голову во время сидения на ГЭКе. Точнее, там пришла несколько иная, но потом я ее додумал и вышло вот это. Может, конечно, это велосипед, но что-то я реализаций его не встречал. Если они есть — сорри.
В HTML , e-mail и т.д. пересылается текст на русском языке. Этот текст пересылается как набор номеров букв. На букву — один байт (или 2, если юникод).
А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
"Словарная средняя длина слова (согласно словарям Даля и Ожегова) составляет 6-7 звуков". Ладно, пусть 6, тем более, что звук и буква не одно и то же.
Будем считать слова различными, если они отличаются хотя бы одним символом. Так что все падежные формы и склонения — это разные слова.
Если слово нумеровать 2 байтами, то мы можем иметь 65 тыс. слов. Этого, конечно, мало для полного словаря.
Если взять 2.5 байта — миллион слов. Этого, я думаю, хватит.
Впрочем, можно и 2 байтами обойтись. Пронумеруем только самые часто встречающиеся слова. Оставшиеся будем передавать как есть, без изменений, что придется делать крайне редко. Никто не мешает передавать смесь кодированного и некодированного текста. Какой-нибудь префикс кодировки ввести (нулевое слово , к примеру), оно же и префикс окончания кодировки. Парсер разберется.
Если исходить из 2-байтной кодировки, то вместо 6 букв (6 или 12 байтов) имеем только 2 байта. Экономия в 3 (6) раз(а).
Кстати, если кодировать все слова без исключения (т.е 2.5 байта), то исчезает понятие кодовой страницы. Передаются просто номера слов. Как их потом буквами записать — дело клиента.
Вполне можно и английский текст также кодировать, если он на русских страницах встречается. Еще один префикс — переключение на английский (и обратно). Конечно, тогда нужен и английский словарь.
Все, что кодировать не удастся (теги HTML и т.д., слова на латыни или на японском ) — слать как обычно. Парсер разберется.
Сам словарь большим не будет. Если даже миллион слов со средней длиной 6 букв — 6 Мб плюс накладные расходы. Мелочь. В конце концов, у многих есть на компьютере англо-русский/русско-английский словарь. Почему бы не быть еще число-русскому/русско-численному ? Да и ставится он один раз и чуть ли не навсегда .
Время кодировки — log(N), где N — число слов, если использовать дерево. Время декодировки — O(1), просто взять по индексу.
Реализовать это можно вообще прозрачно для приложений. Сервер (HTTP или Mail) на выходе кодирует. Клиент (броузер или почтовый) на входе декодирует. Никакое приложение ничего и не узнает. Но для этого, конечно, надо в сервер и клиент изменения вносить.
Или можно реализовать в приложениях. Выходной фильтр на сервере и что-то в стиле AJAX на клиенте.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>В HTML , e-mail и т.д. пересылается текст на русском языке. Этот текст пересылается как набор номеров букв. На букву — один байт (или 2, если юникод). PD>А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
Вопрос 1: какие проблемы вы хотите решить такой кодировкой? Действительно ли это проблемы, а не фантазия?
Вопрос 2: кроме русского, все остальные языки предлагаете игнорировать?
Вопрос 3: если на предыдущий вопрос отвечать отрицательно, то добавлю, что Unicode символ уже сейчас может занимать до 4 байт (см. UTF-32). О каких 2,5 байтах на слово вы вообще говорите?
Здравствуйте, Хитрик Денис, Вы писали:
ХД>Вопрос 1: какие проблемы вы хотите решить такой кодировкой? Действительно ли это проблемы, а не фантазия?
Я все же исхожу из того, что сокращение объема в 3 раза не есть фантазия.
ХД>Вопрос 2: кроме русского, все остальные языки предлагаете игнорировать?
Читайте внимательно. Про английский там сказано. Что же касается текстов на смеси русского, хинди и арабского — покажите мне такую страницу
ХД>Вопрос 3: если на предыдущий вопрос отвечать отрицательно, то добавлю, что Unicode символ уже сейчас может занимать до 4 байт (см. UTF-32). О каких 2,5 байтах на слово вы вообще говорите?
2.5 байта на слово русского языка. С помощью 2.5 байтов можно закодировать миллион различных русских слов. Слов, а не букв.
При чем тут UTF-32 ? В нем 4 байта на символ, а мне хватит 2.5 на слово
With best regards
Pavel Dvorkin
Re: Кодирование слов при передаче по сети (покритикуйте идею
Собственно задавался этой идеей в детстве ещё. Собирал словарь, всё такое. Может конечно тогда чего-то недопонял... Но оказалось, что на практике тот же zip сжимает гораздо эффективнее. Та и ему всё равно, что сжимать. Так что как по-моему затея ненужная. Кстати у нас очень не мало и коротких слов...
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Alexey M., Вы писали:
AM>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Жду комментариев.
AM>А что делать с жаргонными словами, специализированными во всех склонениях и спряжениях? Да и просто написанными с ошибками?
Ответ был дан — все, что не кодируется, слать как есть.
AM>PS. Ваше сообщение в формате UTF-16 было сжато архиватором более чем 3 раза. Какого сжатия вы ожидаете от предложенного решения?
Посчитаем. Итак, UTF-16, 2 байта на букву, 12 байт на слово (при средней длине в 6), да в 3 раза архиватор сжал — 4 байта. А у меня 2 или 2.5 выходит.
With best regards
Pavel Dvorkin
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, fddima, Вы писали:
F> Собственно задавался этой идеей в детстве ещё. Собирал словарь, всё такое. Может конечно тогда чего-то недопонял... Но оказалось, что на практике тот же zip сжимает гораздо эффективнее.
судя по врифметике в моем предыдущем письме — это не совсем так.
>Та и ему всё равно, что сжимать. Так что как по-моему затея ненужная. Кстати у нас очень не мало и коротких слов...
А их можно и не шифровать. Шифровщик, встретив фразу "Я там был, а он там не был" — может вполне разобраться и отправить обычным текстом. Аналогично тому, как NTFS сжимает файлы — если кусок в 16 кластеров не удается сжать хотя бы до 15 — не сжимает , и все.
With best regards
Pavel Dvorkin
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>судя по врифметике в моем предыдущем письме — это не совсем так.
Я только что взял текст, на 160 слов (текст песни). 782 байта. Rar зажал в 483 байта (не забываем о том что всё таки это не просто поток, а архив). 160 x 2.5 = 400 байт. Выигрыш неочевиден, а я ничего не делал с пробелами, и прочей пунктуацией. Как-то кодировать нужно ж. "Оставить как есть", это да, но управлять то потоком нужно.
Или вот. Взял текст побольше. 6905 слов. 55187 байт в тексте (1251). 6905 x 2.5 = 17250. Rar = 11423 байт. Опять же, я думаю умножать на 2.5 это очень грубо, т.к. нужны какие-то управляющие символы и прочее.
PD>А их можно и не шифровать. Шифровщик, встретив фразу "Я там был, а он там не был" — может вполне разобраться и отправить обычным текстом. Аналогично тому, как NTFS сжимает файлы — если кусок в 16 кластеров не удается сжать хотя бы до 15 — не сжимает , и все.
Ну а как узнать что зашифровано, а что нет? Это ж тоже понесёт расходы.
Здравствуйте, Pavel Dvorkin, Вы писали:
ХД>>Вопрос 1: какие проблемы вы хотите решить такой кодировкой? Действительно ли это проблемы, а не фантазия? PD>Я все же исхожу из того, что сокращение объема в 3 раза не есть фантазия.
Во-первых, вам ещё предстоит это доказать, что сжатие в 3 раза гарантировано или близко к этой цифре в вашей схеме.
Во-вторых, вопрос был в другом: так ли уж нужно сжимать именно русские тексты при передаче данных по сети? Чем это будет лучше того же gzip?
ХД>>Вопрос 2: кроме русского, все остальные языки предлагаете игнорировать? PD>Читайте внимательно. Про английский там сказано. Что же касается текстов на смеси русского, хинди и арабского — покажите мне такую страницу
Я неточно выразился. Правильно ли я понимаю, что вы предлагаете кодировать только русские тексты, а английские, хинди и арабские передавать также как и сейчас?
ХД>>Вопрос 3: если на предыдущий вопрос отвечать отрицательно, то добавлю, что Unicode символ уже сейчас может занимать до 4 байт (см. UTF-32). О каких 2,5 байтах на слово вы вообще говорите? PD>2.5 байта на слово русского языка. С помощью 2.5 байтов можно закодировать миллион различных русских слов. Слов, а не букв. PD>При чем тут UTF-32 ? В нем 4 байта на символ, а мне хватит 2.5 на слово
Не забудьте про префиксы, отличающие закодированное слово от буквы, они тоже место занимают.
Здравствуйте, Pavel Dvorkin, Вы писали:
AM>>PS. Ваше сообщение в формате UTF-16 было сжато архиватором более чем 3 раза. Какого сжатия вы ожидаете от предложенного решения? PD>Посчитаем. Итак, UTF-16, 2 байта на букву, 12 байт на слово (при средней длине в 6), да в 3 раза архиватор сжал — 4 байта. А у меня 2 или 2.5 выходит.
Это в идеальном случае. В реальности в письмах часто бывают ссылки, названия на других языках. В итоге получим коэффициент сравнимый с обычным архиватором.
Re: Кодирование слов при передаче по сети (покритикуйте идею
PD>А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
Как отличить номер слова от переданной в тексте цифры?
Как отличить номер слова от (не)юникодной последовательности слова на другом языке?
Как кодировать падежи и спряжения?
Например:
Вчера мне удалось найти целых два решения твоей проблемы
|| || || || || || || || ||
Вчера я? удасться? найти целое? два решение? твой? проблема?
Pavel Dvorkin пишет:
> А что, если вместо этого пронумеровать *слова* русского языка и > пересылать их номера ? Конечно, для этого на сервере должен быть > шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
Архиваторы примерно так и работают. Только у них слово не совпадает со
словом языка, да и словарь они вместе с сообщением пересылают.
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Re: Кодирование слов при передаче по сети (покритикуйте идею
Разговаpивают два пpогpаммиста.
— Слyшай, вчеpа написал новый аpхиватоp. Любой файл сжимает в 5 байт!
— Hy пpосто pyлез!
— Ага. Сейчас pаботаю над pазаpхиватоpом.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
The top programs in this test are specifically optimised for (English) text compression and/or include an internal or external dictionary. This partly explains the relatively big difference between the top and the programs just behind them.
Украли идею, гады!
Re: Кодирование слов при передаче по сети (покритикуйте идею
Вашу идею активно развивали еще в 1986 году (см. A locally adaptive data compression scheme — Bentley, Sleator et al. — 1986).
Кучу работ можете найти по ключевым словам Word-Based Text Compression.
А в оригинальном виде она наверняка была описана еще во времена римской империи.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, D. Mon, Вы писали:
DM>Вашу идею активно развивали еще в 1986 году (см. A locally adaptive data compression scheme — Bentley, Sleator et al. — 1986). DM>Кучу работ можете найти по ключевым словам Word-Based Text Compression. DM>А в оригинальном виде она наверняка была описана еще во времена римской империи.
Египетской, египетской. Они тогда еще все продумали и стали повсеместно использовать иероглифы Ну, чтобы эффективнее использовать папирусы
Re: Кодирование слов при передаче по сети (покритикуйте идею
Алгоритмы компрессии иногда позволяют задавать входящий словарь.
То есть что они делают? Находят повторяющееся сочетание байт, заменяют его некой последовательностью бит (то есть дают ему "номер") и дальше вставляют эту последовательность бит, вместо найденной повторяемой последовательности байт.
Обычно, словарь изначально пуст, то есть нет последовательности байт закодированных потоком бит.
Но можно перед компрессией (и соответственно декомпрессией) задавать этот словарь.
Главное, чтоб и компрессор и декомпрессор подставили один и тот-же.
Собственно, твоя идея к заданию некоего фиксированного предварительного словаря и сводится.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>В HTML , e-mail и т.д. пересылается текст на русском языке. Этот текст пересылается как набор номеров букв. На букву — один байт (или 2, если юникод). PD>А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
Идея не новая. У автора ARJ был следующий архиватор JAR (не путать с явовским суффиксом файлов), в котором был словарь английского и подстановка номера слова при сжатии. Я его видел в районе 95-го, но он страшно жрал память и диск, и что-то с реализацией не сложилось. Но примерно тогда же начал кончаться и ARJ.
The God is real, unless declared integer.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, andy1618, Вы писали:
PD>>Экономия в 3 (6) раз(а). A>... PD>>Жду комментариев.
A>3-6 раз для текста — это дело обычное: A>http://www.maximumcompression.com/data/text.php (лидеры умудряются сжимать в 9 раз)
Что-то архиватор по имени "Дурилка 0.5" вызывает у меня сомнение.:)))
) — слать как обычно. Парсер разберется.
Но оказалось, что на практике тот же zip сжимает гораздо эффективнее. Та и ему всё равно, что сжимать. Так что как по-моему затея ненужная. Кстати у нас очень не мало и коротких слов... 
