контрольная работа по информатике. Контрольная Word. Контрольная работа по учебной дисциплине Информатика по теме Текстовый редактор ms word
 Скачать 0.86 Mb.
|
Алгоритм RLE.В основу алгоритма RLE положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент их повтора. Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байтов) образуется следующий вектор: Таблица 2
При записи в строку он имеет вид: 0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов). В данном примере коэффициент сжатия равен 8/10 (80%). Программные реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но в среднем обеспечивают недостаточное сжатие. Наилучшими объектами для данного алгоритма являются графические файлы, в которых большие одноцветные участки изображения кодируются длинными последовательностями одинаковых байтов. Этот метод также может давать заметный выигрыш на некоторых типах файлов баз данных, имеющих таблицы с фиксированной длиной полей. Для текстовых данных методы RLE, как правило, неэффективны. Алгоритм KWE.В основу алгоритмов кодирования по ключевым словам (Keyword Encoding) положено кодирование лексических единиц исходного документа группами байтов фиксированной длины. Примером лексической единицы может служить слово (последовательность символов, справа и слева ограниченная пробелами или символами конца абзаца). Результат кодирования сводится в таблицу, которая прикладывается к результирующему коду и представляет собой словарь. Обычно для англоязычных текстов принято использовать двухбайтовую кодировку слов. Образующиеся при этом пары байтов называют токенами. Эффективность данного метода существенно зависит от длины документа, поскольку из-за необходимости прикладывать к архиву словарь длина кратких документов не только не уменьшается, но даже возрастает. Данный алгоритм наиболее эффективен для англоязычных текстовых документов и файлов баз данных. Для русскоязычных документов, отличающихся увеличенной длиной слов и большим количеством приставок, суффиксов и окончаний, не всегда удается ограничиться двухбайтовыми токенами, и эффективность метода заметно снижается. Алгоритм Хаффмана (Huffman).В основе этого алгоритма лежит кодирование не байтами, а битовыми группами. Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов. Чем чаще встречается кодируемый символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность). Образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия. Как видно из схемы, представленной на рисунке, используя 16 бит, можно закодировать до 256 различных символов. Однако ничто не мешает использовать и последовательности до 20 бит – тогда можно закодировать до 1024 лексических единиц (это могут быть не символы, а группы символов, слоги и даже слова). В связи с тем, что к сжатому файлу необходимо прикладывать дерево соответствия, на файлах малых размеров алгоритм Хаффмана малоэффективен. Практика также показывает, что его эффективность зависит от заданной предельной длины кода (размера словаря). В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит). Синтетические алгоритмы.Рассмотренные выше алгоритмы в «чистом виде» на практике не применяют из-за того, что эффективность каждого из них сильно зависит от начальных условий. В связи с этим, современные средства архивации данных используют более сложные алгоритмы, основанные на комбинации нескольких теоретических методов. Общим принципом в работе таких «синтетических» алгоритмов является предварительный просмотр и анализ исходных данных для индивидуальной настройки алгоритма на особенности обрабатываемого материала. | ||||||||||||||||||