Кодирование с изъятием информации. Часть 1-я, философская

    Написано в сотрудничестве с Ревазом Бухрадзе и Кириллом Перминовым


    1. Введение


    Offline oбмен сообщениями сейчас является одним из наиболее популярных способов общения (1, 2, 3) — судя по аудитории способов общения и динамике её роста.


    При этом, ключевым требованием при обмене сообщениями всегда будет являться полное соответствие отправленного сообщения – полученному, то есть передача данных не должна необратимо искажать сами данные. Естественное желание – сэкономить привело к созданию алгоритмов сжатия данных, которые, убирают естественную избыточность данных минимизируя объём хранимых и передаваемых файлов.


    Максимально достигаемый объём сжатия, гарантирующий однозначное восстановление данных, определяется работами К. Шеннона по теории информации, и в общем-то является непреодолимым так как изъятие не только избыточной, но и смысловой информации не позволит однозначно восстановить исходное сообщение. Стоит отметить, что отказ от точного восстановления в некоторых случаях и не является критически важным и используется для эффективного сжатия графических, видео и музыкальных данных, где потеря несущественных элементов оправдана, однако о общем случае целостность данных, куда важнее их размера.


    Соответственно интересным является вопрос о том, можно-ли не нарушая положения теории информации передать сообщение объёмом меньше, чем минимальный объём, который может быть достигнут при самом лучшем сжатии данных.



    2. Пример


    Поэтому давайте разберём пример, который позволит изучить особенности передачи информации. И хотя в «английской» традиции участников информационного обмена принято именовать Алиса и Боб, мы же в преддверии нового года воспользуемся более знакомыми любителями месседжинга: Матроскиным и Шариком соответственно.


    image


    В качестве же сообщения m выберем: «Поздравляю тебя, Шарик, ты балбес!». Длина его в односимвольной кодировке- len(m) — 34 байта.


    Можно заметить, что длина сообщения заметно больше количества информации в нём. Это можно проверить вычеркивая из сообщения сначала каждый десятый символ, потом, (опять же из оригинального сообщения) каждый девятый и так далее до каждого четвёртого, результатом чего будет — «Позравяю ебя Шаик,ты албс!»-26 байт. Соответственно степень «загадочности» будет постепенно повышаться, но, догадаться о чём речь, будет достаточно просто. Более того, «Яндекс» распознаёт данное обращение.


    Ещё более высокой степени сокращения длины сообщения при сохранении смысла можно добиться отбрасывая гласные и часть пробелов: “Пздрвл тб,Шрк,т блбс!” — 21 байт, стоит отметить, что хотя поисковики и не справляются таким написанием, восстановить фразу труда не составляет.


    Если же посмотреть на количество информации I(m) в этом сообщении определяемое более строго через понятие информационной энтропии, то видно, что объём информации передаваемый в этом сообщении, составляет примерно 34*4,42/8=18,795 байт. Здесь: 4.42 бит/символ среднее количество информации в одном байте русского языка (4, 5), а 8 — приведение от битов к байтам. Это показывает, что воспользовавшись самым лучшим способом сжатия данных необходимо будет затратить не менее 19 байт на передачу сообщения от Матроскина Шарику.


    Более того, верно и обратное утверждение о том, что передать нужное нам сообщение без потерь меньше чем за 19 байт невозможно (К. Шеннон, Работы по теории информации и кибернетике., изд. Иностранной литературы, Москва, 1963г.) Теорема 4. стр. 458.


    3. Дальнейшие рассуждения


    Однако продолжим… Пусть у Матроскина и у Шарика есть некоторое дополнительное количество информации k и пара функций, одна из которых m'=E(k,m), рассчитывающая пересечение дополнительной информации k и исходного сообщения m image, а вторая D(k,m') =m — обратная к E. Причём количество информации определяемой по Шеннону, удовлетворяет следующему условию: image. Соответственно, если нам удастся построить определённую выше пару функций E(k,m) и *D(k,m'), такие, что выполняются следующие два условия:


    • image,
    • image

    то это будет означать, что для передачи информации между адресатами может потребоваться меньше информации чем содержится в исходном сообщении.


    image


    При этом стоит обратить внимание на то, что по определению указанных функций не происходит нарушения утверждений теории информации.


    Похожие, алгоритмы предусматривающие замену передаваемой информации её хешем, активно используются в системах оптимизации сетевого трафика. При этом, однако, в отличие от описываемого алгоритма, для того, чтобы эффективно использовать данный вид оптимизации требуется хотя бы однократная передача данных.


    Ввиду того, что сообщения на естественном языке содержат объём данных, больший чем объём информации, то если предварительно сжать исходное сообщение при помощи какого-либо из алгоритмов, обеспечивающих эффективное устранение избыточности, например, арифметического кодирования.


    Обозначим применение операции сжатия m’= Ar(m) такой, что image. Если теперь использовать определённую выше функцию E над предварительно сжатым сообщением, то можно заметить, что и объём передаваемых данных и количество информации передаваемых между адресатами могут оказаться меньше объёма данных и количества информации в исходном сообщении.


    То есть, обобщая: в предположении, что существует обратимое преобразование D(k,E(k,m)) =m, такое, что image применение операций устранения избыточности даёт возможность передать объём и количество информации в объёме не превосходящие соответствующие параметры (длина len(m) и количество информации I(m)) исходного сообщения.


    В общем осталось только подобрать функции…..

    Поделиться публикацией

    Комментарии 83

      +2
      Ещё более высокой степени сокращения длины сообщения при сохранении смысла можно добиться отбрасывая гласные и часть пробелов: “Пздрвл тб, Шрк, т блбс!”

      Думаю, здесь имеет место не сжатие, а хэширование, т.к. однозначно восстановить фразу человеку, не смотревшему "Простоквашино", будет невозможно.

        +1
        В общем-то да. Тут скорее расчёт на то, что и смотрели и мультфильм вполне новогодний и фраза простая.
        А если серьёзно, то получается так, что если и в тексте и в ключе можно выделить общую информацию, которую можно отбросить, то восстановить данные, по информации меньшей чем минимум достигаемый сжатием, не имея ключа, довольно сложно.
          0
          Может быть, стоит определиться сначала с тем, что подразумевается под количеством информации? Если Шарик знает, что никаких других сообщений он получить не может, то количество информации 0, если его могут еще поздравить верблюдом, то 1. Информация в классическом понимании — мера разнообразия вероятных исходов. В постановке задачи этот математический термин используется спекулятивно, хотя нельзя не признать и присутствия разумного зерна в поднятом вопросе.
          0
          Для уменьшения длины при сохранении смысла можно выбросить обращение: своё имя Шарик и так знает.
            0

            Если сообщения идут только Шарику, то да, можно. Если же есть, скажем, Дядя Фёдор — словарь надо расширять.

            0
            Насколько я понимаю, арабы пишут, выкидывая гласные (в алфавите только Алеф (алиф) — гласная). Так что, запись только согласных — хороший способ сэкономить папирус, пергамент и байты на диске.
            Ссылка — Арабское письмо
              0

              Просто всегда хочется подумать, а можно ли ещё сэкономить.

                0
                Арабский язык хорошо приспособлен под запись без гласных. Русский текст записать таким способом без потерь не получится.

                Но если интересно, почитайте про Китабы — тексты на белорусском языке, записанные арабицей :)
                  0

                  Прочитал, что нашёл помимо wiki, — вот, вот и вот. Но тут тема такая, что меняется по сути только алфавит, что как кажется сохраняет информацию.
                  Или не так Вас понял?

                    0
                    Да, меняется только алфавит (какие-то звуки передаются даже точнее, какие-то хуже), в целом информация сохраняется. Но я хотела сказать, что сократить количество знаков для записи за счёт выкидывания гласных в русском вряд ли получится, потому что будет много неоднозначностей (кот, кит, заря, зеро — так, от балды придумала примеры. Можно более показательные найти, думаю).
                    Арабским я не владею, поэтому совсем точно не скажу, но встречала такую аналогию: у нас почти никогда на письме не указывается ударение, но трудности при этом мы испытываем редко. У арабов примерно то же с гласными: их как бы не пишут, но прочитать не проблема: это особенность языка. А там, где нужно железно точно передать чтение, всё равно используются огласовки.

                    С Китабами я похоже запутала немного, просто это очень интересная штука, которая к слову пришлась :)
              +1
              В общем осталось только подобрать функции

              Например, одинаковый словарь у отправителя и получателя. Передаем только индексы слов, получаем уменьшение размера сообщения.

              В русском языке несколько миллионов словоформ. То есть, достаточно около 3 байт на слово. Старший бит можно сделать признаком знаков препинания, для них достаточно одного байта.

              000000 80 000001 81 000002 81 000003 80 000004 82 (20 байт)
              Пздрвл тб,Шрк,т блбс! (21 байт)

              Можно еще биты поэкономить.
                0
                Да, при этом мы размениваем рост размера словаря на объём передаваемой информации и т.к.формула энтропии устроена так, что в балансируются вероятности появления символов, то мы сможем оптимизировать алгоритм арифметического сжатия. Но при этом мы полностью передадим информацию содержащуюся в сообщении. Мне же думается, что можно построить функции, одна из которых сначала частично отбросит не только данные, но и информацию, а другая восстановит её. И такая, что пригодна не только к осмысленным текстам, но и к данным т.е. переложить на C++/
                  0
                  Отбрасывание и угадывание информации — это частный случай способа со словарем, только на более высоком уровне — на уровне семантики, а не данных. В этом примере словарем выступает мультфильм «Простоквашино».
                  Информацию в осмысленном тексте можно восстановить по семантике соседних слов, для произвольных данных это невозможно (00 ?? — какой следующий байт я загадал). Всегда будет какое-то подмножество сообщений, размер которых после применения всех функций увеличится.
                    0

                    :) Конечно по такому маленькому "хвосту" восстановить нереально. Но насчёт невозможности не уверен т.к. противоречий с теорией информации нет.
                    Спасибо за комментарии и, кстати, с наступающим.

                      0
                      Действительно, доподлинно неизвестно — как звали фараонов Египта… Например, как звучало имя того, кого мы именуем Тутунхамоном — может быть, это был Титинхамен? В письменных источниках, откуда мы знаем эти имена, не было обозначения гласных звуков — считалось, что любой грамотный человек сам должен знать, где какая гласная буква проставляется… Так что теперь, когда у нас нет древних «словарей» (пусть даже в неявной форме), мы не можем восстановить «сокращённую» информацию, нам приходится угадывать (возможно, руководствуясь теми или иными принципами, но кто сказал, что они остались неизменными за всё это время?).
                        0

                        Добрый вечер!


                        Тут идея скорее в том, что не всё можно восстановить однозначно, по неполной информации и без ключа, а раз так, то перехватывать неполные данные — существенно меньше смысла чем полные.

                    0
                    Пустить побитно «пузырёк», и записать «дела» функции?)
                      0
                      Можно и по «Пифагорить».
                      C^2+остаток = (А^2 +B^2) +остаток = (огромный 1011001110001......)+(остаток ...011)= files.txt
                      Подмена «блока» файла
                      С^2=(А^2 + B^2) числом (A^2-B^2), получим (мелкий ...10001)+(остаток ...011)=files.arh
                      только нужны большие и «чистые» Пифагоровы числа вида 3;4;5, и чтобы разность была
                      A-B=1 для минимальности(архива) и однозначности(распаковки). Даже тут на «мелочи»
                      экономия 40%
                      25 = 1 1 0 0 1,
                      7 = 1 1 1
                        0

                        Правильно понимаю тему, что экономия возникает, за счёт того, что разность представима числом заметно меньшей размерности чем каждое из слагаемых?

                          0
                          Да.И это показуемо ) примерно так…
                          10^2 — 9^2 — 8^2 — 7^2 — 6^2 — 5^2 — 4^2 — 3^2 — 2^2 — 1^2 — 0^2
                          … 19 17 15 13 11 9 7 5 3 1
                          … однозначность результатов на это можно оперется.
                            0
                            Число 181 = 10110101 можно заменить 19 = 10011
                              0

                              Для понимания
                              1) если представляем 181 = 10^2+9^2 => 10^2-9^2 => 19
                              2) 147 = 9^2+8^2+2 => 9^2-8^2+2 = 19


                              или какая-то другая схема?

                                0
                                Другая.Хвостик не плюсуется, но бинарно пристыковывается(лего)
                                  0
                                  Хвостики это «часть первого результата», когда с огромным числом закончатся преобразования,«хвостики»(лего) станут следующим числом для работы
                                    0
                                    В смысле «Хвостик числа», это «остаток» или как в химии «осадок 1», ....., «осадок N», и легообразно «склеившись» по правилам, они ведь «не размешаны» значит могут выступать как следующее рабочее число.
                                      0

                                      Т.е. правильно понял алгоритм
                                      на примере 15||2


                                      • Вариант 1 15||2 => 15^2||2 => 113^2-112^2||2 => 113^2||2 => 12769||2 =>12771- это и есть исходное сообщение. должно работать ввиду однозначности троек такого типа
                                      • Вариант 2 15||2 => (2*7+1)||2 => (8^2-7^2)||2 =>(8^2+7^2)||2 = 113||2 => 115
                                        0
                                        А теперь плавно можно перейти к теме «инструкция в „код-цвет“», который объяснит компрессору сколько раз нужно приложиться этим методом к «Гамлету» Шекспира (12771), чтобы получился Бедный Йорик(15II2)....)))
                                          0
                                          Я представлял это как 12771=>12769||2 => 113^2||2 =>
                                          => 8^2 + 7^2||2 => 8^2 — 7^2||2 => 15||2 и обратно
                                            0
                                            … или дальше 15||2 => 3^2+2^2||2||2=> 3^2 — 2^2||2||2=> 5||2||2 =>
                                            => 2^2+1^2||2||2 => 2^2 — 1^2||2||2 => 3||2||2 => 11 10 10
                                              0
                                              тут надобно момент появления хвоста числа, или его не появления как-то отмечать
                                    0
                                    Много-много раз пропустив число через этот компресс можно получить желаемое сжатие.
                                0
                                > Ввиду того, что сообщения на естественном языке содержат объём данных, больший чем объём информации, то если предварительно сжать исходное сообщение при помощи какого-либо из алгоритмов, обеспечивающих эффективное устранение избыточности, например, арифметического кодирования.

                                … то что?

                                Такое впечатление, что в этом предложении демонстрируется передача информации с потерей большей, чем допустимая по информационной емкости.
                                  0

                                  Тут скорее высказывается предположение, о том, что можно можно можно сократить не только объём данных, но и объём информации в передаваемом сообщении. Почему это может быть интересно — усложнить восстановление без ключа, который нужен не только для того, чтобы закодировать, но и для того, чтобы выделить общую с исходным сообщением информацию и не передавать её.
                                  Почему вроде бы можно: в некоторых случаях человек это может сделать, не нарушается теория информации.
                                  А вот вопрос как алгоритмизировать восстановление именно отброшенной информации- пока вопрос.

                                  0
                                  Много достаточно очевидных заявлений, приправленных формулами.
                                  Так в чем основная суть статьи?
                                    0

                                    Чутка выше написал — предположение, о том, что можно можно можно сократить не только объём данных, но и объём информации в передаваемом сообщении. Почему это может быть интересно — усложнить восстановление без ключа, который нужен не только для того, чтобы закодировать, но и для того, чтобы выделить общую с исходным сообщением информацию и не передавать её.
                                    Почему вроде бы можно: в некоторых случаях человек это может сделать, не нарушается теория информации.
                                    А вот вопрос как алгоритмизировать восстановление именно отброшенной информации- пока вопрос.

                                      0
                                      Алгоритмизировать для кого? Для человека или для машины.
                                      В вашем контексте этого непонятно. Под ключом вы понимаете словарные таблицы или что?
                                      Я бы предложил вам начать с терминологии. И многое само встанет на места.
                                        0

                                        Спасибо за уточнения — надо будет написать более строго. Под ключом понимаю


                                        • для сжатия по объёму данных словарь;
                                        • для отбрасывания информации некую строку с более или менее равномерно распределенными символами [0,1].

                                        А так да, для компьютера конечно. Человеческий фактор — для примера.


                                        С наступающим.

                                          0
                                          Спасибо. Вас тоже с наступающим.
                                          Трудовых свершений вам в новом году.
                                    0
                                    В свое время, когда интернет был маленьким, думал о видеокодеке на похожем принципе, с базой готовых паттернов из набора n*n пикселей, пусть бы весил под гиг, зато фильмы весили бы пару мб.
                                      0

                                      Наверно, при кодировании без потерь номер паттерна будет иметь ту же длину, что и сам паттерн.

                                        0
                                        думал использовать принцип схожий с жпег кодированием, подбор близких паттернов, + светлее/темнее.
                                        0
                                        Рекурсия… Создание серии энциклопедий — паттернов, кто кому что сказал. На основе этих энциклопедий — компиляция, и отсылка. И получение с декомпиляцией. Допустима подмена энциклопедий, что создаёт механизм вариантности.
                                        +2
                                        Есть предложение по названию кодека
                                        “Пздрвл тб, Шрк, т блбс!”

                                        image
                                          +1
                                          Эти средние числа не могут дать никаких точных оценок для конкретного сообщения. Какое-то нельзя за 19 байт передать, а какое-то и за 18 можно. У Шеннона много оговорок про бесконечные величины, и одно конкретное сообщение всегда можно уложить в 1 бит, а вот как ваш алгоритм будет работать с любым сообщением любой длины… И ссылочки про энтропию сомнительны, там почему-то 32, а не 33 буквы рассматривают, а тут ещё знаки препинания, а потом и нерусские слова многие любят использовать в русской транскрипции.
                                            0
                                            Более того, если вы попробуете архиватором сжимать стенограмму этого мультика, получается лучше, чем 4,42 бит/символ… Однако никаких теорем Шеннона архиватор не нарушит.
                                              0

                                              Вечер!
                                              Т.к. текст в принципе легко сжимаем, то хотелось нестрого "на пальцах" показать, что


                                              1. вопрос сжатия меньше предела, который можно добиться при помощи алгоритмов архивирования ставить корректно
                                              2. если построить обратимую функцию, которая выделяет общую информацию у передаваемых данных и ключа, то эти данные нет необходимости передавать.
                                              3. если нет необходимости что-то передавать, то и нет возможности это перехватить
                                                0
                                                0) Текст легко сжимаем, т.к. он закодирован с большим избытком… там 6 бит из 8 для текста точно достаточно.
                                                2) Я бы хотел уточнить, что такое «ключ» это словарь, шифроблокнот или алгоритм, который нужно знать всем?
                                                3) Кто-то не знающий алгоритм/словарь/блокнот не должен что-то перехватить?
                                                  0

                                                  2) Ключ скорее, похоже на шифроблокнот т.е. данные которые есть только у обменивающихся сообщениями, хотя шифроблокнот, наверное, слишком громкий термин.
                                                  3) Да, не должен.

                                                    0
                                                    Идея описания на пальцах состоит в том, чтобы использовать имеющиеся всем понятные термины, которые есть у всех (пальцы), без введения новых.
                                                    Таким образом Вы предлагаете, Шарику и Матроскину обменяться словарём русского языка и словарём типовых фраз из кинофильмов, при этом, оставив в секрете для Печкина структуру этих словарей?
                                                      0

                                                      Не совсем так.
                                                      Если просто обменяться словарями, то придётся передавать код слова, что никак не влияет на количество информации и активно используется для сжатия трафика.


                                                      Если же не заменять слово его кодом, а отбрасывать его часть, то тот кто знает что отбрасывали может восстановить исходное сообщение. Т.к. язык штука мощная — видимо, зря такой пример использовал — по контексту легко восстанавливаем.


                                                      Давайте предположим, что речь идёт не об осмысленном тексте, а об обмене данными между софтами и если что-то выкинуть из отправляемого сообщения, получатель, если не предпримет дополнительных усилий по восстановлению исходного сообщения, то и принять его не сможет.


                                                      В общем поэтому и попытался обойтись без "многоматематики".

                                                        0
                                                        Чтобы на приёме можно было распарсить сжатие нужно иметь этот словарь (ну там или нейросеть обученную на этом словаре, что суть та же).
                                                        Имея просто даже словарь, будем иметь кучу вариантов от «Прфсср, кнчн»:
                                                        -профессура окончена
                                                        -профессор конечн
                                                        -профессора иконочная
                                                        Кто знает алгоритм со словарём поймёт всё.
                                                          0
                                                          «если что-то выкинуть из отправляемого сообщения, получатель, если не предпримет дополнительных усилий по восстановлению исходного сообщения, то и принять его не сможет.»
                                                          — Мысль интересная, но это больше относится к шифрованию, а не архивированию. Вы пытаетесь не передавать часть информации, «защищая» ее, подразумевая, что у отправителя и получателя уже имеется ключ (последовательность недостающих бит или алгоритм ее генирирующий), добавив который к исходному сообщению — получим/восстановим всю информацию в нем. При этом, надо понимать, что отправитель создавая сообщение, создает и ключ, который тоже должен быть передан получателю, что в сумме никак не уменьшает общее кол-во информации переданной получателю (в сравнении с обычной передачей архивированной информации).

                                                          В случае же с архиваторами, такие ключи либо сразу имеются у отправителя и получателя (открытые одинаковые словари) либо ключ/словарь передается открыто вместе с сообщением.

                                                          Поэтому:

                                                          1. вопрос сжатия меньше предела, который можно добиться при помощи алгоритмов архивирования ставить корректно
                                                          — Верно

                                                          2. если построить обратимую функцию, которая выделяет общую информацию у передаваемых данных и ключа, то эти данные нет необходимости передавать.
                                                          — Не верно, т.к.

                                                          если ключ это одинаковые словари у отпр/получ — то индексы слов передавать в любом случае надо.

                                                          если ключ это набор недостающей информации — то ключ тоже надо передавать иначе восстановление будет невозможно.

                                                          если ключ это просто дополнительный набор бит-информации, то теоретически, можно в нем найти повторяющиеся элементы и создать словарь ключа, заменяя в сообщении некоторые слова индексами не из общего словаря, а индексами из словаря ключа. Это и есть ваша обратимая ф-ция. Но, не забывайте, что ключ все равно как-то надо передавать получателю. Т.е. мы просто словарь разбиваем на открытый и закрытый, сокращая по нему кол-во передаваемых данных как в обычном архиваторе, что кол-во передаваемых данных никак не уменьшает по сравнению с обычным словарем.

                                                          3. если нет необходимости что-то передавать, то и нет возможности это перехватить
                                                          Это, конечно верно :)

                                                            0

                                                            К п.2 могу добавить, что здесь в любом случае ключ передавать придётся — если по открытому каналу — то будет просто сжатие, если отдельно от сообщения — получается, что защита информации возможна, как доп. нагрузка.


                                                            Что касается словаря — то думал — в чистом виде не очень применимо, т.к. Вы верно заметили, что его тоже сначала надо бы передать.


                                                            Сейчас вроде бы получается доказать, что можно обойтись без словаря, воспользовавшись тем, что сумма последовательности "0" и "1" является возрастающей (если совсем строго, то неубывающей ) и, соответственно может превзойти некоторые наперёд заданные значения, а если в этих позициях стоят подряд, например, 2 единицы и в ключе единица, то первую "1" можно отбросить и не передавать. Соотв. потом восстановить можно т.к. у получателя тот же ключ. Если же в очередной позиции ключа "0" соотв. последовательность можно инвертировать "0"<=>"1", что позволяет провести те же рассуждения. Вот то, что строго сейчас надо будет описать.

                                                              0
                                                              Ага, только при этом надо еще передать признак — инвертировали бит в этом месте или нет.
                                                                0

                                                                Не надо — это может быть либо регулярная операция (т.е., например, когда сумма равна N), либо данные в ключе.

                                                                  0
                                                                  11101100 - сообщение
                                                                  10101010 - ключ
                                                                  
                                                                   110 100 - отбросили дублирующиеся единицы, там где в ключе 1
                                                                  10101010
                                                                  
                                                                  110100   - приняли сообщение
                                                                  10101010 - ключ
                                                                  первый бит 1, в ключе 1, добавляем единицу
                                                                  
                                                                  1110100
                                                                  10101010
                                                                  третий бит 1, в ключе 1, добавляем единицу
                                                                  
                                                                  11110100 - восстановленное сообщение
                                                                  11101100 - исходное сообщение
                                                                  упс
                                                                  
                                                                    0

                                                                    Видел эту тему немного по другому (пример, понятно подстроен под возможность восстановления):


                                                                    • "11101100" — сообщение
                                                                      • "1" — ключ
                                                                      • устанавливаем пороговую сумму = 4 и считаем когда мы её превысим
                                                                      • соотв. "11101^100" — вот здесь можно выкинуть 1 => "1110100"
                                                                      • дальше обратное преобразование при той же пороговой сумме получаем, что "1" надо добавлять "1110^100"

                                                                    Так вроде совпадает исходное и конечное.

                                                                      0
                                                                      Ок, мы получили сообщение 1110100000000000. Как узнать, надо ли туда добавлять 1 при превышении порога 4, или оно такое и было?
                                                                        0

                                                                        Никак. Контрпример — чего :). Неправ и с примером и с алгоритмом. Т.к. нарушается однозначность восстановления.


                                                                        Некорректно пересёк текст и ключ.

                                                                0
                                                                Проблема в том, что передаваемые данные в общем случае не зависят от ключа, а вы как раз таки пытаетесь восстанавливать обрезанные биты сообщения по ключу, что приводит к неоднозначности интерпретации обрезанного сообщения.

                                                                На мой взгляд есть только один способ изъять информацию из сообщения и потом восстановить ее. Это возможно только при условии, что данная информация ВСЕГДА присутствует в сообщении. Например, мы знаем, что 10й бит в сообщении всегда 1, тогда да, этот бит можно не передавать и длина сообщения уменьшится на 10%. Но естественно, мы должны один раз сообщить об этом получателю, либо он должен обладать этой информацией по умолчанию.

                                                                Еще пример, договорится, что 10ым битом сообщения всегда должен быть некоторый циклически перебираемый по порядку бит ключа, тогда этот бит можно убрать из сообщения. Соответственно, тогда любое сообщение мы отправить в исходном виде не сможем, нам надо будет его «подготовить» в соответствии с нашей договоренностью. При этом и сам ключ должен быть передан получателю.

                                                                Философский смысл здесь такой — мы можем исключить из сообщения только ту информацию, которая уже есть у получателя.
                                                                  0
                                                                  «Философский смысл здесь такой — мы можем исключить из сообщения только ту информацию, которая уже есть у получателя.»…
                                                                  Алфавит!))
                                                                    0
                                                                    Перейти на символизм Египта или глаголицу.)
                                                                      0

                                                                      Вот по этому и написал, что исключать надо не то, что есть у получателя — в этом нет смысла, а пересечение того, что есть у двух сторон и того, что надо передать.


                                                                      ^^Выше писал^^Сейчас вроде бы получается доказать, что можно обойтись без словаря, воспользовавшись тем, что сумма последовательности "0" и "1" является возрастающей (если совсем строго, то неубывающей ) и, соответственно может превзойти некоторые наперёд заданные значения, а если в этих позициях стоят подряд, например, 2 единицы и в ключе единица, то первую "1" можно отбросить и не передавать. Соотв. потом восстановить можно т.к. у получателя тот же ключ. Если же в очередной позиции ключа "0" соотв. последовательность можно инвертировать "0"<=>"1", что позволяет провести те же рассуждения. Вот то, что строго сейчас надо будет описать.

                                                                        0
                                                                        Ну если получается, то конечно пробуйте продолжать :)
                                                                        Просто на то, что вы писали выше, я выше же и ответил… Поясню еще раз: передаваемые данные не зависят от ключа, соответственно от пересечения с ключом они тоже не зависят.

                                                                        То, что в предлагаемом вами варианте есть коллизии писал и я и michael_vostrikov.
                                                                        Подумайте, вот мы пытаемся восстановить переданное сообщение, посчитали заранее заданное значение и видим в сообщении 1 в ключе тоже 1, по описанной вами логике мы должны добавить(восстановить пропущенную 1), но представьте, что в исходном сообщении за 1 изначально следовал 0 (т.е. 2х подряд 1ц не было) и мы ничего не обрезали, а значит и добавлять/восстанавливать 1цу не должны. Вот и вопрос — как без доп.информации вы можете утверждать, надо ли восстанавливать 1цу или не надо???

                                                                          0

                                                                          В случае если критерии удаления не выполняются, ничего не удаляем, — бежим по сообщению дальше. Соотв. не надо удалять 1. По тому же критерию единицу не надо будет восстанавливать.

                                                                            0
                                                                            «По тому же критерию единицу не надо будет восстанавливать. „
                                                                            — к сожалению, вы пока никак не поймете, что такого критерия нет.

                                                                            Хм, похоже пока не закончите свое доказательство, вам возникающую проблему трудно воспринять :) Просто попробуйте следуя своей же логике передать и восстановить 2 сообщения:
                                                                            [Исходное]->[Передаваемое]->[Восстановленное]
                                                                            1) 111101000 -> 111101000 -> 111101000
                                                                            2) 111101100 -> 11110100 -> 111101?00
                                                                            Так называемое наперед заданное значение = 5

                                                                            По какому критерию определяется наличие/отсутствие 1цы на месте знака вопроса?
                                                                              0

                                                                              Ок, Вы правы, так информации недостаточно. Хотя может быть сам факт передачи будет служить признаком того, что сообщение удовлетворяет критерию изъятия т. е., например, при пределе =5
                                                                              1) 111101000 — ждём последующих символов
                                                                              2) 1111011 || 00 -> 111101 -> 1111011
                                                                              00 — ждём


                                                                              При пределе = 4
                                                                              1) 111101|| 000 -> 11110 -> 111101
                                                                              000 — ждём
                                                                              2) 111101 ||100 -> 11110 -> 111101
                                                                              100 — ждём


                                                                              При пределе = 3 — аналогично 4


                                                                              При пределе = 2
                                                                              1) 111||101000 -> 11 -> 111
                                                                              101000 — ждём
                                                                              2) 111||1011||00 -> 11||101 -> 111||1011
                                                                              00 — ждём


                                                                              Хотя так не очень понятно, что делать с последним сообщением.

                                                                                0
                                                                                Хм, ну тут у вас уже троичная система вводится [ (0),(1),(||) ]
                                                                                При таком раскладе маркером изъятия 1 как раз и служит задержка, являющаяся 3им состоянием линии связи. А в троичной системе сообщение можно представить гораздо короче без изъятий 111101100 -> 200020 или в вашем представлении: || 000 || 0. Если захотим изымать и отсюда, то придется вводить еще один тип задержки 4е состояние, которое в четверичной системе опять будет проигрывать по длине представления… и т.д… Это бесперспективный путь. Примерно тоже самое, что создать дополнительную линию связи по которой передавать только признаки изъятия типа:

                                                                                1111011000 -> 111101000 ->
                                                                                ----------------------------------> 1111011000
                                                                                -------------------000001000 ->

                                                                                Вместо того чтобы, передавать информацию по обеим линиям повышая скорость передачи в 2 раза

                                                                                1111011000 -> 11110 ->
                                                                                ----------------------------------> 1111011000
                                                                                --------------------11000 ->

                                                                                Думаю, идею с изъятием информации из сообщения и последующем восстановлении можно реализовать только в том смысле, о котором я писал ранее выше в сообщениях. Но вполне возможно, что есть еще варианты.
                                                    0
                                                    «Соответственно интересным является вопрос о том, можно-ли не нарушая положения теории информации передать сообщение объёмом меньше, чем минимальный объём, который может быть достигнут при самом лучшем сжатии данных.»
                                                    МОЖНО!… Взглядом!))… когда сообщение одной цифрой через «шрифт» и «цвет» будет указывать на сервис взглядов жён!)))… а там за каждым номером туча алгоритмов!)))
                                                      0

                                                      :) Если воспринимать шрифт и цвет как разные символы, то количество информации по сути то же!!! :)

                                                        0
                                                        Допустим, каждая буква цвет-кода указывает на метод сжатия применимый к информации как-бы #4145A т.е применён алгоритм 4, затем 1,… А и получилось в остатке число 10100101. В ответе останется архив с содержанием 10100101+#4145A.servis.opps(пример)
                                                      0
                                                      «Поздравляю тебя, Шарик, ты балбес!» можно описать как «Пт, Ш, тб!+код цвета(указатель на группу алгоритмов сервиса специального сервера)»
                                                        0

                                                        Если эти данные войдут в ключ- да.ок.


                                                        Раз уж новый год, то всё жду когда напишут "Прфсср, кнчн, лпх, но ппртр пр нммм, пр нммм! Кк слшн?" :)

                                                      0
                                                      Хотите ещё поле для деятельности, у нас был один преподаватель, который предлагал следующий метод сжатия для телевидения:
                                                      Иметь у каждого пользователя огромный магазин звуков и изображений, а передавать ему только сценарий фильма, типа идёт дождь (подгружаем звук дождя из базы), актёр1 говорит актёру2: " *** ** " (генерируем голос из текста)…
                                                      Однако передача информации с такими потерями мало кому нужна, краткое содержание Войны и мира для школьников и то полезнее.
                                                        0
                                                        У меня была идея сделать рекламный фильтр на телевизор схватывающий первые ноты рекламы в чёрный список и уходящий на другой канал)
                                                          0
                                                          Хорошо, что для тех, кому интернеты заменили телевизер, который кому-то заменил природу, уже сделали адблокплюс))
                                                          0
                                                          … и кстати, что делать с «кратким содержанием» это забота онлайн-сервера. У пользователя только хэши (номера инструкций сервера на добавление и раздувание числа +осадок числа)
                                                            0
                                                            … и сервер может вернуть пользователю уже эксклюзивный набор методов для распаковки его файла на его «машине».
                                                          0
                                                          Соответственно интересным является вопрос о том, можно-ли не нарушая положения теории информации передать сообщение объёмом меньше, чем минимальный объём, который может быть достигнут при самом лучшем сжатии данных.

                                                          Насколько хорошо ваше "самое лучшее сжатие данных"?


                                                          По опыту знаю, что если обработать исходные данные примитивным сжатием с учётом специфики данных (дельта-кодированием, или просто удалить повторяющиеся нули, наподобие RLE; или в некоторых случаях записать матрицы по столбцам, а не по строкам), то архиваторы начинают справляться лучше (иногда — сильно лучше). Так что, если ваше "самое лучшее сжатие" не обеспечивает теоретического минимального объёма, то ответ — "можно".


                                                          Чтобы получить близкий к теоретически минимальному объём, нужно кодировать сообщения с существенным учётом контекста.
                                                          Как минимум, если это речь — нужно кодировать семантику, а не слова (что-то вроде Лингва Технис у Адептус Механикус, хотя это вымышленный язык).
                                                          Например, «Поздравляю тебя, Шарик, ты балбес!», может кодироваться как
                                                          ( :обращение-к=Шарик :истинность=:сарказм :я :поздравляю :тебя ( :ты :есть :балбес))
                                                          где : слово — некоторые понятия из известного обоим сторонам словаря. Подобным способом можно однозначно и без потерь закодировать любое выражение языка, любую мысль. (а вот мой пример получился неоднозначным)


                                                          Контекстное кодирование может дополнительно уменьшить объём данных, например, если речь идёт о том, произошли ли события А, В, С,D то достаточно 4х бит, если есть дополнительные известные обоим сторонам причинно-следственные связи, то может быть достаточно меньшего числа бит.
                                                          Арифметическое кодирование дополнительно может упаковать сообщения с нецелым количеством бит информации.


                                                          А слова из букв идеально не сжать, по крайней мере без знания языка архиватором. Они сами по себе имеют избыточность; для архиватора, не имеющего хорошей модели языка, сложно её обработать корректно и полностью.

                                                            0

                                                            Спасибо.


                                                            Под "самым лучшим сжатием" имел ввиду не столько достижение теоретического предела, сколько возможность легально перейти эту грань.


                                                            Скажите пожалуйста, есть ли нормальные материалы по кодированию семантики? Т.к. нашёл либо работы лингвистов-теория, либо программистов — нейросети, а вот на стыке пока не нашёл.

                                                              0
                                                              Шекспировская рифма можно в переводе Пастернака)
                                                                0
                                                                Можно начать с «Теории фреймов» Минского (краткая «реклама» фреймового подхода для ваших задач: http://www.rusnauka.com/17_APSN_2009/Philologia/48463.doc.htm)

                                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                            Самое читаемое