Широкопетлева М.С.

Харьковский национальный университет радиоэлектроники

Применение методов нечеткого поиска при реализации обучающих систем

Сейчас алгоритмы нечеткого поиска строк получили широкое распространение в системах автоматизации перевода, орфографических корректорах, программах распознавания печатного текста и в поисковых системах. В общем случае нечеткий текстовый поиск подразумевает отыскание произвольных участков текста, но часто задачу можно свести к словарному поиску. Задачу нечеткого поиска [1] можно сформулировать так: «По заданному слову найти в тексте или словаре размера n все слова, совпадающие с этим словом (или начальной этого слова) с учетом k возможных различий».

К обучающим системам (ОС) [2] относят программы, выдающие материал в последовательности, определяемой структурой программы и результатами работы обучаемого, но подсистема представления учебного материала в таких системах зачастую жестко запрограммирована и не зависит от желания пользователя – обучаемого. При необходимости перехода к определенному блоку учебного материала может возникнуть несколько вариантов:

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

- переход может быть невозможен в связи с недостаточным (с точки зрения системы) уровнем подготовки обучаемого;

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

Целью работы является исследование применимости методов нечеткого поиска для реализации подсистемы представления учебного материала в ОС.

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

Рассмотрим методы нечеткого поиска.

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

В числе наиболее известных метрик - расстояния Хемминга, Левенштейна и Дамерау-Левенштейна. Наиболее часто применяемой метрикой является расстояние Левенштейна, или расстояние редактирования, алгоритмы вычисления которого можно найти на каждом шагу. Расстояние Левенштейна равно минимальному числу элементарных операций редактирования, необходимых для преобразования одной строки в другой. Также бывает необходимо вычислять расстояние между префиксом-образцом и строкой. В этом случае необходимо взять наименьшее из расстояний от префикса-образца до всех префиксов строки. Очевидно, что префиксное расстояние не может считаться метрикой в строгом математическом смысле, что ограничивает его применение. Зачастую при нечетком поиске важно не столько само значение расстояния, сколько факт того, превышает оно или нет определенную величину. Расстояние Дамерау-Левенштейна вносит в определение расстояния Левенштейна еще одно правило — транспозиция двух соседних букв также учитывается как одна операция, наряду со вставками, удалениями и заменами, что может найти применение в ОС.

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

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

Алгоритмы индексирования объектов в общих метрических пространствах весьма многочисленны. Метрические деревья - алгоритмы, которые используют для индексирования набор расстояний до некоторых образующих точек. Различные алгоритмы метрических деревьев, в частности vp-дерева [3], используют разбиение пространства на подпространства в зависимости от расстояния элементов подпространства к создающим его точкам. В ОС пригодны алгоритмы, размер индекса которых линейно зависит от числа проиндексированных записей.

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

При реализации полнотекстового поиска (например, в MS SQL Server 2008 и выше) может быть достигнут требуемый результат, но учебный материал редко хранится с использованием реляционных СУБД.

Таким образом, в работе рассмотрены методы нечеткого поиска и показана применимость оффлайн методов для реализации подсистемы представления учебного материала в ОС. В работе не была рассмотрена значимость результатов поиска.

Литература

1. Л.М. Бойцов. Использование хеширования по сигнатуре для поиска по сходству / Прикладная математика и информатика, ВМиК МГУ, №8 стр. 135-154, 2001.

2. Мельников А.В, Цытович П.Л. Принципы построения обучающих систем и их классификация // Педагогические и иниформационные технологии в образовании. – 2002, №4

3. Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms P.N. Yianilos. Data Structures and Algorithms for Nearest