Индивидуальные задания по информатике

Калининградский государственный технический университет
ИНФОРМАТИКА
Методические указания для выполнения индивидуальных заданий
для студентов направления 552800 «Информатика и вычислительная техника»
КАЛИНИНГРАД
2000
УДК 681.3.06
Автор – Топоркова О.М., к.т.н., доцент кафедры систем управления и вычисли-
тельной техники Калининградского государственного технического университета
Методические разработки рассмотрены и одобрены кафедрой систем управления и
вычислительной техники 20.9.99, протокол № 1.
Рецензент – кафедра систем управления и вычислительной техники Калининград-
ского государственного технического университета
©Калининградский государственный технический университет, 2000
Введение
Тенденция усиления фактора самостоятельной работы студентов привела к разра-
ботке данных методических указаний по выполнению индивидуальных заданий по инфор-
матике. Они призваны, с одной стороны, подробно ознакомить обучающихся с некоторы-
ми практическими задачами информатики, а с другой – закрепить навыки прикладного
программирования и составления блок-схем.
Настоящие методические указания состоят из трех самостоятельных частей, в ко-
торых излагаются три практические задачи современной информатики – адресация эле-
ментов данных линейного списка, автокоррекция естественно языковых текстов, сжатие
данных.
Первая задача нашла свое применение в таких программных продуктах, как систе-
мы управления базами данных, операционные системы (организация поисковых операций
в системных данных), компиляторы (работа с таблицами идентификаторов) и многих дру-
гих. Алгоритмы адресации имеют универсальный характер и используются практически во
всех задачах, в которых ведется организация и поиск информации в одномерных массивах,
независимо от места ее нахождения – основная память или внешняя.
Вторая задача носит более частный характер, а изложенные методы используются
при проверке орфографии в текстовых и табличных процессорах, издательских системах, а
также как средство верификации результатов работы сканера – после распознавания текста
для устранения возможных ошибок выполняется его орфографический анализ.
Проблема сжатия данных решается в современных архиваторах. Они, как правило,
используют комбинацию методов, изложенных в третьей части.
Задачи программируются на языке программирования, который изучается в курсе
«Алгоритмические языки и программирование», и, тем самым, закрепляют навыки, полу-
ченные в этой дисциплине. Кроме этого, требование подготовки блок-схем средствами
WinWord позволяет углубить знания, связанные, с одной стороны, с логическим проекти-
рованием алгоритма, а с другой – с правилами начертания блок-схем.
Запрограммированные и отлаженные задачи должным образом оформляются, что
также способствует умению студента правильно и аккуратно закреплять результат работы
на бумажном носителе информации.
ЧАСТЬ 1. МЕТОДЫ АДРЕСАЦИИ
ВВЕДЕНИЕ
Одной из проблем при создании информационных систем является работа со струк-
турированными данными, которые чаще всего являются линейными списками – упорядо-
ченным множеством элементов, порядковые номера которых определяют местоположение
элемента в списке. Элементы списка имеют структуру – они состоят из конечного множе-
ства полей, каждое из которых имеет определенный смысл, например, фамилии, адреса и
т.д. Для таких списков важна задача адресации элементов списков – определение адреса
элемента списка по одному из его полей или по совокупному набору полей. Такие поля
называются ключевыми (или ключами) (в простейшем случае ключом, например, может
быть номер зачетной книжки студента).
Иногда бывает необходимо объединить несколько полей, чтобы образовать уни-
кальный ключ, называемый в этом случае сцепленным ключом: например, ключ, иденти-
фицирующий студента в институте, является комбинацией номера группы, фамилии, име-
ни и отчества студента (есть случаи, когда в одной группе учатся студенты с одинаковыми
фамилиями и именами).
Кроме простого и сцепленного, ключ может быть первичным – определять макси-
мум один элемент в списке или вторичным – определять множество (в общем случае не
одноэлементное) элементов в списке. Например, фамилия студента в учебной группе, как
правило, является первичным ключом, а пол студента – вторичный ключ, поскольку одно-
му значению этого ключа (мужской или женский) соответствует, в общем случае, группа
студентов.
Основную проблему при адресации элементов списков можно сформулировать
следующим образом: как по первичному ключу определить местоположение элемента с
данным ключом (задача поиска)? Существует несколько различных способов адресации.
Они рассматриваются далее.
1. Теоретическая часть
1.1. Последовательное сканирование списка
Наиболее простым способом локализации элемента списка является сканирова-
ние списка с проверкой ключа каждого элемента. Этот способ, однако, требует слишком
много времени для большинства применений. Он может быть эффективен только при па-
кетной обработке последовательного файла, находящегося, например, на магнитной ленте,
когда каждая запись все равно должна быть прочитана.
1. 2. Блочный поиск
Если элементы упорядочены по ключу, то при сканировании списка не требуется
чтение каждого элемента. Компьютер мог бы, например, просматривать каждый n-ный
элемент в последовательности возрастания ключей. При нахождении элемента с ключом,
большим, чем ключ, используемый при поиске, просматриваются последние n-1 элемен-
тов, которые были пропущены. Этот способ называется блочным поиском: элементы
группируются в блоки, и каждый блок проверяется по одному разу до тех пор, пока ни
будет найден нужный блок. Вычисление оптимального для блочного поиска размера бло-
ка выполняется следующим образом: в списке, содержащем N элементов, число просмот-
ренных элементов минимально при длине блока, равной ?N. При этом в среднем анализи-
руется ?N элементов.
1.3. Двоичный поиск
При двоичном поиске рассматривается элемент, находящийся в середине области, в
которой выполняется поиск, и его ключ сравнивается с поисковым ключом. Затем поиско-
вая область делится пополам, и процесс повторяется. При этом, если N велико, то в сред-
нем будет просмотрено примерно log2N-1 элементов. Это число меньше, чем число про-
смотров для случая блочного поиска.
1.4. Индексно-последовательная организация
В общем случае сканирование (последовательный поиск) в списках для нахожде-
ния в них элемента является процессом, требующим много времени, если он выполняется
над всем списком. Однако его можно использовать для точной локализации элемента в
небольшой области, если эта область найдена некоторым другим способом.
Если список упорядочен по ключам, то обычно при адресации используется табли-
ца, называемая индексом. При обращении к таблице задается ключ искомого элемента,
а результатом процедуры поиска в таблице является относительный или абсолютный ад-
рес элемента.
Индекс можно определить как таблицу, с которой связана процедура, восприни-
мающая на входе информацию о некоторых значениях атрибутов и выдающая на выходе
информацию, способствующую быстрой локализации элемента или элементов, которые
имеют заданные значения атрибутов. Индекс использует в качестве входной информа-
ции ключ и дает на выходе информацию, относящуюся к физическому адресу данного
элемента.
Если для адресации используется индекс, ЭВМ в основном производит поиск в
индексе, а не в списке. При этом существенно экономится время, но требуется память
для хранения индекса. Это похоже на использование картотеки в библиотеке. Пользова-
тель отыскивает название требуемой книги в картотеке и находит номер книги по катало-
гу, который является как бы относительным адресом положения книги на полках.
Если элементы списка упорядочены по ключу, индекс обычно содержит не ссылки
на каждый элемент, а ссылки на блоки элементов, внутри которых можно выполнить по-
иск или сканирование.
Хранение ссылок на блоки элементов, а не на отдельные элементы в значительной
степени уменьшает размер индекса. Причем даже в этом случае индекс часто оказывается
слишком большим для поиска и поэтому используется индекс индекса. В больших списках
может быть больше двух уровней индекса.
Для ускорения поиска сегменты нижнего уровня индекса могут находиться среди
данных, на которые они указывают. Например, в файле на диске обычно имеется на каж-
дом цилиндре индекс дорожек, содержащий ссылки на записи, хранящиеся на этом ци-
линдре.
Индексно-последовательные файлы представляют собой наиболее распространен-
ную форму адресации файлов.
1.5. Индексно-произвольная организация
Произвольный (непоследовательный) список можно индексировать точно так же,
как и последовательный список. Однако при этом требуется значительно больший по раз-
мерам индекс, так как он должен содержать по одному элементу для каждого элемента
списка, а не для блока элемента. Более того, в нем должны содержаться полные абсо-
лютные (или относительные) адреса, в то время как в индексе последовательного спи-
ска адреса могут содержаться в усеченном виде, так как старшие знаки последова-
тельных адресов будут совпадать.
По сравнению с произвольным доступом индексно-последовательный список бо-
лее экономичен как с точки зрения размера индекса, так и с точки зрения времени, необ-
ходимого для поиска в нем. Произвольные списки в основном используются для обеспе-
чения возможности адресации элементов списка с несколькими ключами. Если список
упорядочен по одному ключу, то он не упорядочен по другому ключу. Для каждого типа
ключей может существовать свой индекс: для упорядоченных ключей индексы будут бо-
лее длинными, так как должны будут содержать по одному данному для каждого элемен-
та. Ключ, который чаще всего используется при адресации списка, обычно служит для
его упорядочения, поскольку наиболее быстрый доступ возможен в том случае, когда
применяется короткий последовательный индекс.
Аналогия с картотекой библиотеки скорее соответствует индексно-
последовательному доступу, чем произвольному. В картотеке используются два ключа -
название книги и фамилия автора, и, как правило, ни тот, ни другой ключ не применяют-
ся при упорядочивании книг на полках, следовательно, оба индекса должны содержать
по элементу для каждой книги. Книги упорядочиваются по номеру в каталоге. После того
как пользователь нашел номер интересующей его книги в каталоге, он отыскивает книгу
на рядах полок. В каждом ряду обычно указаны начальный и конечный номера книг в
нем. Пользователь сравнивает номер, который он получил из каталога (индекса), с номе-
рами, указанными в рядах. Найдя нужный ряд, он ищет полку, на которой стоит книга.
Аналогично ЭВМ выполняет поиск в файлах, начиная, например, с главного индекса, да-
лее просматривая индекс цилиндров, а затем индекс дорожек.
В картотеке библиотеки не указывается физическое местоположение книги на пол-
ках. Вместо этого в ней содержится номер в каталоге, который может рассматриваться как
символический адрес. Символический адрес указывается потому, что книги перес-
тавляются, и, если бы использовался физический адрес, это потребовало бы частой коррек-
тировки картотеки библиотеки. По той же причине в индексно-произвольных списках
часто используются символические, а не абсолютные адреса. При добавлении новых или
удалении старых элементов изменяется местоположение остальных элементов. Если име-
ется несколько ключей, то индекс вторичного ключа может содержать в качестве выхода
первичный ключ записи. При определении же местоположения элемента по его первич-
ному ключу можно использовать какой-нибудь другой способ адресации. По этому мето-
ду поиск осуществляется медленнее, чем поиск, при котором физический адрес элемента
определяется по индексу. В списках, в которых положение элементов часто изменяется,
символическая адресация может оказаться предпочтительнее.
Другой причиной для непоследовательного размещения элементов могут служить
частые изменения списка. Интенсивное включение новых и удаление старых элементов
в последовательно упорядоченном списке связано с большими трудностями и значи-
тельным расходом машинного времени. Если бы книги хранились на полках библиотеки в
алфавитном порядке, то обеспечение такого порядка занимало бы излишне много време-
ни, так как каждый раз при добавлении новой книги требовалось бы передвигать много
книг.
1.6. Адресация с помощью ключа, эквивалентного адресу
Известно много методов преобразования ключа непосредственно в адрес в файле.
В тех случаях, когда такое преобразование возможно, оно обеспечивает самую быструю
адресацию; при этом нет необходимости организовывать поиск внутри файла или выпол-
нять операции с индексами.
Наиболее простое решение задачи адресации - указывать во входном сообщении
относительный машинный адрес запрашиваемой записи. В некоторых ранних банковских
системах номера счетов видоизменялись так, чтобы новый номер или его часть являлись
бы адресом элемента для данного счета в списке. Таким образом, адрес был равен ключу
или определялся по нему простым способом.
Во многих приложениях такой прямой подход невозможен. Номера изделий на за-
воде не могут изменяться только ради удобства использования ЭВМ, поскольку для работ-
ников фирмы они имеют в запросе определенный смысл.
Иногда во входном сообщении используется внутренний машинный код; при
этом не требуется, чтобы он был равен номеру клиента или номеру изделия. Например,
адрес записи счета в файле может печататься в банковской расчетной книжке клиента
сберкассы и указываться далее в запросе с терминала.
Такие схемы называются прямой адресацией, хотя обычно этот термин использу-
ется в более широком смысле для обозначения любого алгоритма, преобразующего
ключ непосредственно в машинный адрес.
1.7. Алгоритм преобразования ключа в адрес
Способ преобразования ключа в адрес дает почти ту же скорость поиска, что и спо-
соб, в котором используется ключ, эквивалентный адресу. В некоторых приложениях ад-
рес может быть вычислен на основе идентификаторов объекта, таких как адрес улицы и
номер дома или номер рейса и его дата. Для таких приложений рассматриваемый метод
адресации является наиболее простым и быстрым. Чаще всего данный способ применяет-
ся в диалоговых системах, где критичным является время поиска в списке, и называется
хешированием, перемешиванием или рандомизацией.
К недостаткам данного способа относится малое заполнение списка: в списке ос-
таются свободные участки, поскольку ключи преобразуются не в непрерывное множество
адресов.
При этом методе вся область памяти для размещения списка делится на участки –
бакеты размером несколько десятков элементов списка. Сам алгоритм хеширования по
первичному ключу определяет, в отличие от других методов, не адрес одного элемента
списка, а адрес бакета, содержащего целую группу элементов. При размещении элемента в
списке каждый новый элемент добавляется в конец уже имеющихся в бакете элементов;
при поиске - после определения адреса бакета поиск нужного элемента выполняется мето-
дом последовательного сканирования.
Алгоритм хеширования выполняется в три этапа:
1) первый этап выполняется только для нечисловых значений ключей и заключается
в замене их числовыми значениями. Для этого составляется таблица соответствия симво-
лов алфавита, в котором записываются значения ключей, с цифрами от 1 до 9. Затем каж-
дый символ нечислового значения ключа заменяется своим цифровым эквивалентом. На-
пример, если нечисловые значения ключей определены на русском алфавите, такая табли-
ца будет иметь вид:
а 1 и 9 р 8 ш 7
б 2 й 1 с 9 щ 8
в 3 к 2 т 1 э 9
г 4 л 3 у 2 ю 1
д 5 м 4 ф 3 я 2
е 6 н 5 х 4 ь 3
ж 7 о 6 ц 5 ъ 4
з 8 п 7 ч 6 ы 5
Очевидно, разным символам присваивается один цифровой код, что ведет к потере
информации.
Тогда, например, для ключа со значением КОМПЬЮТЕР цифровой эквивалент име-
ет вид 264731168.
2) формируется относительный адрес элемента списка. Для этого числовое значение
адреса приводится к порядку, равному порядку адресов памяти, где размещен список. На-
пример, список размещен на диске в кластерах с номерами от 10 до 999, т.е. в адресах с
порядком, равным 3. Тогда для ключа, полученного на предыдущем этапе, надо выполнить
такое преобразование, чтобы из девятизначного числа превратить его в трехзначное. По-
добные преобразования выполняются разными способами. Рассмотрим некоторые из них:
- возведение в квадрат. Числовое значение ключа возводится в квадрат и в получен-
ном числе по центру выбирается нужное количество цифр. Для нашего случая 2647311682
= 70082591310644200, центральными цифрами являются 131. Таким образом, относитель-
ный адрес для ключа КОМПЬЮТЕР равен 131,
- метод складывания (не путать со сложением). Числовое значение ключа делится на
три части: средняя часть (размещается по центру) имеет количество цифр, равное порядку
адресов памяти, где размещен список; оставшиеся правая и левая части «заворачиваются»
к средней и совпавшие цифры складываются до образования цифр. Например, для ключа
264731168 этот способ дает следующий результат:
264 731 168
левая средняя правая
часть часть часть
После складывания:
731- средняя часть
462 - левая часть, «завернутая» по месту стыка со средней частью
861 - правая «завернутая» часть.
После сложения совпавших цифр (сложение идет до достижения значения цифры):
(7+4+8)(3+6+6)(1+2+1) = (19)(15)(4) = (1+9)(1+5)(4) = (10)(6)(4) = (1+0)(6)(4) = 164
Таким образом, относительный адрес для ключа КОМПЬЮТЕР, полученный вто-
рым способом, равен 164,
- метод деления. Числовое значение ключа делится на количество адресов памяти, в
которой размещается список. Остаток от деления – относительный адрес. Например, для
ключа 264731168 и для числа адресов 989 (999 – 10) остаток от деления равен 593. Это и
есть относительный адрес для ключа КОМПЬЮТЕР,
- метод сдвига. Числовое значение ключа делится на две равные части, которые
смещаются друг навстречу другу так, чтобы общее число разрядов стало равно порядку
адресов памяти. Совпавшие разряды складываются. Например, для ключа 264731168 и для
тех же адресов:
02647 31168
левая правая
часть часть
направление движения
правой и левой частей числа
02647 после сдвига
31168
3 3 7 (10)(15) = 337(1+0)(1+5)=33716
Поскольку полученное число имеет порядок, больший трех, процедура сдвига по-
вторяется:
033 716
левая часть правая часть
033 после сдвига
716
749 – конечный результат – относительный адрес для ключа КОМПЬЮТЕР.
Очевидно, и этот этап дает потерю информации.
3) вычисление абсолютного адреса. Исходная информация – диапазон изменения
относительных адресов (очевидно, от 0 до 999) и адреса размещения элементов списка в
памяти (напомним, что список занимает кластеры с адресами от 10 до 999). Тогда абсо-
лютный адрес для элементов списка получается по формуле:
* const,
где const – константа, получаемая по формуле:
число доступных адресов / максимальный относительный адрес, причем число дос-
тупных адресов – разность между максимальным и минимальным адресами размещения
списка в памяти.
Для нашего случая const = 989 / 999 = 0,989
Тогда, например, для относительного адреса 199 абсолютный адрес (читай – номер
кластера) равен 10 + 199*0,989 = 10+197 = 207.
2. Задания
1. Создать на диске линейный список в соответствии с вариантом (состав полей эле-
ментов списка выбрать самостоятельно по смыслу задачи).
2. Разработать алгоритмы и программы поиска нужной информации в линейном
списке в соответствии с вариантом.
3. Выполнить автоматизированный сравнительный анализ методов адресации, дан-
ных в варианте, на основе обобщенного критерия - произведения числа обращений к ма-
шинному носителю на объем информационной базы (вместе с индексами).
Варианты заданий
Таблица 1
№
варианта
Характеристика записей
файла
Методы адресации (пунк-
ты из п. 1)
Ключ
1
2
3
4
1.
Учетная карточка студен-
ческой группы
1.1, 1.7
Ф. И. О. студента
2.
То же
1.2, 1.6
Порядковый номер в
группе
3.
Экзаменационная ведо-
мость
1.3, 1.4
Ф. И. 0. студента
4.
То же
1.3, 1.5
Номер зачетной книжки
5.
То же
1.1, 1.6
Номер по порядку
6.
Ведомость выдачи сти-
пендии
1.1, 1.5
То же
7.
То же
1.1, 1.4
Ф. И. 0. студента
8.
Прейскурант цен
1.2, 1.7
Наименование товара
9.
То же
1.2, 1.6
Индекс товара
10.
Расписание движения са-
молетов
1.2, 1.5
Номер рейса
11.
Фрагмент телефонного
справочника
1.2, 1.4
Ф. И. 0. абонента
12.
То же
1.2, 1.6
Номер телефона
Продолжение таблицы 1
1
2
3
4
13.
Из варианта 1
1.2, 1.7
Номер в группе
14.
Из варианта 1
1.3, 1.4
Номер в группе
15.
Из варианта 3
1.1, 1.7
Ф. И. 0. студента
16.
То же
1.2, 1.6
Номер зачетной книжки
17.
Из варианта 6
1.2, 1.7
Номер по порядку
18.
То же
1.1, 1.6
То же
19.
То же
1.3, 1.5
То же
20.
Из варианта 8
1.1, 1.5
Индекс товара
21.
То же
1.3, 1.4
То же
22.
Из варианта 10
1.1, 1.7
Номер рейса
23.
То же
1.3, 1.6
То же
24.
Из варианта 11
1.1, 1.5
Номер телефона
25.
То же
1.3, 1.7
То же
ЧАСТЬ 2. АВТОКОРРЕКЦИЯ ТЕКСТА
ВВЕДЕНИЕ
Программы автоматического обнаружения и исправления ошибок в текстах на есте-
ственных языках (назовем их автокорректорами - АК, хотя терминология ещё не сложи-
лась) получают все большее распространение. Они используются, в частности, в пакетах
WINWORD и EXCEL для проверки орфографии текстовой информации.
Говоря точнее, АК производят автоматически лишь обнаружение ошибок, а собст-
венно коррекция ведется обычно при участии человека.
В высокофлективных языках, к которым относятся, в частности, все славянские, от
одной основы могут образовываться до нескольких сот различных словоформ. В этих ус-
ловиях в АК неизбежны средства морфологического анализа той или иной сложности, а
непосредственное использование западных АК и перенос методов их работы на неанглоя-
зычные тексты едва ли даст удовлетворительные результаты, если исключить метод "гру-
бой силы" - неограниченное наращивание объема оперативной памяти (ОП) и быстродей-
ствия ЭВМ.
1. Теоретическая часть
1.1. Методы обнаружения ошибок
Известны, по крайней мере, три метода автоматизированного обнаружения орфо-
графических ошибок в текстах - статистический, полиграммный и словарный.
При статистическом методе из текста одна за другой выделяются составляющие его
словоформы, а их перечень по ходу проверки упорядочивается согласно частоте встречае-
мости. По завершении просмотра текста упорядоченный перечень предъявляется человеку
для контроля, например, через экран дисплея. Орографические ошибки и описки в сколь-
нибудь грамотном тексте несистематичны и редки, так что искаженные ими слова оказы-
ваются где-то в конце перечня. Заметив их здесь, контролирующее лицо может автомати-
зированно найти их в тексте и исправить.
При полиграммном методе все встречающиеся в тексте двух- или трехбуквенные
сочетания (биграммы и триграммы) проверяются по таблице их допустимости в данном
естественном языке. Если в словоформе не содержится недопустимых полиграмм, она счи-
тается правильной, а иначе - сомнительной, и тогда предъявляется человеку для визуаль-
ного контроля и, если нужно, исправления.
При словарном методе все входящие в текст словоформы, после упорядочения или
без него, в своем исходном текстовом виде или после морфологического анализа, сравни-
ваются с содержимым заранее составленного машинного словаря. Если словарь такую
словоформу допускает, она считается правильной, а иначе предъявляется контролеру. Он
может оставить слово как есть; оставить его и вставить в словарь, так что далее в сеансе
подобное слово будет опознаваться системой без замечаний; заменить (исправить) слово в
данном месте; потребовать подобных замен по всем дальнейшему тексту; отредактировать
слово вместе с его окружением. Операции над сомнительным участком текста, указанные
или иные возможные, могут комбинироваться исходя из замысла проектировщика АК.
Результаты неоднократных исследований показали, что только словарный метод
экономит труд человека и ведет к минимуму ошибочных действий обоих родов - пропуска
текстовых ошибок, с одной стороны, и отнесения правильных слов к сомнительным, с дру-
гой. Поэтому словарный метод стал доминирующим, хотя полиграммный метод иногда и
применяют как вспомогательный.
1.2. Автоматизация процесса исправления
Можно предложить три степени автоматизации процесса коррекции текста:
1) только обнаружение ошибок,
2) обнаружение их и выдвижение гипотез (альтернатив, кандидатов) по исправле-
нию;
3) обнаружение ошибок, выдвижение гипотез и принятие одной из них (если хотя
бы одна выдвинута системой) в качестве автоматически вносимого исправления.
Без первой степени АК немыслим.
Вторая и третья степень возможны только при словарном методе. Уже вторая суще-
ственно облегчает внесение исправлений, ибо в большинстве случаев исключает перена-
бор сомнительного слова. Особенно полезны найденные альтернативы, когда контро-
лирующее текст лицо нетвердо знает данный естественный язык или конкретную терми-
нологическую область. Однако выдвижение гипотез требует больших переборов с поиском
по словарю. Поэтому современные АК часто имеют средство выдвижения гипотез лишь в
качестве факультативного, запускаемого, если требуется, избирательно для данного со-
мнительного слова.
Третья степень автоматизации заманчива и одновременно опасна. Заманчивость за-
ключается в полной автоматизации процесса исправления. Опасность же в том, что ни
один словарь, в том числе - заключенный в человеческом мозгу, никогда не бывает исчер-
пывающе полным. Когда незнакомое слово встречает система, основанная на неполном
словаре, она может "исправить" его на ближайшее ей знакомое, порой резко исказив ис-
ходный смысл текста. Особо опасно править собственные имена лиц, фирм, изделий, За-
манчиво уметь пропускать (обходить) собственные имена и сугубо специальные термины,
априори полагая их правильными, но безошибочные способы обхода, особенно - терми-
нов, нам не известны.
Чисто автоматическому исправлению мог бы способствовать автоматический син-
таксический и семантический анализ проверяемого текста, но он ещё не стал принадлеж-
ностью обычных АК. И даже при его наличии лишь человек сможет диагностировать бы-
стро меняющиеся совокупности собственных имен, терминов и аббревиатур, а также окка-
зионализмы - случайно появляющиеся словесные новации.
В связи со сказанным полная автоматизация исправлений может применяться лишь
в любом из следующих ограничительных условий:
I) Текст имеет вид перечня терминов и терминологических словосочетаний в стан-
дартной их форме, так что в АК достаточно иметь словарь, замкнутый по объему и про-
блематике. При этом все термины между собой "непохожи" (например, в словаре нет од-
новременно АДСОРБЦИЯ и АБСОРБЦИЯ).
2) Ошибки носят характер замены кодов исходных букв на коды литер, совпадаю-
щих или близких к исходным по начертанию. Например, заменяются коды ASCII русских
букв А, В, С, Е, У на коды латинских букв А, В, С, Е, У; латинские буквы I и 0 - на цифры I
и 0 и т.п. Сюда же отнесем повторы одной и той же литеры, возникающие из-за продлен-
ного нажима клавиши дисплея или его неисправности. В подавляющем большинстве, если
в словоформе более 2 -3 букв, такие исправления абсолютно правильны.
1.3. Диалоговый и пакетный режимы
Возможны, в общем случае, два режима работы АК: диалоговый, когда текст прове-
ряется слово за словом и пользователю предоставляется возможность снять очередное за-
труднение по мере его возникновения, и пакетный, когда готовые большие тексты анали-
зируются в отсутствии пользователя.
Во втором случае ненайденные словоформы либо как-то отмечаются в исходном
тексте, либо запоминаются отдельно в виде своих адресов (в качестве адреса может ис-
пользоваться, например, номер строки и номер символа, с которого начинается слово, в
строке). Подобная проверка ведется до конца проверяемого файла без вмешательства че-
ловека. Далее файл вызывается снова и предъявляется для контроля тех строк, где были
замечены сомнительные слова.
2. Задания
1. Создать русскоязычный текстовый файл в ASCII-кодах размером с машинопис-
ный лист.
2. Разработать алгоритмы и программы автокорректора русскоязычного текста с
характеристиками, указанными в вариантах. Автокорректор должен позволять обнаружи-
вать и исправлять ошибки в любом тексте, представленном в ASCII-кодах в виде файла.
Варианты заданий
Таблица 2
№ ва-
рианта
Метод обнаружения
ошибок
Метод исправления ошибок
Способ реали-
зации
1
2
3
4
1.
Статистический
Исправления только в тексте, без гипотез
Диалоговый
2.
То же
Исправления и в словаре, без гипотез
Пакетный
3.
То же
Исправления только в тексте, с выдвижени-
ем гипотез
Диалоговый
4.
То же
Исправления и в словаре, с выдвижением
гипотез
Пакетный
5.
Полиграммный (би-
граммы)
Исправления только в тексте, без гипотез
Диалоговой
6.
То же
Исправления и в словаре, без гипотез
Пакетный
7.
То же
Исправления только в тексте, с выдвижени-
ем гипотез
Диалоговый
8.
То же
Исправления и в словаре, с выдвижением
гипотез
Пакетный
9.
Словарный
Исправления только в тексте, без гипотез
Диалоговый
10.
То же
Исправления и в словаре, без гипотез
Пакетный
Продолжение таблицы 2
1
2
3
4
11.
То же
Исправления только в тексте, с выдвижени-
ем гипотез
Диалоговый
12.
То же
Исправления и в словаре, с выдвижением
гипотез
Пакетный
ЧАСТЬ 3. СЖАТИЕ ИНФОРМАЦИИ
ВВЕДЕНИЕ
В процессе ускоренной компьютеризации общества объемы данных, хранимых на
машинных носителях, быстро растут. Ещё совсем недавно они измерялись килобайтами и
мегабайтами, а теперь - гигабайтами и более крупными единицами. Естественно желание
хранить эти данные предельно компактно. Причем интересны обратимые методы, устра-
няющие избыточность информации при сжатии и восстанавливающие её при разжатии.
Описанные в методических указаниях методы обратимы.
Объектами сжатия являются:
- числовые данные,
- упорядоченные текстовые данные (словари),
- специальные тексты на формализованных языках,
- естественно-языковые тексты общего вида,
- структурированные данные.
В качестве количественной меры сжатия используется коэффициент сжатия - отно-
шение длины первоначального к сжатому тексту, а также продолжительность требуемых
преобразований.
1. Теоретическая часть
1.1. Сжатие числовых данных
Наиболее распространены методы: разностное кодирование, кодирование повторе-
ний и подавление незначащих нулей.
Суть разностного кодирования заключается в хранении вместо абсолютных значе-
ний разностей двух смежных чисел или отклонения чисел от их среднего значения. На-
пример, для последовательности чисел 2, 14, 18, 27, 34 первый способ даст после-
довательность 2, 12, 4, 9, 7. Второй способ порождает последовательность: -17, -5, -1, 8, 15
(среднее значение для исходной последовательности - 19).
Первый вариант эффективен для медленно меняющихся последовательностей, вто-
рой - когда максимальное отклонение от среднего значительно меньше абсолютного зна-
чения среднего.
Кодирование повторений заключается в замене цепочки одинаковых символов ко-
дом этого числа и числом повторений. Например, для последовательности 5555 6666
888888 применение этого способа даст последовательность 5(4) 6(4) 8(6).
Подавление незначащих нулей означает отбрасывание незначащих нулей в старших
разрядах целой части числа и в младших разрядах дробной части. Например, применение
этого способа сжатия к последовательности 0010 01,100 011 011 даст последовательность:
10 1,1 11 11.
1.2. Сжатие словарей
Под словарями понимают списки неповторяющихся цепочек символов в алфавит-
ном или ином строгом порядке. Такой словарь можно рассматривать как монотонную по-
следовательность чисел и для его сжатия применять метод разностного кодирования (см.
п.1.1). Здесь он заключается в отбрасывании у каждого слова начальных букв, совпадаю-
щих с начальными символами предыдущего слова и замене их на число отброшенных
букв. Например, словарь:
вычислитель
вычислительный
вычислять
в результате рассматриваемого способа кодирования будет заменен словарем:
вычислитель
11ный
6ять.
Такой метод, однако, неудобен тем, что при декодировании любого конкретного
слова требуется последовательно декодировать все предшествующие слова. Поэтому по-
рой используются отдельные перечни наиболее часто встречающихся частей слов (суф-
фиксы, префиксы), где каждой из них ставится в соответствие более короткий код, заме-
няющий её в словаре. Например, словарь:
встречающийся
заменяющий
с помощью этого способа сжатия заменится на совокупность словарей:
основной вспомогательный
встреча1ся 1- ющий
заменя1
Важнейшим здесь является алгоритм выбора достаточно длинных и часто встре-
чающихся подцепочек. При его разработке используются эвристические алгоритмы, по-
скольку эффективного алгоритма поиска оптимального решения не существует.
Когда составляющие словаря образуют сильно обособленные группы слов, можно
разделить весь словарь на подсловари, присвоив каждому из них свой индекс, и кодиро-
вать слова независимо в каждом из них кодами минимальной длины, а слова из различных
подсловарей различать этими индексами. Такой метод является модификацией описанного
в п. 1.1 метода сжатия числовых данных через их среднее значение.
1.3. Сжатие специальных текстов
К специальным относятся тексты на формальных языках, отличающихся ограничен-
ным словарем, замкнутой грамматикой. Сюда прежде всего относятся тексты на языках
программирования, машинные коды, различные формулы и обозначения, а также ограни-
ченные подмножество фраз естественного языка в таких четко формализованных задачах
как организация реплик в интерактивных системах, выдача сообщений при компиляции и
т.п.
Для данного типа информации пригодны методы, описанные в п. 1.5. В то же время
специфика этих текстов позволяет осуществить экономное хранение, основанное на выде-
лении длинных часто повторяющихся фрагментов. Например, текст Фортран-программы:
ТYРЕ *,'ФОРТРАН'
ТYРЕ *,'ПРОГРАММА'
может быть представлен с использованием кодового словаря:
программа словарь
1,'ФОРТРАН' 1 - ТУРЕ *
1,'ПРОГРАММА'
1.4. Сжатие структурированных данных
Структурированные данные содержат текстовую и иную информацию и хранятся в
определенном формате, приемлемом для тех или иных прикладных задач, например, для
документального или фактографического поиска информации. Пример структурированных
данных - библиографические описания.
Разнородность данных структурированного типа обуславливает различные типы
информационной избыточности, поэтому необходимо использовать комбинацию методов,
приспособленных к своим подгруппам данных. Так, для числовых полей целесообразно
применять методы п. 1.1, для текстовых - описанные в п. 1.5. По некоторым оценкам ком-
бинация этих методов дает сокращение объема данных в 1,5-4 раза, по другим оценкам -
даже до 6 раз.
В структурированных данных наряду с типами информационной избыточности, ха-
рактерных для текстовых или нетекстовых данных, существует особый позиционный тип
избыточности. Он связан с дублированием информации для идентификации структуры
данных. Например, если записи файла имеют структуру:
Ф.И.О. студента
отношение к воинской обязанности
домашний адрес
специальность
оценки за сессию,
причем поля имеют длину, соответственно, 40, 20, 50, 15, 10 байт, то при различных
значениях тех или иных полей для конкретных студентов часть области памяти, отводимой
под отдельные поля, не будет использоваться. Тогда, если поле «Отношение к воинской
обязанности» пусто, его можно исключить из конкретной записи и вся запись будет иметь
следующий вид:
(Ф.И.О. студента)1(домашний адрес)3(специальность)4(оценки за сессию)5,
где индексы означают принадлежность того или иного значения соответствующему
полю.
1.5. Сжатие текстовой информации общего вида
Принципиальная возможность сжатия текстовой информации связана с тем, что со-
ставляющие текста - буквы и словоформы - различаются по частоте встречаемости в тек-
сте, в то время как их длины слабо связаны с частотой.
Все алгоритмы сжатия можно классифицировать по используемому методу кодиро-
вания и характеру использования статистики и грамматики текста.
Методы кодирования можно разделить на четыре класса в зависимости от того,
какие группы символов кодируются (постоянной или переменной длины), и какие коды
используются (постоянной или переменной длины).
По использованию статистики и грамматики алгоритмы сжатия можно разделить
на семантически зависимые и семантически независимые. Первые (лингвистические) ме-
тоды опираются на грамматику естественного языка для выделения в текстах элементов,
подлежащих кодированию (как правило, это отдельные слова – словоформы).
Семантически независимые методы сжатия в свою очередь можно разделить на те,
которые не используют, и те, которые используют априорные сведения о статистике тек-
ста. В соответствии с этим существуют два типа алгоритмов сжатия: одно - и двухфазные,
которые будем называть соответственно адаптивными и статистическими.
Семантически зависимые методы не используют для сжатия никаких априорных
сведений о статистике текста. Кодирование производится в процессе однократного скани-
рования текста. Оно сводится к замене цепочек символов текста на встроенные указатели,
адресованные к той части текста, где такие цепочки уже встречались. В этом случае гово-
рят о внутренней адресации, а сами методы называются адаптивными.
В алгоритмах второго типа выполняется ссылка на таблицу кодов, которая может
создаваться заново для каждого текста или использоваться одна на все гипотетические
тексты. В этом случае говорят о внешней адресации и локальных или глобальных кодовых
таблицах.
1.5.1. Адаптивные алгоритмы
Строят код постоянной длины для фрагментов переменной длины.
Сжимают текст в процессе однократного его сканирования. Кодирование заключа-
ется в нахождении повторяющихся участков текста и замене каждого участка указателем,
адресованным к той части текста, где такой участок уже встречался. Для декодирования в
этом случае кодовой таблицы не требуется. В качестве указателя может использоваться
структура (m, n), где m – количество символов назад или вперед по тексту, переместив-
шись на которые можно найти подобный фрагмент текста; n – длина фрагмента в симво-
лах.
Существует два типа встроенных указателей, указывающих на предшествующие
или последующие участки. Алгоритмы, использующие указатели назад, могут работать с
непрерывным входным потоком данных, генерируя непрерывный выходной поток сжатой
информации. На каждом шаге алгоритма входной текст заполняет буфер фиксированной
длины, внутри которого производится идентификация одинаковых подстрок максимально
возможной длины. При нахождении двух таких подстрок вторая заменяется указателем,
адресованным в начало первой.
Алгоритмы с указателями вперед могут работать лишь с текстами конечной длины,
поскольку требуют обратного сканирования текста. Здесь также используется поиск сов-
падающих подстрок в буфере переменной длины с уже закодированным текстом.
Одной из характерных черт адаптивных алгоритмов является достаточная их уни-
версальность, т.е. возможность работать с любыми, не только текстовыми данными, не-
нужность начальной информации о характере данных и их статистике. Эта черта снижает
эффективность сжатия и достигаемое сжатие, как правило, меньше полученного другими
методами. Но часто адаптивные алгоритмы просты и все же приемлемы по эффективности.
Коэффициент сжатия текстовых данных этим методом лежит в пределах 1,8 - 2,5.
1.5.2. Статистические алгоритмы.
1.5.2.1. Кодирование фрагментов фиксированной длины
Простейшей формой словаря в этом случае является кодовая таблица символов ал-
фавита, ставящая в соответствие каждому символу свой код. Коды выбираются с таким
расчетом, чтобы общая длина закодированного ими текста была минимальной. Такую же
таблицу можно составить для всех или наиболее часто встречающихся комбинаций из
двух, трех и т.д. букв, т.е. фрагментов с фиксированным числом символов. Ниже приведе-
ны частоты букв в русском языке:
пробел 0,174 ы 0,016
о 0,080 з 0,016
е, ё 0,071 ъ 0,014
а 0,061 ь 0,014
и 0,061 б 0,014
т 0,052 г 0,013
м 0,052 ч 0,012
с 0,045 й 0,010
р 0,040 у 0,009
в 0,038 ж 0,007
л 0,035 ю 0,006
к 0,028 ш 0,006
н 0,026 ц 0,003
д 0,025 щ 0,003
п 0,023 э 0,003
у 0,021 ф 0,002
я 0,018 х 0,002
Сами коды рассчитываются на основании частот отдельных символов (в случае таб-
лицы символов) или их комбинаций (в этом случае общая частота рассчитывается как про-
изведение частот отдельных символов, входящих в комбинацию) с помощью методов
Шеннона-Фано или Хаффмена (описание методов см. в приложении 1).
Избыточность информации заключается ещё в корреляции между символами (сло-
вами). Метод Хаффмена сохраняет эту избыточность. Существуют модификации метода,
позволяющие учесть взаимозависимости. Наиболее простая из них используется, когда все
символы можно разделить на небольшое число групп с сильной корреляцией внутри групп
и слабой - между ними. Это иногда имеет место для числовых и буквенных символов тек-
ста.
К другим недостаткам хаффменовских методов относится относительная сложность
декодирования - необходимость анализа битовой структуры префиксных кодов, замед-
ляющая процесс декодирования.
Дальнейшим развитием метода Хаффмена являются арифметические коды. Они
происходят из так называемых конкатенационных, или блочных, кодов. Суть их заключа-
ется в том, что выходной код генерируется для цепочки входных символов фиксированной
длины без учета межсимвольных корреляций. В основе метода лежит представление веро-
ятности каждой цепочки К входных символов (А1, А2, ... АК ) в виде числа, получаемого
как сумма К слагаемых вида
p(А1)p(А2)..р(АI-1)P(АI), I=1, 2, 3, …… K
где р (S) - вероятность символа S,
Р(S)- куммулятивная вероятность символа S, равная сумме вероятностей всех сим-
волов AI, для которых р(АI) больше р(S).
1.5.2.2. Кодирование фрагментов переменной длины
Другой формой словаря может являться словарь фрагментов переменной длины.
Словари фрагментов переменной длины строятся из словоформ, которые выделяются в
тексте по естественным разделителям – пробелам и знакам пунктуации. Затем рассчиты-
ваются частоты каждой словоформы как отношение числа ее повторений к общему коли-
честву словоформ. Используя эти частоты, применяют метод Хаффмена или Шеннона-
Фано для кодирования словоформ кодом переменной длины.
2. Задания
1. Создать файл с информацией, соответствующей объекту сжатия.
2. Разработать алгоритмы и программы сжатия и разжатия информации по вариан-
там из таблицы. Исходные данные после выполнения обеих процедур должны соответст-
вовать результату.
3. Определить результативность алгоритмов сжатия, соотнеся объем сжатого и ис-
ходного текста.
Варианты заданий
Таблица 3
№
вари
анта
Объект сжатия
Метод сжатия
1
2
3
1
Числовые данные
Разностное кодирование (разность двух смежных чисел)
2
То же
Разностное кодирование (отклонение числа из массива от
среднего значения массива чисел)
3
То же
Кодирование повторений (повторяется один символ)
4
То же
Кодирование повторений (повторяется один или два символа)
5
То же
Подавление незначащих нулей
6
Словарь
Разностное кодирование
7
То же
С помощью словаря суффиксов (задается априори)
8
То же
С помощью словаря префиксов (задается априори)
9
То же
С помощью словаря префиксов, который создается динамиче-
ски, в зависимости от обрабатываемого текста; длина префикса
– не более 4 символов
10
То же
С помощью словаря суффиксов (задается априори, делится на
подсловари)
11
То же
С помощью словаря префиксов (задается априори, делится на
подсловари)
12
Специальный текст –
Паскаль-программа
Кодовый словарь
Продолжение таблицы 3
1
2
3
13
Структурированные
данные
Индексация структурных единиц
14
Естественно-
языковый текст
Адаптивный с указателями назад
15
То же
Адаптивный с указателями вперед
16
То же
Метод Шеннона-Фано, глобальный словарь символов
17
То же
Метод Хаффмена, локальный словарь символов
18
То же
Метод Хаффмена, глобальный словарь биграмм
19
То же
Метод Шеннона-Фано, локальный словарь биграмм
20
То же
Метод Хаффмена, глобальный словарь триграмм
21
То же
Метод Шеннона-Фано, локальный словарь триграмм
22
То же
Метод Хаффмена, локальный словарь триграмм
23
То же
Арифметические коды, К=5
24
То же
Метод Шеннона-Фано для словоформ
25
То же
Метод Хаффмена для словоформ
ПРИЛОЖЕНИЕ 1. Методы сжатия данных
Метод Шеннона-Фано
Знаки упорядочиваются по возрастанию их частот и образуют частичные суммы Si =
?pj (j = 1, 2, 3, ….. i), где рj - частота j-того знака. Далее процесс разбивается на несколько
шагов. В первом шаге столбец знаков рассекается на две части так, чтобы частичная сумма
сечения была близка к 0,5. Процесс деления подстолбцов повторяется так, чтобы каждый
раз частичная сумма в точке сечения оказывалась ближе к среднему арифметическому час-
тичных сумм на нижнем и верхнем краях разделяемого подстолбца. При каждом разбие-
нии элементам верхней части ставится в соответствие 1, нижней - 0. Например: пусть
знаки рi
A 0,11
B 0,15
C 0,20
D 0,24
E 0,30
Тогда процедура разбиения складывается из шагов:
Знаки pi коды
A 0,11 1 1 111
B 0,15 1 0 110
C 0,20 0 10
D 0,24 0 1 01
E 0,30 0 00
шаг1 шаг2 шагЗ
Метод Хаффмена
Знаки упорядочиваются по возрастанию частоты. Два самых редких знака объеди-
няются в один класс, и их частоты складываются. Полученные частоты переупорядочива-
ются и процесс повторяется до тех пор, пока все знаки ни будут объединены в один класс.
Например,
Знаки pi Знаки pi
A 0,11 (0) C 0,20 (0)
B 0,15 (1) D 0,24 (1)
C 0,20 F 0,26
D 0,24 E 0,30
E 0,30
Знаки pi Знаки pi
F 0,26 (0) G 0,44 (0)
E 0,30 (1) H 0,56 (1)
G 0,44
Тогда коды исходных символов (они «собираются» из частных кодов дополнитель-
ных обозначений – F, G, H- в обратном относительно хода кодировки порядке):
Исходные Коды Пояснения
символы
A 100 (А вошел в F с кодом 0; F вошел в H с кодом 0; у H код 1.
Тогда обратный порядок - 100)
B 101 (B вошел в F с кодом 1; F вошел в H с кодом 0; у H код 1.
Тогда обратный порядок – 101)
С 00 (С вошел в G с кодом 0; у G код 0)
D 01 (D вошел в G с кодом 1; у G код 0. Тогда обратный поря-
док – 01)
E 11 (E вошел в H с кодом 1, у H код 1)
ПРИЛОЖЕНИЕ 2. Правила оформления индивидуальных заданий
Оформление индивидуальных заданий должно быть выполнено аккуратно от руки
или отпечатано на принтере, на листах формата А4, включать блок-схемы алгоритмов и
рисунки, описывающие структуры информационных массивов, используемых при реше-
нии задачи (например, индексов, словарей, кодовых таблиц), а также, возможно, различ-
ные иллюстрации к происходящим процессам, выполненные в текстовом процессоре
WinWord, тексты (возможно, распечатки) программ.
Для заданий, связанных с методами адресации, включить распечатки файлов, со-
ставляющих информационную базу, результаты работы программ поиска информации и
сравнения различных методов по обобщенному критерию.
Для заданий, связанных с автокоррекцией текстов, включить распечатки словарей,
если они используются.
Для заданий по методам сжатия включить распечатки исходного, сжатого и разжа-
того файлов.
Структура отчета:
1. Титульный лист (оформление см. далее).
2. Задание (из соответствующей таблицы заданий).
3. Основной текст, отвечающий на следующие вопросы:
? функциональное назначение программы,
? для какого компьютера, операционной системы она предназначена. Требуемые ресурсы
компьютера,
? какие данные являются входными, как они вводятся и есть ли ограничения на их значе-
ния; как организован контроль вводимых данных в программу,
? какие данные являются выходными, в каком формате они представлены и на каком но-
сителе,
? какие информационные структуры используются при решении задачи (включить их
описание в виде рисунков с пояснениями),
? состав программ программного обеспечения: какие программные модули входят и ка-
кие функции каждый из них выполняет (комментарии к модулям представить в виде
блок-схем),
? взаимосвязь модулей и данных. Отразить ее в таблице следующей структуры:
Название модуля
Входные данные
Выходные данные
имена файлов, информационных
массивов, переменных
имена файлов, информацион-
ных массивов, переменных
? организация диалога с программой: какие вопросы и в каком формате задает програм-
ма и как на них отвечает пользователь. Оценить диалог в соответствии с критериями
хорошего диалога.
Калининградский государственный технический университет
Кафедра систем управления и вычислительной техники
Индивидуальное задание по информатике
на тему: ___________________________
(название темы)
Вариант № ___
Работу принял: Работу выполнил:
_____________________ ст. гр. ______________
(ученая степень и звание преподавателя) (номер учебной группы)
_____________________ ____________________
(Ф.И.О. преподавателя) (Ф.И.О. студента)
_____________________
(оценка)
Подпись:_____________ Подпись:____________
Дата: ________________ Дата:_______________
Калининград
____ г.
ОГЛАВЛЕНИЕ
Введение 3
ЧАСТЬ 1. МЕТОДЫ АДРЕСАЦИИ 4
ВВЕДЕНИЕ 4
1. Теоретическая часть 4
1.1. Последовательное сканирование списка 4
1. 2. Блочный поиск 5
1.3. Двоичный поиск 5
1.4. Индексно-последовательная организация 5
1.5. Индексно-произвольная организация 6
1.6. Адресация с помощью ключа, эквивалентного адресу 8
1.7. Алгоритм преобразования ключа в адрес 8
2. Задания 12
ЧАСТЬ 2. АВТОКОРРЕКЦИЯ ТЕКСТА 14
ВВЕДЕНИЕ 14
1. Теоретическая часть 14
1.1. Методы обнаружения ошибок 14
1.2. Автоматизация процесса исправления 15
1.3. Диалоговый и пакетный режимы 16
2. Задания 17
ЧАСТЬ 3. СЖАТИЕ ИНФОРМАЦИИ 19
ВВЕДЕНИЕ 19
1.Теоретическая часть 19
1.1. Сжатие числовых данных 19
1.2. Сжатие словарей 20
1.3. Сжатие специальных текстов 21
1.4. Сжатие структурированных данных 21
1.5. Сжатие текстовой информации общего вида 22
1.5.1. Адаптивные алгоритмы 23
1.5.2. Статистические алгоритмы. 24
1.5.2.1. Кодирование фрагментов фиксированной длины 24
1.5.2.2. Кодирование фрагментов переменной длины 25
2.Задания 26
ПРИЛОЖЕНИЕ 1. Методы сжатия данных 28
Метод Шеннона-Фано 28
Метод Хаффмена 28
ПРИЛОЖЕНИЕ 2. Правила оформления индивидуальных заданий 30
Добавление незначащего нуля обусловлено требованием четности числа цифр
1
31