С появлением компьютеров человечество получило потрясающую возможность хранения больших объемов информации в компактном и удобном электронном виде. Многие книги, по объему такие как «Война и Мир» Льва Николаевича Толстого, теперь можно «уместить» на одной 3.5-дюймовой дискете, даже не прибегая при этом к сжатию данных.

Вся «Большая Советская Энциклопедия» без иллюстраций теперь займет около десяти мегабайт дискового пространства, против тридцати трех томов своего печатного предшественника. Причем теперь даже не придется выдумывать «хитрых» схем поиска необходимой информации, содержащейся в БЭС, так как достаточно набрать в текстовом редакторе, в который будет загружена БЭС, необходимое слово в строке поиска и почти мгновенно вы получите интересующую вас информацию. Это не говоря уже о том, что вам не придется тратить свое драгоценное время на то, чтобы специально идти в библиотеку, где вы смогли бы получить интересующую вас информацию. Достаточно просто загрузить с 6-7 дискет или одного компакт диска всю БЭС на ваш домашний или рабочий компьютер и воспользоваться ее по своему усмотрению. Мы не хотим сказать, что нужно вовсе отказаться от книг, но для поиска информации удобнее и быстрее использовать их электронный аналог.

Это всего лишь небольшой пример компактности и удобства хранения большого количества информации в электронном виде. Но наряду со всеми преимуществами есть и серьезные недостатки. Например, для того, чтобы перевести столь большой объем информации из печатного варианта в электронный, необходимо воспользоваться таким техническим средством ввода информации, как сканер. Причем полученная вами информация будет представлять всего лишь «картинку», которую необходимо будет распознать с помощью специальных программ, и представить ее в конечном счете не как графическую, а как текстовую информацию.

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

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

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

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

В процессе исследования данной проблемы было найдено несколько теорем, позволяющих осуществлять анализ и сравнение текстовой информации.

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

Далее был написан программный модуль в соответствии с этим алгоритмом. Данный программный модуль позволяет отслеживать ошибки пользователя при вводе и «предлагает» варианты правильного написания вещества или элемента из словаря. В данном случае необходимо каким-либо образом ограничивать число допустимых ошибок со стороны пользователя, иначе нахождение правильного варианта в словаре будет затруднительно. В слове с большей длиной можно допустить большее количество ошибок, и наоборот.

В результате тестирования программного продукта был определен порог допустимых ошибок. В среднем он составил 25% от длины слова. Т.е. если 3/4 символов входной последовательности совпали в требуемом порядке с последовательностью символов слова- оригинала, то программа предлагала это слово как один из вариантов правильного написания. Т.о. в слове с большей длиной можно допустить большее количество ошибок, и при этом программа выведет варианты правильного написания этого слова. Если количество ошибок в слове превышает 25% от его длины, то программа не считает это слово возможным правильным вариантом написания.

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

Необходимо заметить, что алгоритм ищет только грамматические ошибки. Это не включает вариант того, что пользователь просто перепутает названия.

Алгоритм нахождения ошибок пользовательского ввода работает в два этапа (первый этап – проверка правильности ввода, второй – поиск возможных вариантов устранения ошибки):

1. На этом этапе просматривается вся база данных и ищется название химического элемента, полностью совпадающее с названием, введенным пользователем. Если такой элемент был найден, то делается заключение о том, что пользователь написал название правильно, и выполнение алгоритма завершается. В противном случае выполнение алгоритма переходит на следующий этап.
2. На этом этапе снова просматривается база данных и для каждого названия химического элемента из базы данных и названия, введенного пользователем, строится наибольшая общая подпоследовательность букв (НОПБ). Подпоследовательность получается удалением из слова некоторых букв. НОПБ – это общая подпоследовательность (причем наибольшей длины) для обоих слов. Далее вычисляется разница между длинной НОПБ и длинной слова из базы данных, а также длинной НОПБ и длинной слова, введенным пользователем. Если эта разница в обоих случаях не превышает определенную величину, то текущее слово из базы данных считается одним из возможных правильных вариантов написания названия химического элемента (практически получилось, что наиболее подходящая величина разницы составляет около 25%).

Время работы алгоритма будет зависеть от длинны сравниваемых слов полиномиально. Это значит, что если длина слова A – m букв, а слова B – n букв, то время работы алгоритма будет зависеть от произведения m • n , столько же потребуется ячеек памяти для хранения решений всех подзадач. Для восстановления НОПБ потребуется m + n шагов (алгоритм восстановления НОПБ описан ниже, после примера построения таблицы решений подзадач). Так как описанный выше алгоритм работает достаточно быстро, то его можно использовать для практического решения задачи поиска НОПБ двух слов.

Рассмотрим пример построения таблицы V для слов A5 = «слово» и B4 = «слво» (см. таблицу1):

Как видно, НОПБ равна 4 буквам, притом можно построить по этой таблице саму НОПБ, это будет X₄ = «слво». Построить НОПБ можно следующим образом: идти с крайней нижней правой ячейки таблицы вверх, пока в ячейках повторяется одна и та же цифра, а потом вправо, пока опять же повторяется одна и та же цифра. Затем записать букву в НОПБ из позиции слова A (B), равной номеру столбца (или строки) текущего положения, затем повторить последовательность действий, пока не будут достигнута ячейка, равные нулю или ячейка V[1,1].

В общем случае может существовать несколько НОПБ. Но в нашем случае строиться только один вариант.

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

Реализованный программный модуль внедрен в сертифицированную Госстандартом Республики Беларусь программу 'MARS' – акт государственных испытаний от 31 июля 2004 г., предназначенную для автоматизированной обработки данных и расчета неопределенностей измерений.

Результаты исследования будут использованы в электронном учебнике по дисциплине «Системное программное обеспечение» кафедры Электронных вычислительных машин, а непосредственно сам модуль – в качестве демонстративного программного приложения.