Alex_D* ::: сообщение от 18.02.2008 | 22:13

Мастер (ур.17) Очки: 34250 И-554 | Т-1144 | К-569 А-904 | Ю-57 Тв. работ: 107 Рег: 27.04.2006 (34)

Итоги пятого тура Apis 1. Алгоритмы сжатия данных 1) Алгоритмы сжатия без потерь: • Преобразование Барроуза-Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь • Преобразование Шиндлера (англ. ST) — модификация преобразования Барроуза-Уилера • Алгоритм DEFLATE (англ.) • Дельта-кодирование — эффективно для сжатия данных, в которых последовательности часто повторяются • Инкрементное кодирование — дельта-кодирование применяемое к последовательности строк • Семейство алгоритмов словарного сжатия Лемпеля-Зива: o LZ77 — родоначальник семейства LZ77-алгоритмов ? LZ77-PM ? LZFG ? LZFG-PM ? LZP ? LZBW ? LZSS ? LZB ? LZH ? LZRW1 o LZ78 — родоначальник семейства LZ78 алгоритмов ? Алгоритм Лемпеля-Зива-Велча (также известен как англ. LZW) — сжатие без потерь ? LZW-PM ? LZMW o LZMA — сокращение от англ. Lempel-Ziv-Markov chain-Algorithm o LZO — алгоритм компрессии данных ориентированный на скорость • Алгоритм сжатия PPM • Кодирование длин серий (Групповое кодирование, также известен как англ. RLE) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений • Алгоритм SEQUITUR (англ.)— сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных • Вейвлет-кодирование на основе вложенных нуль-деревьев (англ.) (EZW-кодирование) • Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов o Кодирование Шеннона-Фано — самый простой алгоритм кодирования o Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев ? Адаптивное кодирование Хаффмана (англ.) — техника адаптивного кодирования, основывающаяся на коде Хаффмана o Усечённое двоичное кодирование (англ.) — используется для однородного вероятностного распределения с конечным алфавитом o Арифметическое кодирование — развитие энтропийного кодирования ? Адаптивное арифметическое кодирование — техника адаптивного кодирования, основывающаяся на арифметическом кодировании o Кодирование расстояний (англ.) — метод сжатия данных, который близок по эффективности к арифметическому кодированию • Энтропийное кодирование с известными характеристиками o Унарное кодирование — код, который представляет число n в виде n единиц с замыкающим нулём o дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа o Кодирование Фибоначчи (англ.)— универсальный код, который кодирует положительные целые числа в двоичные кодовые слова o Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением o Кодирование Райса (англ.)— форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением. 2)Алгоритмы сжатия с потерями • Линейное предсказывающее кодирование (англ.)— сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде • А-закон — стандартный алгоритм компандирования. Применяется в РФ. • Мю-закон — стандартный алгоритм компандирования • Фрактальное сжатие — метод, использующий фракталы для сжатия изображений • Трансформирующее кодирование (англ.) — тип сжатия данных для «естественных» данных, таких как аудио-сигналы или фотографические изображения • Векторная квантизация (англ.)— техника, часто используемая в сжатии данных с потерями • Вейвлетное сжатие — тип компрессии данных хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио) В ответе просто перечислены названия каких-то алгоритмов с некоторыми пояснениями. По-моему, концептуально описан тут лишь метод «Кодирование длин серий». И то поверхностно. Но такое ощущение, что пользователь не слишком вдавался в подробности задания. За это назначаю 0,5 штрафных балла. Итог за задание: 2 - 0,5 балла (L) 2. 1) Хэш - это комбинация цифр и букв для однозначной идентификации файла. Хэш не зависит от имени файла, только от его содержимого. Это позволяет находить источники файла независимо от того, какое имя тот или иной пользователь дал файлу. 2) MD5 (Message Digest 5) — 128-битный алгоритм хэширования, разработанный профессором Рональдом Л. Ривестом в 1991 году. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Пришёл на смену MD4, который был несовершенен. 3) SHA (Secure Hash Algorithm 1) — один из алгоритмов криптографического хэширования. Описан в RFC 3174. Разработан в 1995 году. Имеет длину результирующего дайджеста 160 бит, существуют варианты (SHA-256, SHA-384, SHA-512) с более длинным дайджестом. Используется в качестве основного хэш-алгоритма в PGP. 4) GPG (GNU Privacy Guard, GnuPG, GPG) — свободная альтернатива набору криптографического ПО PGP, выпущенная под лицензией General Public License. Является частью проекта GNU, получила гранты от Германского правительства. GnuPG полностью совместим со стандартом IETF OpenPGP. Текущие версии GnuPG могут взаимодействовать с PGP и другими OpenPGP-совместимыми системами в режиме совместимости. GnuPG позволяет шифровать и подписывать данные в целях безопасного хранения и передачи информации. С этим вопросом участник разобрался лучше! Хороший ответ! Итог за задание: 4 балла (L) 3. На мой взгля закодировать текстовую информацию прощего всего в "Документ Microsoft Word" Алгоритм кодирования информации: 1)В меню Файл выберите команду Сохранить как. 2)В поле Имя файла введите новое имя файла. 3)В поле Тип файла выберите Обычный текст. 4)Нажмите кнопку Сохранить. 5)В группе Кодировка текста выберите необходимый параметр. Чтобы использовать стандарт кодировки, установленный по умолчанию, выберите параметр Windows (по умолчанию). Чтобы использовать стандарт кодировки MS-DOS, выберите параметр MS-DOS. Чтобы указать определенный стандарт кодировки, выберите параметр Другая, а затем выберите нужный стандарт кодировки из списка. В поле Просмотр можно просмотреть текст в выбранной кодировке. Я советую использовать кодировку под рубрикой Другая, это даст вам большие гарантии, что никто посторонний не раскодиреут. Ответ некорректен. Дана "инструкция для программиста-неудачника" Как ты себе представляешь ситуацию? Пользователь программы сохранил изменения, после этого прибегает программист, открывает документ в MS Word, меняет быстренько кодировку, сохраняет и убегает? Программа при сохранении должна записывать уже закодированные данные. Более того, программная запись в формате MS Word потребует дополнительных и неоправданных усилий со стороны программиста, если он решится на это. Этот формат - для комфортной работы пользователей. Но все-таки идея реализуема (doc, по сути, кодированный файл, но если сохранить расширение, то пользователю не составит труда прочитать содержимое). Полбалла за "юмористичность" Итог за задание: 0,5 балла (A_D) воркута 1. Алгоритмы сжатия данных - это избавление от избыточных данных, осуществляемое по алгоритму эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее, это сжатие без потери кода, .Алгоритмы сжатия применяются для сжатия мультимедийных данных. Например, возьмем обычный текстовый файл и удалим из абзацев все символы переноса строки, заменим в файле все цепочки пробелов в начале абзацев на символ табуляции, а также удалим все незначащие пустые строки и сохраним текстовый файл. Тем самым мы получили точно такой же читаемый (текстовый) файл с неизмененной информацией, но меньшего размера. Все алгоритмы по своим свойствам очень сходны. Чем больше качество файла, тем больше дискового пространства он занимает. Не рассмотрено ни одного реального алгоритма. Читай ответы других кучастников Итог за задание: 0 баллов (L) 2. Хеш (цифровая подпись) -используются обычно для генерации дайджеста сообщения при создании цифровой подписи. Хэш-функции отображают сообщение в имеющее фиксированный размер хэш-значение таким образом, что все множество возможных сообщений распределяется равномерно по множеству хэш-значений. При этом криптографическая хэш-функция делает это таким образом, что практически невозможно подогнать документ к заданному хэш-значению. Криптографические хэш-функции обычно производят значения длиной в 128 и более бит. Это число значительно больше, чем количество сообщений, которые когда-либо будут существовать в мире. MD5 (Message Digest 5) — 128-битный алгоритм хэширования, разработанный профессором Рональдом Л. Ривестом в 1991 году. Он предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Пришёл на смену MD4, который был несовершенен. Secure Hash Algorithm 1 — один из алгоритмов криптографического хэширования. Был разработан в 1995 году в качестве замены более слабого алгоритма SHA. Имеет длину результирующего дайджеста 160 бит, существуют варианты (SHA-256, SHA-384, SHA-512) с более длинным дайджестом. Он используется в качестве основного хэш-алгоритма в PGP. GPG — свободная альтернатива набору криптографического ПО PGP. GnuPG полностью совместим со стандартом IETF OpenPGP. Текущие версии GnuPG могут взаимодействовать с PGP и другими OpenPGP-совместимыми системами в режиме совместимости. GnuPG позволяет шифровать и подписывать данные в целях безопасного хранения и передачи информации. Не дано четкое определение Хэшу. Итог за задание: 3 балла (L) 3. Для таки нужд я бы воспользовался программой File Encryption XP. Эта программа предназначена для защиты конфиденциальной информации на компьютере. File Encryption XP шифрует любые файлы, в том числе Microsoft Word, Excel и PowerPoint документы, используя сильный Blowfish алгоритм с 384-bit ключом. Пароль шифрованного файла не хранится в контейнере, что делает невозможным взломать защиту. Подобный выбор далек от оптимального. Предположу, что с использованием командной строки все-таки возможно выполнить кодирование и декодирование файла, но о подобных шагах нет ни слова. И "конфиденциальная информация" для заданной ситуации - слишком громко сказано. Предлагаемое решение проблемы намекает на существование некоего вездесущего программиста И еще один момент, учитывая который, я бы отказался от этого решения - продукт не является свободно распространяемым, и за использование его лишь в личных целях придется отдать $29.95 (но ситуация попахивает коммерческим использованием). В ответе дано лишь описание продукта. Итог за задание: 0 баллов (A_D) Semyon 1. Алгоритмы сжатия без потерь: Преобразование Барроуза-Уилера (Burrows-Wheeler transform, BWT, также исторически называется блочно-сортирующим сжатием, хотя сжатием и не является) — это алгоритм используемый в техниках сжатия данных, таких как bzip2. Он был изобретён Майклом Барроузом и Дэвидом Уилером. Дельта-кодирование (Delta encoding) — способ сохранения или передачи данных в форме разницы (дельты) между последовательными данными вместо самих данных. Это часто называется дельта-компрессия, потому что некоторые образцы кодирования могут получать кодированные данные в более коротком виде, чем исходные данные. Инкреме?нтное коди?рование также известное под названием фронтальное сжатие или тыловое сжатие — это тип дельта-кодирования (delta encoding) где общие префиксы или суффиксы и их длины записываются таким образом, что избегается дублирование данных. Этот алгоритм хорошо подходит для компрессии отсортированных данных, например — списка слов в словаре. LZ — семейство алгоритмов словарного сжатия данных. Название получил по инициалам двух исследователей — Абрахама Лемпэла (Abraham Lempel) и Якоба Зива (Jacob Ziv), разработавших в 1970 году алгоритмы LZ77 и LZ78. На базе LZ77 и LZ78, изменяя и комбинируя их с другими методами, исследователями был создан ряд других алгоритмов. Другие алгоритмы семейства LZ — LZO, LZS, LZW, LZC, LZMA. LZ77 и LZ78 - это названия двух алгоритмов сжатия без потерь, опубликованных в статьях Абрама Лемпела (Abraham Lempel) и Якоба Зива (Jacob Ziv) в 1977 и 1978. Эти два алгоритма являются наиболее известными вариантами в семействе LZ*, которое также включает в себя LZW, LZSS, LZMA и другие алгоритмы. Оба алгоритма относятся к словарным методам, в отличие от других методов уменьшения избыточности, таким как RLE и арифметическое сжатие. LZ77 является алгоритмом со «скользящим окном», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78. LZH — формат архивирования файлов, построенный на алгоритме HA, но немного улучшенный. Как и прародитель, разрабатывался для архивирования текстовых файлов. В настоящее время не используется. Алгори?тм Ле?мпеля — Зи?ва — Ве?лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем (Abraham Lempel), Якобом Зивом (Jacob Ziv) и Терри Велчем (Terry Welch). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных. LZMA (сокращение от англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм сжатия данных, разрабатываемый с 2001 года и использованный в формате 7z архиватора 7-Zip. В алгоритме используется схема сжатия данных по словарю, сходная с использованной в LZ77, обеспечивающая высокий коэффициент сжатия (обычно превышающий коэффициент, получаемый при сжатии с использованием bzip2), а также позволяет использовать словари различного размера (до 4 ГиБ). LZO это алгоритм сжатия данных разработанный для достижения максимальной скорости распаковки. LZO — это аббревиатура от фамилий разработчкиков: Lempel-Ziv-Oberhumer (Лемпель-Зив-Оберхеймер). Это алгоритм сжатия без потерь и его базовая реализация может работать в многопоточной среде. Алгоритм PPM (Prediction by Partial Matching — предсказание по частичному совпадению) — это адаптивный статистический алгоритм сжатия данных, основанный на контекстном моделировании и предсказании. Модель PPM использует контекст — множество символов в несжатом потоке, предшествующих данному, чтобы предсказывать значение символа на основе статистических данных. Сама модель PPM лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана, арифметическое кодирование. Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов — это очень простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов. Кодирование энтропии — кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее короткие коды. Кодирование Шеннона-Фано (англ. Shannon-Fano coding) - алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделированя нулевого порядка). Подобно алгоритму Хаффмана алгоритм Шеннона-Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, т.е. заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов - более длинными двоичными последовательностями. Алгоритм Хаффмана (англ. Huffman) — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее время используется во многих программах сжатия данных. В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами. Этот метод кодирования состоит из двух основных этапов: 1. Построение оптимального кодового дерева. 2. Построение отображения код-символ на основе построенного дерева. Арифметическое кодирование - обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H бит, где H — информационная энтропия источника. В отличии от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например для строки бит 010101...0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше. Адаптивное арифметическое кодирование Для арифметического кодирования существуют также адаптивный алгоритм, т.е. алгоритм, который при каждом сопоставлении символу кода, кроме того, изменяет внутренний ход вычислений так, что в следующий раз этому же символу может быть сопоставлен другой код, т.е. происходит “адаптация” алгоритма к поступающим для кодирования символам. При декодировании происходит аналогичный процесс. Кодирование энтропии — кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее короткие коды. Уна?рное коди?рование — это энтропийное кодирование, которое представляет число n в виде n единиц с замыкающим нулём (либо n нулей и единица). Например 5 представляется в виде 111110. Алгоритмы сжатия с потерями: А-закон — алгоритм сжатия с потерей информации, применяется для сжатия звуковых данных. В телекоммуникациях, мю-закон (?-закон) — стандарт аналогового сжатия, используемый системах цифровой связи Северной Америки и Японии для модификации динамического диапазона аналогового речевого сигнала до оцифровки. Он подобен алгоритму A-закона используемуму в Европе. Фрактальное сжатие изображений - это алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых функций (IFS, как правило являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры - до 1000 раз при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Из-за сложной ситуации с патентованием широкого распространения алгоритм не получил. Вейвлетное сжатие — общее название класса методов кодирования изображений, использующих двумерное вейвлет-разложение кодируемого изображения или его частей. Обычно подразумевается сжатие с потерей качества. Существенную роль в алгоритмах вейвлетной компрессии играет концепция представления результатов вейвлет-разложения в виде нуль-дерева (zero-tree). Упорядоченные в нуль-дереве битовые плоскости коэффициентов вейвлет-разложения огрубляются и кодируются далее с использованием алгоритмов сжатия без потерь. Выделены: дельта-кодирование, LZ-семейство, PPM, Кодирование длин серий, Алгоритм Хаффмана, Арифметическое кодирование, Фрактальное сжатие изображений, Вейвлетное сжатие. Такое впечатление, что участник не читал текст: зачем-то приведены механизмы шифрования, а энтропийное сжатие описано дважды. При анализе текста выявлено абсолютное цитирование страниц Википедии!.. даже не удалены артефакты копи-паста В качестве штрафа назначается ограничение максимальной оценки пунктов в 1 балл и игнорирование алгоритмов, не указанных выше. Положительная оценка поставлена только потому, что для составления этого ответа необходимо хотя бы на низшем уровне просмотреть 24 страницы и выбрать по несколько первых абзацев. Надеюсь, хоть что-то отложится в памяти у участника... Уважаемый Семен, если вы будете продолжать работать в таком духе, то в университете столкнетесь с большими проблемами при сдаче различных работ, т.к. системой "Антиплагиат" стало пользоваться уже немало вузов... Итог за задание: 8-- баллов (A_D, L) 2. Электро?нная цифрова?я по?дпись (ЭЦП)— реквизит электронного документа, предназначенный для защиты данного электронного документа от подделки, полученный в результате криптографического преобразования информации с использованием закрытого ключа электронной цифровой подписи и позволяющий идентифицировать владельца сертификата ключа подписи, а также установить отсутствие искажения информации в электронном документе. MD5 (Message Digest 5) — 128-битный алгоритм хэширования, разработанный профессором Рональдом Л. Ривестом в 1991 году. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Пришёл на смену MD4, который был несовершенен. Описан в RFC 1321 Secure Hash Algorithm 1 — один из алгоритмов криптографического хэширования. Описан в RFC 3174. Разработан в 1995 году в качестве замены более слабого алгоритма SHA. Имеет длину результирующего дайджеста 160 бит, существуют варианты (SHA-256, SHA-384, SHA-512) с более длинным дайджестом. Используется в качестве основного хэш-алгоритма в PGP. На данный момент обнаружена уязвимость, позволяющая за небольшое время находить коллизии. GNU Privacy Guard, GnuPG, GPG — свободная альтернатива набору криптографического ПО PGP, выпущенная под лицензией General Public License. Является частью проекта GNU, получила гранты от Германского правительства. GnuPG полностью совместим со стандартом IETF OpenPGP. Текущие версии GnuPG могут взаимодействовать с PGP и другими OpenPGP-совместимыми системами в режиме совместимости. GnuPG позволяет шифровать и подписывать данные в целях безопасного хранения и передачи информации. 16.02.2008 16:42 Определение Хэша не однозначно. Итог за задание: 3 балла (L) 3. Используем gpg кодирование: $gpg -c some_secret.txt вас попросят ввести два раза пароль для кодирования теперь закодированный файл лежит в some_secret.txt.gpg раскодируем его $gpg some_secret.txt.gpg опять вводим пароль в some_secret.txt снова наш файл Ещё можно закодировать письмо непосредственно при его подготовке к отсылке. Также закодировать файл с текстом письма, выполнив следующие действия: 1. В корневом меню выбрать "Опции". 2. Выбрать "UUENCODE". 3. Программа предложит ввести имя документа. Это можно сделать одним из перечисленных способов. Во-первых - набрать имя файла с указанием полного пути к нему. Во-вторых - нажать. На экран будет выдан текущий каталог жесткого диска. Передвигая курсор по каталогам жесткого диска нужно выбрать файл, который будет закодирован и нажать. Внимание! Закодированный файл будет помещен в тот же каталог, где находится исходный файл, с тем же именем, но с расширением - uue (например letter.uue). Соответственно при отсылке закодированного документа следует обязательно указывать это расширение. Если первая часть ответа содержит здравый смысл и близка к применению в реальной ситуации, то вторая совсем "оффтоп". В задании сказано: "закодировать РАБОЧИЕ файлы созданной вами программы" - почему "мысль ушла" на отправку почтовых сообщений? Положительные баллы списаны штрафными! В использовании gpg-кодирования не учтен факт программного (а не человеческого) управления процессом. Итог за задание: 1-1 балл (A_D) Юлька 1. Методы сжатия изображений SDF – формоопределенные форматы. SDF – один из простейших и наиболее разносторонних форматов. Этот формат определяет графическое изображение как совокупность геометрических фигур и образцов. Таким способом хранятся данные систем автоматизированного проектирования (CAD), так как для них обычно нет необходимости определять значение цвета для каждой точки растра. RLE (Run-Length Encoding) – сжатие длинных последовательностей. Самый простой алгоритм сжатия. С большим успехом применяется по сей день на различных потоках данных, но чаще всего в качестве дополнительного алгоритма сжатия. Наиболее эффективен в примитивных малоцветных изображениях, где существуют довольно большие участки кода, передающего один цвет. Формат PCX – одна из реализаций этого алгоритма. При хорошей реализация алгоритм дает большую скорость преобразований. Основной недостаток описанного алгоритма – невозможность сжатия картинок с большим количеством цветов и оттенков и плавными переходами цвета. RLE используется и в сжатии данных при передаче по каналам связи. Например, реализации модемных протоколов сжатия (MNP) в своей основе используют именно этот алгоритм. LZ – Lempel-Ziv. Это метод словарей, несколько улучшенный алгоритм сжатия изображений, впервые опубликованный в 1977 г. На сегодняшний день LZ-алгоритм и его модификации получили наиболее широкое распространение по сравнению с другими методами сжатия. Принцип в общем похож на RLE. Из повторяющихся участков кода формируется индексированный словарь. А поскольку индекс занимает гораздо меньше места, чем участок кода, получается достаточно эффективный метод сжатия. Основной плюс – сжимаются повторы комбинаций. Основной недостаток – словарь требуется хранить в том же файле. Существует большое число модификаций этого метода LZ – LZW, LZ77, LZSS и т. д. Вероятностные методы сжатия. В основе вероятностных методов сжатия (алгоритмов Шеннона-Фано (Shannon Fano) и Хаффмана (Huffman) лежит идея построения “дерева”, в котором положение символа на “ветвях” определяется частотой его появления. Каждому символу присваивается код, длина которого тем меньше, чем выше частота появления этого символа. Существуют две разновидности вероятностных методов, различающихся способом определения вероятности появления каждого символа: 1. Статические (static) методы, использующие фиксированную таблицу частоты появления символов, рассчитываемую перед началом процесса сжатия на основе анализа фрагмента сжимаемого текста. 2. Динамические (dinamic) или адаптивные (adaptive) методы, в которых частота появления символов все время меняется и по мере считывания нового блока данных происходит перерасчет начальных значений частот. Их несомненным достоинством является создание для каждого конкретного потока данных индивидуального кода, обеспечивающего максимальный коэффициент сжатия. Статические методы характеризуются хорошим быстродействием и не требуют значительных ресурсов оперативной памяти. Они нашли широкое применение в многочисленных программах-архиваторах, например, ARC, ZIP, RAR и т. д. Арифметические методы. В 70-х годах прошлого века были заложены основные принципы арифметического кодирования. Основная идея состоит в том, что берется интервал от 0 до 1, который разбивается на подынтервалы с длинами, пропорциональными вероятностям появления символов в потоке данных. По мере увеличения длины сообщения интервал, необходимый для его представления, становится все меньше и меньше, а число бит, необходимых для задания этого интервала, увеличивается. Каждый символ сообщения по порядку сокращает этот интервал пропорционально вероятности появления этого символа. Наиболее вероятный символ меньше всех сокращает интервал и таким образом добавляет меньше бит к коду сообщения. В результате арифметического кодирования строка символов заменяется действительным числом больше нуля и меньше единицы. Поскольку производится анализ однобайтных символов, арифметическое кодирование позволяет обеспечить высокую степень сжатия. Особенно эффективен этот метод в случаях, когда сжимаются данные, где частота появления различных символов сильно варьируется. Но сама процедура арифметического кодирования требует мощных вычислительных ресурсов, и до недавнего времени этот метод мало применялся при сжатии передаваемых данных из-за медленной работы алгоритма. Лишь появление мощных процессоров, особенно с RISC-архитектурой, позволило создать эффективные устройства арифметического сжатия данных. Квантование. Алгоритм, приводящий вместе с приличной степенью сжатия картинок с большим количеством цветов к потере кода. Соответственно, при восстановлении несколько ухудшается качество изображения. Степень потери качества зависит от степени квантования. Принцип сжатия следующий: берется некоторое количество наиболее часто встречающихся цветов, с учетом чувствительности глаза к определенным цветам. Далее для каждой точки изображения назначается ближайший цвет из выбранных, как среднеквадратичная разность RGB-составляющих. После такого преобразования появляются большие области одного цвета, которые можно “скормить” любому из предыдущих алгоритмов. Большой плюс метода – сжатие “сложных” картинок, ну а минус – некоторая потеря качества. Соответственно, чем больше цветов “загрубляется”, тем больше потеря качества при лучшем сжатии. S3TC – S3 Texture Compression. При этом методе анализируются уже не ряды, а блоки. Изображение разбивается на квадраты (блоки) пикселей. Для каждого блока выполняется уже рассмотренное нами квантование. Производится оценка по минимальному количеству цветов (например, для блоков размером 4х4 – 4 цвета). Составляется таблица цветов и индексов. Исходя из того, что пиксель в памяти занимает 3 байта, блок 4х4 занимает в памяти 4*4*3=48 байт. Для этого же блока получится после преобразования 4*4*2/8(индексы цветов)+2*4(таблица выбранных 4-х цветов, 2 байта на цвет)=12 байт. Сжатие получилось в 4 раза. DCT – Digital Cosines Transform. Цифровое косинус-преобразование. Раскладывает изображение на частотные составляющие. Алгоритм основан на том, что глаз воспринимает искажение в высокочастотной составляющей гораздо меньше, чем в низкочастотной. Благодаря этому высокочастотные искажения (“цветовой шум”) кодируются с бо€льшими потерями. Не углубляясь в формулы, можно лишь отметить, что в JPEG используется именно этот метод с небольшим развитием алгоритма для предопределения качества сжатия. После такого преобразования получается матрица с большим количеством нулей, которые преобразуются RLE-алгоритмом в еще более сжатый код. Этот код можно дополнительно обработать арифметическим кодированием или алгоритмом Хаффмана. В итоге получается очень эффективное сжатие изображения. Фрактальное сжатие. Этот метод основан на том, что реальные изображения практически всегда содержат похожие фрагменты. Одним из рассмотренных методов уменьшается количество цветов. Для облегчения поиска похожих фрагментов осуществляется поиск перебором, запоминаются области. Фрагменты могут иметь другие размер, яркость, угол поворота. Цвета восстанавливаются, а распознанные области уменьшаются и индексируются. Алгоритм достаточно сложный, содержит много математических преобразований, но при умелом подходе – очень эффективный. Недостаток – медленный. Положительная сторона – может быть достигнута очень высокая степень сжатия. Wavelets. Принцип в том, что вдвое уменьшенная картинка сжимается намного лучше исходной. Итак, берутся 4 пикселя, приводятся к одному с минимальным цветом. Теперь этим цветом заполняются все четыре (уменьшенная копия увеличивается). Отличия между исходным и полученным блоками невелики по модулю и хорошо сжимаются. Большие отличия по модулю заменяются “максимально разрешенными”, что ведет к незначительной потере качества. Далее к уменьшенной вдвое цельной картинке применяется рекурсия (та же процедура обработки) и так до тех пор, пока картинка не станет размером 1х1. Распаковка – читаются значения, прибавляются к ним распакованные отличия и так до полного восстановления картинки. Методы сжатия звука Качество сжатого файла определяется битрейтом и частотой дискретизации. Битрейт (bit rate, битовая частота) определяет количество передаваемой за единицу времени информации: чем больше битрейт, тем выше реалистичность и соответствие исходному звуковому потоку. Оптимальное значение, обеспечивающее качество компакт-диска, – 128 Kbit/s. Частота дискретизации – максимальная частота выходного сигнала. Чем она больше, тем ближе звучание к оригиналу. Восприятие человеком звука ограничено частотным диапазоном от 20 Hz до 20 KHz. Значение частоты дискретизации устанавливается в два раза большее, чем верхний порог восприятия (около 48 KHz). Дискретизация. Очень простой алгоритм сжатия. Диапазон значений уровня громкости (как правило, 16-битные значения) приводится к интервалу 0-15, тогда каждый уровень можно будет задать 4 битами. У стереосигнала это преобразование выполняется для каждого канала. Или сигнал преобразуется в JoinedStereo – обрабатывается один канал, а второй получается из первого и отличий от первого. Для повышения качества при распаковке диапазон значений преобразуется обратно в 16-битные значения по нелинейному интерполяционному методу. Сжатие этим методом достигается более чем в 10 раз. Спектральный. Суть в том, что сигнал раскладывается на сумму синусоидных колебаний различной частоты. Зависимость амплитуды от частоты и есть спектр. Спектр, как правило, изменяется медленнее, чем сам сигнал, соответственно, очень хорошо сжимается. Эффективно такой алгоритм применяется при сжатии речи. MP3. Алгоритм основан на особенностях слуха. Человек более чувствителен к восприятию средних частот звукового диапазона. Из спектра удаляются неслышимые и слабо воспринимаемые частоты, после этого звук обрабатывается алгоритмом дискретизации. Для дополнительной компрессии некоторые похожие спектры могут сливаться в один с усредненными частотами. Методы сжатия видео Известно, что пороговая частота дискретного восприятия человеком сменяющих друг друга графических образов – 25 кадров в секунду. Поэтому наличие в выходном потоке большего числа кадров не оправдано. Алгоритмов сжатия видео существует достаточно много, но все они основаны на рассмотренных выше алгоритмах в различных сочетаниях и последовательностях. Но поскольку видео – это поток картинок, возникают и дополнительные методы компрессии. Например, можно сохранять не целиком следующий кадр, а только отличия его от предыдущего. На неизмененные пиксели накладываются прозрачные. Похожие приемы применяются в GIF и несколько усложненные в FLI-форматах. Еще более сложный алгоритм использует MPEG. Идея состоит в следующем: объекты, как правило, быстро двигаются, но медленно изменяются. Изображение разбивается на квадраты, полученные блоки сравниваются с блоками предыдущего кадра. Наименее отличающиеся сохраняются всего один раз за несколько кадров. Изменяющиеся блоки кодируются разностным алгоритмом, развитым от JPEG. У данного метода есть особенность. Для того чтобы можно было воспроизвести видео с любого места, через определенный промежуток времени сохраняется кадр целиком (KeyFrame), поскольку алгоритм может восстановить следующую серию кадров только на основе начального. MPEG-2 используется в рамках технологии DVD и обеспечивает высокое качество выходного видео. Особой степенью сжатия не характеризуется в силу того, что носители, используемые в технологии DVD, обладают достаточной емкостью (от 4,7 Gb). Процесс декодирования не требователен к аппаратным ресурсам ПК. MPEG-4 имеет самую высокую степень сжатия при очень неплохом качестве. Но при всех его преимуществах он очень требователен к вычислительной мощности ПК. Засчитаны: SDF (2), RLE (3), LZ (2), Хаффмана (3), Арифметическое кодирование (2), Квантование (2), DCT (3), Фрактальное сжатие (3), Wavelets (2), Методы сжатия звука (2), Методы сжатия видео (3). Много копипасты. Назначается штраф в 2 балла. Итог за задание: 27 - 2 балла (L, A_D) 2. Электронная цифровая подпись (ЭЦП)— реквизит электронного документа, предназначенный для защиты данного электронного документа от подделки, полученный в результате криптографического преобразования информации с использованием закрытого ключа электронной цифровой подписи и позволяющий идентифицировать владельца сертификата ключа подписи, а также установить отсутствие искажения информации в электронном документе. Схема электронной подписи обычно включает в себя: - алгоритм генерации ключевых пар пользователя; - функцию вычисления подписи; - функцию проверки подписи. Функция вычисления подписи на основе документа и секретного ключа пользователя вычисляет собственно подпись. В зависимости от алгоритма функция вычисления подписи может быть детерминированной или вероятностной. Детерминированные функции всегда вычисляют одинаковую подпись по одинаковым входным данным. Вероятностные функции вносят в подпись элемент случайности, что усиливает криптостойкость алгоритмов ЭЦП. Однако, для вероятностных схем необходим надёжный источник случайности (либо аппаратный генератор шума, либо криптографически надёжный генератор псевдослучайных бит), что усложняет реализацию. В настоящее время детерминированые схемы практически не используются. Функция проверки подписи проверяет, соответствует ли данная подпись данному документу и открытому ключу пользователя. Открытый ключ пользователя доступен всем, так что любой может проверить подпись под данным документом. Поскольку подписываемые документы — переменной (и достаточно большой) длины, в схемах ЭЦП зачастую подпись ставится не на сам документ, а на его хэш. Для вычисления хэша используются криптографические хэш-функции, что гарантирует выявление изменений документа при проверке подписи. Хэш-функции не являются частью алгоритма ЭЦП, поэтому в схеме может быть использована любая надёжная хэш-функция. Алгоритмы ЭЦП делятся на два больших класса: обычные цифровые подписи и цифровые подписи с восстановлением документа. Обычные цифровые подписи необходимо пристыковывать к подписываемому документу. К этому классу относятся, например, алгоритмы, основанные на эллиптических кривых (ECDSA, ГОСТ Р 34.10-2001, ДСТУ 4145-2002). Цифровые подписи с восстановлением документа содержат в себе подписываемый документ: в процессе проверки подписи автоматически вычисляется и тело документа. К этому классу относится один из самых популярных алгоритмов — RSA. Следует различать электронную цифровую подпись и код аутентичности сообщения, несмотря на схожесть решаемых задач (обеспечение целостности документа и неотказуемости авторства). Алгоритмы ЭЦП относятся к классу асимметричных алгоритмов, в то время как коды аутентичности вычисляются по симметричным схемам. Цифровая подпись обеспечивает: - Удостоверение источника документа. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д. - Защиту от изменений документа. При любом случайном или преднамеренном изменении документа (или подписи) изменится хэш, следовательно, подпись станет недействительной. - Невозможность отказа от авторства. Так как создать корректную подпись можно лишь, зная закрытый ключ, а он известен только владельцу, то владелец не может отказаться от своей подписи под документом. Алгоритм MD5 MD5 (Message Digest 5) — алгоритм хэширования, разработанный профессором Рональдом Л. Ривестом в 1991 году. Алгоритм md5 позволяет создавать хеш (контрольную сумму), которую достаточно сложно подделать. Он используется для всевозможных проверок подлинности данных, когда необходима передача их в зашифрованном виде. Обратное кодирование (расшифровка) в данном алгоритме невозможна. Алгоритм SHA SHA (Secure Hash Algorithm) - алгоритм аутентификации и проверки целостности информации. Много лишнего. Штраф в балл Итог за задание: 3-1 балла (L) мурзилка 1. Сжатие – это избавление от избыточных данных, осуществляемое по алгоритму кодирования информации, при котором она занимает меньший объем памяти. Алгоритмы сжатия данных: SDF – один из простейших и наиболее разносторонних форматов сжатия. Он определяет графическое изображение как совокупность геометрических фигур и образцов. Таким способом хранятся данные систем автоматизированного проектирования, так как для них обычно нет необходимости определять значение цвета для каждой точки растра. RLE - метод сжатия данных, при котором одинаковые последовательности одних и тех же байт заменяются однократным упоминанием повторяющегося байта (или целой цепочки байтов), и числа его повторений в исходных данных. Применяется RLE в тех случаях, когда изображение имеет большие участки одинакового цвета. Применяется для монохромных изображений, сохраненных в цветовой модели Bitmap, где при сжатии данных с его использованием можно добиться наилучших результатов. Применим для сжатия других типов файлов (даже не графических), но малоэффективен, так как сжимаемые данные должны иметь простую повторяющуюся структуру. RLE имеет преимущество – он прост, позволяет быстро производить распаковку и упаковку в этот формат. Этот метод сжатия графических данных используется в файлах формата PSD, BMP… LZ. Принцип похож на RLE. Из повторяющихся участков кода формируется индексированный словарь. Основной плюс – сжимаются повторы комбинаций. Основной недостаток – словарь требуется хранить в том же файле. Существует большое число модификаций этого метода LZ – LZW, LZ77, LZSS и т. д. LZW - алгоритм архивации, основанный на поиске и замене в исходном файле одинаковых последовательностей данных, для их исключения, и уменьшения размера архива. Данный тип не вносит искажений в исходный графический файл, и подходит для сжатия монохромных, черно - белых, или полноцветных изображений. Наилучшие результаты получаются при сжатии изображений с большими областями одинакового цвета или изображений с повторяющимися одинаковыми структурами. Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. Этот метод сжатия графических данных используется в файлах формата TIFF, PDF, GIF, PostScript и других. ZIP - метод сжатия данных, в основу которого положен метод, аналогичный LZW. Этот способ не вносит искажений в исходный файл, и лучше всего подходит для сжатия графических данных с одинаковыми одноцветными или повторяющимися областями. ZIP отличается быстродействием и не требует значительных ресурсов оперативной памяти. Он используется для графических данных в файлах формата PDF, TIFF и т.д. JPEG - метод, используемый для хранения полутоновых и полноцветных изображений, позволяющий добиться наивысшей степени сжатия и минимальный размер выходного файла. При нем полученные данные сжимаются по RLE или LZW - алгоритму, для получения еще большего сжатия. Данный формат предназначен для хранения, в основном, фотографических изображений с большим количеством оттенков и цветовых переходов, и практически не подходит для хранения однотонных изображений типа кадров из мультфильмов (сжатие будет слишком низким, или качество картинки окажется просто неприлично низким). JPEG широко применяется в веб-камерах, видеосерверах и других сетевых устройствах. Этот метод сжатия графических данных используется в файлах формата PDF, PostScript и других. Motion JPEG (MJPEG) – алгоритм сжатия JPEG для видеоинформации. Представляет собой стандартизированный формат записи потока отдельных кадров, каждый из которых сжат по алгоритму JPEG независимо от остальных. Алгоритм сжатия H-263.Он часто используется при передаче видеоизображения по каналам связи с полосой пропускания меньше 64 кбит. Похож на JPEG, но его отличие состоит в том, что обработке подлежат только те элементы изображения, которые изменились по сравнению с соответствующими элементами предыдущего кадра. Этот алгоритм обеспечивает высокую степень сжатия видеоизображения, но дает плохое качество, если изображение содержит движущиеся объекты. Wavelet. Используется в цифровых системах видеонаблюдения. Последовательность действий в целом аналогична алгоритму JPEG. Преимущество метода сжатия Wavelet перед JPEG состоит в том, что Wavelet преобразует полное изображение, а не его отдельные фрагменты, и позволяет получить качественное изображение при больших коэффициентах сжатия. При высокой степени сжатия этот метод может давать искажения. JPEG2000 предполагает увеличение коэффициента сжатия по сравнению с JPEG на 30%. Этот метод сжатия использует вейвлет-преобразование, благодаря чему характерные для JPEG блочные искажения исчезают, а коэффициент сжатия может достигать 200. MPEG используется в видеоизображениях, разделенных малым интервалом времени. Между двумя соседними кадрами обычно изменяется только малая часть сцены. В этом случае полная информация о сцене сохраняется выборочно – только для опорных изображений. При кодировании в форматах сжатия MPEG формируется цепочка кадров разных типов. Идея состоит в следующем: объекты, как правило, быстро двигаются, но медленно изменяются. Изображение разбивается на квадраты, полученные блоки сравниваются с блоками предыдущего кадра. Наименее отличающиеся сохраняются всего один раз за несколько кадров. Изменяющиеся блоки кодируются разностным алгоритмом, развитым от JPEG. MPEG-2 используется в рамках технологии DVD и обеспечивает высокое качество выходного видео. MPEG-4 имеет самую высокую степень сжатия при очень неплохом качестве. Но при всех его преимуществах он очень требователен к вычислительной мощности ПК. MP3. Алгоритм основан на особенностях слуха. Человек более чувствителен к восприятию средних частот звукового диапазона. Из спектра удаляются неслышимые и слабо воспринимаемые частоты, после этого звук обрабатывается алгоритмом дискретизации. Алгоритмов сжатия видео существует достаточно много, но все они основаны на рассмотренных выше алгоритмах в различных сочетаниях и последовательностях. Замечу, что RLE неплохо справляется и с любыми двоичными данными. ZIP использует множество алгоритмов и их комбинации. Засчитано: SDF (2), RLE (3), семейство алгоритмов словарного сжатия данных (3: LZ, LZW), вейвлетное сжатие (3: JPEG2000, Wavelet), ZIP (2), JPEG (3), MJPEG (3), H-263 (3), MPEG (3). Вероятностное сжатие Итог за задание: 27 баллов (A_D) 2. Хеш - это последовательность символов, полученная от исходных данных путем выполнения над ними преобразований по определенному алгоритму. От шифрования хеширование отличается тем, что обычно алгоритм хеширования необратим, т.е. по хешу однозначно восстановить исходные данные нельзя, можно лишь подобрать данные под конкретный хеш. Алгоритмы хеширования бывают стандартные, бывают самописные. Хеши отличаются друг от друга, как количеством символов, так и алфавитом (набором возможных символов). Часто цифровая подпись ставится не на сам документ, а на его хэш. Цифровая подпись обеспечивает: 1) Удостоверение источника документа; 2) Защиту от изменений документа. При любом случайном или преднамеренном изменении документа (или подписи) изменится хэш, следовательно, подпись станет недействительной; 3) Невозможность отказа от авторства. Создать корректную подпись можно, зная закрытый ключ, а он известен только владельцу, то владелец не может отказаться от своей подписи под документом. MD5 — 128-битный алгоритм хэширования. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. SHA - стандарт хеширования, работает чуть ли не во всех протоколах и программах защиты информации, применяемых в компьютерах и сетях GPG - алгоритм, позволяющий шифровать и подписывать данные в целях безопасного хранения и передачи информации. Вывод – все это алгоритмы хэширования. По хешу - хорошо, но алгоритмы расплывчаты. Итог за задание: 2,5 балла (A_D) 3. Написав программу, я бы хранила файлы в бинарном виде (не прочтешь их, пока не узнаешь структуру) + еще на ходу каким-нибудь алгоритмом сжатия можно пожать. Хотя, обычный пользователь не знает языков программирования и шифрования, так что кодировать бессмысленно. Рассуждение верное. Если разобраться в ситуации, то пользователь не сможет понять массу банальных методов "шифрования". Можно записать файл посимвольно в обратном порядке, можно из кода каждого символа вычесть определенное значение ("подогнать" к невизуальным символам), можно наложить на файл (изменить код каждого символа) математическую функцию (например, периодическую sin для целых значений с некоторым коэффициентом, т.е. код символа будет отличаться от истинного, к примеру, на 10, 0 или -10, 50, 0 или -50). Применение алгоритмов сжатия также сделает текст нечитабельным. Вообще любое коверкание и перемешивание символов затруднит и сделает невозможным чтение текста. Итог за задание: 2,5 баллов (A_D) Shishok 1. Сжатие данных – это процедура, в результате которой данные кодируются. Данная процедура проводится с такой целью, чтобы уменьшить объём данных, хранящихся на ЭВМ. Алгоритмы сжатия данных можно разделить на две огромных подгруппы: 1) Алгоритмы сжатия без потерь; 2) Алгоритмы сжатия с потерями. Алгоритмы сжатия без потерь: 1) Алгоритм Хаффмана – один из самых распространённых на сей день алгоритмов сжатия данных. Он применяется во многих программах сжатия данных. Очень редко используется отдельно, наоборот, в большинстве случаев используется в связке с другими алгоритмами. В отличие от алгоритма Шеннона-Фано, данный алгоритм сжатия данных оптимален для двоичных алфавитов, более чем с двумя символами. Этот алгоритм заключается в том, чтобы принимать оптимальные решения на каждом этапе кодирования, другими словами можно сказать, что это «жадный алгоритм». Первый этап кодирования заключается в том, чтобы выстроить оптимальное кодовое дерево. Второй этап подразумевает построение отображения код-символ на основе уже построенного кодового дерева. 2) Кодирование Шеннона-Фано – это алгоритм неоднородного префиксного кодирования. Самый простой алгоритм кодирования. Это вероятностный метод сжатия, то есть это метод контекстного моделирования нулевого порядка. Алгоритм Шеннона-Фано, подобно алгоритму Хаффмана, использует в кодировании избыточность сообщения, которая заключена в том, что частоты символов первичного алфавита распределены неоднородно. Данный алгоритм заменяет двоичными последовательностями коды более частых символов, а более длинными двоичными последовательностями – коды более редких символов. 3) Преобразование Барроуза-Уилера (блочное-сортирующее сжатие) – используется в техниках сжатия файлов, таких как bzip2. Используется для предварительной обработки данных, для улучшения сжатия без потерь. Данный алгоритм не изменяет ни один из символов символьной строки, а только меняет их порядок. Отличительная способность преобразования Барроуза-Уилера в том, что оно обратимо. 4) Дельта-кодирование (дельта-компрессия) подразумевает передачу или сохранение данных в форме разницы между последовательными данными. Оно эффективно для сжатия данных, где последовательности часто повторяются. Иногда образцы кодирования могут получать закодированные данные намного в более коротком виде, чем исходные данные. Очень эффективно для отсортированных списков, в которых мало различия между строками (Например, список слов из словаря). Работает замечательно в том случае, если данные содержат маленькую или постоянную вариацию. 5) Инкрементное кодирование (фронтальное сжатие, тыловое сжатие) – это тип дельта-кодирования, который заключается в том, что общие префиксы или суффиксы и их длины записываются так, что дублирования данных не происходит. Отлично подходит для компрессии отсортированных данных (как впрочем и дельта-кодирование). 6) LZ77 – это один из наиболее известных алгоритмов в семействе LZ (вместе с LZ78). Этот алгоритм использует словарный метод. Представляет собой более сложное обобщение простого и интуитивного способа сжатия данных. Является алгоритмом со «скользящим окном». Принцип скользящего окна заключается в том, что метод кодирования учитывает информацию, встречающуюся ранее, которая известна кодировщику и декодировщику. Недостатки данного алгоритма заключаются в следующем: 1) Невозможно кодировать подстроки, которые стоят друг от друга на расстоянии, большем длины словаря; 2) Длина подстроки, которую возможно закодировать, ограничена размером буфера. 7) LZ78 аналогичен LZ77, кроме того, что он не использует «скользящее окно». 8) LZO – это алгоритм сжатия данных, который разработан специально для достижения максимально возможной скорости распаковки файлов. Реализуется данный алгоритм в программе Izop. Может работать в многопоточной среде. В данном алгоритме существует несколько степеней сжатия. Сжатие и распаковка файлов крайне быстрая и простая. Для того, чтобы сжать данные, требуется только 64 кб памяти. 9) LZMA – используется в формате 7z в программе-архиваторе 7-Zip. В данном алгоритме используется схема сжатия по словарю, которая сходна с использованной в LZ77. Очень велик коэффициент сжатия данных. Поддерживает многопоточность. Скорость сжатия – примерно 1 мб/сек. Скорость извлечения данных – около 10-20 мб/сек. 10) Алгоритм Лемпеля — Зива — Велча – это универсальный алгоритм сжатия данных. Данный алгоритм не обязательно оптимален, т.к. не проводит никакого анализа входных данных. Данный алгоритм при сжатии создаёт таблицу, которая преобразует строки. Определённым последовательностям символов в соответствие ставятся группы бит фиксированной длины. По мере кодирования, алгоритм просматривает текст и сохраняет каждую новую двухсимвольную строку в таблицу, представляющую собой пару «код/символ». После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка с максимальной длиной. После этого в таблице сохраняется код этой строки со следующим символом на входе. А на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки. Был впервые реализован в программе compress (стандартная для UNIX-систем). Это часть стандарта на формат изображений *gif. Также используется в формате *tiff. Реализован в настоящее время в программе Adobe Acrobat. 11) Алгоритм сжатия PPM (предсказание по частичному совпадению) - адаптивный статистический алгоритм, который основан на предсказании и контекстном моделировании. Модель PPM использует контекст, то есть множество символов в несжатом потоке, которые предшествуют данному, для того, чтобы предсказывать значение символа. Сама модель PPM только предсказывает значение символа, непосредственное сжатие осуществляется такими алгоритмами, как например, алгоритм Хаффмана, арифметическое кодирование. Современные реализации PPM являются наилучшими среди алгоритмов сжатия для текстов на естественном языке. PPM требует огромное количество оперативной памяти. 12) Кодирование длин серий (RLE) – это простейший алгоритм сжатия данных, который заключается в оперировании последовательностей, в которых один и тот же символ встречается несколько раз. При кодировании строка одинаковых символов, которые составляют серию, заменяется такой строкой, в которой содержится сам повторяющийся символ и количество его повторов. Используется для простых графических изображений, например для иконок. Форматы для упаковки данных с помощью данного алгоритма включают в себя PackBits, PCX и ILBM. Звуковые данные, имеющие длинные последовательные серии байт, могут быть сжаты с помощью RLE после того, как к ним будет применено Дельта-кодирование. 13) Кодирование энтропии — кодирование словами переменной длины, при которой длина кода символа имеет обратную зависимость. Тремя самыми распространёнными техниками кодирования энтропиии являются: кодирование Хаффмана, кодирование длин серий, арифметическое кодирование. 14) Арифметическое кодирование - обеспечивает почти самый оптимальный коэффициент сжатия. Данный алгоритм отличается от алгоритма Хаффмана тем, что он показывает высочайшую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. 15) Адаптивное арифметическое кодирование – заключается в том, что при каждом сопоставлении символу кода он изменяет внутренний ход вычислений так, что в следующий раз этому же символу может быть сопоставлен другой код. Широко распространено применение данного алгоритма в сжатии поточных данных. 16) Коды Голомба — это разновидность энтропийных кодеров. Также под кодом Голомба может подразумеваться один из представителей данного семейства. Код Голомба позволяет представить последовательность символов в таком виде как последовательности двоичных слов. 17) Унарное кодирование - это энтропийное кодирование, подразумевающее представление числа n в виде n единиц с замыкающим нулём. Например, число 8 представляется в виде 111111110. Используется при программировании машин Тьюринга. Это часть кода Голомба. Алгоритмы сжатия с потерями: 1) А-закон применяется для сжатия звуковых файлов. 2) Мю-закон является стандартом аналогового сжатия. Используется в системах цифровой связи Японии и Северной Америки, с целью модификации динамического диапазона аналогового речевого сигнала до оцифровки. Он подобен алгоритму A-закона, который используется в Европе. 3) Фрактальное сжатие изображений - алгоритм сжатия изображений, который основан на применении систем итерируемых функций к изображениям. Этот алгоритм прославлен тем, что иногда позволяет получить достаточно высокие коэффициенты сжатия для реальных фотографий природных объектов. Широкого распространения алгоритм не получил, т.к. ситуация с патентованием довольно сложная. 4) Вейвлетное сжатие — название класса методов кодирования изображений, которые используют двумерное разложение кодируемого изображения. Обычно сжатие происходит с потерей качества. большую роль в данных алгоритмах играет концепция представления результатов вейвлет-разложения в виде нуль-дерева. Упорядоченные в нуль-дереве битовые плоскости коэффициентов вейвлет-разложения огрубляются и кодируются далее с использованием алгоритмов сжатия без потерь. Самый известный алгоритм вейвлетной компрессии – это JPEG-2000. Также используется при кодировании в формат DjVu. Одними из наиболее известных алгоритмов, которые применяются в системах видеонаблюдения, являются Motion Wavelet и 3D Wavelet. За читабельность - спасибо! Алгоритмы описаны верно, но не оцениваются: 3, 5, 7-10, 13, 17 (вытекает из 16) и 1, 2 (с потерями). 1 балл: 14. 2 балла: 15, 16, 3, 4 (с потерями). Остальные - 3 балла. Итог за задание: 27 баллов (L, A_D) 2. Электронная подпись файла (Хэш)— блок данных фиксированного размера, полученный в результате хэширования массива данных. Это ассоциативный массив, ибо доступ к данным осуществляется с помощью ключа, ассоциированного со значением. Хэши начинаются с префикса. Для работы с с хэш-массивами следует использовать разыменовывающий префикс. Элетронная подпись обычно состоит из трёх элементов: 1) алгоритм генерации ключевых пар пользователя; 2) функция вычисления подписи; 3) функция проверки подписи. Криптографическая хэш-функция обеспечивает стойкость к коллизиям и необратимость (невозможно вычислить исходные данные по результату преобразования). MD5 (Message Digest 5) — 128-битный алгоритм хэширования, который подразумевает создание «отпечатков» или «дайджестов» сообщений произвольной длины. Пришёл на смену MD4. SHA - алгоритм идентификации и проверки целостности информации. Это один из алгоритмов криптографического хэширования. Используется в качестве основного хэш-алгоритма в PGP. У этого алгоритма есть уязвимость, которая позволяет за наибольшее время находить коллизии. GPG - свободная альтернатива набору криптографического ПО PGP. PGP (Pretty Good Privacy) в свою очередь – это компьютерная программа, которая позволяет выполнять операции шифрования (кодирования) и цифровой подписи сообщений, файлов и т.д. Что ж, приветствуем лучший ответ) Итог за задание: 4+0,5 балла (L) 3. Самым простым решением этой задачи является то, чтобы провести над исходными файлами хэширование или кодирование любым алгоритмом сжатия. Верно, но только это не является самым простым. Все можно сделать гораздо проще! Смотри ответы других участников. Итог за задание: 2 балла (A_D) Virtual 1. Существуют алгоритмы сжатия с потерями и без потерь. Алгоритмы сжатия с потерями: Разпакованный файл будет отличаться от оригенала. Такие потери не всегда бывают важными, но при сжатии текста могут оказаться неприемлимыми. Алгоритмы сжатия без потерь: При таком алгоритме сжатия файл можно точно восстановить. Оно будет вточь вточь как исходный файл. Эти алгоритмы применяются для того что бы экономить место на жостком диске, так как обьём файла при сжатии становиться меньше, ещё эти алгоритмы применяются для того чтобы пользователю можно было быстрее передать файл или же скачать от куда либо, так как размер файла уменьщиться. Не описан ни один алгоритм. Итог за задание: 0 баллов (L) 2. Хеш — число фиксированной длины, которое ставится в соответствие данным произвольной длины таким образом, чтобы вероятность появления различных данных с одинаковым хешем стремилась к нулю, а восстановить данные по их хешу было как можно труднее. MD5 — 128-битный алгоритм хэширования, предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Пришёл на смену MD4, который был несовершенен. SHA 1 — один из алгоритмов криптографического хэширования. Описан в RFC 3174. Разработан в 1995 году в качестве замены более слабого алгоритма SHA. Имеет длину результирующего дайджеста 160 бит, существуют варианты (SHA-256, SHA-384, SHA-512) с более длинным дайджестом. Определение Хэша не верно. Итог за задание: 2 балла (L) -------------------- The procedure's completed. Successful system updating... Hey, have a nice day! -x-