Индивидуальные задания по информатикеРефераты >> Программирование и компьютеры >> Индивидуальные задания по информатике
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ять.
Такой метод, однако, неудобен тем, что при декодировании любого конкретного слова требуется последовательно декодировать все предшествующие слова. Поэтому порой используются отдельные перечни наиболее часто встречающихся частей слов (суффиксы, префиксы), где каждой из них ставится в соответствие более короткий код, заменяющий её в словаре. Например, словарь:
