Здравствуйте, ., Вы писали: .>Разовьём идею дальше. Я уверен, что во всём мире существует не более 8^1024 текстов (и ещё на долго хватит). А значит _любой_ текст, любой длины можно ужать в 1кб!
Я уже как-то предлагал в этом форуме сделать такой хеш-код, чтобы двум сообщениям с одинаковым смыслом сопоставлялось одно 32хбитное число. А разным, естественно — разные числа. Это бы позволило эффективно бороться с баянами.
Предположение о том, что сообщений с различными смыслами больше четырех миллиардов не выдерживает никакой критики — очевидно, что вообще различных сообщений меньше двух миллионов. Поскольку некоторые из них являются баянами (в частности, твое сообщение, на которое я отвечаю), то четырех миллиардов хеш-кодов нам хватит с запасом на много лет вперед.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Те, кто утверждают, что архивация будет эффективнее — возможно, правы.
Те, кто утверждают, что данный подход имеет какое-то отношение к алгоритмам архивации — безусловно неправы. Это совершенно разные вещи.
Представим себе, что создано ПО для маленьких детей, не умеющих еще писать и читать. Это ПО позволяет им обмениваться картинками, но по прихоти разработчика не любыми, а только теми, что есть в базе данных этого ПО. Естественно, база у обоих ребятишек одна и та же.
В этом случае программист, который будет пересылать эти картинки вместо того, чтобы пересылать их номера , будет <пропускаю определение из соображений политкорректности>. Программист же, который будет аргументировать пересылку картинок тем, что их можно еще и сжать, будет <пропускаю определение из соображений политкорректности> в квадрате.
А знаете, кто эти дети ? Мы с вами, вполне взрослые люди. Мы обмениваемся друг с другом наборами картинок и передаем при этом по сети их номера. Если кто-то еще не понял — для русскоязычных таких картинок 64 (или 66), для англоязычных — 52. А в качестве внешней базы данных используем некий TTF или FON файл.
Только не надо рассуждений на тему о том, что мол, таких TTF файлов много. В старые добрые досовские времена пересылали тексты так же. А в качестве базы данных картинок у нас в России использовался незабвенный rkvga.com. Ничего в принципе здесь не изменилось.
А вот если я вас попрошу прислать мне текст хоть и на русском языке, но записанный глаголицей, а не кириллицей, то у вас два варианта. Либо прислать мне базу данных (TTF для глаголицы ), договориться о номерах и потом как обычно, либо, если первое невозможно, действительно слать картинки. Если у вас эти картинки в формате BMP, то не мешает их предварительно сжать (или в другой, сжатый, формат перевести).
Таким образом, пересылка информации с внешним словарем имеет место гораздо чаще, чем некоторые здесь думают. И вопрос о том, кодировать ли буквы, или слова (а может, слоги, а может, пары букв) — этот вопрос не принципиальный, а технический. Проще говоря, вопрос звучит так — при каком способе кодирования можно получить код минимальной длины ? Вполне возможно, что для разных национальных языков этот ответ может оказаться различным.
Что же касается сжатия — его можно применятть в обоих случаях, это совсем другой вопрос. Естественно, качество сжатия может быть (и будет) лучше при кодировании буквами , чем словами. Вопрос — насколько и что получится в результате. Хотите сравнивать несжатые коды — бога ради. Хотите сжатые — тоже бога ради.
Если же вопрос рассматривать в более общем плане, то можно сказать вот что. Если я хочу вам передать некоторую информацию, то у меня есть два способа. Либо передать ее в абсолютном формате, так чтобы вы (человек!) могли ее воспринять без привлечения чего бы то ни было еще (штатное ПО не рассматриваем). Либо передать вам способ, с помощью которого вы сможете ее получить сами, используя ту информацию, которая, как я предполагаю, у вас на компьютере уже имеется. Этот способ может быть и именем файла, и запросом SELECT и даже одним битом . И в случае передачи абсолютной информации, и в случае передачи способа дело закончится передачей некоторого массива байтов, который можно при необходимости и сжать перед пересылкой. И вопрос тут только один — какой код будет короче в данном конкретном случае.
M>>Сколько точно — хз Если мы будем только формы глагола считать, не ударясь в причастия и деепричастия E>Обычно причастия и деепричастия в русской морфологии считаются формами глагола. Ещё можно возвратные формы включать или не включать в парадигму, кстати...
Всё правильно. Вот тут можно заценить всю мощь русского языка, введя какой-нибудь хороший глагол (например, парадигма глагола "программировать" состоит из примерно 170-180 словоформ): http://starling.rinet.ru/cgi-bin/morphque.cgi?encoding=win
Здравствуйте, 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: Кодирование слов при передаче по сети (покритикуйте идею
Данный вариант берет текст в виндовой кодировке и все русские слова длиной больше 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 строк кода.
Если такую задачу готовы дать в качестве курсовой, это много говорит о Омском "университете" и его преподавателях.
Здравствуйте, 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>По-моему, таки наоборот
Почему ? В текстах явно больше избыточность, чем в файле номеров, и он лучше будет сжиматься.
With best regards
Pavel Dvorkin
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 курса вполне нормальная задача, я считаю.
Здравствуйте, 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[3]: Кодирование слов при передаче по сети (покритикуйте и
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну а мне в ответ — можно архивировать. Можно, не спорю. Но если вы (не ты лично) хотите архивировать исходный текст — дайте и мне право архивировать ДБК. А то иначе получается, что я вроде бы утверждаю, что я новый алгоритм архивации изобрел. Перечти мои постинги — где я такое сказал ?
А так что ты изобрел? Я вот так и не понял. Ну кодируешь ты текст цифрами, а зачем? Передавать по сети — для этого есть кодировки по буквам. Чем твой вариант лучше? Позволяет иметь меньший объем для передачи данных? Ну так это и есть архивация по сути своей.
Или главное не уменьшение размера? А что тогда?
Только не надо рассказывать страшные сказки про детей, которых злой создатель не научил читать и говорить, но дал компьютер с ограниченным числом картинок, каждая из которых описывает 200 слов по 3000 букв в каждом слове. Абстрактных ситуаций придумать можно много. Вопрос в практическом применении.
PD>И то, что в результате получается в 1.5 раза лучше, чем зипом и в 1.25 лучше, чем раром в лучшем его режиме — кое о чем говорит.
Да чем же он лучше? Лучше только опять же после прохода того же зипа или рара. И при этом, что характерно, в примере используется словарь, который строится из данного же текста. Когда будет один общий словарь и натравливаться будет на другой текст — эффект будет хуже. Хотя бы из-за некодируемых последовательностей и префиксов-суффиксов смены режима.
PD>Этот выпад оставлю на твоей совести. Отмечу только, что я собирался дать именно реальную задачу, с настоящим словарем. Это немного иная ситуация, чем брать слова из данного текста и кодировать. Для 3 курса вполне нормальная задача, я считаю.
Это та же самая задача, просто разбитая на две части — отдельно вырезано построение словаря, который наполняется предварительно на некоторых текстах, и отдельно уже идет архивация других текстов, не использовавшихся при построении словаря.
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 байтами обойтись). И т.д.
)
