Данный вариант берет текст в виндовой кодировке и все русские слова длиной больше 3 букв заменяет на трехбайтные коды, у которых первый символ — от 128 до 143 (они не встречаются в тестовом файле, это спецсимволы), второй и третий — от 16 до 255, т.е. всего можно закодировать 240*240*16 = 921600 разных слов. При кодировании строится словарь и сохраняется в файл. Декодер читает этот словарь и полностью восстанавливает исходный текст.
Чуть изменив иходник, можно перейти на кодирование двухбайтными кодами всех слов длиннее 2 букв. Но тогда доступно всего 3840 слов, что маловато.
Результат применения на тестовом русском тексте:
Оригинал — 24351 байт, 3904 слов общей длиной 19453 байта (остальное — пробелы и пунктуация). Слов длиннее 3 букв — 2449 штук, из них 1629 разных. Они занимают в сумме 16468 байт до сжатия (и 7,5 кб после).
Слов длиннее 2 букв — 2986 штук, из них 1723 разных, они в сумме занимают 18079 байт до сжатия и около 3 кб после.
Размер сжатого файла при компрессии в трехбайтные коды — 15230 (63% от оригинала).
Размер сжатого файла при компрессии в двухбайтные коды — 12244 (50% от оригинала). Но тут все слова поместились в словарь, а в общем случае такого не будет, поэтому степень сжатия будет существенно хуже.
Сжатый зипом — 11075 байт (45%).
Сжатый раром в режиме best — 9014 (37%).
А вот если сжатый двухбайтными кодами файл еще зазиповать, то получается уже 7316 байт (30%).
Вывод: как самостоятельный метод сжатия никуда не годится, а как препроцессор для дальнейшего сжатия — сойдет. Собственно, такие препроцессоры применяются в компрессорах уже десятки лет.
Полная реализация компрессора и декомпрессора заняла по 8 строк кода.
Если такую задачу готовы дать в качестве курсовой, это много говорит о Омском "университете" и его преподавателях.
Re[5]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Если не сложно, приведи пример дипломной работы твоего вуза, удостоенной "Editor Choice" в PC Magazine.
А медаль "лучшему бетоноукладчику" не показать? Сама постановка вопроса уже выдает Вас с головой.
Пример, который Вы привели и просите у меня, — это результат добротной инженерной работы: ноль науки, зато много вероятно неплохого кодинга. Это отличный результат для трехмесячных курсов программирования ("освой MFC за 12 уроков") или даже для профессионального училища (ПТУ). В университете дипломные работы обычно совсем другие — они должны содержать хоть сколько-то науки, изобретать что-то новое, содержать какие-то нетривиальные идеи. Умения пользоваться MSDN и клепать формочки недостаточно для защиты диплома.
Теперь что касается студенческих работ моего вуза.
Я не преподаватель и не в курсе большей части работ, но кое-какие примеры видел. Вот, например, некоторые студенческие работы моего факультета в области обработки и сжатия видео: http://compression.ru/video/index_ru.htm
Те же технологии в коммерческой упаковке: http://www.yuvsoft.com/technologies.html
Из клиентов (покупателей технологий) — Intel, Samsung, Real и куча компаний поменьше.
Если немного вернуться к теме компрессии, которую тут обсуждали.
У нас на факультете есть спецкурс (т.е. даже не основной предмет), в рамках которого студенты выполняют ряд интересных заданий, в том числе написание универсального компрессора — на это задание дается 2-3 недели (в Вашем вузе за это академика бы давали, похоже). http://graphics.cs.msu.ru/courses/mdc2003/assigns/index.html
А вот пример решения такого задания (написанный за пару недель), который сжимал в среднем лучше, чем тогдашний rar: http://about.thedeemon.com/products/arh/
Re[9]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А вот если под словами "в первую очередь" понимать, что это главное (а это , видимо, и есть, то понимание, которое ты сюда вложил) — согласен лишь отчасти. База — дело очень важное, но и знание современных технологий — не менее. Вот предсавь себе выпускника, который эту базу знает очень хорошо, но кроме консольных приложений (разве с их помощью нельзя разрабатывать алгоритмы ?) ничего писать не умеет ? В академическом институте он себе место найдет и будет дальше разрабатывать алгоритмы, но ведь мы готовим все-таки практических программистов. Куда его возьмут в реальных условиях ?
При современном-то кадровом голоде? Если не будет запрашивать денег как сеньёр-девелопер, то возьмут в любую сколь-то приличную контору на должность стажера. При мозгах, правильно поставленных на обучение новым вещам, он через месяц уже сможет участвовать в разработке под чутким руководством, через 2-3 самостоятельно на простых задачах, а через полгода — уже будет прекрасно знать все что требуется.
Причем, что характерно, изучит именно то, что нужно в данной компании.
Собственно у меня пример перед глазами — мы пишем под ASP.NET. Полгода назад взяли разработчика — окончил из академического полувоенного НИИ, который там писал расчеты на Фортране. С ASP.NET и даже .NET не работал вообще(!). Сейчас — очень даже хороший разработчик, которому можно доверить задачу и быть уверенным, что он ее выполнит, причем выполнит хорошо — а что не знает, найдет и изучит.
И другие примеры я видел. Вот был разработчик — выпускник курсов, ASP.NET знает, веб знает, все вроде нормально. Дашь задачу — сделает. Но сделает так, что хоть стой хоть падай — технически все достаточно верно, но алгоритмически сплошь ошибки, да непродуманные моменты, но так, что все вроде работает... При нормальных условиях. Но шаг влево-шаг вправо — ситуация непредсказуема. Поддерживать решение сложно — всегда вылезают ошибки и недочеты, а в какой-то момент оказывается проще все выкинуть и переделать.
Дашь задачу исправить ошибку — исправит, все вроде работает. Посмотришь в код на ревью — и наступает ох... удивление — вместо того, чтобы изменить проблемный код, он обложен условными операторами, добавлены ветки в коде, которые тщательно обходят найденные случаи ошибок и для них предусмотрены свои решения... ну а что не предусмотрели — по прежнему старый баг на месте...
Вот что тут делать? Я могу обучить человека .NET-у и ASP.NET-у и даже, может быть, грамотному ООП. Но как научить человека ДУМАТЬ, или хотя бы просто не бросаться решать задачу с первой мысли, а обдумать и сравнить несколько вариантов — я не знаю как, тут у меня навыков никак не хватит. И именно развитие умения думать, на мой взгляд, — главная задача ВУЗа...
З.Ы.1 Сколько мы ни берем людей — чему-то обучать все равно приходится. Лучше, если обучать надо меньше, но это все не критично, главное, чтобы голова работала нормально.
З.Ы.2 Я сам сейчас в нашей компании и разрабатываю на .NET и людей контролирую и консультирую. При этом в университете в основной программе курса по .NET не было вообще ни в каком виде...
З.Ы.3 В универе не преподавали ни одной библиотеки для построения Windows-интерфейса, хотя я их изучал самостоятельно под свои нужды (да-да, только в консоли работали). Так вот, за все время работы я участвовал в разработке по-моему 2х прилад с Windows-интерфейсом (и то, на .NET, которого все равно не было вообще), и при этом моя роль была не в собственно интерфейсе
Далее, библиотеки и фреймворки для разработки Web-приложений тоже в универе не преподавали, но, хотя я сейчас с ними работаю постоянно, проблем от этого никогда не испытывал...
Хуже того, нам негодяйские преподаватели даже не рассказывали как работать с Oracle или Sql Server... И я тоже от этого не страдаю, скорее наоборот, потому что вместо этого читали общий курс по организации баз данных и реляционной алгебре, с описанием стандартного ANSI SQL и самой механики работы БД и вытекающих оттуда правил использования..
А поработать, кроме тех двух, пришлось и с Postgres, и c MySql, с Sqlite...
Вот такая странная идея пришла мне в голову во время сидения на ГЭКе. Точнее, там пришла несколько иная, но потом я ее додумал и вышло вот это. Может, конечно, это велосипед, но что-то я реализаций его не встречал. Если они есть — сорри.
В 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 на клиенте.
Жду комментариев.
With best regards
Pavel Dvorkin
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Жду комментариев.
До идеи словаря ты додумался. Подкидываю следующие — упорядочить словарь по частоте встречаемости, и более частые элементы кодировать меньшим количеством бит, ограничить словарь только реально встречающимися словами, отдельно кодировать корни, приставки и суффиксы, если это выгодно.
Потом можно почитать про Huffman coding.
... <<RSDN@Home 1.2.0 alpha 4 rev. 1090 on Windows Vista 6.0.6001.65536>>
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Это же не картинка, где если в одном пикселе вместо истинного RGB(100,134,156) будет RGB(100,135,156) — никто и не заметит. Текст должен воспроизводиться точно.
Ну почему. Допустим, в КСВ персонаж S******* обозвал персонажа k** словом из 17-ти букв. Если при сжатии заменить его на слово из 3-х букв — тоже никто и не заметит (наверное, даже сам S*******). Пример, утрированный, но вполне жизненный. Не всегда текст нужно воспроизводить точно. Например, в тех же форумных дискуссиях в каждом сообщении есть некоторая полезная информация, определяющая позицию автора и ход дискуссии, а есть — мусор, вроде взаимных оскорблений, сравнений длины и т.п.
Кстати говоря, крайним случаем задачи сжатия с потерями (ИМХО) можно считать автоматическое реферирование — тоже довольно интересное направление.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Между тем сами звуки ровно ничего не означают (если, конечно, речь не идет о воинственных кличах ). Элементом словаря (предметной области, человеческой деятельности, человеческой жизни вообще) является не звук, а слово. Именно из слов состоит наша речь, и тот факт, что для передачи слов мы их расчленяем на звуки — это лишь исторически и биологически так сложилось. Если бы мы слова произносили не голосом, а как-то иначе — возможно, никаких звуков бы и не было.
Дваркин, я тебя умоляю, ты только иероглифы не изобретай, а то ведь китайцы и японцы в суд подадут.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, D. Mon, Вы писали:
DM>Вашу идею активно развивали еще в 1986 году (см. A locally adaptive data compression scheme — Bentley, Sleator et al. — 1986). DM>Кучу работ можете найти по ключевым словам Word-Based Text Compression. DM>А в оригинальном виде она наверняка была описана еще во времена римской империи.
Египетской, египетской. Они тогда еще все продумали и стали повсеместно использовать иероглифы Ну, чтобы эффективнее использовать папирусы
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, andy1618, Вы писали:
PD>>Экономия в 3 (6) раз(а). A>... PD>>Жду комментариев.
A>3-6 раз для текста — это дело обычное: A>http://www.maximumcompression.com/data/text.php (лидеры умудряются сжимать в 9 раз)
Что-то архиватор по имени "Дурилка 0.5" вызывает у меня сомнение.:)))
The God is real, unless declared integer.
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Жду комментариев.
Сорри, совсем оффтопик, но раз уж философия, да еще и программирования...
Предлагаю следующую предварительную оптимизацию
1. Ввести один язык. Заодно поработить остальные народы, но это уже не столь важный побочный эффект
2. Сократить язык до размеров новояза. Представляете перспективы уменьшения трафика?!
И наконец, хит маркетинговой мысли
3. Выпускать Lite версию броузера в котором все слова интерпретироваться в язык Эллочки Людоедки
Те, кто утверждают, что архивация будет эффективнее — возможно, правы.
Те, кто утверждают, что данный подход имеет какое-то отношение к алгоритмам архивации — безусловно неправы. Это совершенно разные вещи.
Представим себе, что создано ПО для маленьких детей, не умеющих еще писать и читать. Это ПО позволяет им обмениваться картинками, но по прихоти разработчика не любыми, а только теми, что есть в базе данных этого ПО. Естественно, база у обоих ребятишек одна и та же.
В этом случае программист, который будет пересылать эти картинки вместо того, чтобы пересылать их номера , будет <пропускаю определение из соображений политкорректности>. Программист же, который будет аргументировать пересылку картинок тем, что их можно еще и сжать, будет <пропускаю определение из соображений политкорректности> в квадрате.
А знаете, кто эти дети ? Мы с вами, вполне взрослые люди. Мы обмениваемся друг с другом наборами картинок и передаем при этом по сети их номера. Если кто-то еще не понял — для русскоязычных таких картинок 64 (или 66), для англоязычных — 52. А в качестве внешней базы данных используем некий TTF или FON файл.
Только не надо рассуждений на тему о том, что мол, таких TTF файлов много. В старые добрые досовские времена пересылали тексты так же. А в качестве базы данных картинок у нас в России использовался незабвенный rkvga.com. Ничего в принципе здесь не изменилось.
А вот если я вас попрошу прислать мне текст хоть и на русском языке, но записанный глаголицей, а не кириллицей, то у вас два варианта. Либо прислать мне базу данных (TTF для глаголицы ), договориться о номерах и потом как обычно, либо, если первое невозможно, действительно слать картинки. Если у вас эти картинки в формате BMP, то не мешает их предварительно сжать (или в другой, сжатый, формат перевести).
Таким образом, пересылка информации с внешним словарем имеет место гораздо чаще, чем некоторые здесь думают. И вопрос о том, кодировать ли буквы, или слова (а может, слоги, а может, пары букв) — этот вопрос не принципиальный, а технический. Проще говоря, вопрос звучит так — при каком способе кодирования можно получить код минимальной длины ? Вполне возможно, что для разных национальных языков этот ответ может оказаться различным.
Что же касается сжатия — его можно применятть в обоих случаях, это совсем другой вопрос. Естественно, качество сжатия может быть (и будет) лучше при кодировании буквами , чем словами. Вопрос — насколько и что получится в результате. Хотите сравнивать несжатые коды — бога ради. Хотите сжатые — тоже бога ради.
Если же вопрос рассматривать в более общем плане, то можно сказать вот что. Если я хочу вам передать некоторую информацию, то у меня есть два способа. Либо передать ее в абсолютном формате, так чтобы вы (человек!) могли ее воспринять без привлечения чего бы то ни было еще (штатное ПО не рассматриваем). Либо передать вам способ, с помощью которого вы сможете ее получить сами, используя ту информацию, которая, как я предполагаю, у вас на компьютере уже имеется. Этот способ может быть и именем файла, и запросом SELECT и даже одним битом . И в случае передачи абсолютной информации, и в случае передачи способа дело закончится передачей некоторого массива байтов, который можно при необходимости и сжать перед пересылкой. И вопрос тут только один — какой код будет короче в данном конкретном случае.
Здравствуйте, ., Вы писали:
.>gandjustas wrote:
>> А зачем слова заменять? Можно ведь заменять целые предложения. Используя >> четырехбайтное кодирование можно в словаре иметь четыре миллиарда >> различных предложений. А то что не заменяется передавать как есть. .>Разовьём идею дальше. Я уверен, что во всём мире существует не более 8^1024 текстов (и ещё на долго хватит). А значит _любой_ текст, любой длины можно ужать в 1кб! :)
Можно и сильнее. Как я однажды сказал так что аж на баше процитировали:) — eDonkey — крупнейший восстанавливатель файла по его md5:)
Только вот разархивация является очень сложным процессом.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>В общем, так. Подумал я еще раз.
PD>Те, кто утверждают, что архивация будет эффективнее — возможно, правы. PD>Те, кто утверждают, что данный подход имеет какое-то отношение к алгоритмам архивации — безусловно неправы. Это совершенно разные вещи.
Очень жаль, что ты не понимаешь сути вещей.
PD>Таким образом, пересылка информации с внешним словарем имеет место гораздо чаще, чем некоторые здесь думают. И вопрос о том, кодировать ли буквы, или слова (а может, слоги, а может, пары букв) — этот вопрос не принципиальный, а технический.
Это вопрос как раз принципиальный. Потому, что принципиальное отличие букв от слов — в том, что букв гарантированно фиксированное количество, благодаря чему можно, как правило, полагаться на наличие подходящей интерпретации на принимающей стороне. "Как правило" — потому, что если я передам "номера", для которых у тебя "картинок" нет (например, что-то из редкоиспользуемого диапазона Unicode), то ты увидишь "прямоугольнички". Что, собственно, и показывает основную уязвимость схемы общения по принятому словарю.
PD>Проще говоря, вопрос звучит так — при каком способе кодирования можно получить код минимальной длины ?
Как только вопрос начинает звучать так, так сразу подход начинает иметь отношение к алгоритмам архивации.
Очень странно, что преподавателям информатики не рассказывают основополагающие вещи, которыми занималась вся информатика, начиная еще с Лейбница: работа с языками, выбор алфавитов, и так далее.
PD>Вполне возможно, что для разных национальных языков этот ответ может оказаться различным.
PD>Что же касается сжатия — его можно применятть в обоих случаях, это совсем другой вопрос. Естественно, качество сжатия может быть (и будет) лучше при кодировании буквами , чем словами. Вопрос — насколько и что получится в результате. Хотите сравнивать несжатые коды — бога ради. Хотите сжатые — тоже бога ради.
PD>Если же вопрос рассматривать в более общем плане, то можно сказать вот что. Если я хочу вам передать некоторую информацию, то у меня есть два способа. Либо передать ее в абсолютном формате, так чтобы вы (человек!) могли ее воспринять без привлечения чего бы то ни было еще (штатное ПО не рассматриваем).
Это, очевидно, невозможно. В любом случае некоторый способ необходим. В частности, не имеет смысла передавать хоть номера букв, хоть изображения, если реципиент не умеет читать. Не имеет смысла передавать звуки, если реципиент не знает языка, на котором они произнесены.
PD> Либо передать вам способ, с помощью которого вы сможете ее получить сами, используя ту информацию, которая, как я предполагаю, у вас на компьютере уже имеется. Этот способ может быть и именем файла, и запросом SELECT и даже одним битом .
Да-да. Учебник информатики, 10-11 класс, рассказ про марафонского бегуна, который передал один бит информации, опираясь на знание получателями древнегреческого языка. Рассказ про гвардейцев, расставленных между Москвой и Петербургом, дабы ружейной пальбой передать факт рождения наследника. Опираясь, естественно, на предварительные договоренности.
PD>И в случае передачи абсолютной информации, и в случае передачи способа дело закончится передачей некоторого массива байтов, который можно при необходимости и сжать перед пересылкой. И вопрос тут только один — какой код будет короче в данном конкретном случае.
Очевидно, что неважно, разделять ли фазу построения словаря и фазу сжатия, или нет, и сколько будет таких фаз. Читайте Шеннона про передачу сообщений — там всё написано. Вкратце напомню один простой факт: вопрос ровно в том, сколько может быть различных сообщений, и насколько они различны, и каковы частоты встречаемости. Вопрос также и в том, как учитывать стоимость обмена словарями в оценке стоимости передачи.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Mr.Cat, Вы писали:
MC>Как Вам уже сказали, идея не нова. ИМХО, тут надо двигаться, в ту же сторону, что и при сжатии звука и изображений — в сторону сжатия с потерями.
Гениально! Аплодирую стоя! Тем более, что для большинства текстов в интернете потеря 95% букв пройдёт незамеченной!
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
M>>Сколько точно — хз Если мы будем только формы глагола считать, не ударясь в причастия и деепричастия E>Обычно причастия и деепричастия в русской морфологии считаются формами глагола. Ещё можно возвратные формы включать или не включать в парадигму, кстати...
Всё правильно. Вот тут можно заценить всю мощь русского языка, введя какой-нибудь хороший глагол (например, парадигма глагола "программировать" состоит из примерно 170-180 словоформ): http://starling.rinet.ru/cgi-bin/morphque.cgi?encoding=win
Re[10]: Кодирование слов при передаче по сети (покритикуйте
D. Mon,
LCR>> Выводы высосаны из пальца.
DM>Возможно. DM>Считаете ли Вы озвученную тему достойной курсовой работы?
Да. Сложность задачи зависит от пристальности взгляда.
Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований: частотный анализ, морфологический анализ, обобщения алгоритма на смешанные тексты, и дальше на произвольные наборы данных. И не надо говорить, что студент изобретёт велосипед. Во-первых, курсовая — это учебный труд, призванная показать, что студент в состоянии использовать изученный материал. Во-вторых, неожиданности-таки случаются, поскольку разум студента не замутнён "широкоизвестными и хорошо зарекомендовавшими себя решениями", и есть вероятность придумать что-то принципиально новое.
DM> Считаете ли Вы допустимым преподавателю программирования в университете не быть знакомым с азами теории информации — идеями Шеннона и Колмогорова?
Да, считаю. Почему? Потому что теория сложности по Колмогорову нужна только при теоретическом анализе вычислительных алгоритмов. В рамках курсов Павла Лазаревича, даже если взять смежные области радиусом с километр, понятие о k(x) будет только мёртвым грузом. Которое, тем не менее думаю, ему известно.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Ты уверен, что gzip сожмет этот массив удвоенной длины до того же размера, что и одинарной длины ? Сомневаюсь.
Напрасно. Почитай про то, как он устроен. На примитивном уровне GZip строит словарь самостоятельно. Ему наплевать на "длину слова", его интересует исключительно "словарный запас".
Инициализация словаря предопределенным набором помогает только для случаев очень коротких текстов.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Мне кажется, это разные вещи. В русском языке средняя длина слова 6 символов. Это не имеет отношения к информатике, так сложилось по иным причинам. Так что текст длиной в N букв занимает 6N байт (или 12N).
PD>А предстваь себе, что в русском (или ином) языке средняя длина слова — 12 символов. При том же лексиконе. Тогда суммарная длина будет 12N (24N) байт при том. что передается та же информация.
PD>Ты уверен, что gzip сожмет этот массив удвоенной длины до того же размера, что и одинарной длины ? Сомневаюсь.
Ты не забывай, что есть еще такой фактор, как частота употребления букв в языке.
Например, в русском гласные О,Е,А,И представляют собой 33% всех букв в текстах (в среднем)
Кроме того, в языке многие двухбуквенные и трехбуквенные сочетания распространены больше, чем другие (а некоторые вообще не могут встречаться). Причем, это может быть связано с положением в слове (начало/конец, то есть еще в сочетании с пробелом)
Пример — http://urikor.net/rus/PH14.html
Все это только поможет zip при увеличении объема текста
Здравствуйте, VUspenskiy, Вы писали:
VU>Итак, религиозные и лингвистические тексты — не сжимаются. VU>Технические тексты, где наполовину английского и терминов-калек с английского тоже плоховато.
VU>Можно легко только общение в аське кодировать:
VU>Привет, как дела? — 0 VU>Нормально — 10 VU>как обычно — 100 VU>и тд.. — 101..
VU>:)
Спасибо за обсуждение. Некоторые замечания интересны. Особенно там, где речь шла о Римской империи и Древнем Египте. Впрочем, у меня было время подумать и самому.
Давайте отвлечемся от GZIP и Хаффмана и рассмотрим с иной стороны.
В русском языке текст передается буквами. Буква есть (неточный) аналог звука. Не надо мне указывать на их отличие, условно примем, что это так. Таким образом, мы имеем передачу пронумерованных звуков.
Между тем сами звуки ровно ничего не означают (если, конечно, речь не идет о воинственных кличах ). Элементом словаря (предметной области, человеческой деятельности, человеческой жизни вообще) является не звук, а слово. Именно из слов состоит наша речь, и тот факт, что для передачи слов мы их расчленяем на звуки — это лишь исторически и биологически так сложилось. Если бы мы слова произносили не голосом, а как-то иначе — возможно, никаких звуков бы и не было.
Кстати, в китайском именно слова передаются (если считать, что один иероглиф — одно слово, что вроде не совсем верно).
Пока не было компьютеров — буквенное письмо безусловно удобнее иероглифического (словного). А вот с компьютерами — как бы не наоборот.
Давайте до абсурда доведем.
Компьютеры стали разумными и обмениваются друг с другом сообщениями. Но до того, как они стали разумными, им Создатель предписал обмениваться сообщениями исключительно фиксированной длины , скажем, в 64 байта. При том, что разных сообщений может быть не более 65 тысяч. Странный какой-то Создатель, но вот такой он. И это для разумных компьютеров табу, нарушать его они никак не могут.
Вот они и гоняют эти 64-байтные датаграммы по сети. Пока не находится один компьютер, который говорит — а за каким богом мы это все делаем ? Разных датаграмм всего 65 тысяч, давайте просто номера их передавать будем, их можно в 64-байтную датаграмму аж 32 штуки заслать. А набор пронумерованных датаграмм у каждого пусть будет, это же константа.
Вот и вся идея.
With best regards
Pavel Dvorkin
Re: Кодирование слов при передаче по сети (покритикуйте идею
Алгоритмы компрессии иногда позволяют задавать входящий словарь.
То есть что они делают? Находят повторяющееся сочетание байт, заменяют его некой последовательностью бит (то есть дают ему "номер") и дальше вставляют эту последовательность бит, вместо найденной повторяемой последовательности байт.
Обычно, словарь изначально пуст, то есть нет последовательности байт закодированных потоком бит.
Но можно перед компрессией (и соответственно декомпрессией) задавать этот словарь.
Главное, чтоб и компрессор и декомпрессор подставили один и тот-же.
Собственно, твоя идея к заданию некоего фиксированного предварительного словаря и сводится.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Читайте внимательно. Про английский там сказано. Что же касается текстов на смеси русского, хинди и арабского — покажите мне такую страницу
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, Pavel Dvorkin.
DM>Вашу идею активно развивали еще в 1986 году (см. A locally adaptive data compression scheme — Bentley, Sleator et al. — 1986). DM>Кучу работ можете найти по ключевым словам Word-Based Text Compression. DM>А в оригинальном виде она наверняка была описана еще во времена римской империи.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А предстваь себе, что в русском (или ином) языке средняя длина слова — 12 символов. При том же лексиконе. Тогда суммарная длина будет 12N (24N) байт при том. что передается та же информация.
PD>Ты уверен, что gzip сожмет этот массив удвоенной длины до того же размера, что и одинарной длины ? Сомневаюсь.
А ты проверь. Фактически то, что делаешь ты приводит к тому, что в тексте уменьгается кол-во повторяющихся блоков больщой длины. Такой текст архивировать должно быть сложнее.
Так вполне может оказаться, что результат работы gzip-а над исходным текстом будет лцчше, если этот текст предварительно обработать твоим алгоритмом.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[3]: ...о гонах, в смысле подробности не пропускай, да?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Читай внимательно исходный постинг. Все слова считаются различными, если они отличаются хоть одной буквой. Формы склонений — различные слова, так что для каждого существительного будет в лексиконе от 1 до 6 слов.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
M>>Сколько точно — хз Если мы будем только формы глагола считать, не ударясь в причастия и деепричастия E>Обычно причастия и деепричастия в русской морфологии считаются формами глагола. Ещё можно возвратные формы включать или не включать в парадигму, кстати...
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Но я готовлю программистов. Не научных сотрудников, а просто программистов.
Как говорится — делай хорошо, а плохо оно само получится.
Обучение науке на программистском вузе/потоке — это в первую очередь разработка алгоритмов, изучение непонятной проблемной области, и построение модели ее решения. А это в последующей "программистской деятельности" пригодится очень много раз.
Я вот никакой хоть сколько то приличной научной работы написать не смог, и все равно считаю, что не зря меня на факультете учили заниматься наукой и преподавали математику и общие основы программирования, а не "то, что потребуется в реальной работе". То, что требуется в реальной работе — меняется постоянно, а необходимость решать проблемы — остается постоянно.
Re[13]: Кодирование слов при передаче по сети (покритикуйте
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>>>Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований:
G>>Насколько я припоминаю, дипломная работа, как любая научная работа, начинается с очень интересной вводной части. В которой пишут историю проблемы, что было сделано уже в этой области, и после этого делается плавный переход к постановке решаемой проблемы.
LCR>Совершенно верно. Заметь, я утверждаю то же самое.
Извини, не заметил. Если бы кто-то удосужился написать или хотя бы вообразить эту вводную часть, то дойдя до алгоритмов LZ стало бы понятно, что никаких предпосылок для дальнейшей работы, которую вы здесь обсуждаете, нет. Сама формулировка обсуждаемой здесь задачи обусловлена тем, что знания человека, ее формулирующего, в области алгоритмов компрессии измеряются скорее отрицательной величиной, чем положительной. Извини, я просто называю вещи своими именами. Все знать невозможно, и иногда, вместо того, чтобы упираться, надо признать что слегонца облажался, тем более что ничего стыдного тут нет. А Дворкин упираться начал. Позор, уважаемый коллега.
G>>Эту работы зарезал бы еще рецензент, уважаемый коллега. А если каким-то чудом рецензент бы (не глядя) то подписал, то потом научного руководителя распяли бы на доске. К сожалению. На ВМиК МГУ, выпускником которого является D.Mon, за такую работу человек с высокой определенностью получит неуд.
LCR>Хотя в оригинале речь шла про курсовую, про диплом тоже можно кое-что сказать.
Разница не такая принципиальная, сам понимаешь. Курсовые работы третьего курса готовят человека к диплому. Не надо давать человеку вместо темы дерьмо, если это курсовая. Это не оправдание.
LCR>Вероятно, твоё воображение нарисовало такую паршивенькую работёнку, настолько жалкую и ничтожную, что даже о ней и упоминать неприлично. Хе. Её в ОмГУ тоже не допустили бы до защиты.
К сожалению, эту паршивенькую работенку нарисовало и в красках описало здесь воображение Дворкина.
LCR>Моё же воображение рисует полноценное ислледование в вышеуказанных направлениях и построение алгоритма, который бъёт максимальный рар на русскоязычных текстах. Такую работу в ОмГУ определённо до защиты допустят.
LCR>Так мы о какой работе говорим?
Мы говорим о той работе, тему которой довольно точно и недвусмысленно сформулировал Дворкин в своем посте, а не о тех работах, которые рисует твое воображение. Извини.
Re[4]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, VladD2, Вы писали:
VD>В прочем, с удовольствием послушал бы его мнение о качестве обучения (у вас) в общем, и о тебе в частности.
Я не тот студент, но тоже закончил один из омских Вузов.
Несколько лет назад был на одной омской вузовской конференции. Там один из преподавателей открыто сказал — "у нас работают кадры 3-го сорта". Все немного покривились... но вообщем согласились. ИМХО сравнивать московские и омские ВУЗы впринципе некорректно. Совсем другое финансирование, другие люди, другие цели. Преподаватель, который вел у нас один из предметов, после обеда торговал хлебом в магазине, хотя "это были девяностые" — возможно сейчас стало шибко лучше. Из всех моих преподавателей, с благодарностью могу лишь вспомнить моего дипломного руководителя — который освободил меня от пары никому не нужных предметов, и дал мне заниматься тем, чем мне было интересно заниматься. В целом, гениев из идиотов в омских вузах не производят, но и идиотов из гениев тоже не делают, что уже само посебе неплохо.
Сам у Павла учиться не имел чести, но отзывы о нем тех моих знакомых, кто у него учился — сугубо положительные, как об одном из лучших преподавателей. Вспоминая некоторых гоблинов, которые у нас преподавали — я этому верю. Вот, яндекс даже выдал его фан сайт
Здравствуйте, Mamut, Вы писали:
M>Сколько точно — хз Если мы будем только формы глагола считать, не ударясь в причастия и деепричастия
Обычно причастия и деепричастия в русской морфологии считаются формами глагола. Ещё можно возвратные формы включать или не включать в парадигму, кстати...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re: Кодирование слов при передаче по сети (покритикуйте идею
ввообще это частный случай инвертированного индекса или файла http://en.wikipedia.org/wiki/Inverted_index
активно применяется при построении индекса, используется скорее всего во всех поисковых системах.
Здравствуйте, Erop, Вы писали:
PD>>Кстати, у идеи есть вариация. Пока что были два варианта — буквы и слова. Есть третий — слоги. Но оценить число слогов в русском языке я не берусь даже приблизительно, да и как их раздобыть — тоже.
E>Ещё можно морфемы нумеровать, кстати... :shuffle:
У кого-то из советских лингвистов был такой пример. В начале лекции от всех потребовали запомнить фразу, но ни в коем случае не записывать её. Далее была насыщенная материалом лекция, в конце всех попросили записать запомненную фразу на отдельных листочках и посмотрели, что запомнено:) Фраза была такая: "Третьего дня здесь приземлился аэроплан". Большинство слушателей записали: "Позавчера здесь сел самолёт".
Если сжатие с потерями и осмысленно, то примерно в этом духе: отсекать вариации смысла, сводить синонимы к одному значению, устранять все красоты слога и сводить к голой фактологии.
Кстати, у Агаты Кристи есть великолепный пример, как такое "сжатие с потерями" приводит к искажению там, где смысл не был понят. В рассказе из серии про мисс Марпл кухарка восстанавливает последние слова убитого как "выпила рыба" (в русском переводе), и почти чудом Марпл восстанавливает, что он говорил "пилокарпин" (противоядие против атропина, которое помогло бы ему, если бы его сразу дать).
The God is real, unless declared integer.
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.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>... PD>Вот и вся идея.
В принципе разумно. И никто не мешает после сжать получившийся набор чисел тем же zip'ом или закодировать по Хаффману.
Только стоит ли оно усилий? Наверняка объём передачи текста по сети по сравнению с видео в сотни раз меньше (а то и больше). Можно было бы для поиска использовать — но врядли будет намного быстрей хорошей хеш-таблицы.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Я не ответил вчера, хотел подумать.
А можно было просто провести натурные эксперименты. Для языков с алфавитной письменностью современные архиваторы упаковывают со степенью 1,5-2,5 байт на исходное слово. Это вместе со словарем. Это при полнейшей независимости от конкретного языка и почти полной независимости от какой угодно их смеси на одной странице. Ну и зачем нам неуниверсальный, одноязыковой по сути, зависимый от внешнего словаря метод с гарантированно худшими параметрами (гарантированно — потому что при 2х-байтной кодировке у тебя неохваченных словарем вставок будет мама-не-горюй. Ты даже про знаки препинания не вспомнил).
Единственное, где твой метод может обогнать существующие на практике — это очень короткие одноязычные тексты. Ну и оно надо?
PD>А предстваь себе, что в русском (или ином) языке средняя длина слова — 12 символов. При том же лексиконе. Тогда суммарная длина будет 12N (24N) байт при том. что передается та же информация. PD>Ты уверен, что gzip сожмет этот массив удвоенной длины до того же размера, что и одинарной длины ? Сомневаюсь.
Не сомневайся. Языки не терпят сверх-избыточности, и на практике большая длина слова будет скомпенсирована меньшим количеством возможных комбинаций звуков и меньшим количеством самих слов во фразе. Естественно, не с точностью до процента или даже двадцати, но принципиально "выпирающей" избыточности не будет.
Все, что здесь сказано, может и будет использоваться против меня.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Жду комментариев.
1) Нифига не ждёшь. Тебе дело говорят и на литературу ссылаются, а ты в ответ гонишь.
2) IMHO такой подход мог бы быть эффективен в чём-то вроде SMS, только мало кто, кроме маньячных пользователей, заинтересован экономить SMS трафик. Так что можно попробовать написать плагинчик для смартфонов, который эксплуатирует такие идеи. Может и пригодиться идея... Правда она не нова. Даже моя, с плагинчиком к телефончикам тоже, AFAIK, не нова...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор. PD>Жду комментариев.
В любом тексте большинство слов встречаются не в начальной форме, а в различных падежах, склонениях, времени и т.п., а для корректного кодирования/раскодирования нужно будет это учитывать (например — отдельно кодировать приставку, корень, суффикс, окончание). Кроме того, в Русском языке очень много исключений и есть такие интересные особенности как, как чередующиеся и пропадающие буквы в корне в разных словоформах (например — корни прыг/прыж, глас/голос). Учёт всех особенностей языка сделает этот способ не выгодным, по сравнению с обычными алгоритмами кодирования. Но, возможно, для искусственных языков (таких, как эсперанто) такой способ кодирования будет удобным.
Re[5]: ...о гонах, в смысле подробности не пропускай, да?
Здравствуйте, Mamut, Вы писали:
M>кстати, это в руском все так радужно. а для языков типа турецокго такое не пройдет
... M>а еще есть глаголы в нескольких временах и т.п. и т.д.
Да ладно, как ты думаешь сколько форм у какого-нибудь заволящего русского глагола?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А насчет архиваторов — да я их и не отменяю. Никто не мешает их применить после.
Смысл?
PD> ИМХО русский язык с формальной точки зрения весьма избыточен.
Смотря что считать "весьма". Естественно, речь обладает избыточностью, иначе о сжатии текста и речи бы не было. Но я говорил о том, что эта избыточность для разных языков более-менее одного порядка, даже если достигается различными способами. Архиватору все равно, достигается ли образование грамматической формы одним суффиксом или тремя — важно, сколько разных грамматических форм встретится в тексте; обозначается родительный падеж аффиксом, увеличивающим длину слова, или предлогом, увеличивающим количество слов. Например, типичный художественный текст на русском языке длиннее соответствующего английского — но за счет большей длины слова, а количество слов при этом в тексте меньше и т.п. Упаковав же эти тексты, мы получим, что русский вариант лишь немного длинее английского, увеличение не будет соответствовать разнице в длине слов.
PD> Надо проверять в натуре.
Ну так за чем дело встало, если на ГЭК больше делать нечего ?
Все, что здесь сказано, может и будет использоваться против меня.
А зачем слова заменять? Можно ведь заменять целые предложения. Используя четырехбайтное кодирование можно в словаре иметь четыре миллиарда различных предложений. А то что не заменяется передавать как есть.
gandjustas wrote:
> А зачем слова заменять? Можно ведь заменять целые предложения. Используя > четырехбайтное кодирование можно в словаре иметь четыре миллиарда > различных предложений. А то что не заменяется передавать как есть.
Разовьём идею дальше. Я уверен, что во всём мире существует не более 8^1024 текстов (и ещё на долго хватит). А значит _любой_ текст, любой длины можно ужать в 1кб!
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, Pavel Dvorkin.
DM>Чем разводить флейм, проще взять и посмотреть.
DM>Вот он, готовый Компрессор имени Павла Дворкина:
увы. руби у меня нет, так что проверить не могу.
DM>Вывод: как самостоятельный метод сжатия никуда не годится, а как препроцессор для дальнейшего сжатия — сойдет. Собственно, такие препроцессоры применяются в компрессорах уже десятки лет.
Для того, чтобы такой вывод сделать, надо написать программу длиной в 0 строк. Потому что здесь никакой программы вообще не надо. Тут арифметика на уровне первого класса.
Примем коэффициент архивации текста RAR как 3. Это примерное значение, конечно, но более или менее верное.
Если средняя длина слова 6 , то мы имеем примерно 6/3 == 2 после архивации. И у меня тоже 2 на слово. Все.
DM>А вот если сжатый двухбайтными кодами файл еще зазиповать, то получается уже 7316 байт (30%).
А вот тут самое интересное в твоем постинге. Прочти еще раз мое исходное сообщение. Я там про архивацию ни слова не писал. Я сказал, что ДБК будет в 3 раза короче исходного текста. Здесь опять-таки арифметика первого класса
6(длина слова) / 2 (размер ДБК) == 3.
Ну а мне в ответ — можно архивировать. Можно, не спорю. Но если вы (не ты лично) хотите архивировать исходный текст — дайте и мне право архивировать ДБК. А то иначе получается, что я вроде бы утверждаю, что я новый алгоритм архивации изобрел. Перечти мои постинги — где я такое сказал ?
И то, что в результате получается в 1.5 раза лучше, чем зипом и в 1.25 лучше, чем раром в лучшем его режиме — кое о чем говорит.
Так что спасибо за исследование.
DM>Полная реализация компрессора и декомпрессора заняла по 8 строк кода. DM>Если такую задачу готовы дать в качестве курсовой, это много говорит о Омском "университете" и его преподавателях.
Этот выпад оставлю на твоей совести. Отмечу только, что я собирался дать именно реальную задачу, с настоящим словарем. Это немного иная ситуация, чем брать слова из данного текста и кодировать. Для 3 курса вполне нормальная задача, я считаю.
With best regards
Pavel Dvorkin
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну а мне в ответ — можно архивировать. Можно, не спорю. Но если вы (не ты лично) хотите архивировать исходный текст — дайте и мне право архивировать ДБК. А то иначе получается, что я вроде бы утверждаю, что я новый алгоритм архивации изобрел. Перечти мои постинги — где я такое сказал ?
А так что ты изобрел? Я вот так и не понял. Ну кодируешь ты текст цифрами, а зачем? Передавать по сети — для этого есть кодировки по буквам. Чем твой вариант лучше? Позволяет иметь меньший объем для передачи данных? Ну так это и есть архивация по сути своей.
Или главное не уменьшение размера? А что тогда?
Только не надо рассказывать страшные сказки про детей, которых злой создатель не научил читать и говорить, но дал компьютер с ограниченным числом картинок, каждая из которых описывает 200 слов по 3000 букв в каждом слове. Абстрактных ситуаций придумать можно много. Вопрос в практическом применении.
PD>И то, что в результате получается в 1.5 раза лучше, чем зипом и в 1.25 лучше, чем раром в лучшем его режиме — кое о чем говорит.
Да чем же он лучше? Лучше только опять же после прохода того же зипа или рара. И при этом, что характерно, в примере используется словарь, который строится из данного же текста. Когда будет один общий словарь и натравливаться будет на другой текст — эффект будет хуже. Хотя бы из-за некодируемых последовательностей и префиксов-суффиксов смены режима.
PD>Этот выпад оставлю на твоей совести. Отмечу только, что я собирался дать именно реальную задачу, с настоящим словарем. Это немного иная ситуация, чем брать слова из данного текста и кодировать. Для 3 курса вполне нормальная задача, я считаю.
Это та же самая задача, просто разбитая на две части — отдельно вырезано построение словаря, который наполняется предварительно на некоторых текстах, и отдельно уже идет архивация других текстов, не использовавшихся при построении словаря.
Здравствуйте, gandjustas, Вы писали:
G>А зачем слова заменять? Можно ведь заменять целые предложения. Используя четырехбайтное кодирование можно в словаре иметь четыре миллиарда различных предложений. А то что не заменяется передавать как есть.
Это безграмотно! То что не заменяется надо отбрасывать. Jpeg же отбрасывает ненужные детали изображения?!
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, D. Mon, Вы писали:
DM>А медаль "лучшему бетоноукладчику" не показать?
Такие аргументы обычно приводят, когда более серьезных нет.
>Сама постановка вопроса уже выдает Вас с головой. DM>Пример, который Вы привели и просите у меня, — это результат добротной инженерной работы: ноль науки, зато много вероятно неплохого кодинга. Это отличный результат для трехмесячных курсов программирования ("освой MFC за 12 уроков") или даже для профессионального училища (ПТУ).
Прекрасная идея! Предлагаю автору приступить к ее реализации. Схема такая — идешь в ближайшее подходящее ПТУ (или курсы), набираешь там человек 15-20, даешь им задания, и через 3 месяца мы имеем с десяток программ , выполненных на уровне мировых стандартов, которые PC Magazine тут же немедленно прореферирует и будет рекомендовать всем, кто этот журнал читает. Дальше, конечно, найдутся последователи, и через пару лет мы закидаем весь мир высококачественным ПО на самую различную тематику, так что PC Magazine и др. журналы будут не успевать их рецензировать!
>В университете дипломные работы обычно совсем другие — они должны содержать хоть сколько-то науки, изобретать что-то новое, содержать какие-то нетривиальные идеи.
Если речь идет о студентах, которые действительно имеют своей целью работать в науке, идти после вуза в аспирантуру, то ты прав — их дипломная работа должна продемонстрировать, что они к такой деятельности способны.
Но я готовлю программистов. Не научных сотрудников, а просто программистов. И студенты мои ориентированы именно на программистскую карьеру, а отнюдь не на научную. И вот здесь идея о том, что они обязательно должны на дипломе заниматься тем, что им больше никогда не придется делать, мне кажется совершенно неверной. Пусть они лучше научатся как следует делать то, чем им придется потом заниматься.
А иначе интересный эффект может получиться. Потребуем от всех студентов, чтобы они, по твоей рекомендации, на дипломе занимались научной работой. Но дипломирование через полгода закончится, и... куда их теперь ? Всех в науку ? Там мест такого количества нет, да и не надо, да и не хотят они. Все же в программисты пойдут ? Но там им мощную конкуренцию составят выпускники трехмесячных курсов программирования ("освой MFC за 12 уроков") и профессиональных училищ (ПТУ), которые за то же время напишут программы мирового класса, как ты обещал. . Они пожалуй, и нынешних программистов всех вытеснят...
Да... До чего не дойдешь, если поставить перед собой задачу во что бы то доказать свою правоту. Несмотря ни и невзирая на.
DM>Если немного вернуться к теме компрессии, которую тут обсуждали. DM>У нас на факультете есть спецкурс (т.е. даже не основной предмет), в рамках которого студенты выполняют ряд интересных заданий, в том числе написание универсального компрессора — на это задание дается 2-3 недели (в Вашем вузе за это академика бы давали, похоже).
Ну никак не может дойти до тебя (и до других тоже, увы), что я вовсе не тему компрессии предложил обсуждать!
DM>А вот пример решения такого задания (написанный за пару недель), который сжимал в среднем лучше, чем тогдашний rar:
И не сжатия! А иного представления входных данных!
With best regards
Pavel Dvorkin
Re[7]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Но я готовлю программистов. Не научных сотрудников, а просто программистов. И студенты мои ориентированы именно на программистскую карьеру, а отнюдь не на научную. И вот здесь идея о том, что они обязательно должны на дипломе заниматься тем, что им больше никогда не придется делать, мне кажется совершенно неверной. Пусть они лучше научатся как следует делать то, чем им придется потом заниматься.
Собственно, примерно это я и понял о Вашем вузе и его преподавателях. Такие училища стране тоже нужны.
PD>А иначе интересный эффект может получиться. Потребуем от всех студентов, чтобы они, по твоей рекомендации, на дипломе занимались научной работой. Но дипломирование через полгода закончится, и... куда их теперь ? Всех в науку ?
Главное, чтобы научились думать и учиться (и правильный диплом должен этому способствовать, и даже требовать). Тогда можно и в борщ, и в красную армию, тьфу, т.е. и в науку, и в индустрию. А вот если научились только конкретный инструмент использовать, то им уже сложнее придется.
PD>Да... До чего не дойдешь, если поставить перед собой задачу во что бы то доказать свою правоту. Несмотря ни и невзирая на.
Вы очень самокритичны, это хорошо.
PD>Ну никак не может дойти до тебя (и до других тоже, увы), что я вовсе не тему компрессии предложил обсуждать!
Ну, раз мне и другим это было столь неочевидно, значит так хорошо объяснили.
Я в первом посте увидел два аспекта идеи:
1. Экономия места/трафика (т.е. все же компрессия). Этот вопрос был позднее разобран, идея не выдержала критики, а автор оказался не знаком ни с азами теории информации (работами Шеннона и Колмогорова), ни с арифметикой. И учиться тоже не хочет, похоже.
2. Независимость от кодировки текста. Это идея не рабочая, т.к. там же было предложено не входящие в словарь слова посылать как есть, т.е. все равно в некоторой кодировке.
Re[13]: Кодирование слов при передаче по сети (покритикуйте
Здравствуйте, Pavel Dvorkin, Вы писали:
G>>Насколько я припоминаю, дипломная работа, как любая научная работа, начинается с очень интересной вводной части. В которой пишут историю проблемы, что было сделано уже в этой области, и после этого делается плавный переход к постановке решаемой проблемы.
PD>А может, все же не стоит путать дипломную работу с курсовой на 3 курсе ? Где я говорил, что это тема для дипломной работы ? Такое передергивание не очень солидно. Некрасиво, проще сказать.
Можно подумать, это все меняет. Что, если это курсовая третьего курса, то значит ты можешь ему такие темы подсовывать не думая, да? Это тебя оправдывает как-то? Ты блин даже comp.compression FAQ почитать не удосужился. И еще споришь. Несолидно так вести себя сотруднику университета, вот что я тебе скажу. Ты позоришь свой ВУЗ.
Здравствуйте, 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: Кодирование слов при передаче по сети (покритикуйте идею
Вашу идею активно развивали еще в 1986 году (см. A locally adaptive data compression scheme — Bentley, Sleator et al. — 1986).
Кучу работ можете найти по ключевым словам Word-Based Text Compression.
А в оригинальном виде она наверняка была описана еще во времена римской империи.
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>В HTML , e-mail и т.д. пересылается текст на русском языке. Этот текст пересылается как набор номеров букв. На букву — один байт (или 2, если юникод). PD>А что, если вместо этого пронумеровать слова русского языка и пересылать их номера ? Конечно, для этого на сервере должен быть шифрующий модуль и словарь, а на клиенте — тот же словарь и дешифратор.
Идея не новая. У автора ARJ был следующий архиватор JAR (не путать с явовским суффиксом файлов), в котором был словарь английского и подстановка номера слова при сжатии. Я его видел в районе 95-го, но он страшно жрал память и диск, и что-то с реализацией не сложилось. Но примерно тогда же начал кончаться и ARJ.
The God is real, unless declared integer.
Re: Кодирование слов при передаче по сети (покритикуйте идею
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Жду комментариев.
обычные алгоритмы сжатия типа LZ примерно так и работают. они выделяют встречающиеся подстроки, строят по ним словарь и передают вместо подстрок индексы. подстрока — просто последовательный кусок текста. может включать и несколько обычных слов.
алгоритм эффективней вашего вот почему
1. кодируются только строки встречающиеся в файле. обьем составляемого словаря много меньше вашего — универсального. таким образом индексы подстрок будут меньше. словари всегда "адаптированы" под данный файл. а не являются словарями какоего-то общего языка. в алгоритме lZ словарь не передается, а хитрым образом составляется так, что восстанавливается при разжатии из самого сжатого потока. насколько я помню, детали немного забыл.
2. алгоритм универсальный и жмет произвольные файлы.
3. строка может сожержать несколько обычных слов, чего нет у вас. и кодироваться всего байтом.
у вашего алгоритма совершенно нет шансов. даже в простешем базовом варианте LZ и вашего алгоритма, ваш проигрыш в среднем будет в 2-3 раза.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
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. там как раз делается анализ частоты встречаемости.
Здравствуйте, VUspenskiy, Вы писали:
VU>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Читайте внимательно. Про английский там сказано. Что же касается текстов на смеси русского, хинди и арабского — покажите мне такую страницу
VU>http://ka.wikipedia.org/wiki/????
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Единственное слово на русском языке не считается куском русского текста. Таких страниц можно найти миллион. Навярняка многие страницы про Будду на русском языке содержат сноски на написание его имени и на многих языках. Ну, так это ж редкое исключение, которое на общее сжатие не влияет и кодируется, как есть, — без сжатия.
Здравствуйте, 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]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, 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 тысяч. Тоже сожмешь до того же размера, что и русский текс ?
With best regards
Pavel Dvorkin
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, L.Long, Вы писали:
LL>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Жду комментариев.
LL>Вообще говоря, давным-давно уже была высказана идея нумеровать анекдоты для удобства рассказывания. Это более высокоуровневый подход, имхо.
Шутки шутками, но читал я однажды какую-то статью о средневековом эпосе, то ли Калевала, то ли Старшая Эдда. Сам эпос я не читал (не осилил), так что за выводы не ручаюсь.
Так вот, там утверждалось, что в этом эпосе иногда просто перечислялись герои. Для нас такое перечисление ничего не говорит. А для средневекового слушателя одно упоминание имени героя вызывало соответствующую ассоциацию. По сути, упоминание имени представляло собой рассказ в одном слове.
With best regards
Pavel Dvorkin
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Pavel Dvorkin, Вы писали: PD>>Жду комментариев.
MC>Как Вам уже сказали, идея не нова. ИМХО, тут надо двигаться, в ту же сторону, что и при сжатии звука и изображений — в сторону сжатия с потерями.
Хм, а как же с потерями ? Это же не картинка, где если в одном пикселе вместо истинного RGB(100,134,156) будет RGB(100,135,156) — никто и не заметит. Текст должен воспроизводиться точно.
With best regards
Pavel Dvorkin
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, andy1618, Вы писали:
A>>>3-6 раз для текста — это дело обычное: A>>>http://www.maximumcompression.com/data/text.php (лидеры умудряются сжимать в 9 раз)
N>>Что-то архиватор по имени "Дурилка 0.5" вызывает у меня сомнение.
A>Блин, точно! 5-м номером идёт! Может, специально под этот тестовый файл написали?
Оказывается, DURILCA — Dirty Useless Really ILlusory Compressor/Archiver
Вот страничка автора на compression.ru (Дмитрий Шкарин): http://www.compression.ru/ds/
Идея, пусть и не оригинальная, но, безусловно, работоспособная.
Можно дать её в качестве задания студентам — пусть потягаются с общеизвестными архиваторами.
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, ZayatsZ, Вы писали:
ZZ>Тоже уже было такое. Например, в древнем финикийском письме при записи гласные опускались, оставлялись только согласные.
И в иврите сейчас так. Но! Всегда имеется однозначное восстановление гласных. Это не потери, а точный способ кодирования при том, что не все звуки записываются.
Кстати, аналог на русском — сокращения слов. Если сокращать так, чтобы неоднозначностей не возникало — вполне годится.
Здравствуйте, andy1618, Вы писали:
PD>>Вот и вся идея.
A>Идея, пусть и не оригинальная, но, безусловно, работоспособная. A>Можно дать её в качестве задания студентам — пусть потягаются с общеизвестными архиваторами.
Может и попробую.
Кстати, у идеи есть вариация. Пока что были два варианта — буквы и слова. Есть третий — слоги. Но оценить число слогов в русском языке я не берусь даже приблизительно, да и как их раздобыть — тоже.
With best regards
Pavel Dvorkin
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Только подумай как следует. А если слова не 12, а 100 байт длину имеют, при том, что различных слов всего 100 тысяч. Тоже сожмешь до того же размера, что и русский текс ?
Длинный текст даже лучше сожмёт...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Alex Reyst, Вы писали:
AR>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Я не ответил вчера, хотел подумать.
AR>А можно было просто провести натурные эксперименты. Для языков с алфавитной письменностью современные архиваторы упаковывают со степенью 1,5-2,5 байт на исходное слово. Это вместе со словарем. Это при полнейшей независимости от конкретного языка и почти полной независимости от какой угодно их смеси на одной странице. Ну и зачем нам неуниверсальный, одноязыковой по сути, зависимый от внешнего словаря метод с гарантированно худшими параметрами (гарантированно — потому что при 2х-байтной кодировке у тебя неохваченных словарем вставок будет мама-не-горюй. Ты даже про знаки препинания не вспомнил).
Про знаки препинания я не забыл, и что за проблема с ними, если их всего с десяток, и вполне их можно словом считать. Встречаются они — один на тридцать-сорок букв.
А насчет архиваторов — да я их и не отменяю. Никто не мешает их применить после.
С одним согласен. Надо проверять в натуре.
AR>Не сомневайся. Языки не терпят сверх-избыточности
Я не сомневаюсь в том, что твои познания в лингвистике намного лучше моих , но вот это утверждение просил бы аргументировать. ИМХО русский язык с формальной точки зрения весьма избыточен. При 32 буквах мы могли бы иметь миллион 4-буквенных слов. Звуки не позволяют, не произнесешь. Склонения и спряжения имеют свои правила. И т.д.
With best regards
Pavel Dvorkin
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Хм, а как же с потерями ? Это же не картинка, где если в одном пикселе вместо истинного RGB(100,134,156) будет RGB(100,135,156) — никто и не заметит. Текст должен воспроизводиться точно.
Например, при сжатии, можно исправлять орфографические ошибки...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Кстати, у идеи есть вариация. Пока что были два варианта — буквы и слова. Есть третий — слоги. Но оценить число слогов в русском языке я не берусь даже приблизительно, да и как их раздобыть — тоже.
Ещё можно морфемы нумеровать, кстати...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
1) Ты вроде место в канале передачи экономить хотел? Или что?
2) Ты не понимаешь, как и почему устроены естественные языки, например русский. Поэтому тебе и кажется, что придумал супер-пупер идею. Просто попробуй свою идею реализовать и всё поймёшь...
Словарь можно скачать из интернета, прямо вот с частотностями. Например качни какой-нибудь большой графоманский сайт, построй по нему словарь и попробуй этот сайт пережать этим словарём. Это будет завышенная оценка эффективности твоей технологии. Ну и сравни с промышленными архиваторами, если тутошнему народу не веришь...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, Pavel Dvorkin, Вы писали:
L>А ты проверь. Фактически то, что делаешь ты приводит к тому, что в тексте уменьгается кол-во повторяющихся блоков больщой длины. Такой текст архивировать должно быть сложнее. L>Так вполне может оказаться, что результат работы gzip-а над исходным текстом будет лцчше, если этот текст предварительно обработать твоим алгоритмом.
Может, ты и прав. Проверять надо.
И все же — можешь ответить на мое доведение до абсурда вот здесь ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, D. Mon, Вы писали:
DM>>Здравствуйте, Pavel Dvorkin.
DM>>Вашу идею активно развивали еще в 1986 году (см. A locally adaptive data compression scheme — Bentley, Sleator et al. — 1986). DM>>Кучу работ можете найти по ключевым словам Word-Based Text Compression. DM>>А в оригинальном виде она наверняка была описана еще во времена римской империи.
PD>Не сомневаюсь. Но вот реализаций не вижу.
Реализации есть. Можно даже про идею статического препроцессинга (так называется исходная идея) почитать на русском здесь (882К) Глава 7. Предварительная обработка данных
You aren't expected to absorb this
Re[4]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Хм, а как же с потерями ? Это же не картинка, где если в одном пикселе вместо истинного RGB(100,134,156) будет RGB(100,135,156) — никто и не заметит. Текст должен воспроизводиться точно.
E>Например, при сжатии, можно исправлять орфографические ошибки...
Черт знает. Так и до полного искажения смысла недалеко. Если встречаем неопознанное слово, то его надо на что-то заменить. Хорошо, как правильно, а ну как нет ? Ты же фактически автоматическое исправление ошибок предлагаешь
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>P.S. Сжатие данных тут ни при чем. Речь о совсем другом идет. Прочти вот это PD>>http://rsdn.ru/forum/message/2999825.1.aspx
E>1) Ты вроде место в канале передачи экономить хотел? Или что? E>2) Ты не понимаешь, как и почему устроены естественные языки, например русский.
Это уж точно. А как они устроены, если не секрет ? А главное — почему ? И еще один вопрос добавлю — а все ли одинаково ? И если нет — почему ?
>Поэтому тебе и кажется, что придумал супер-пупер идею.
Да нет, я на такое не претендую. Просто интересно, есть ли тут рациональное зерно. Я же и просил критику изначально.
>Просто попробуй свою идею реализовать и всё поймёшь...
Да, это самое лучшее. Дам кому-нибудь в качестве курсовой
E>Словарь можно скачать из интернета, прямо вот с частотностями. Например качни какой-нибудь большой графоманский сайт, построй по нему словарь и попробуй этот сайт пережать этим словарём. Это будет завышенная оценка эффективности твоей технологии. Ну и сравни с промышленными архиваторами, если тутошнему народу не веришь...
Можно и так.
With best regards
Pavel Dvorkin
Re[5]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Черт знает. Так и до полного искажения смысла недалеко. Если встречаем неопознанное слово, то его надо на что-то заменить. Хорошо, как правильно, а ну как нет ? Ты же фактически автоматическое исправление ошибок предлагаешь
Нет, я просто привёл вариант потери информации из исходного текста, которая могла бы быть приемлемой...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Это уж точно. А как они устроены, если не секрет ? А главное — почему ? И еще один вопрос добавлю — а все ли одинаково ? И если нет — почему ?
Ну есть естественные механизмы, которые ограничивают степень избыточности языка сверху и снизу. Сверху избыточность ограничивает стремление людей к лаконичности, так как передавать информацию быстро эффективнее, то есть практически выгоднее. Снизу избыточность ограниченна помехоустойчивостью. Так как обычно помехоустойчивость важнее лаконичности. Соотвественно у разных народов немного разная жизнь, поэтому баланс этих двух причин в разных языках был разным и степень избыточности получилась разной. Но всё равно примерно одинаковой. Мало того, избыточность естественных языков имеет несколько другую структуру, чем ты думаешь, так скажем.
Реально кодирование устроено не словами, а более локально. Чем-то вроде слогов/морфем. Во многих языках, кстати, понятия слогов и морфем совпадают. Если говорить о русском, то, можно привести такой пример. Если взять множество встречающихся в русском триграмм (троек букв идущих подряд), и выработать кодирование так, что бы кодировать только триграммные цепочки, при этом без избыточности, то мы уже отожмём значительную часть избыточности русского языка. Именно поэтому локальные на первый взгляд ужималки так эффективны на естественных языках. Естественным языкам слова вообще пофиг обычно, им важны более короткие цепочки, так что твой подход не годится.
Он годился, если бы русский язык состоял из миллиона 6-7 буквенных случайных цепочек байт. Тогда да, твой алгоритм работал бы суперски эффективно. Но у естественных языков совсем другая структура избыточности. И если ты неудачным предварительным преобразованием эту структуру избыточности не испортишь, то хороший современный промышленный архиватор всю эту избыточность почти полностью "отожмёт".
Такая вот беда.
PD>Можно и так.
Удачи! Правда студента жалко
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[4]: ...о гонах, в смысле подробности не пропускай, да?
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Читай внимательно исходный постинг. Все слова считаются различными, если они отличаются хоть одной буквой. Формы склонений — различные слова, так что для каждого существительного будет в лексиконе от 1 до 6 слов.
E>гон E>гона E>гону E>гоном E>гоне E>гоны E>гонов E>гонам E>гонами E>гонах
кстати, это в руском все так радужно. а для языков типа турецокго такое не пройдет
ev дом evim мой дом evimiz наш дом
evin твой дом eviniz ваш дом
evi его/ее дом evleri их дом
eve к дому
evde в доме evdeyim я в доме evdeyiz мы в доме
evdesin ты в доме evdesiniz вы в доме
evde он/она в доме evdeler они в доме
evimde в моем доме evimdeyim я в моем доме
evimdesin, evimdeyiz, evimdesiniz, evimdeler
evinde в твоем доме evindeyim я в твоем доме
evindesin, evindeyiz, evindesiniz, evindeler
и так далее в нашем, вашем, их доме
evler дома evlerim мои дома
evlerim, evleri, evlerimiz, evleriniz
evlere к домам
evlerde в домах evlerdeyim, evlerdesin.......
evlerimde в моих домах evlerimdeyim, evlerimdesin.........
и так далее для твоих, его, наших, ваших, их домах
evden из дому evimden - из моего дома и т.п. evinden, evimizden, evinizden........
evlerden из домов evlerimden - из моих домов и т.п. evlerinden.....
или вот такое
evdeydim я был дома
evdeydin ты был дома и т.п.
evimdeydim я был у себя дома и т.п.
а еще есть глаголы в нескольких временах и т.п. и т.д.
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Mamut, Вы писали:
M>>кстати, это в руском все так радужно. а для языков типа турецокго такое не пройдет E>... M>>а еще есть глаголы в нескольких временах и т.п. и т.д.
E>Да ладно, как ты думаешь сколько форм у какого-нибудь заволящего русского глагола?
Ну, даже если считать совершенный и несовершенный виды разныими глаголами То тоже наберется порядочно. Но до турецкого далеко Потому что, например:
soylemek — сказать (-mek — это инфинитив)
soyleyecekmissiniz = soyle + (y) + ecek + mis + siniz
Здравствуйте, Mamut, Вы писали:
E>>Да ладно, как ты думаешь сколько форм у какого-нибудь заволящего русского глагола?
M>Ну, даже если считать совершенный и несовершенный виды разныими глаголами То тоже наберется порядочно. Но до турецкого далеко Потому что, например:
Это не ответ на вопрос сколько...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Спасибо. Я Huffman_coding рассказывал студентам еще лет 10 так назад на лекциях.
Если честно — не заметно.
PD>А вот одно ты не понял. Хоть Хаффман, хоть LZH — слова исходного текста (в той или иной форме) в сжатом архиве хранятся. А у меня вообще нет.
И это все отличия? Внешний словарь?
PD>Только подумай как следует. А если слова не 12, а 100 байт длину имеют, при том, что различных слов всего 100 тысяч. Тоже сожмешь до того же размера, что и русский текс ?
Да. Хаффман очень примитивный алгоритм, он предполагает "слова" фиксированного размера. Есть алгоритмы, умеющие находить повторяющриеся блоки значительно большей длины.
... <<RSDN@Home 1.2.0 alpha 4 rev. 1090 on Windows Vista 6.0.6001.65536>>
E>>>Да ладно, как ты думаешь сколько форм у какого-нибудь заволящего русского глагола?
M>>Ну, даже если считать совершенный и несовершенный виды разныими глаголами То тоже наберется порядочно. Но до турецкого далеко Потому что, например:
E>Это не ответ на вопрос сколько...
Ну, даже если считать совершенный и несовершенный виды разныими глаголами То тоже наберется порядочно.
Сколько точно — хз Если мы будем только формы глагола считать, не ударясь в причастия и деепричастия
А говорил, что сжатие текстов с потерями не канает PD>
Но вообще-то глубина анализа поражает. Правда помнится проскакивало амерское же "исследование" на тему о целях эстетического дизайна советских кораблей и связи этого аспекта с военной доктриной СССР
Особенно меня порадовла средняя длина японского слова в 10,8 символов. Интересно, они в курсе, что в японском иногда иероглифы применяются :)))
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Особенно меня порадовла средняя длина японского слова в 10,8 символов. Интересно, они в курсе, что в японском иногда иероглифы применяются :)))
Это проблемы журналиста. В исследовании были, конечно же, звуки — речь же идет об отдаваемых устно командах в случае внезапного боевого столкновения.
AR>>Ну и зачем нам неуниверсальный, одноязыковой по сути, зависимый от внешнего словаря метод с гарантированно худшими параметрами (гарантированно — потому что при 2х-байтной кодировке у тебя неохваченных словарем вставок будет мама-не-горюй. Ты даже про знаки препинания не вспомнил).
PD>Про знаки препинания я не забыл, и что за проблема с ними, если их всего с десяток, и вполне их можно словом считать. Встречаются они — один на тридцать-сорок букв.
Возможно, это, конечно, и так, хотя, вроде, совсем не факт, но, однако, они, "редиски", текст-то мусорят...
При этом есть такой "знак препинания" как пробел. В сумме знаки препинания плюс пробелы встречаются с частотой более чем 1 на слово (иногда идет " — ", или "??? " или "!? — "). Но уж один на каждое слово — точно есть.
Еще можно вспомнить, что иногда слова начинаются с большой буквы. С регулярностью чуть более чем одно на предложение. Кодировать отдельным словом?
Адаптирующийся алгоритм сжатия с собственным словарем на сколь-то приличном тексте обойдет сжималку с фиксированным словарем разумных размеров.
Здравствуйте, fmiracle, Вы писали:
F>Это проблемы журналиста. В исследовании были, конечно же, звуки — речь же идет об отдаваемых устно командах в случае внезапного боевого столкновения.
А почему не время произнесения приказа, например?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, ., Вы писали:
.>Разовьём идею дальше. Я уверен, что во всём мире существует не более 8^1024 текстов (и ещё на долго хватит). А значит _любой_ текст, любой длины можно ужать в 1кб!
Замечательная идея, осталось только словарь составить
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, ZayatsZ, Вы писали: ZZ>Тоже уже было такое. Например, в древнем финикийском письме при записи гласные опускались, оставлялись только согласные.
Нет, это не то.
Сжатие с потерями — идея не новая и в сжатии текста, просто простора для изысканий там больше.
Re[5]: ...о гонах, в смысле подробности не пропускай, да?
Здравствуйте, Mamut, Вы писали:
M>кстати, это в руском все так радужно. а для языков типа турецокго такое не пройдет :)
M> M>ev дом evim мой дом evimiz наш дом
С турецким это и не нужно — там нужно пронумеровать эти суффиксы по роли (к счастью, для подавляющего большинства слов они одинаковы с точностью до ряда гласных, исключений крайне мало и нескольких склонений нет) и, возможно, ещё оптимизировать по структуре предложения. А этот результат уже можно обрабатывать (кодировать, например, статическими деревьями по частоте). На входе нужен только словарь корней.
Здравствуйте, Mamut, Вы писали:
M>>>Как отличить номер слова от переданной в тексте цифры?
PD>>А как отличают в UTF-8 однобайтный символ от двух или трех-байтного ? Примерно так же.
M>Как же? :)
M>вот у нас идет подряд 232, где 2 — это "попытка", 3 — "номер", 2 — "2"
Ну посмотри, как реально устроены архиваторы. Например, у zip deflate и прочих LZ77-based передаётся или цепочка входного текста без изменений, или данные типа "повторим кусок буфера с позиции K длиной N". Но к каждому из этих вариантов идёт префикс, который при соответствующем состоянии парсера однозначно определяет один из этих вариантов.
Так что, условно говоря, будет что-то вроде "R2,3T2". R, T — префиксы.
The God is real, unless declared integer.
Re[4]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
ZZ>>Тоже уже было такое. Например, в древнем финикийском письме при записи гласные опускались, оставлялись только согласные.
PD>И в иврите сейчас так. Но! Всегда имеется однозначное восстановление гласных. Это не потери, а точный способ кодирования при том, что не все звуки записываются.
Таки с потерей. И тогда, и сейчас некоторые детали теряются так, что могут быть вероятно восстановлены по контексту — например, какое время применено — настоящее, прошедшее или будущее. (А ещё есть другие наклонения...) В обычном тексте контекста достаточно, чтобы получить ответ. Но в той же Библии, при крайне туманном стиле выражения во многих случаях, время и наклонение терялись, и современные трактовки весьма произвольны.
Здравствуйте, Ilya10k, Вы писали:
I>Единственное слово на русском языке не считается куском русского текста. Таких страниц можно найти миллион. Навярняка многие страницы про Будду на русском языке содержат сноски на написание его имени и на многих языках. Ну, так это ж редкое исключение, которое на общее сжатие не влияет и кодируется, как есть, — без сжатия.
Итак, религиозные и лингвистические тексты — не сжимаются.
Технические тексты, где наполовину английского и терминов-калек с английского тоже плоховато.
Можно легко только общение в аське кодировать:
Привет, как дела? — 0
Нормально — 10
как обычно — 100
и тд.. — 101..
RO>Поищи на Яндексе по словам «дело рыбака».
А что должно было отыскаться?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, ., Вы писали: .>Разовьём идею дальше. Я уверен, что во всём мире существует не более 8^1024 текстов (и ещё на долго хватит). А значит _любой_ текст, любой длины можно ужать в 1кб!
Я уже как-то предлагал в этом форуме сделать такой хеш-код, чтобы двум сообщениям с одинаковым смыслом сопоставлялось одно 32хбитное число. А разным, естественно — разные числа. Это бы позволило эффективно бороться с баянами.
Предположение о том, что сообщений с различными смыслами больше четырех миллиардов не выдерживает никакой критики — очевидно, что вообще различных сообщений меньше двух миллионов. Поскольку некоторые из них являются баянами (в частности, твое сообщение, на которое я отвечаю), то четырех миллиардов хеш-кодов нам хватит с запасом на много лет вперед.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Очень жаль, что ты не понимаешь сути вещей.
Или ты не понимаешь, о чем я пишу.
PD>>Таким образом, пересылка информации с внешним словарем имеет место гораздо чаще, чем некоторые здесь думают. И вопрос о том, кодировать ли буквы, или слова (а может, слоги, а может, пары букв) — этот вопрос не принципиальный, а технический. S>Это вопрос как раз принципиальный. Потому, что принципиальное отличие букв от слов — в том, что букв гарантированно фиксированное количество, благодаря чему можно, как правило, полагаться на наличие подходящей интерпретации на принимающей стороне.
Пар букв — тоже. Их ну никак не может быть нефиксированное количество . Их 33*33 за вычетом тех комбинаций, которые не встречаются (например, ьь)
Слогов — скорее всего тоже. Тут филологи точнее скажут, сколько их.
Слов — вообще-то тоже. Если словарь составить и зафиксировать его.
Что касается интерпретации на той стороне — зависит от интерпретатора. Если интерпретатор на принимающей стороне будет понимать слова, а не буквы и иметь нужный словарь — все будет в порядке.
А впрочем, зачем я все это доказываю ? Есть же очевидное доказательство — китайский язык. Там иероглифы и есть (примерно) слова. Так что они и передаются. И вполне интерпретируются.
Все остальное сериализовано в Гольфстрим , так как обсуждать твою демагогию и нападки я не хочу.
With best regards
Pavel Dvorkin
Re[6]: ...о гонах, в смысле подробности не пропускай, да?
N>С турецким это и не нужно — там нужно пронумеровать эти суффиксы по роли (к счастью, для подавляющего большинства слов они одинаковы с точностью до ряда гласных, исключений крайне мало и нескольких склонений нет) и, возможно, ещё оптимизировать по структуре предложения. А этот результат уже можно обрабатывать (кодировать, например, статическими деревьями по частоте). На входе нужен только словарь корней.
N>С русским так просто не получится.
В таком случае для каждого языка придется разрабатывать свой алгоритм сжатия? Ну, то есть не столько алгоритм, сколько набор правил, описывающих грамматическую структуру языка. Лучше уже тогда по слогам сжимать
N>Ну посмотри, как реально устроены архиваторы. Например, у zip deflate и прочих LZ77-based передаётся или цепочка входного текста без изменений, или данные типа "повторим кусок буфера с позиции K длиной N". Но к каждому из этих вариантов идёт префикс, который при соответствующем состоянии парсера однозначно определяет один из этих вариантов.
N>Так что, условно говоря, будет что-то вроде "R2,3T2". R, T — префиксы.
PD>Слов — вообще-то тоже. Если словарь составить и зафиксировать его.
В английском языке по некоторым оценкам — 4 миллиона слов (не словоформ, слов). В русском — чуть меньше (Alex Reyst может меня поправить, если не так).
Причем словарь — это не статический объект. Например, недавно словарь Merriam-Webster зафиксировал появление нового слова google
PD>Что касается интерпретации на той стороне — зависит от интерпретатора. Если интерпретатор на принимающей стороне будет понимать слова, а не буквы и иметь нужный словарь — все будет в порядке.
На каждый из нескольких тысяч языков на планете? Кто будет составлять и обновлять эти словари?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>В общем, так. Подумал я еще раз.
PD>Те, кто утверждают, что архивация будет эффективнее — возможно, правы. PD>Те, кто утверждают, что данный подход имеет какое-то отношение к алгоритмам архивации — безусловно неправы. Это совершенно разные вещи.
Ну почему так и разные? Сжатие без потерь, которое мы тут для удобства обозначаем архивацией — почему оно не может быть ориентировано на представление о типичном виде содержимого? Вполне допустим архиватор, ориентированный на текст, и архиватор, ориентированный на картинки...
Все реальные архиваторы так или иначе ориентированы на какой-то типичный контент. Например, в (в здешних обозначениях) LZH — ему ведь частотные списки для кодирования по Хаффману откуда брались? Наверняка был взят какой-то реальный пример (вроде содержимого диска разработчика) с кашей из исходников, бинарей, текстов песен и книг и так далее — и взята статистика по нему. Для ориентации на только бинарник значения были бы другие, и на текст — третьи.
Продолжая тему тех же LZH — обычно у них несопоставленная часть входного потока передаётся в сжатое представление побайтно и как раз на границах исходных байтов. Теперь представим себе передачу одного и того же текста в cp1251 и в utf-8, и предположим, что ссылки в буфер в одних и тех же местах. Тогда для utf-8 входа выход будет в 1.2-1.5 раз больше из-за большего размера буквальных цитат входа. Но если архиватор будет способен понять, что для входа есть хорошее отображение в другую кодировку, и пойдёт сжимать уже в cp1251 или любой другой аналогичной восьмибитке, пусть самопальной — что помешает ему это сделать?
Я не вижу смысла ужимать понятие такого архиватора до такого, что имеет понимание только на уровне байтиков и их фиксированных последовательностей, не выше и не ниже.
PD>Представим себе, что создано ПО для маленьких детей, не умеющих еще писать и читать. Это ПО позволяет им обмениваться картинками, но по прихоти разработчика не любыми, а только теми, что есть в базе данных этого ПО. Естественно, база у обоих ребятишек одна и та же. PD>В этом случае программист, который будет пересылать эти картинки вместо того, чтобы пересылать их номера , будет <пропускаю определение из соображений политкорректности>. Программист же, который будет аргументировать пересылку картинок тем, что их можно еще и сжать, будет <пропускаю определение из соображений политкорректности> в квадрате. PD>А знаете, кто эти дети ? Мы с вами, вполне взрослые люди. Мы обмениваемся друг с другом наборами картинок и передаем при этом по сети их номера. Если кто-то еще не понял — для русскоязычных таких картинок 64 (или 66), для англоязычных — 52. А в качестве внешней базы данных используем некий TTF или FON файл.
Ну если ты читаешь до сих пор по буквам, то для тебя именно такая "картина" из этих картинок, извини за каламбур. А вот если хотя бы дорос до чтения вслух нормальным темпом без слогов (в чём я на 100% уверен, как-никак программист;)) — то у тебя такими картинками, с ходу хватаемыми глазами, являются минимум слоги и короткие слова. А если овладел даже самыми базовыми техниками скорочтения — то уже слова среднего размера и типичные словосочетания. И это возможно именно потому, что их — осмысленных и реально встречающихся разных комбинаций букв — не так уж много. А к тому же мозгу помогает настройка на тип текста, которая ещё больше сужает диапазон автоматически распознаваемых слов. Всё это давно известные из физиологии факты (ссылку не дам, читал бумажно, но физиологи знают).
Потому — ориентированный на текст архиватор (или модуль соответствующей ориентации;)) может и должен использовать знание языка — и по составу слов, и по их частоте. А на такие картинки — их список. Но см. ниже про совместимость.
PD>А вот если я вас попрошу прислать мне текст хоть и на русском языке, но записанный глаголицей, а не кириллицей, то у вас два варианта. Либо прислать мне базу данных (TTF для глаголицы ), договориться о номерах и потом как обычно, либо, если первое невозможно, действительно слать картинки. Если у вас эти картинки в формате BMP, то не мешает их предварительно сжать (или в другой, сжатый, формат перевести).
Либо прислать в кириллице (возможно, с доп. знаками для того что есть только в глаголице — но мне те две странные буквы как-то не нужны).
PD>Таким образом, пересылка информации с внешним словарем имеет место гораздо чаще, чем некоторые здесь думают. И вопрос о том, кодировать ли буквы, или слова (а может, слоги, а может, пары букв) — этот вопрос не принципиальный, а технический. Проще говоря, вопрос звучит так — при каком способе кодирования можно получить код минимальной длины ? Вполне возможно, что для разных национальных языков этот ответ может оказаться различным.
Верно. Остался только вопрос совместимости:) Байты везде одинаковые. А вот получатель, у которого не будет модуля разжатия русского текста в utf-8 (который делает промежуточную восьмибитку) — будет страдать в отличие от того, у кого есть только gzip, но зато гарантированно для всех байт.
PD>Что же касается сжатия — его можно применятть в обоих случаях, это совсем другой вопрос. Естественно, качество сжатия может быть (и будет) лучше при кодировании буквами , чем словами.
По-моему, таки наоборот:)
PD> Вопрос — насколько и что получится в результате. Хотите сравнивать несжатые коды — бога ради. Хотите сжатые — тоже бога ради.
PD>Если же вопрос рассматривать в более общем плане, то можно сказать вот что. Если я хочу вам передать некоторую информацию, то у меня есть два способа. Либо передать ее в абсолютном формате, так чтобы вы (человек!) могли ее воспринять без привлечения чего бы то ни было еще (штатное ПО не рассматриваем). Либо передать вам способ, с помощью которого вы сможете ее получить сами, используя ту информацию, которая, как я предполагаю, у вас на компьютере уже имеется. Этот способ может быть и именем файла, и запросом SELECT и даже одним битом :-). И в случае передачи абсолютной информации, и в случае передачи способа дело закончится передачей некоторого массива байтов, который можно при необходимости и сжать перед пересылкой. И вопрос тут только один — какой код будет короче в данном конкретном случае.
Но её практическая реализация — реальная проблема. Для архиватора по современным меркам имеет смысл придумать виртуальную машину для постпроцессинга результата разархивации:))
The God is real, unless declared integer.
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, D. Mon, Вы писали:
DM>Данный вариант берет текст в виндовой кодировке и все русские слова длиной больше 3 букв заменяет на трехбайтные коды, у которых первый символ — от 128 до 143 (они не встречаются в тестовом файле, это спецсимволы), второй и третий — от 16 до 255, т.е. всего можно закодировать 240*240*16 = 921600 разных слов. При кодировании строится словарь и сохраняется в файл. Декодер читает этот словарь и полностью восстанавливает исходный текст.
Имеет смысл сделать аналогичное сравнение с английским — именно для того, чтобы сравнить с языком с почти неизменяемыми словами. Я взял с Мошкова английский перевод "Пути на Амальтею" и срезал html — из 149288 получилось 109104 (73%). Это ещё и с тем, что получились дубли с заглавными буквами. После gzip — 32% против 38, после bzip2 — 26 против 31 (gzip и bzip с максимумом сжатия, ключ -9).
DM>Вывод: как самостоятельный метод сжатия никуда не годится, а как препроцессор для дальнейшего сжатия — сойдет.
Угу.
DM>Полная реализация компрессора и декомпрессора заняла по 8 строк кода. DM>Если такую задачу готовы дать в качестве курсовой, это много говорит о Омском "университете" и его преподавателях.
А вот тут не спешите с выводами. Во-первых, Ваш код на Ruby совершенно не студенческий:) Во-вторых, для курсовой важнее не результат (в математических может быть результатом даже одна цифра), а чтобы был виден соответствующий курсу и изученным предметам ход работы.
Здравствуйте, netch80, Вы писали:
N>Ну почему так и разные? Сжатие без потерь, которое мы тут для удобства обозначаем архивацией — почему оно не может быть ориентировано на представление о типичном виде содержимого? Вполне допустим архиватор, ориентированный на текст, и архиватор, ориентированный на картинки...
+1. Но в реальности мы зипом и раром обходимся, ну еще юниксовское хозяйство
N>Все реальные архиваторы так или иначе ориентированы на какой-то типичный контент. Например, в (в здешних обозначениях) LZH — ему ведь частотные списки для кодирования по Хаффману откуда брались? Наверняка был взят какой-то реальный пример (вроде содержимого диска разработчика) с кашей из исходников, бинарей, текстов песен и книг и так далее — и взята статистика по нему. Для ориентации на только бинарник значения были бы другие, и на текст — третьи.
Может быть. Автора спросить надо .
N>Ну если ты читаешь до сих пор по буквам, то для тебя именно такая "картина" из этих картинок, извини за каламбур. А вот если хотя бы дорос до чтения вслух нормальным темпом без слогов (в чём я на 100% уверен, как-никак программист)
> — то у тебя такими картинками, с ходу хватаемыми глазами, являются минимум слоги и короткие слова. А если овладел даже самыми базовыми техниками скорочтения — то уже слова среднего размера и типичные словосочетания. И это возможно именно потому, что их — осмысленных и реально встречающихся разных комбинаций букв — не так уж много. А к тому же мозгу помогает настройка на тип текста, которая ещё больше сужает диапазон автоматически распознаваемых слов. Всё это давно известные из физиологии факты (ссылку не дам, читал бумажно, но физиологи знают).
+1. Да, конечно, но я же не об этом , а только о способе их передачи говорил. Воспринятие этих картинок человеком потом — это другой вопрос. В конце концов некоторые тексты мы вообще по диагонали читаем
N>Потому — ориентированный на текст архиватор (или модуль соответствующей ориентации) может и должен использовать знание языка — и по составу слов, и по их частоте. А на такие картинки — их список. Но см. ниже про совместимость.
PD>>А вот если я вас попрошу прислать мне текст хоть и на русском языке, но записанный глаголицей, а не кириллицей, то у вас два варианта. Либо прислать мне базу данных (TTF для глаголицы ), договориться о номерах и потом как обычно, либо, если первое невозможно, действительно слать картинки. Если у вас эти картинки в формате BMP, то не мешает их предварительно сжать (или в другой, сжатый, формат перевести).
N>Либо прислать в кириллице (возможно, с доп. знаками для того что есть только в глаголице — но мне те две странные буквы как-то не нужны).
Я не такой специалист в глаголице, чтобы сказать, можно ли сделать то, о чем ты пишешь. Как я понял, ты варииацию на тему Runglish предлагаешь.
Про 2 странные буквы не понял.
N>Верно. Остался только вопрос совместимости Байты везде одинаковые. А вот получатель, у которого не будет модуля разжатия русского текста в utf-8 (который делает промежуточную восьмибитку) — будет страдать в отличие от того, у кого есть только gzip, но зато гарантированно для всех байт.
Тоже верно. А также верно, что пользователь, у которого нет ни одного шрифта в кодировке КОИ-8, будет страдать, если ему русский текст в этой кодировке пришлют (возможность перекодировки я сейчас не рассматриваю). И страдает порой, хоть не сильно. Я недавно Windows переустановил, ну и FAR, конечно, тоже, а таблицы добавить забыл. Сегодня аукнулось.
PD>>Что же касается сжатия — его можно применятть в обоих случаях, это совсем другой вопрос. Естественно, качество сжатия может быть (и будет) лучше при кодировании буквами , чем словами.
N>По-моему, таки наоборот
Почему ? В текстах явно больше избыточность, чем в файле номеров, и он лучше будет сжиматься.
Здравствуйте, Alex Reyst, Вы писали:
AR>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>> Но в реальности мы зипом и раром обходимся
AR>FYI: RAR использует специализированные алгоритмы для текста, графики, звука, исполняемых файлов.
Если бы он ещё всё старое поддерживал... для нашей RT я был вынужден категорически запретить аттачи в RAR, потому что файл пятилетней давности не читался новым RAR. (Старым — читался — так что это не проблема целостности)
А само по себе наличие специальных алгоритмов — конечно, полезно.
The God is real, unless declared integer.
Re[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Для того, чтобы такой вывод сделать, надо написать программу длиной в 0 строк. Потому что здесь никакой программы вообще не надо. Тут арифметика на уровне первого класса.
И ошибка в ней на уровне первого класса. Не принципиальная, но заметная.
DM>>А вот если сжатый двухбайтными кодами файл еще зазиповать, то получается уже 7316 байт (30%). PD>А вот тут самое интересное в твоем постинге. Прочти еще раз мое исходное сообщение. Я там про архивацию ни слова не писал. Я сказал, что ДБК будет в 3 раза короче исходного текста. Здесь опять-таки арифметика первого класса PD>6(длина слова) / 2 (размер ДБК) == 3.
Это в твоей теории. А теперь учтём пробел, который твоим методом не заменяется. Запятые, и прочее. В среднем 1.2 символа пунктуации на слово. Тогда уже не 6/2, а 7.2/3.2, и результат не 3, а 2.25. А чтобы совсем близко к реалии, возьмём тот же образцовый текст... почему в нём только 26-40%? Потому что коротких слов очень много.
PD>И то, что в результате получается в 1.5 раза лучше, чем зипом и в 1.25 лучше, чем раром в лучшем его режиме — кое о чем говорит.
Не "лучше чем RAR" а "лучше чем RAR без него"
А в общем — мы вернулись к тому же что раньше — что специализированный алгоритм, который способен преобразовать данные в более короткую форму благодаря какому-то внешнему знанию, может как минимум сильно помочь в сжатии.
The God is real, unless declared integer.
Re[4]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, netch80, Вы писали:
N>Это в твоей теории. А теперь учтём пробел, который твоим методом не заменяется. Запятые, и прочее. В среднем 1.2 символа пунктуации на слово. Тогда уже не 6/2, а 7.2/3.2, и результат не 3, а 2.25. А чтобы совсем близко к реалии, возьмём тот же образцовый текст... почему в нём только 26-40%? Потому что коротких слов очень много.
А пробел между словами вроде ставится всегда, если нет знака препинания. Или нет ?
PD>>И то, что в результате получается в 1.5 раза лучше, чем зипом и в 1.25 лучше, чем раром в лучшем его режиме — кое о чем говорит.
N>Не "лучше чем RAR" а "лучше чем RAR без него"
да, верно.
N>А в общем — мы вернулись к тому же что раньше — что специализированный алгоритм, который способен преобразовать данные в более короткую форму благодаря какому-то внешнему знанию, может как минимум сильно помочь в сжатии.
+1.
With best regards
Pavel Dvorkin
Re[4]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, netch80, Вы писали:
N>Это в твоей теории. А теперь учтём пробел, который твоим методом не заменяется. Запятые, и прочее. В среднем 1.2 символа пунктуации на слово. Тогда уже не 6/2, а 7.2/3.2, и результат не 3, а 2.25. А чтобы совсем близко к реалии, возьмём тот же образцовый текст... почему в нём только 26-40%? Потому что коротких слов очень много.
Вот это как раз и может быть предметом курсовой. В каких случаях лучше вообще не кодировать, может , даже, иначе — какие слова лучше не кодировать, может, даже независимо от длины (место-то в словаре жалко, если 2 байтами обойтись). И т.д.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А впрочем, зачем я все это доказываю ? Есть же очевидное доказательство — китайский язык. Там иероглифы и есть (примерно) слова.
Скорее морфемы тогда уж...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>А впрочем, зачем я все это доказываю ? Есть же очевидное доказательство — китайский язык. Там иероглифы и есть (примерно) слова.
E>Скорее морфемы тогда уж...
Я не большой специалист в китайском языке , но вот что говорит Википедия
Большинство иероглифов не представляет собой ни простых изобразительных знаков, ни идеограмм, а принадлежит к третьему, смешанному типу, так называемым фоноидеограммам. Одна из частей фоноидеографического иероглифа носит название фонетик, другая — детерминатив. Слово, обозначаемое иероглифом (выделено мной — PD) , фонетически тождественно слову, обозначаемому фонетиком; другими словами, чтение знака в целом совпадает с чтением одной его части. Например, иероглиф 誹 «злословить, чернить, порочить» и 非, одно из значений которого «дурной, плохой, зло», оба произносятся фэй; знаки 柑 «апельсин», 蚶 «устрица» и 甘 «сладкий» читаются гань (蚶 читается хань). Другая часть знака имеет идеографическое значение, a именно, она определяет область, к которой относится конкретное значение данного знака, отчего и называется «детерминатив».
Может и верно, если фонетик считать корнем, а детерминант — аффиксом. А может, и нет.
PD> Например, иероглиф ? «злословить, чернить, порочить» и ?, одно из значений которого «дурной, плохой, зло», оба произносятся фэй; знаки ? «апельсин», ? «устрица» и ? «сладкий» читаются гань (? читается хань). Другая часть знака имеет идеографическое значение, a именно, она определяет область, к которой относится конкретное значение данного знака, отчего и называется «детерминатив».
Это не совсем верно, потому что разные диалекты, использующие китайскую письменность, могут эти части произносить совершенно по-разному.
не существует и единого К. яз., на к-ром бы говорила «монолитная», как принято считать, 400-миллионная масса китайцев. Уже не говоря о национальных меньшинствах, населяющих Китай (маньчжуры, дунгане, монголы, тибетцы, мяоцзы, лоло, хакка и др.), говорящих на своих яз., собственно китайское население также не имеет общего яз. К. яз. есть понятие, обобщающее несколько яз.: разговорный яз. по линии социальной подразделяется на так наз. «мандаринский» яз. (гуаньхуа), являющийся обязательным «государственным» яз., и на «простонародные», местные яз. (сухуа, тухуа), отличающиеся от «гуаньхуа» как фразеологией, так и некоторыми различиями в грамматической структуре. По линии территориально-географической разговорный яз. подразделяется на несколько самостоятельных диалектов или наречий, разнящихся друг от друга фонетическим строем. Письменный К. яз., не имеющий ничего общего с разговорными яз., подразделяется на классический яз. (вэньянь) и современный яз. (байхуа), отличные друг от друга в такой же мере, как напр. латынь от современного французского. Кроме того в письменном яз. различается ряд стилей (официальный, коммерческий, эпистолярный, литературный и т. п.), к-рые имеют свой грамматический и стилистический строй и несколько разнятся друг от друга фразеологией.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Может и верно, если фонетик считать корнем, а детерминант — аффиксом. А может, и нет. PD>http://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D1%80%D1%84%D0%B5%D0%BC%D0%B0
Вики, конеччно, это хорошо, но в китайском языке есть много слов, состоящих из нескольктх иероглифов. Хотя почти каждый иероглиф и является словом...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, IT, Вы писали:
IT>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Жду комментариев.
IT>Что насчёт мморфологии? В выражениях "бредовый пост" и "бредовая идея" выделенное это одно или два разных слова?
А прочитать исходный постинг можно было внимательно ? Там же ясно сказано
>Будем считать слова различными, если они отличаются хотя бы одним символом. Так что все падежные формы и склонения — это разные слова.
Здравствуйте, Sinclair, Вы писали:
S>Я уже как-то предлагал в этом форуме сделать такой хеш-код, чтобы двум сообщениям с одинаковым смыслом сопоставлялось одно 32хбитное число. А разным, естественно — разные числа. Это бы позволило эффективно бороться с баянами.
Интересная идея
S>Предположение о том, что сообщений с различными смыслами больше четырех миллиардов не выдерживает никакой критики.
Предположение о том, что некто может однозначно и непогрешимо различать имеют ли разные сообщения одинаковый или различающийся смысл не выдерживает никакой критики.
S>очевидно, что вообще различных сообщений меньше двух миллионов.
Э.. это общее количество сообщений на RSDN вообще?
Здравствуйте, SE, Вы писали:
SE>Предположение о том, что некто может однозначно и непогрешимо различать имеют ли разные сообщения одинаковый или различающийся смысл не выдерживает никакой критики.
С таким настроением ты грант не получишь S>>очевидно, что вообще различных сообщений меньше двух миллионов. SE>Э.. это общее количество сообщений на RSDN вообще?
Это заведомо больше, чем общее количество сообщений на RSDN.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>>>очевидно, что вообще различных сообщений меньше двух миллионов. SE>>Э.. это общее количество сообщений на RSDN вообще? S>Это заведомо больше, чем общее количество сообщений на RSDN.
Либо я чего то не понял, либо это количество давно уже за 3 млн. перевалило.
... << RSDN@Home 1.2.0 alpha 4 rev. 1095 on Windows Vista 6.0.6001.65536>>
Здравствуйте, D. Mon, Вы писали:
DM>А вот пример решения такого задания (написанный за пару недель), который сжимал в среднем лучше, чем тогдашний rar: DM>http://about.thedeemon.com/products/arh/
Ну, то что арифметическое сжатие один из лучших в плане качества алгоритмов (и весьма простой. кстати) — давно известно. Проблема только в том, что он очень медленный. Хотя конечно, с учетом современных многоядрастых процов, SSE и всяких CUDA ... Неплохая темка для диплома, кстати
... << RSDN@Home 1.2.0 alpha 4 rev. 1095 on Windows Vista 6.0.6001.65536>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Либо я чего то не понял, либо это количество давно уже за 3 млн. перевалило.
ой,
Тогда придется брать хешкоды подлиннее
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[7]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, AndrewVK, Вы писали:
AVK>Ну, то что арифметическое сжатие один из лучших в плане качества алгоритмов (и весьма простой. кстати) — давно известно. Проблема только в том, что он очень медленный. Хотя конечно, с учетом современных многоядрастых процов, SSE и всяких CUDA ...
Само арифметическое сжатие не такое уж и медленное — оно и в rar'е давно используется, и в видеокодеках (например, Lagarith — довольно шустро сжимает видео без потерь, используя быструю реализацию арифм. сжатия, где деление выражено через умножение; и CABAC — то что в H.264 вместо Хаффмана). Но само по себе оно много не дает по сжатию, и мощным становится в сочетании с контекстным моделированием, которое требует кучу памяти и потому уже тормозит.
Здравствуйте, Nuzhny, Вы писали:
VD>>Дваркин, я тебя умоляю, ты только иероглифы не изобретай, а то ведь китайцы и японцы в суд подадут.
N>Стыд и срам. Переход на личности в споре, оскорбления и каверканье фамилии. Давно такого не было, но я краснею.
Какой спор? Какой переход? Смешно, вот и смеюсь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Sergey, Вы писали:
S>Архиваторы примерно так и работают. Только у них слово не совпадает со словом языка, да и словарь они вместе с сообщением пересылают.
У архиваторов могут быть адаптивные алгоритмы.
Договариваются об исходных стартовых условиях (например: равномерное распределение букв), кодируют/декодируют очередную букву (Хаффман) или строчку (Лемпел-Зив) и корректируют словарь.
В этом случае пересылка стартового словаря — это пересылка номера (каким словарём пользоваться). Очень компактно!
Ну а ЛЗ с окном вообще не требует словаря — там в роли словаря выступает хвост декодированного текста.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, netch80, Вы писали:
N>Идея не новая. У автора ARJ был следующий архиватор JAR (не путать с явовским суффиксом файлов), в котором был словарь английского и подстановка номера слова при сжатии. Я его видел в районе 95-го, но он страшно жрал память и диск, и что-то с реализацией не сложилось. Но примерно тогда же начал кончаться и ARJ.
Дядюшка Арджи скончался, отчасти, потому что не поддерживал длинные имена (Windows 95 с FAT32).
Я очень хорошо помню этот трах-тибидох с форматом ZIP, было несколько конкурирующих версий архиватора (две из которых — фирменные, PKWare: pkzip25 и кажется, pkzipw), поддерживавшие LFN. И благодаря этой конкуренции всё как-то хорошо сложилось.
А ардж так и вошёл в Лету с форматом имён 8.3
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[8]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR> Выводы высосаны из пальца.
Возможно.
Считаете ли Вы озвученную тему достойной курсовой работы? Считаете ли Вы допустимым преподавателю программирования в университете не быть знакомым с азами теории информации — идеями Шеннона и Колмогорова?
Re[11]: Кодирование слов при передаче по сети (покритикуйте
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
DM>>Возможно. DM>>Считаете ли Вы озвученную тему достойной курсовой работы? LCR>Да. Сложность задачи зависит от пристальности взгляда.
LCR>Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований:
Насколько я припоминаю, дипломная работа, как любая научная работа, начинается с очень интересной вводной части. В которой пишут историю проблемы, что было сделано уже в этой области, и после этого делается плавный переход к постановке решаемой проблемы.
Эту работы зарезал бы еще рецензент, уважаемый коллега. А если каким-то чудом рецензент бы (не глядя) то подписал, то потом научного руководителя распяли бы на доске. К сожалению. На ВМиК МГУ, выпускником которого является D.Mon, за такую работу человек с высокой определенностью получит неуд.
Re[11]: Кодирование слов при передаче по сети (покритикуйте
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований: частотный анализ, морфологический анализ, обобщения алгоритма на смешанные тексты,
Именно это я имел в виду. В частности, есть такое наблюдение — средний человек имеет активный словарный запас всего лишь в несколько тысяч слов (где-то читал, что вроде 2000, боюсь ошибиться). Это, конечно, не означает, что у всех этот запас один и тот же, но безусловно означает, что есть слова "популярные", а есть не очень. Это как-то следует учесть или нет ? Впрочем, это не единственное соображение, конечно, так что прежде чем давать это в виде курсовой, необходимо все хорошенько продумать. И , вполне возможно и даже наверняка здесь нужна консультацию не столько математика, сколько хорошего филолога — лингвиста.
With best regards
Pavel Dvorkin
Re[8]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, fmiracle, Вы писали:
F>Обучение науке на программистском вузе/потоке — это в первую очередь разработка алгоритмов, изучение непонятной проблемной области, и построение модели ее решения. А это в последующей "программистской деятельности" пригодится очень много раз.
Если под словами "в первую очередь" понимать, что это должно быть в начале курса обучения — согласен. Именно это и делается, есть курс по структурам данным и алгоритмам, который я читал лет 7-8. А вот если под словами "в первую очередь" понимать, что это главное (а это , видимо, и есть, то понимание, которое ты сюда вложил) — согласен лишь отчасти. База — дело очень важное, но и знание современных технологий — не менее. Вот предсавь себе выпускника, который эту базу знает очень хорошо, но кроме консольных приложений (разве с их помощью нельзя разрабатывать алгоритмы ?) ничего писать не умеет ? В академическом институте он себе место найдет и будет дальше разрабатывать алгоритмы, но ведь мы готовим все-таки практических программистов. Куда его возьмут в реальных условиях ?
With best regards
Pavel Dvorkin
Re[12]: Кодирование слов при передаче по сети (покритикуйте
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, Lazy Cjow Rhrr, Вы писали:
G>Насколько я припоминаю, дипломная работа, как любая научная работа, начинается с очень интересной вводной части. В которой пишут историю проблемы, что было сделано уже в этой области, и после этого делается плавный переход к постановке решаемой проблемы.
А может, все же не стоит путать дипломную работу с курсовой на 3 курсе ? Где я говорил, что это тема для дипломной работы ? Такое передергивание не очень солидно. Некрасиво, проще сказать.
With best regards
Pavel Dvorkin
Re[12]: Кодирование слов при передаче по сети (покритикуйте
Здравствуйте, Gaperton, Вы писали:
LCR>>Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований:
G>Насколько я припоминаю, дипломная работа, как любая научная работа, начинается с очень интересной вводной части. В которой пишут историю проблемы, что было сделано уже в этой области, и после этого делается плавный переход к постановке решаемой проблемы.
Вполне возможно.:)) Но исходное обсуждение касалось курсовой работы, насколько я помню...
The God is real, unless declared integer.
Re[9]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, fmiracle, Вы писали:
F>>Обучение науке на программистском вузе/потоке — это в первую очередь разработка алгоритмов, изучение непонятной проблемной области, и построение модели ее решения. А это в последующей "программистской деятельности" пригодится очень много раз.
PD>Если под словами "в первую очередь" понимать, что это должно быть в начале курса обучения — согласен. Именно это и делается, есть курс по структурам данным и алгоритмам, который я читал лет 7-8. А вот если под словами "в первую очередь" понимать, что это главное (а это , видимо, и есть, то понимание, которое ты сюда вложил) — согласен лишь отчасти. База — дело очень важное, но и знание современных технологий — не менее. Вот предсавь себе выпускника, который эту базу знает очень хорошо, но кроме консольных приложений (разве с их помощью нельзя разрабатывать алгоритмы ?) ничего писать не умеет ? В академическом институте он себе место найдет и будет дальше разрабатывать алгоритмы, но ведь мы готовим все-таки практических программистов. Куда его возьмут в реальных условиях ?
А что имеется в виду под неконсольными приложениями? GUI? Так оно в основе осваивается за день с хорошей книжкой наперевес. Серверность? Она как и GUI требует понимания событийно-управляемого подхода, далее всё тривиально и работает только местная специфика. COM, ATL и прочее?
Впрочем, я ориентируюсь на своё идеальное представление о студенте:)
The God is real, unless declared integer.
Re[12]: Кодирование слов при передаче по сети (покритикуйте
Уважаемый, Gaperton,
LCR>>Когда студент принесёт программу и результаты сравнения с известными алгоритмами, возникнут вопросы: "почему так плохо?", "как улучшить?". И направления для дальнейших исследований:
G>Насколько я припоминаю, дипломная работа, как любая научная работа, начинается с очень интересной вводной части. В которой пишут историю проблемы, что было сделано уже в этой области, и после этого делается плавный переход к постановке решаемой проблемы.
Совершенно верно. Заметь, я утверждаю то же самое.
G>Эту работы зарезал бы еще рецензент, уважаемый коллега. А если каким-то чудом рецензент бы (не глядя) то подписал, то потом научного руководителя распяли бы на доске. К сожалению. На ВМиК МГУ, выпускником которого является D.Mon, за такую работу человек с высокой определенностью получит неуд.
Хотя в оригинале речь шла про курсовую, про диплом тоже можно кое-что сказать.
Вероятно, твоё воображение нарисовало такую паршивенькую работёнку, настолько жалкую и ничтожную, что даже о ней и упоминать неприлично. Хе. Её в ОмГУ тоже не допустили бы до защиты.
Моё же воображение рисует полноценное ислледование в вышеуказанных направлениях и построение алгоритма, который бъёт максимальный рар на русскоязычных текстах. Такую работу в ОмГУ определённо до защиты допустят.
PD>Ты уверен, что gzip сожмет этот массив удвоенной длины до того же размера, что и одинарной длины ? Сомневаюсь.
Совершенно точно ужмет. Он не только повторяющиеся строки учитывает, а и разные частоты разных букв.
Хотя gzip дерьмовый компрессор, во всех отношениях — есть и быстрее в разы, чем gzip на минимуме, и получше качеством при той же скорости, что gzip на максимуме.
Здравствуйте, Maxim S. Shatskih, Вы писали:
MSS>Хотя gzip дерьмовый компрессор, во всех отношениях — есть и быстрее в разы, чем gzip на минимуме, и получше качеством при той же скорости, что gzip на максимуме.
У gzip есть неоспоримый плюс — он умеет жать /бесконечные/ потоки, а не только файлики.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Если нам не помогут, то мы тоже никого не пощадим.
Перекуём баги на фичи!
