Содержание к диссертации
Введение
ГЛАВА 1. Сущность задачи построения системы автокоррекции, индексации и поиска. Постановка задачи исследования . 12
1.1 Проблема сравнения векторных показателей. Методы снижения размерности и построения интегральных критериев 12
1.2 Анализ существующих методов снижения размерности и построения интегральных критериев 13
1.2.1 Эвристические методы 13
1.2.2 Экспертные методы построения интегрального показателя 14
1.2.3 Экспертно-статистические методы построения интегрального показателя 14
1.2.4 Метод экстремальной группировки признаков 16
1.2.5 Многомерное шкалирование 17
1.2.6 Факторный анализ 18
1.2.7 Метод главных компонент 19
1.2.8 Прочие методы снижения размерности 21
1.3 Обзор исследований по проблеме информационного поиска и поиска по сходству 21
1.3.1 Сущность задачи информационного поиска 21
1.3.2 Необходимые определения 27
1.3.3 Сравнение алгоритмов организации индекса ИПС 30
1.3.3.1 Инвертированные файлы (ИФ) 32
1.3.3.2 Сигнатурные файлы (СФ) 32
1.3.3.3 Векторные модели (ВМ) 34
1.3.4 Сущность задачи текстового поиска по сходству 37
1.3.5 Обзор исследований по алгоритмам вычисления расстояния редактирования 39
1.3.6 Анализ методов словарного поиска по сходству 52
1.3.6.1 Методы п-грамм 52
1.3.6.2 Trie-деревья (лучи) 54
1.3.6.3 Метрические (триангуляционные) деревья 54
1.4 Постановка задачи и обоснование методов исследования 56
Выводы по Главе 1 58
ГЛАВА 2. Анализ хеширования по сигнатуре . 59
2.1 Анализов факторов, влияющие на скорость поиска по сходству . 59
2.2 Описание метода хеширования по сигнатуре ключевых слов (ХС) . 64
2.3 Оценки эффективности ХС 70
2.4 Решение задачи коррекции текстов с особенностями с применением обобщенного расстояния редактирования 84
Выводы по Главе 2 86
ГЛАВА 3. Синтез корректирующего модуля с использованием метода главных компонент . 88
3.1 Описание алгоритмов словарного поиска по сходству, использованных для тестирования 88
3.1.1 Trie-деревья или лучи 89
3.1.2 Метод п-грамм 91
3.1.3 Частотные trie-деревья 91
3.1.4 Метрические деревья 92
3.2 Адаптация метода главных компонент для сравнения методов словарного поиска по сходства 93
3.3 Анализ экспериментальных данных методом главных компонент . 97
Выводы по Главе 3 100
ГЛАВА 4. Реализация ИФ на базе реляционной СУБД . 101
4.1 Проблема реализации поискового модуля для персональной ЭВМ . 101
4.2 Оценки размера индекса при «наивном» кодировании 105
4.3 Оценки размера сжатого индекса для коллекций, подчиняющихся обобщенному закону Ципфа со степенной константой, превышающей единицу 109
4.4 Решение задачи создания поискового модуля для персональной ЭВМ с использоанием сжатых модифицируемых ИФ 112
4.4.1 Суть проблемы обновления ИФ 112
4.4.2 Условия экспериментов 115
4.4.3 Описание метода блочной адресации «в чистом виде» 116
4.4.4 Описание модификации метода блочной адресации N 1 117
4.4.5 Описание модификации метода блочной адресации N 2 122
4.4.6 Анализ результатов экспериментальной проверки модификации N 2 124
Выводы по Главе 4 128
- Экспертно-статистические методы построения интегрального показателя
- Анализов факторов, влияющие на скорость поиска по сходству
- Trie-деревья или лучи
- Проблема реализации поискового модуля для персональной ЭВМ
Введение к работе
В современных информационных системах полнотекстовый поиск - важный инструмент работы с документальными базами данных. Первые информационно-поисковые системы (ИПС) появились более тридцати лет назад, и с тех произошли существенные изменения как в поисковых алгоритмах, так и в техническом оснащении. Современные поисковые системы (ПС) «научились» автоматически собирать информацию в интернете, учитывать морфологические особенности и гипертекстовую структуру документов.
Сегодня ИПС, наряду с экспертными системами и базами знаний, являются важным звеном в процессе принятия решений, а электронные архивы предприятия, научных учреждений и библиотек вытесняют свои бумажные аналоги. Поиск документов, относящихся к заданной теме, категоризация и поиск закономерностей при составлении документов: вот далеко не полный перечень задач, решаемых ИПС.
Несмотря на важность задачи ведения электронных архивов, на рынке практически отсутствуют интегрированные решения по обработке, хранению и обновлению документальной информации, вводимой с бумажных носителей и вручную. Существующие программные комплексы, как правило, предназначаются либо для автокоррекции, как, например, программа AfterScan, либо для индексации и поиска, как, например, системы DtSearch, AspSeek, и многие другие.
Особенностью обработки текстовой информации, сканируемой с бумажных носителей, заключается в применении нечеткого словарного поиска. Нечеткий поиск может использоваться как на стадии коррекции, так и на стадии поиска в уже выверенной базе данных. При этом качество коррекции может существенно возрасти, если модуль коррекции использует не только заранее скомпилированный языковой словарь, но и динамический словарь индексируемой коллекции, содержащий термины и сокращения предметной области.
Программный комплекс коррекции и индексации документов должен функционировать как единая открытая система: оператор принимает решение о выборе правильной форме в случае, когда выбор неоднозначен. Настройка системы на конкретную предметную область может осуществляться как за счет расширения языковой словаря слов специфическими для предметной области терминами, так и за счет накопления статистической информации о характере искажений.
Большинство современных программ проверки орфографии, такие как спел-чекер текстового процессора Ms Word или программа ispell, - универсальны и используют статические языковые словари. Это значит, что они не подходят для
обработки документов в условиях наличия небольшого набора вероятных искажений. В частности, такие искажения естественным образом возникают в результате сканирования с бумажных носителей, и обусловливаются спецификой процесса распознавания. Задача обработки считанных данных заключается в поиске правильных аналогов написания слов.
Наиболее распространенные типы ошибок - это орфографические ошибки, опечатки, и ошибки распознавания (сканирования). Орфографические искажения связаны, в основном, с похожестью звучания, например, замена «а» на «о», удвоение согласных и пр. Ошибки распознавания возникают из-за визуальной похожести символов и могут порождать с высокой вероятностью замены «8» на «з», «I» на «1», а опечатки вызваны ошибками при наборе на клавиатуре. Как правило, правильный символ заменяется символом одной из соседних клавиш, или символов из другого языкового регистра. С использование языкового словаря описанные искажения могут быть скорректированы автоматически.
Проблема, коррекции «фонетических» искажений достаточно неплохо исследована. Так, например, функция SOUNDEX, оценивающая похожесть звучания слов английских слов, реализована в большинстве современных СУБД. К сожалению, алгоритм SOUNDEX не очень хорошо параметризуется, и, как отмечают в своей работе Зобель и Дарт, обладает невысокой точностью и полнотой.
Задача автокоррекции является не единственной областью применения нечеткого поиска в индексирующих и поисковых системах. Нечеткий поиск в «чистом виде», в отличие от автокоррекции, используется гораздо реже, но иногда он просто незаменим. В частности, когда нужно найти документ по терминам, написание которых известно лишь приблизительно, например, по названиям лекарств, химических соединений.
С одной стороны, системный подход к построению программного комплекса коррекции и индексации позволяет повысить качество коррекции и, соответственно, поиска, но с другой стороны, он обуславливает высокие требования к алгоритмам коррекции и нечеткого поиска. Используемый алгоритм должен удовлетворять множеству критериев таких, как скорость поиска и создания индекса, размер индекса, простота реализации. В условиях большого числа характеристик невозможно выбрать метод оптимальный по всем параметрам. Таким образом, возникает многокритериальная задача, для решения которой применяются методы факторного анализа. Суть ее заключается в снижении размерности и построении интегрального показателя качества.
Чтобы откорректированные тексты не лежали «мертвым грузом» необходимо
обеспечить эффективный и функциональный поиск в массиве документов. Рассматриваемое в диссертационной работе интегрированное программное решение ориентировано для использования на персональной ЭВМ. Это значит, что с одной стороны, оно должно быть недорогим и эффективным, а с другой стороны, экономичным в смысле использования процессорного времени. В идеале процесс индексации и коррекции должен происходить незаметно для пользователя.
В последнее время все чаще задачу создания недорогих и эффективных поисковых систем пытаются решить с помощью готовых инструментов для хранения и обработки данных, в основном, реляционных и объектных СУБД. В качестве примера можно привести информационно поисковые системы (ИПС) MnogoSearch () и AspSeek () . Существенной особенностью такого подхода является многоплатформенность, понимаемая, как совместимость с различными СУБД: пользователь может купить дешевую СУБД, либо использовать уже приобретенную.
Существует довольно много расширений СУБД (т.к. называемых экстенде-ров), обеспечивающих полнотекстовый поиск в таблицах базы данных. Расширения СУБД, обеспечивающие полнотекстовый поиск достаточно специфичны: они не удовлетворяют единому стандарту, их внедрение может потребовать больших затрат на обучение специалистов и закупку нового программного обеспечения, поэтому их область применения ограниченна. Используя такую систему, пользователь «привязывает» себя к конкретной реализации СУБД.
В свою очередь, подход, основанный на использовании стандартных интерфейсов баз данных, в т.ч. языка SQL, отличается большой гибкостью и низкой стоимостью разработки. Однако применение СУБД имеет и свои недостатки. Если используется чисто реляционная модель, когда каждое вхождение слова в документ представлено записью в таблице ссылок, то скорость поиска и индексации оставляют желать лучшего. Проблемы появляются при работе с коллекциями среднего размера: порядка 1млн. 2-3 трех-страничных документов. При этом среднее время индексации одного документа может составлять 2-3 секунды, а средняя скорость поиска - 10-20 секунд.
Система AspSeek, упомянутая выше, осуществляет поиск на порядок быстрее и использует фактически статический индекс. AspSeek создает по результатам обработки заданного набора документов временный файл, а затем проводит слияние основного индекса с временным файлом. Недостаток такого подхода заключается в том, что время слияния линейно зависит от размера документальной коллекции, а процесс слияния может использовать процессор практически монопольно.
Наиболее популярное решение проблемы с производительностью - кластеризация. Как правило, рядовой пользователь не имеет возможности выделить несколько ЭВМ для распараллеливания поискового процесса, поэтому задача повышение производительности пользовательских поисковых систем или поисковых систем малых предприятий, использующих СУБД в качестве хранилища индекса, исключительно актуальна. Ее решение видится нам в использовании блочных индексов с инкрементной индексацией.
Цель работы - разработка программного комплекса для решения задач поиска информации с предварительной коррекцией.
Для достижение цели потребовалось:
Выбрать набор характеристик для оценки целесообразности алгоритмов нечеткого словарного поиска. Получить числовые значения выбранных характеристик и применить МГК для выбора представления словаря в модуле автокоррекции.
Оптимизировать и реализовать метод хеширования по сигнатуре в модуле коррекции, получить теоретические оценки его эффективности и проверить их экспериментально.
Разработать и реализовать модификацию метода блочной адресации для модуля индексации, позволяющую быстро (в пределах нескольких часов) индексировать документальные коллекции среднего объема: до 1 млн. документов со средним размером текстовой информации в несколько килобайт. Модуль индексации должен обеспечивать приемлемую скорость поиска: порядка 1 запроса в секунду, и возможность использования модифицируемого сжатого индекса.
Произвести экспериментальную проверку метода блочной адресации.
Решение поставленных в диссертации задач определило научную новизну исследования, которая заключается в том, что впервые:
1. Предложена методика ранжирования реализаций алгоритмов нечеткого словарного поиска на основе характеристик, полученных в результате экспериментальной проверки и экспертных оценок, с помощью метода главных компонент. В результате применения предложенной методики было получено, что реализации trie-деревьев и ХС лучше других использованных методов. Они обеспечивают хорошее время доступа: менее 20 мс для поиска в памяти
и порядка 100 мс для «дискового» поиска для словарей, содержащих 3 млн. терминов.
Была предложена и реализована новая модификация известного метода словарного поиска: хеширование по сигнатуре, а также доказана целесообразность его использования в модуле коррекции. Для хеширования по сигнатуре получены теоретические оценки эффективности, правильность которых подтверждена экспериментами.
Осуществлен теоретический анализ методов блочной адресации для коллекций, подчиняющихся законам Ципфа и Хипса. Дополнительно показано, что закон Хипса является следствием закона Ципфа.
Предложены алгоритмы для поисково-индексирующего модуля, использующего СУБД, дающие компромиссное решение задачи индексации и поиска на персональной ЭВМ. Предложенные алгоритмы обеспечивают высокую скорость инкрементной индексации, приемлемую скорость поиска, компактность индекса и переносимость в смысле использования различных СУБД.
Практическая значимость работы заключается в том, что результаты исследования используются в поисковой машине Punto (), разработанной фирмой «Аллсистем» , что подтверждается актом внедрения.
Основными положениями сформулированными в ходе диссертационной работы и выносимыми на защиту, являются:
1. При принятии решения о выборе подходящей структуры словаря для модуля коррекции необходимо сравнивать различные методы, используя, в том числе, результаты экспериментальной проверки. Каждый метод характеризуется упорядоченным множеством признаков. Далеко не все наборы признаков могут быть однозначно сопоставлены. Такая неоднозначность сравнения характерна для векторных показателей. Основным методом преодоления неоднозначности является снижение размерности. Метод главных компонент (МГК) - перспективный метод снижения размерности и сравнения векторных показателей. Он позволяет выделить наиболее перспективные алгоритмы в случае, когда невозможно выбрать Парето оптимальные алгоритмы по совокупности всех признаков. Результаты выбора с помощью МГК хорошо коррелируют с выбором Парето оптимальных методов по подмножествам признаков.
Результаты теоретического анализа и практической проверки разработанной модификации нечеткого словарного поиска (хеширования по сигнатуре) свидетельствуют о том, что предложенный метод подходит для решения задачи коррекции и является наряду с методом лучей (trie-деревьев) одним ИЗ лучших методов представления словаря.
В результате анализа двухуровневых блочных полнотекстовых индексов было найдено компромиссное решение, позволяющее сочетать высокую скорость инкрементной индексации и компактность индекса. Дополнительно было показано, что закон Хипса является следствием закона Ципфа.
Экспериментальная проверка показала, что метод блочной адресации может быть использован для индексации коллекций среднего размера: порядка 1 млн. документов. Предложенный метод является переносимым с точки зрения использования различных СУБД, а по скорости поиска и индексации соответствует коммерческим аналогам, системам с открытым кодом, а по некоторым показателям и превосходит их.
Диссертация состоит из введения, четырех глав, выводов, списка литературы, приложений и изложена на 144 листах машинописного текста, в том числе основного текста на 130 листах. Работа иллюстрирована 15 таблицами и 9 рисунками. Список литературы содержит 99 источников в том числе 80 на иностранных языках.
Экспертно-статистические методы построения интегрального показателя
Экспертно-статистические методы построения интегрального показателя применимы, когда интегральный показатель используется для оценки «качества» системы на основании набора частных характеристик (Xi,X2,...,Xn), каждая из которых имеет числовой вид и может быть измерена. При этом наборы характеристик в целом оказываются несравнимы. В качестве примера получения такого показателя можно рассмотреть задачу сравнения моделей автомобилей по мощности, расходу топлива, цене, или задачу выбора сильнейшего спортсмена по результатам достижений в различных видах спорта.
При решении задачи методом экспертно-статистических оценок предполагается, что искомый показатель Y является функцией известного общего вида от (Xi,X2,..., Хп), т. е. Y = f(Xi,X2,..., Хп; Р), и требуется вычислить лишь неизвестное значение параметра (в общем случае векторного) Р.
Для решения этой задачи используется дополнительно экспертная информация, полученная на основе исходных данных. Как мы уже отмечали в предыдущем разделе, экспертная информация обычно представлена одним из трех способов: Числовая оценка интегрального критерия, которое можно понимать, как «выходное качество» (линейные шкалы) Упорядочение объектов по степени убывания «выходного качества». При этом точные значения не известны, известен лишь порядок, (ранговые шкалы) Результаты сравнения наблюдений по «выходному качеству». В этом случае экспертные данные могут быть представлены в виде булевой матрицы. Алгоритмы вычисления параметра Р используют экспертную информацию, поэтому они называются экспертно-статистическими. Они основаны на следующей идее. Если было бы известно значение параметра Р, то можно было бы подсчитать значение Y = f(X\, Х2,..., Хп\ Р) для каждого из наблюдаемых объектов и определить с ее помощью, балльные оценки, ранги и булеву матрицу попарных сравнений. Поэтому если хотим формализовать с помощью целевой функции f(X;P) экспертные критерийные установки, в соответствии с которыми формируется единый интегральный показатель «выходного качества», то мы должны применить один из методов оптимизации для определения параметра Р. Конечный вид оптимизируемого функционала определяется критерием оценки. Разработаны алгоритмы и программы, позволяющие вычислять Р для всех трех вариантов представления экспертных оценок [2]. Результаты применения экспертно-статистических методов в задаче оценке мастерства спортсменов приведены в [1]. Данными методами анализировалась макроструктура фондов потребления, результаты приведены в [20]. На основании экспертно-статистических методов был построен сводный показатель эффективности деятельности промышленных предприятий [12]. К методологическим недостаткам этой группы методов [13] следует отнести то, что его реализация основана не только на статистической информации об объектах, но и на использовании экспертных оценок анализируемого интегрального свойства, так как получить экспертную информацию по влиянию на это интегральное свойство отдельных показателей, как правило, не представляется возможным. Следует также отметить, что вычислительная реализация сводится к методу наименьших квадратов лишь в тех редких случаях, когда от экспертов удается получить балльные оценки анализируемого интегрального свойства по каждому из исследуемых объектов. Если же в распоряжении исследователя лишь сравнительные оценки объектов по анализируемому свойству, то вычислительная процедура существенно усложняется. Необходимым условием достоверности и эффективности группы методов, базирующихся на экспертных оценках, является четкое определение требований к анализируемому интегральному свойству и компетентность используемых экспертных мнений. Метод экстремальной группировки признаков заключается в разбиении совокупности исходных показателей на заданное число групп Si,S2,-..,Sp таким образом, что признаки, принадлежащие одной группе, взаимокоррелированы сравнительно сильно, в то время как признаки, принадлежащие к разным группам, -слабо. Одновременно решается задача замены каждой группы сильно взаимокоррелированных исходных показателей одним вспомогательным «равнодействующим» показателем Zt, который хорошо коррелирует с признаками своей группы. В качестве класса допустимых преобразований исходных показателей будем использовать все нормированные (с единичной дисперсией) линейные комбинации Xi, Х2, .., Хп, а искомое решение будем искать из условия максимума суммы квадратов корреляций между исходными и «равнодействующими» показателями : В ряде случаев, например, когда исходные статистические данные получают с помощью специальных опросов, анкет, возможны ситуации, когда исследователь получает данные не по состоянию г-го объекта, описываемого вектором ХІ а характеристики Qij попарной близости двух признаков (или объектов) с номерами В этом случае исходная информация представляет собой матрицу статистических данных размера п х п. Задача многомерного шкалирования состоит в том, чтобы «погрузить» наши объекты в такое ]У-мерное пространство (р значительно меньше min(p, п)), чтобы исходная геометрическая конфигурация совокупности анализируемых точек-объектов (или точек-признаков) оказалась наименее искаженной в смысле некоторого критерия средней «степени искажения» A(Z) взаимных попарных расстояний.
Анализов факторов, влияющие на скорость поиска по сходству
Все современные операционные системы и СУБД кешируют операции ввода-вывода. Хеширование - это метод ускорения работы системы с более медленной (например дисковой) памятью за счет хранения наиболее часто используемых страниц в более быстрой (оперативной) памяти. За счет использования кеширования запись и чтение на диск происходят с меньшей интенсивностью. Самая простая модель памяти: двухуровневая. В ней есть только два уровня: оперативная и дисковая память. В современных ЭВМ кеширование осуществляется на многих уровнях: регистры процессора, быстрый кэш, оперативная память и дисковая. Следует отметить, что быстрый кэш ввиду его относительно небольшого (по сравнению с оперативной памятью размера) играет небольшую в роль в оптимизации дисковых операций при работе со словарями больших и средних размеров. Скорость доступа к данным в кэше значительно больше, чем к данным на внешнем устройстве и при подходящей стратегии кеширования общая производительность возрастает в десятки раз.
Но это не значит, что можно не принимать затраты процессорных ресурсов во внимание: например, сложность вычисления обобщенного выравнивания почти на два порядка больше 2.4, чем проверка нечеткого соответсвия с точностью до 1-3 элементарных операций редактирования. Таким образом, поисковый алгоритм должен не только минимизировать число дисковых операций, но и число нечетких сопоставлений.
Существует довольно много алгоритмов, например, модификации метода п-грамм, исключительно эффективно работающих с данным в оперативной памяти, однако проигрывающих методам последовательного сканирования плоского файла в случае прямых чтений с диска. Это связано с «дороговизной» чтений с большим количеством позиционирований головок магнитных или оптических носителей.
Возникает естественный вопрос: а не лучше ли отказаться от идеи оптимизации дисковых операций и использовать при поиске по сходству только сканирование? Нам кажется, что это нецелесообразно. Во-первых последовательный доступ к словарю большого размера составляет 10-20 секунд для самых быстро вычисляемых алгоритмов «похожести» двух строк.
Если количество записей в словаре не превышает миллион, то последовательный поиск неплохо справляется с задачей поиска редких терминов. Если персональ ная ЭВМ используется в качестве библиотечного сервера, выдающего данные из электронного каталога, то поисковый модуль должен обрабатывать десятки запросов в минуту или даже в секунду. Кроме системы поиска на такой ЭВМ обычно работают веб-сервер и почтовые службы. Очевидно, что в данном случае время поиска в словаре равное двум секундам может быть неприемлемым. Задача уменьшения количества считываемых с диска страниц особенно актуальна, когда объем индекса превышает размер выделенной под кэш оперативной памяти. Для решения задачи автокоррекции также необходимы высокопроизводительные алгоритмы.
Современные жесткие диски устроены так, что на скорость считывания влияет не только и не столько объем считываемой информации, сколько количество позиционирований головки. Пиковая скорость считывания с диска достигается при сканировании дефргаментированных файлов 125 потому что диск в этом случае вращается с большей скоростью и не тратится время на позиционирование. Время позиционирования обычного диска составляет несколько миллисекунд, поэтому чтение всего лишь 100-200К «вразброс» требует примерно одной секунды.
Этот широко известный факт подтверждает следующий простой эксперимент: будем последовательно считывать блоки большого дефрагментированного файла считывая сначала все блоки подряд, потом каждый второй блок, затем каждый четвертый, и.т.д., и измерять общее время чтения. Пусть время доступа равно т, а время считывания файла последовательно - Т, тогда на к шаге эксперимента мы осуществляем 2 позиционирований за время 2кт и затрачиваем время Т/2 непосредственно на чтение данных. Мы осуществляли тестирование в системе MSDOS, потому что MSDOS практически не кеширует операции ввода-вывода, с двумя различными жесткими дисками. Размер считываемого блока равен 1024 байта - при данном размере блока скорость чтения может быть немного меньше чем, скажем для блока размера 4096, однако числовые характеристики зависимости времени от объема не сильно отличаются. Аналогичный эксперимент был проведен нами в операционной системе Линукс, но каждом шаге мы очищали кэш с помощью вызова функции ядра InvalidatelnodePages из специально написанного драйвера, причем результаты экспериментов почти в точности совпали с результатам, полученными в системе MSDOS.
Как и следовало ожидать, время считывания не пропорционально объему считываемых данных. Время считывания тг-ой - части файла при тг 2 (при условии, что читается каждый n-ый блок) имеет порядок j by- И только, когда п достаточно велико, зависимость времени от объема близка к линейной. 12т.е. файлов, при чтении которых нужно последовательно считывать смежные блоки на диске В третьей колонке приведено значение эталонной функции СЛ , где t - время последовательного сканирования файла целиком. Легко заметить, что значения эталонной функции имеют тот же порядок, что и время считывания с диска, а в некоторых случаях погрешность не превышает 15-20 процентов.
Это говорит о том, что зависимость времени чтения далеко не линейная, и скорость чтения быстро убывает при большом количестве позиционирований. При случайном чтении страниц она составляет примерно 100-200 килобайт в секунду. Если вычислить среднюю скорость считывания данных в экспериментах с разным значением п, то можно легко заметить, что она убывает с увеличением п. Если для тестов в верхней части таблицы скорость чтения составляет почти три мегабайта в секунду, то для тестов из нижней нижней - всего 100-300 килобайт в секунду. Это более чем десятикратная разница.
К сожалению, фактор фрагментации почти невозможно учесть: физическое расположение страниц на диске контро ллируется даже не на уровне ОС, а на уровне дискового драйвера. Именно поэтому большинство оптимизаторов в современных СУБД оценивают сложность запросов в рамках линейной модели.
В идеале, данные считываемые по одному запросу, должны занимать всегда соседние блоки, однако в случае нечеткого словарного это вряд ли возможно. Дело в том, а это, пожалуй, основная проблема оптимизации нечеткого поиска, что поиск по сходству - это поиск «объемный», то есть поиск на множестве с принципиально многомерной, хотя и дискретной, структурой. Буквы слова: это его координаты.
Trie-деревья или лучи
Два наиболее распространенных способа создания электронного документа -это сканирование с бумажных носителей и набор текст вручную. Оба способа не являются идеальными, с точки зрения орфографических ошибок и прочих искажений. Например, при сканировании программа распознавания часто «путает» буквы с похожими очертаниями, а человек «промахивается» мимо нужной клавиши и нажимает соседнюю. Если документы, содержащие искажения, индексировать «как есть», то есть без предварительной обработки и исправления ошибок, то они впоследствии могут «затеряться». Если, например, все или часть ключевых терминов документа оказываться введенными неправильно, то по запросам, содержащим данные термины документы может быть либо вовсе не найден, либо находиться близко к концу отранжированной выборки.
Поиск с учетом возможных опечаток не всегда желателен, потому что значительно более ресурсоемок, а результат выборки часто «зашумлен». С нашей точки зрения, правильнее предварительно скорректировать документ по возможности в автоматическом режиме. Абсолютное большинство ошибок - порядка 80-90% - это одна элементарная (однобуквенная) операция редактирования. Искажения двух букв редки. Такие искажения либо носят фонетический характер, либо возникают в длинных словах. Изменения трех букв - явление чрезвычайно редкое. Таким образом, модуль автокоррекции должен уметь находить в проиндексированном словаре наиболее похожие слова, отличающиеся, в основном, на одну операцию редактирования.
В настоящее время существуют, как и обычные программы проверки орфографии, например, программа ispell и спелл-чекер редактора MS WORD, автокоррек-тирующие программы, например Afterscan (http://www.afterscan.com), которые решают поставленную задачу, но они обладают рядом недостатков: они либо используют исключительно метод расширения выборки и индекс, полностью загружаемый в память (MS WORD, ispell), либо, ориентируясь на совсем слабооснащен-ные компьютеры, никогда загружают индекс в оперативную память (Afterscan) и не слишком эффективны. Наша задача заключается в том, чтобы выбрать подходящий метод или несколько методов для индексации языкового словаря, лишенного вышеперечислен ных недостатков, а именно: Поиск должен быть эффективным, как для случая чтения индексных страниц с диска, так и из памяти. При поиске по более чем одной ошибке не должно происходить значительное снижение эффективности, как в методе расширения выборки, обуславливаемое так называемым «комбинаторным взрывом». Скорость точного поиска должна быть высокой, чтобы можно было использовать комбинированный подход: стандартный поиск с максимально допустимым числом опечаток от одного до трех в зависимости от длинны слова и метод расширения выборки (несколько наиболее вероятных вариантов) для замен типа «гк» на «х». Метод не должен иметь слишком высокую сложность реализации. Идеи, лежащие в основе тестируемых методов, описаны во разделе 1.3.6, тем не менее, в данной главе мы дадим более подробной описание алгоритмов нечеткого словарного поиска, используемых для синтеза модуля коррекции. Для краткости, на графиках и диаграммах используются мнемонические коды для обозначения методов словарного поиска. Хеширование по сигнатуре (мнемонический код SignHashDisc) описано нами выше и основано на группировке слов по набору, содержащихся в них букв. Мнемонический код: Tries. Trie-дерево строится по следующему принципу: все слова, имеющие одинаковый префикс, размещаются в одном и том же поддереве. Например, для слов тара, тарелка, торт, тормоз соответствующее trie-дерево изображено на рис. 1. Каждая ветка поддерева помечена строкой. Результат слияния строк, которыми помечены ветки, при спуске из корня дерева в лист - это слово, соответствующее листу дереву. Например, в дереве, изображенном на рис. 1, листу, ближе всего расположенному к левому краю рисунка, соответствует слово тарелка. При спуске из корня дерева сначала присоединяется подстрока т, потом подстрока ар, а в самом конце подстрока елка. Trie-дерево особенно эффективно для поиска слов по префиксу, но его можно использовать и для нечеткого поиска. Если задано максимально допустимое расстояние редактирования к, префикс р и искомое слово w, то используя процедуру вычисления расстояния редактирования, можно определить, есть ли у искомого слова префикс, отличающий от р не более чем на А; элементарных замен. Это свойство позволяет искать в trie-деревьях достаточно эффективно и отличать поддеревья, которые могут содержать искомые слова от тех, которые такие слова не могут содержать.
Пусть, например, нужно найти слово ара с точностью до одной опечатки. Искать начинаем с корня дерева. У корня есть поддерево, которому соответствуют префикс т. Расстояние редактирования между т и началом слова ара длины 1 равно 1, значит нужно продолжать поиск в поддеревьях рассмотренного узла. У него есть два поддерева, соответствующие префиксам тар и тор. Расстояние редактированием между префиксом искомого слова ара длины 2 (ар) и префиксом первого поддерева (тар) равно 1, значит нужно продолжить поиск в левом поддереве (см. рис 1). Это не верно для правого поддерева, которое исключается из дальнейшего рассмотрения. Окончательно получаем два слова-кандидата: тара и тарелка, из которых только одно соответствует поисковому образцу.
Проблема реализации поискового модуля для персональной ЭВМ
Выясним прикладной смысл первой главной компоненты. Из таблицы 3.3 видно, что первая главная компонента положительно и очень сильно коррели-рована со временами поиска, создания индекса, с размером индекса, а также с признаком использования индексных файлов и отрицательно - со сложностью реализации. Размер индекса, время поиска и создания индекса можно рассматривать, как критерий непроизводительности (производительность наоборот или производительность со знаком минус) системы, чем больше, например, время поиска, тем система хуже, а сложность реализации, как плату за устранение непроизводительности, или по-другому обеспечения высокой скорости поиска, небольшого объема индекса и времени построения индекса.
Таким образом, при движении вдоль первой главной компоненты растет непроизводительность системы, но уменьшается сложность реализации. Применяя общий подход, будем считать эффективностью отношение производительности системы к плате за достижение этой производительности. Зная величины первых главных компонент (см. табл. 3.3) можно подсчитать эффективность согласно данному определению. Как и ожидалось, для всех методов она одинакова и равна отношению сумм положительных элементов первого столбца матрицы А к сумме абсолютных значений отрицательных элементов первого столбца А. Поскольку относительно ГК1 все методы одинаково эффективны, то необходимо ранжировать их по производительности.
В итоге, используя данные таблицы 3.3, получаем, что лучшим является метод trie-деревьев, за ним идут ХС и частотные деревья. Замыкают рейтинг метрические деревья и метод п-грамм. Эксперименты были проведены для шести словарей различных размеров. Было бы неправильным использовать только часть результатов для построения рейтинга. С точки зрения автора, нецелесообразно решать задачу с очень большой матрицей корреляции. Вместо этого МГК был использован для обработки набора тестовых данных для каждого словаря, и было получено, что для всех наборов тестовых данных результаты почти идентичны, а именно: ГК1 соответствует более 80% дисперсии, при том, что доля дисперсии первых двух ГК больше 95%. Рейтинг методов относительно ГК1 практически не меняется на различных тестовых наборах. Единственное небольшое отличие заключается в том, что для небольших словарей ГК1 практически уравнивает ХС и частотные деревья, поэтому для более тонкого сравнения были использованы значения второй ГК. Смысл ГК2 также довольно прост: единственный фактор, с которыми она заметно и притом отрицательно коррелирует - это сложность реализации. Например, метод ХС проще реализуется, чем метод частотных деревьев. Выводы по Главе 3 Анализ словарных методов по сходству с использованием метода главных компонент позволил выяснить, что поставленная задача фактически двумерна. Основными характеристиками сравниваемых методов являются эффективность и сложность реализации. Из результатов анализа следует, что методы ХС и trie-деревьев являются наиболее перспективными для использования в модуле коррекции.
Полнотекстовый поиск - неотъемлемая часть современных систем обработки и хранения информации. Несмотря на множество разработок в области встраиваемых поисковых модулей, потребность в специфичных поисковых решений велика. Готовые системы, как правило, имеют высокую стоимость владения и настройки. Расходы на разработку поисковой системы «с нуля» на основе бесплатной программы сравнимы с расходами на покупку и настройку для конкретной предметной области со стоимостью доработки бесплатной или условно-бесплатной программы
И В последнее время появилось довольно много работ [97], [31], [28],[93], посвященных вопросу компактного представления данных и индексов. Повышенный интерес к этой проблеме вызван, в свою очередь, стремительным ростом сети Интернет и увеличением числа электронных документальных коллекций. База данных настольного ПК может содержать сотни тысяч документов. Эффективный поиск и индексация данных такого объема - непростая задача.
Если для больших поисковых систем в сети Интернет сейчас используют целые вычислительные комплексы, то для настольных ПК такое решение проблемы с производительностью неприемлемо. Персональные компьютеры имеют, как правило, не слишком большой объем оперативной памяти и свободного места на жестком диске также. В свою очередь, индексирующие модули должны работать параллельно другим программам и обеспечивать минимальную загрузку системы.
Многие коллективы программистов, в том числе разрабатывающие «коробочные» поисковые системы, сталкиваются с проблемой выбора подходящей структуры индекса. В отличие от производителей «коробочных» решений, которые могут позволить себе потратить много времени на оптимизацию и отладку, прикладные программисты оказываются в жестких временных рамках. Поэтому выбор структуры индекса обусловливается часто не только, и не столько скоростью поиска и эффективностью обновления, сколько легкостью реализации и надежности программы.
Система, ориентированная на внедрение на рабочем месте, должна быть дешевой. Стоимость разработки может быть снижена за счет использования готовых систем индексации и модификации данных. С нашей точки зрения, в качестве базового средства индексации и хранения данных наиболее подходящими являются системы управления базами данных (СУБД). Выбор и покупка СУБД осуществляется предприятием, как правило, независимо от выбора системы индексации и поиска. Это значит, что индексирующая система должна быть совместима с наиболее распространенными СУБД.
