Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Наиболее простое решение задачи адресации - указывать во входном сообщении относительный машинный адрес запрашиваемой записи. В некоторых ранних банковских системах номера счетов видоизменялись так, чтобы новый номер или его часть являлись бы адресом элемента для данного счета в списке. Таким образом, адрес был равен ключу или определялся по нему простым способом.

Во многих приложениях такой прямой подход невозможен. Но­мера изделий на заводе не могут изменяться только ради удобс­тва использования ЭВМ, поскольку для работников фирмы они име­ют в запросе определенный смысл.

Иногда во входном сообщении используется внутренний машинный код; при этом не требуется, чтобы он был равен номеру клиента или номеру изделия. Например, адрес записи счета в файле может печататься в банковской расчетной книжке клиента сберкассы и указываться далее в запросе с терминала.

Такие схемы называются прямой адресацией, хотя обычно этот термин используется в более широком смысле для обозначе­ния любого алгоритма, преобразующего ключ непосредственно в машинный адрес.

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² = 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

левая правая

часть часть

направление движения

правой и левой частей числа

0 2647 после сдвига

3 1168

3 3 7 (10)(15) = 337(1+0)(1+5)=33716

Поскольку полученное число имеет порядок, больший трех, процедура сдвига повторяется:

033 716

левая часть правая часть

0 33 после сдвига

749 – конечный результат – относительный адрес для ключа КОМПЬЮТЕР.

Очевидно, и этот этап дает потерю информации.

3) вычисление абсолютного адреса. Исходная информация – диапазон изменения относительных адресов (очевидно, от 0 до 999) и адреса размещения элементов списка в памяти (напомним, что список занимает кластеры с адресами от 10 до 999). Тогда абсолютный адрес для элементов списка получается по формуле:

+ * const,

где const – константа, получаемая по формуле:

число доступных адресов / максимальный относительный адрес, причем число доступных адресов – разность между максимальным и минимальным адресами размещения списка в памяти.

Для нашего случая const = 989 / 999 = 0,989

Тогда, например, для относительного адреса 199 абсолютный адрес (читай – номер кластера) равен 10 + 199*0,989 = 10+197 = 207.

Выводы по части 1.

Одной из проблем при создании информационных систем является работа со структурированными данными, которые чаще всего являются линейными списками – упорядоченным множеством элементов, порядковые номера которых определяют местоположение элемента в списке. Элементы списка имеют структуру – они состоят из конечного множества полей, каждое из которых имеет определенный смысл, например, фамилии, адреса и т.д. Для таких списков важна задача адресации элементов списков – определение адреса элемента списка по одному из его полей или по совокупному набору полей. Такие поля называются ключевыми (или ключами) (в простейшем случае ключом, например, может быть номер зачетной книжки студента).

ЧАСТЬ 2. АВТОКОРРЕКЦИЯ ТЕКСТА

ВВЕДЕНИЕ

Программы автоматического обнаружения и исправления оши­бок в текстах на естественных языках (назовем их автокорректорами - АК, хотя терминология ещё не сложилась) получают все большее распространение. Они используются, в частности, в пакетах WINWORD и EXCEL для проверки орфографии текстовой информации.

Говоря точнее, АК производят автоматически лишь обнару­жение ошибок, а собственно коррекция ведется обычно при участии человека.

1. Теоретическая часть

1.1. Методы обнаружения ошибок

Известны, по крайней мере, три метода автоматизированного обнаружения орфографических ошибок в текстах - статистичес­кий, полиграммный и словарный.

При статистическом методе из текста одна за другой выде­ляются составляющие его словоформы, а их перечень по ходу про­верки упорядочивается согласно частоте встречаемости. По завершении просмотра текста упорядоченный перечень предъявляется человеку для контроля, например, через экран дисплея. Орогра­фические ошибки и описки в сколь-нибудь грамотном тексте не­систематичны и редки, так что искаженные ими слова оказывают­ся где-то в конце перечня. Заметив их здесь, контролирующее лицо может автоматизированно найти их в тексте и исправить.

При полиграммном методе все встречающиеся в тексте двух- или трехбуквенные сочетания (биграммы и триграммы) проверяют­ся по таблице их допустимости в данном естественном языке. Если в словоформе не содержится недопустимых полиграмм, она считается правильной, а иначе - сомнительной, и тогда предъяв­ляется человеку для визуального контроля и, если нужно, исправ­ления.

При словарном методе все входящие в текст словоформы, пос­ле упорядочения или без него, в своем исходном текстовом виде или после морфологического анализа, сравниваются с содержимым заранее составленного машинного словаря. Если словарь такую словоформу допускает, она считается правильной, а иначе предъявляется контролеру. Он может оставить слово как есть; оставить его и вставить в словарь, так что далее в сеансе подобное сло­во будет опознаваться системой без замечаний; заменить (испра­вить) слово в данном месте; потребовать подобных замен по всем дальнейшему тексту; отредактировать слово вместе с его окруже­нием. Операции над сомнительным участком текста, указанные или иные возможные, могут комбинироваться исходя из замысла проек­тировщика АК.

Результаты неоднократных исследований показали, что толь­ко словарный метод экономит труд человека и ведет к миниму­му ошибочных действий обоих родов - пропуска текстовых ошибок, с одной стороны, и отнесения правильных слов к сомнительным, с другой. Поэтому словарный метод стал доминирующим, хотя полиграммный метод иногда и применяют как вспомогательный.

1.2. Автоматизация процесса исправления

Можно предложить три степени автоматизации процесса кор­рекции текста:

1) только обнаружение ошибок,

2) обнаружение их и выдвижение гипотез (альтернатив, кандидатов) по исправлению;

3) обнаружение ошибок, выдвижение гипотез и принятие од­ной из них (если хотя бы одна выдвинута системой) в качестве автоматически вносимого исправления.

Без первой степени АК немыслим.

Вторая и третья степень возможны только при словарном методе. Уже вторая существенно облегчает внесение исправлений, ибо в большинстве случаев исключает перенабор сомнительного слова. Особенно полезны найденные альтернативы, когда контро­лирующее текст лицо нетвердо знает данный естественный язык или конкретную терминологическую область. Однако выдвижение гипотез требует больших переборов с поиском по словарю. Поэто­му современные АК часто имеют средство выдвижения гипотез лишь в качестве факультативного, запускаемого, если требуется, избирательно для данного сомнительного слова.

Третья степень автоматизации заманчива и одновременно опасна. Заманчивость заключается в полной автоматизации процесса исправления. Опасность же в том, что ни один словарь, в том числе - заключенный в человеческом мозгу, никогда не бывает исчерпывающе полным. Когда незнакомое слово встречает система, основанная на неполном словаре, она может "исправить" его на ближайшее ей знакомое, порой резко исказив исходный смысл текста. Особо опасно править собственные имена лиц, фирм, изделий, Заманчиво уметь пропускать (обходить) собственные имена и сугубо специальные термины, априори полагая их правильными, но безошибочные способы обхода, особенно - терминов, нам не известны.

Характеристики

Список файлов реферата