- •Информатика
- •Информация и информатика
- •Кодирование данных двоичным кодом
- •Структуры данных
- •Устройство персонального компьютера
- •Структурная схема пк
- •Архитектура современных программных средств
- •Прикладное программное обеспечение
- •Средства обработки текстовой информации
- •Средства обработки графической информации
- •Средства численных и символьных вычислений
- •Табличная обработка информации (электронные таблицы)
- •Системы управления базами данных (субд)
- •Основные положения
- •Архитектура субд
- •Иерархическая и сетевая даталогические модели субд
- •Реляционные даталогические модели субд
- •Системы управления базами знаний и экспертные системы
- •Пользователь
- •Системы распознавания образов и принятия решений
- •Word 2007: офисная эволюция
- •Меню Office
- •Лента и панель быстрого доступа
- •Мини-панель инструментов
- •Строка состояния
- •Упрощенное создание списков
- •Работа с графикой
- •Объекты SmartArt
- •Темы документа
- •Сохранение в Open Document, pdf и xps
- •Анализ и представление информации
- •Универсальный язык программирования
- •Структура программы. Алфавит. Простейшие конструкции. Выражения
- •Типы данных
- •Примеры операций, допустимых над данными перечисляемого типа:
- •Примеры операций, допустимых над данными интервального типа.
- •Примеры операций, допустимых над данными целого типа
- •Примеры операций, допустимых над данными логического типа.
- •Примеры операций, допустимых над данными символьного типа.
- •Основные операторы
- •Оператор выбора Case
- •0:Writeln(‘Ноль’);
- •1,3,5,7,9:Writeln(‘Нечетное’);
- •2,4,6,8:Writeln(‘Четное’)
- •Организация ввода-вывода
- •Структурированные типы данных: массивы
- •Процедуры и функции
- •Математический процессор Mathcad
- •Компьютерные сети локальные сети
- •Цели создания и преимущества использования локальных компьютерных сетей
- •Особенности организации локальных сетей
- •Одноранговая сеть
- •Сеть с выделенным сервером
- •Топология локальных сетей
- •Топология "кольцо"
- •Топология «шина»
- •Топология "звезда"
- •Методы доступа и протоколы передачи данных в локальных сетях
- •Глобальная сеть интернет
- •Классификация сервисов Internet
- •Электронная почта
- •Сетевые новости Usenet
- •Списки рассылки
- •Система гипермедиа www
- •Система адресации в Internet
- •Доменная система имен
- •Универсальные указатели ресурсов
- •Схемы адресации ресурсов internet
- •Приемы и методы работы со сжатыми данными
- •Алгоритм rle
- •Алгоритм kwe
- •Алгоритм Хаффмана
- •8 Значений
- •16 Значений
- •128 Значений
- •Синтетические алгоритмы
- •Вредоносные программы и борьба с ними
- •Компьютерные вирусы
- •Происхождение термина
- •Классификация
- •Канал распространения
- •Сетевые и файловые черви
- •Троянские программы
- •Антивирусные средства
- •Методы обнаружения вирусов
- •Классификация антивирусов
- •Антивирусные компании и программы
- •Сканер eset nod32 – защита от всех известных вирусов, червей, шпионов и Троянов
- •Spybot-Search&Destroy 1.4 – служба «внутренней контрразведки»
Алгоритм rle
В основу этого алгоритма положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указхывается код данных и коэффициент повтора.
Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байт) образуется следующий вектор:
Значение |
Коэффициент повтора |
0 |
3 |
127 |
2 |
0 |
1 |
255 |
4 |
При записи в строку он имеет вид: 0; 3; 127;2; 0; 1; 255;4 (всего 8 байт).
В данном примере коэффициент сжатия равен 8/10, т.е. экономия объема составляет 20 %.
Программные реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но в среднем обеспечивают недостаточное сжатие. Наилучшими объектами для данного алгоритма являются графические файлы, в которых большие одноцветные участки изображения кодируются длинными последовательностями одинаковых байтов. Этот метод также может давать заметный выигрыш на некоторых типах файлов баз данных, имеющих таблицы с фиксированной длиной полей. Для текстовых файлов данных методы RLE, как правило, не эффективны.
Алгоритм kwe
В основу алгоритмов кодирования по ключевым словам положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Примером лексической единицы может служить слово. Результат кодирования сводится в таблицу, которая прикладывается к результирующему коду и представляет собой словарь. Обычно для англоязычных текстов принято использовать двухбайтовую кодировку слов. Образующиеся при этом пары байтов называют токенами.
Эффективность данного метода существенно зависит от длины документа, поскольку из-за необходимости прикладывать к архиву словарь длина кратких документов не только не уменьшается, но даже возрастает.
Данный алгоритм наиболее эффективен для англоязычных текстовых документов и файлов баз данных. Для русскоязычных документов, отличающихся увеличенной длиной слов и большим количеством приставок, суффиксов и окончаний, не всегда удается ограничится двухбайтовыми токенами, и эффективность заметно снижается.
Алгоритм Хаффмана
В основе этого алгоритма лежит кодирование не байтами, а битовыми группами:
перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов;
чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется;
образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.
Пример кодирования символов русского алфавита представлен на рис.1.
А
1
1 бит
О
01
2 бит
Е
0010
Т
0011
4 бит
С
000100
И
000101
К
000110
Р
000111
6 бит
8
8 Значений
бит ……………………… ……………………….
1
16 Значений
0 бит ……………………… ………………………
…………………………………………………………………………………….
128 Значений
16 бит ………………………. ……………………..
Рис..1. Пример побуквенного кодирования русского алфавита по алгоритму Хаффмана
Как видно из схемы, представленной на рис.1, используя 16 бит, можно закодировать до 256 различных символов. Однако ничто не мешает использовать и последовательности длиной до 20 бит – тогда можно закодировать до 1024 лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова).
В связи с тем, что к сжатому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хаффмана малоэффективен. В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит).