В процессе работы необходимо было решить такие задачи




Скачать 166.89 Kb.
НазваниеВ процессе работы необходимо было решить такие задачи
страница1/2
Дата публикации29.08.2013
Размер166.89 Kb.
ТипАнализ
www.vbibl.ru > Информатика > Анализ
  1   2
Оценка алгоритмов поиска по сходству

На сегодняшний день задачи создания эффективных средств для автоматизированного исправления разного рода ошибок в текстовой информации все еще актуальны[О.О. Тодоріко, Г.А. Добровольський «Словниковий пошук за схожістю за допомогою хешів на основі сигнатур» // Вісник Херсонського державного технічного університету. – № 3(39). – Херсон: ХДТУ. – 2010. – С. 467-471]. По данным поисковой системы Яндекс, около 10% запросов содержат ошибки или опечатки [Поиск в интернете: региональные особенности http://company.yandex.ru/facts/researches/ya_regions_search_2010.xml#2.3]. Это говорит о том, что поисковый механизм должен учитывать возможные ошибки как на стадии обработки информации, так и на стадии выполнения запроса пользователя.

^ Целью работы является построение алгоритма для решения задачи поиска по сходству:

Пусть Sсловарь, состоящий из n слов, h – искомый образец. Обозначим длину образца L. Необходимо найти подмножество слов словаря, максимально «похожих» на заданный образец. Образец может отличаться от слова наличием лишних, пропущенных, изменённых или переставленных символов. Максимальное допустимое число ошибок d задается заранее.

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

Первый вариант нуждается в больших объемах памяти, второй требует большего времени на выполнение, третий, насколько известно, рассматривался лишь в некоторых роботах [Гниловская Л. П. Автоматическая коррекция орфографических ошибок / Л. П. Гниловская, Н. Ф. Гниловская // Культура народов Причерноморья. – 2004. – Т. 2, № 48. – С. 171–180, Бойцов Л.М. Использование хеширования по сигнатуре для поиска по сходству / Л.М. Бойцов // Прикладная математика и информатика. М. Изд-во факультета ВМиК, МГУ 2000, № 7].

^ В процессе работы необходимо было решить такие задачи, как построение индекса, который бы занимал минимальный объем, учитывал всевозможные формы слова и позволял приближенно сравнивать содержимое словаря с образцом. Полученный индекс должен обеспечивать возможность поиска по сходству и допускать параллельное выполнение.
^ Анализ публикаций.

На сегодняшний день в качестве контрольной меры степени «похожести» используется метрика Дамерау-Левенштейна [http://www.seobuilding.ru/wiki/Расстояние_Дамерау_—_Левенштейна http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance], или, как ее еще называют, расстояние редактирования. Расстояние Дамерау-Левенштейна Lev(u,v) между словами u и v равно минимальному количеству операций редактирования, необходимых для преобразования u в v. Под операциями редактирования понимают вставку, замену, удаление символа и перестановку соседних символов. Расстояние редактирования формализует интуитивное понятие об «ошибке», и существует множество алгоритмов эффективного его вычисления [http://ru.wikibooks.org/wiki/Расстояние_Левенштейна ]. При этом основной проблемой является их значительная вычислительная сложность. Что делает неэффективным их использование для поиска на больших массивах данных.

Аналогичная проблема возникает при поиске по сходству с использованием полного перебора всех терминов словаря, или последовательного поиска [http://ru.wikipedia.org/wiki/Полный_перебор Обзор поисковых методов. Автор: Бойцов Леонид http://alglib.sources.ru/articles/search.php], когда при каждом поиске необходимо каждое слово из словаря сравнить с образцом. В большом словаре многократное повторение даже простейшего сравнения требует значительных затрат времени.

Метод расширения выборки, или метода спел-чекера[Информационный поиск и поиск по сходству [электронный ресурс]. − Режим доступа: http://www.itman.narod.ru/, свободный Поиск на неточное соответствие: коды Хемминга Харитоненков Андрей Валерьевич http://www.jurnal.org/articles/2009/inf32.html ] опирается на известные методы быстрого поиска точного соответствия, однако при допущении 2-х и более ошибок расширенная выборка становится слишком большой.

^ Построение различных типов деревьев: trie-деревья, триангуляционные деревья, частотные деревья, kd-деревья [Л.Бойцов Обзорная статья, посвященная методам индексации текстов, в основном словарным, и алгоритмам поиска по сходству. http://www.itman.narod.ru/ir/review/review.html], - позволяет за счёт структуры данных уменьшить количество сравнений. К недостаткам таких алгоритмов можно отнести сложность составления их хорошо сбалансированных паралельных аналогов.

^ Предварительная фильтрация с помощью быстрых и неточных функций сравнения проста для реализации как в обычном послеловательном варианте, так и в параллельном. Наиболее известными из таких методов являются метод n-грам[ Manber U. A text compression scheme that allows fast searching directly in the compressed file in Combinatorial Pattern Matching / U. Manber // 5th Annual Symposium, CPM 94. Proceedings, Asilomar, CA, USA, 5-8 June 1994, Р. 113-24; Мазнов, Н. А. N-граммные методы обработки текстовой информации / Н. А. Мазнов // Материалы 2-ой межд. конф. "Крым-95", Евпатория, Украина, 10–18 июня 1995. – М., 1995. – С. 139–142] и хеширование по сигнатуре[Л.М. Бойцов. Использование хеширования по сигнатуре для поиска по сходству. Прикладная математика и информатика, ВМиК МГУ, № 8 стр. 135-154, 2001.]

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

Аналогичным целям в случае поиска на точное соответствие служит фильтр Блума[Фильтр Блума http://habrahabr.ru/blogs/algorithm/112069/ Фильтр Блума http://ru.wikipedia.org/wiki/Фильтр_Блума]. Фильтр Блума может обходиться малыми объёмами памяти, жертвуя детерминизмом. Обычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом (например, расположенной на жестком диске или в сетевой базе данных), то есть для «фильтрации» запросов к ней.

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

^ Метод n-грамм [Manber U. A text compression scheme that allows fast searching directly in the compressed file in Combinatorial Pattern Matching / U. Manber // 5th Annual Symposium, CPM 94. Proceedings, Asilomar, CA, USA, 5-8 June 1994, Р. 113-24] основан на предположении, что похожие слова обладают достаточным количеством общих подстрок длины n (n-грамм). При создании индекса для каждого слова составляется список содержащихся в нем n-грамм, который сохраняется в инвертированном виде.

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

^ Идея, лежащая в основе хеширующих методов, состоит в следующем: придумать отображение (хеш-функцию) слова, например, во множество чисел, или строк, описывающие основные характеристики исходного слова, и устойчивое к его искажениям. На основании хеш-функции можно сохранить словарь в виде хеш-таблицы, что значительно ускоряет поиск.

Например, хеш-функция soundex встроена в СУБД Sybase, MS SQL Server и Oracle. Однако метод soundex устойчив только на узком классе искажений, а предвидеть как изменится значение хеша после вставки произвольного символа достаточно сложно.

В методе хеширования по сигнатуре [Л.М. Бойцов. Использование хеширования по сигнатуре для поиска по сходству. Прикладная математика и информатика, ВМиК МГУ, № 8 стр. 135-154, 2001] для каждого слова v при заданном алфавите А вычисляется сигнатура sign(v) — битовый вектор размерности m, k-ый элемент которого равняется единице, если в слове v есть k-й символ алфавита. Битовый вектор sign(v) интерпретируется как двоичная запись числа, которое считается значением хеш-функции H(v), что позволяет организовать словарь в виде хеш-таблицы.

Пусть слово v получено из u в результате одной операции редактирования: замены, добавления (удаления) буквы или перестановки символов. В силу определения сигнатуры, битовые векторы sign(v) и sign(u) отличаются не более чем в одном разряде в случае операции добавления (удаления), и не более чем двух разрядах — в случае замены. Несложно также видеть, что, если при замене символов изменяются два элемента сигнатуры, то общее количество единиц (модуль сигнатуры) остается неизменным, а произвольные перестановки, вообще, не влияют на сигнатуру. Это свойство позволяет использовать сигнатурный хеш для поиска по сходству.

^ Фильтр Блума [Bloom, Burton H. (1970), "Space/time trade-offs in hash coding with allowable errors", Communications of the ACM Т. 13 (7): 422–426] — вероятностная структура данных, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. Для создания фильтра следует определить k независимых хеш-функций h1, …, hk, отображающих каждый элемент в одну из позиций битового массива длины m достаточно равномерным образом.

Для добавления элемента e необходимо записать единицы на каждую из позиций h1(e), …,hk(e) битового массива.

Для проверки принадлежности элемента e к множеству хранимых элементов, необходимо проверить состояние битов h1(e), …,hk(e). Если хотя бы один из них равен нулю, элемент не может принадлежать множеству (иначе бы при его добавлении все эти биты были установлены). Если все они равны единице, то структура данных сообщает, что е может принадлежать множеству. Ниже будет проверена гипотеза о том, что структура аналогичная фильтру Блума, при подходящих хеш-функциях может быть успешно использована для поиска по сходству.

^ Исследованные алгоритмы.

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

По аналогии с фильтром Блума один набор сигнатур может соответствовать не одному слову, а некоторому множеству слов. Например, слово и все его словоформы. Тогда необходимый для их хранения объем памяти сокращается и становится пропорционален размеру словаря. Построение сигнатур является подготовительным этапом и выполняется один раз.

Было исследовано четыре различных варианта построения множества сигнатур. Была поставлена такая задача:

Дано: словарь S, состоящий из n слов, u – словарное слово, h – искомый образец. Необходимо найти подмножество слов словаря, максимально «похожих» на заданный образец. Образец может отличаться от слова наличием лишних, пропущенных, изменённых или переставленных символов. Максимально допустимое число ошибок d задается заранее, до начала поиска.

Исходные данные одинаковы для всех вариантов алгоритмов, отличаются только способы построения индекса, ранжирования результатов. Рассмотрим эти отличия более подробно.

Вариант 1

Каждое слово в поисковом индексе описывается набором сигнатур ^ H: все буквы слова и его словоформ H0 , длина словарной формы слова и множество из n сигнатур, в котором i-я сигнатура Hi (i=1,2,3,...,n) описывает все символы слова и его словоформ, находящиеся на i-й позиции.

Перед вычислением релевантности слова вычисляется количество общих бит сигнатур H0(u) и H0(h). Если количество общих букв меньше минимально допустимого, слово считается неподходящим и впоследствии не рассматривается. Таким образом происходит сужение выборки уже в процессе обработки, что позволяет экономить вычислительные ресурсы.

В отличии от метода хеширование по сигнатуре [Л.М. Бойцов. Использование хеширования по сигнатуре для поиска по сходству. Прикладная математика и информатика, ВМиК МГУ, № 8 стр. 135-154, 2001] дополнительные хеши Hi (i=1,2,3,...,n) используются для вычисления релевантности и ранжирования результатов поиска.

Релевантность каждого из оставшихся после фильтрации слов вычисляется по формуле:
(1)
где Lu, Lh - длины образца и слова, dw - количество общих букв у образца и слова, с учетом его словоформ, wi - количество совпадающих бит i-й сигнатуры образца Hi(h) с i, i-1, i+1 сигнатурами слова Hi(u), Hi-1(u), Hi+1(u).

Вариант 2

Способ построения сигнатур и формула вычисления релевантности отличаются от варианта 1 добавочными хешами: минимальная Lмин и максимальная Lмах длины слова и его форм, и способом вычисления вклада i-й сигнатуры в релевантность - wi‏.

В данном варианте wi расчитывается как количество совпадений комбинации i, i+1, i+2 сигнатур образца Hi(h), Hi+1(h), Hi+2(h) с комбинацией соответствующих сигнатур слова Hi(u), Hi+1(u), Hi+2(u). Таким образом сравниваются все подстроки длиной в три символа. Если i равно длине строки, недостающие символы берутся из начала строки. При длине строки меньше трех, рассматривается комбинация соответствующей длины.

Для фильтрации слов, кроме сигнатурH0(u) и H0(h), используются Lмин и Lмах .

Релевантность вычисляется по формуле:
(2)
где Lh - длины образца, Lu = Lмин, если длина образца меньше минимальной длины слова и Lu = Lмах, если длина образца больше максимальной длины слова.
  1   2

Добавить документ в свой блог или на сайт

Похожие:

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

В процессе работы необходимо было решить такие задачи iconК заданию №6 «Разработка рекламной кампании»
Вам необходимо разработать рекламную кампанию для описываемой вами организации. Для этого нужно решить следующие задачи

В процессе работы необходимо было решить такие задачи iconКурсовой работы «Калькулирование себестоимости с полным отнесением...
Теоретические и методологические основы калькулирования себестоимости продукции

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

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

В процессе работы необходимо было решить такие задачи iconЛабораторная работа №1
До выполнения лабораторной работы нужно внимательно разобраться с примерами, ответить на контрольные вопросы изученного теоретического...

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

В процессе работы необходимо было решить такие задачи iconЧевардин А. В. Польская ссылка в свердловской области в 1940 – 1941 гг. (2006 г.)
Галиция, вообще никогда не входили в сферу российского влияния, власти с особым вниманием отнеслись к политике насаждения нового...

В процессе работы необходимо было решить такие задачи iconЗадани Решить задачи и выполнить практическое задание
Правомерны ли действия сторон трудового договора? Каков порядок заключения указанного договора? Составьте трудовой договор по условиям...

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

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
www.vbibl.ru
Главная страница