Реферат: Методические указания по информатике - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Методические указания по информатике

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 38 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Методические указания для выполн ения индивидуальных заданий для сту дентов направления 552800 “Информатика и вычислительная техника” Введение Тенденция усиления фактора самостоятельной работы студентов привела к разработке данн ых методических указаний по выполнению индиви дуальных заданий по инфор матике . Они п ризваны , с одной стороны , подробно ознакомить обучающихся с некоторыми практическими задач ами информатики , а с другой – закрепить навыки прикладного программирования и состав ления блок-схем. Настоящие методические указания состоят и з трех само стоятельных частей , в котор ых излагаются три практические задачи совреме нной информатики – адресация элементов данны х линейного списка , автокоррекция естественно языковых текстов , сжатие данных. Первая задача нашла свое применение в таких программных проду ктах , как сист емы управления базами данных , операционные си стемы (организация поисковых операций в систе мных данных ), компиляторы (работа с таблицами идентификаторов ) и многих других . Алгоритмы адресации имеют универсальный характер и испо льзуются практич е ски во всех зада чах , в которых ведется организация и поиск информации в одномерных массивах , независимо от места ее нахождения – основная п амять или внешняя. Вторая задача носит более частный хар актер , а изложенные методы используются при проверке орфограф ии в текстовых и табличных процессорах , издательских системах , а также как средство верификации результатов работы сканера – после распознавания текс та для устранения возможных ошибок выполняетс я его орфографический анализ. Проблема сжатия данных решается в современных архиваторах . Они , как правило , и спользуют комбинацию методов , изложенных в тр етьей части. Задачи программируются на языке программи рования , который изучается в курсе “Алгоритми ческие языки и программирование” , и , тем с амым , закрепляют навыки , полученные в это й дисциплине . Кроме этого , требование подготов ки блок-схем средствами WinWord позволяет углубить знания , связанные , с одной стороны , с логич еским проектированием алгоритма , а с другой – с правилами начертания блок-схем. Запрограммированны е и отлаженные зада чи должным образом оформляются , что также способствует умению студента правильно и акку ратно закреплять результат работы на бумажном носителе информации. ЧАСТЬ 1. МЕТОДЫ АДРЕСАЦИИ ВВЕДЕНИЕ Одной из проблем при создании информа ционных систем является работа со структуриро ванными данными , которые чаще всего являются линейными списками – упорядоченным множеств ом элементов , порядковые номера которых опред еляют местоположение элемента в спи ске . Элементы списка имеют структуру – они состоят из конечного множества полей , каждо е из которых имеет определенный смысл , нап ример , фамилии , адреса и т.д . Для таких списков важна задача адресации элементов спис ков – определение адреса элемента списка п о одному из его полей или по совокупному набору полей . Такие поля называются ключевыми (или ключами ) (в просте йшем случае ключом , например , может быть н омер зачетной книжки студента ). Иногда бывает необходимо объединить неско лько полей , чтобы образовать ун икальный ключ , называемый в этом случае сцепленным ключом : например , ключ , идентифицирующий студент а в институте , является комбинацией номера группы , фамилии , имени и отчества студента (есть случаи , когда в одной группе уча тся студенты с одинаковыми фамил и ями и именами ). Кроме простого и сцепленного , ключ мож ет быть первичным – определять максимум один элемент в списке или вторичным – определять множество (в общем случае не одноэлементное ) элементов в списке . Например , фамилия студента в учебной группе , как правило , является первичным ключом , а пол студента – вторичный ключ , поскольку одному значению этого ключа (мужской или женский ) соответствует , в общем случае , груп па студентов. Основную проблему при адресации элементов списков можно сформулировать следую щим образом : как по первичному ключу определи ть местоположение элемента с данным ключом (задача поиска )? Существует несколько различных способов адресации . Они рассматриваются дале е. 1. Теоретическая часть 1.1. Послед овательное сканирование списка Наиболее простым способом локализации эле мента списка является сканирование списка с проверкой ключа каждого элемента . Этот сп особ , однако , требует слишком много времени для большинства применений . Он может быть эффективен только при пакетной обработке последовательного файла , находящегося , например , на магнитной ленте , когда каждая запись все равно должна быть прочитана. 1. 2. Блочный поиск Если элементы упорядочены по ключ у , то при ск анировании списка не т ребуется чтение каждого элемента . Компьютер м ог бы , например , просматривать каждый n-ный элемент в последовательности возрастания ключей . При нахождении элемента с ключом , больши м , чем ключ , используемый при поиске , просм атриваются п о следние n-1 элементов , кото рые были пропущены . Этот способ называется блочным поиском : элементы группируются в бл оки , и каждый блок проверяется по одному разу до тех пор , пока ни будет на йден нужный блок . Вычисление оптимального для блочного поиска размер а блока выполняется следующим образом : в списке , содер жащем N элементов , число просмотренных элементов минимально при длине блока , равной N . При этом в среднем анализирует ся N элемен тов. 1.3. Двоичный поиск При двоичном поиске рассматривается элеме нт , находящийся в середине области , в кото рой выполняется поиск , и его ключ сравнива ется с поисковым ключом . Затем поисковая о бласть делится пополам , и процесс повторяется . При этом , если N велико , то в сре днем будет просмотрено примерно log 2 N-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. Тогда для ключа , получе нного на предыдущем этапе , надо выполнить такое преобразов а ние , чтобы из дев ятизначного числа превратить его в трехзначно е . Подобные преобразования выполняются разными способами . Рассмотрим некоторые из них : возведение в квадрат . Числовое значение ключа возводится в квадрат и в получен ном числе по центру выбираетс я нужное количество цифр . Для нашего случая 264731168 2 = 70082591310644200, центральными ц ифрами являются 131. Таким образом , относительный адрес для ключа КОМПЬЮТЕР равен 131, метод складывания (не путать со сложен ием ). Числовое значение ключа делится на три части : средняя часть (размещается по центру ) имеет количество цифр , равное п орядку адресов памяти , где размещен список ; оставшиеся правая и левая части “заворачив аются” к средней и совпавшие цифры склады ваются до образования цифр . Например , для ключа 2 64731168 этот способ дает следующ ий результат : После складывания : 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. Это и есть относительный адрес для ключа КОМПЬЮТЕР, 3) вычисление абсолютного адре са . Исх одная информация – диапазон изменения относи тельных адресов (очевидно , от 0 до 999) и адреса размещения элементов списка в памяти (нап омним , что список занимает кластеры с адре сами от 10 до 999). Тогда абсолютный адрес для элементов списка получает с я по формуле : <начальный адрес размещения списка > + <отн осительный адрес элемента > * const, где const – константа , получаемая по форм уле : число доступных адресов / максимальный отн осительный адрес , причем число доступных адре сов – разность между максималь ным и минимальным адресами размещения списка в памяти. Для нашего случая const = 989 / 999 = 0,989 Тогда , например , для относительного адреса 199 абсолютный адрес (читай – номер кластер а ) равен 10 + 199*0,989 = 10+197 = 207. ЧАСТЬ 2. АВТОКОРРЕКЦИЯ ТЕКСТА ВВЕДЕНИЕ Программы автоматического обнаружения и и справления ошибок в текстах на естественных языках (назовем их автокорректорами - АК , х отя терминология ещё не сложилась ) получ ают все большее распространение . Они и спользуются , в частности , в пакетах WINWORD и EXCEL д ля проверки орфографии текстовой информации. Говоря точнее , АК производят автоматическ и лишь обнаружение ошибок , а собственно ко ррекция ведется обычно при участии че ловека. В высокофлективных языках , к которым о тносятся , в частности , все славянские , от о дной основы могут образовываться до нескольки х сот различных словоформ . В этих условиях в АК неизбежны средства морфологического анализа той или иной сложности , а непо средственное испо льзование западных АК и перенос методов и х работы на неа нглоязычные тексты едва ли даст удовлетворите льные результаты , если исключить метод "грубой силы " - неограниченное наращивание объема опер ативной памяти (ОП ) и быстродействия ЭВМ. 1. Теоретическая часть 1.1. Методы обнаружения ошибок Известны , по крайней мере , три метода автоматизированного обнаружения орфограф ических ошибок в текстах - статистический , поли граммный и словарный. При ст атистическом методе из текс та одна за другой выделяются составляющие его словоформы , а их перечень по ходу проверки упорядочивается согласно частоте встр ечаемости . По завершении просмотра текста упо рядоченный перечень предъявляется человеку для контроля , н апример , через экран ди сплея . Орографические ошибки и описки в ск оль-нибудь грамотном тексте несистематичны и редки , так что искаженные ими слова оказыв аются где-то в конце перечня . Заметив их здесь , контролирующее лицо может автоматизирова нно найти их в т ексте и испр авить. При полиграммном методе все встречающиеся в тексте двух - или трехбуквенные сочетани я (биграммы и триграммы ) проверяются по та блице их допустимости в данном естественном языке . Если в словоформе не содержится недопустимых полиграмм , она с читается п равильной , а иначе - сомнительной , и тогда п редъявляется человеку для визуального контроля и , если нужно , исправления. При словарном методе все входящие в текст словоформы , после упорядочения или бе з него , в своем исходном текстовом виде или посл е морфологического анализа , сра вниваются с содержимым заранее составленного машинного словаря . Если словарь такую словофо рму допускает , она считается правильной , а иначе предъявляется контролеру . Он может оста вить слово как есть ; оставить его и вс тавить в словарь , так что далее в сеансе подобное слово будет опознаваться системой без замечаний ; заменить (исправить ) слово в данном месте ; потребовать подобных замен по всем дальнейшему тексту ; отредак тировать слово вместе с его окружением . Оп ерации над сомните л ьным участком текста , указанные или иные возможные , могут комбинироваться исходя из замысла проектировщи ка АК. Результаты неоднократных исследований показа ли , что только словарный метод экономит тр уд человека и ведет к минимуму ошибочных действий обоих род ов - пропуска текст овых ошибок , с одной стороны , и отнесения правильных слов к сомнительным , с другой . Поэтому словарный метод стал доминирующим , хотя полиграммный метод иногда и применяют как вспомогательный. 1.2. Автоматизация процесса испра вл ения Можно предложить три степени автоматизаци и процесса коррекции текста : 1) только обнаружение ошибок, 2) обнаружение их и выдвижение гипотез (альтернатив , кандидатов ) по исправлению ; 3) обнаружение ошибок , выдвижение гипотез и принятие од ной из них (если хотя бы одна выдвинута системой ) в качестве автоматически вноси мого исправления. Без первой степени АК немыслим. Вторая и третья степень возможны толь ко при словарном методе . Уже вторая сущест венно облегчает внесение исправлений , ибо в бол ьшинстве случаев исключает перенабор сомнительного слова . Особенно полезны найденные альтернативы , когда контролирующее текст лиц о нетвердо знает данный естественный язык или конкретную терминологическую область . Однак о выдвижение гипотез требует больших п ереборов с поиском по словарю . Поэтому современные АК часто имеют средство выдв ижения гипотез лишь в качестве факультативног о , запускаемого , если требуется , избирательно д ля данного сомнительного слова. Третья степень автоматизации заманчива и одновременно опасна . Заманчивость заключает ся в полной автоматизации процесса исправлени я . Опасность же в том , что ни один словарь , в том числе - заключенный в челове ческом мозгу , никогда не бывает исчерпывающе полным . Когда незнакомое слово встречает система , основа н ная на неполном сл оваре , она может "исправить " его на ближайш ее ей знакомое , порой резко исказив исходн ый смысл текста . Особо опасно править собс твенные имена лиц , фирм , изделий , Заманчиво уметь пропускать (обходить ) собственные имена и сугубо специа льные термины , априори полагая их правил ьными , но безошибочные способы обхода , особенн о - терминов, нам не известны. Чисто автоматическому исправлению мог бы способствовать автоматический синтаксический и семантический анализ проверяемого текста , но он ещё не ст ал принадлежностью о бычных АК . И даже при его наличии лишь человек сможет диагностировать быстро меняющ иеся совокупности собственных имен , терминов и аббревиатур , а также окказионализмы - случайн о появляющиеся словесные новации. В связи со сказанным полная авт оматизация исправлений может применяться лишь в любом из следующих ограничительных услов ий : I) Текст имеет вид перечня терминов и терминологических словосочетаний в стандартной их форме , так что в АК достаточно иметь словарь , замкнутый по объему и пр об лематике . При этом все термины между собой "непохожи " (например , в словаре нет одновременно АДСОРБЦИЯ и АБСОРБЦИЯ ). 2) Ошибки носят характер замены кодов исходных букв на коды литер , совпадающих или близких к исходным по начертанию . Например , заменяются ко ды ASCII русских букв А , В , С , Е , У на коды латинских букв А , В , С , Е , У ; латин ские буквы I и 0 - на цифры I и 0 и т.п . С юда же отнесем повторы одной и той же литеры , возникающие из-за продленного нажима клавиши дисплея или его неисправности . В подавляющем большинстве , если в словофо рме более 2 -3 букв , такие исправления абсолютно правильны. 1.3. Диалоговый и пакетный режимы Возможны , в общем случае , два режима работы АК : диалоговый , когда текст проверяет ся слово за словом и пользо вателю предоставляется возможность снять очередное за труднение по мере его возникновения , и пак етный , когда готовые большие тексты анализиру ются в отсутствии пользователя. Во втором случае ненайденные словоформы либо как-то отмечаются в исходном тексте , ли бо запоминаются отдельно в виде своих адресов (в качестве адреса может использоваться , например , номер строки и номер символа , с которого начинается слово , в строке ). Подобная проверка ведется до конца проверяемого файла без вмешательства человек а . Далее ф айл вызывается снова и предъявляется для контроля тех строк , где были замечены сомнительные слова. ЧАСТЬ 3. СЖАТИЕ ИНФОРМАЦИИ ВВЕДЕНИЕ В процессе ускоренной компьюте ри з ации общества объемы данных , хранимых на машинных носителях , быст ро растут . Ещё совсем недавно они измеряли сь килобайтами и мегабайтами , а теперь - ги габайтами и более крупными единицами . Естеств енно желание хранить эти данные пред е льно компактно . Причем интересны обратимые ме тоды , устраняющие избыточность информации при сжатии и восстанавливающие её при разжатии. Описанные в методически х указаниях методы обратимы. Объектами сжатия являются : - числовые данные, - упорядоченные текстовые данные (словари ), - специальные тексты на формализованных языках, - естественно-языковые тексты общего вида, - структурированные данные. В качестве к оличественной меры сжатия исполь з уется коэффициент сжатия - отноше ние длины первоначального к сжатому тексту , а также продолжительность требуемых преобра з ований. Теоретическая часть 1.1. Сжатие числовых данных На иболее распространены ме тоды : ра з ностное кодировани е , кодирование повторений и подавление незначащих нулей. Суть разностного кодирования заключается в хранении вместо абсолютных значений разност ей двух смежных чисел или отклонения чисел от их среднего значения . Например , для последовательности чисел 2 , 14, 18, 2 7, 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.3. Сжатие специальных тексто в К специал ьным относятся тексты на формальных языках , отличающихся о граниченным словарем , замкнутой грамматикой . Сюда прежде всего относятся тексты на языках программирования , машинные коды , различные фо рмулы и обозначения , а также ограниченн ы е подмножество фраз е стественного языка в таких четко формализован ных з адачах как организа ция реплик в интерактивных системах , выдача сообщений при компиляции и т.п. Для данного типа информации пригодны методы , описанны е в п. 1.5 . В то же вре мя специфика этих текстов по з воляет осуществить экономное хранение , основанное на выделении длинных часто по вторяющихся фрагмент ов. Например , текст Фортран-программы : Т YРЕ *, ’ ФОРТРАН ’ Т YРЕ *, ’ ПРОГРАММА ' может быть представлен с использованием кодового словаря : 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,07 1 ъ -0,014 а 0,06 1 ь -0,014 и 0,061 б -0,014 т 0,0 5 2 г -0,013 м 0,052 ч -0,01 2 с 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 , равная сумме вероятностей всех символов A I , для которых р ( А I ) больше р ( S ). 1.5.2.2. Кодирование фрагментов п еременной длины Другой формой словаря может являть ся словарь фрагментов переменной длины . Словари фрагментов переменной длины строятся из словоформ , которые выделяются в тексте по естественным разделителям – про белам и знакам пунктуации . Затем рассчитывают ся частоты каждой словоформы как отношение числа е е повторений к общему количеству словоформ . Используя эти частоты , применяют метод Хаффмена или Шеннона- Фано для кодирования словоформ кодом переменн ой длины.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
В связи с принятием антитабачного закона депутаты теперь бегают курить за Кремль.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Методические указания по информатике", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru