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




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

Вариант 3

Для каждого слова поисковый индекс описывается таким набором хешей: сигнатура множества всех букв слова и его словоформ H0 , длина самой короткой Lмин и самой длинной Lмах формы слова, как и в варианте 2. Далее строятся сигнатуры непересекающихся подстрок длиной три символа Hi (i=1,2,...,n, где n=L/3, L - длина слова). Если количество символов слова не кратно трем, то в конец слова добавляются пробелы.

Релевантность каждого слова вычисляется по формуле:
Rel =const + dw+ Σiwi‏, (i=1,2,3,...,n) (2)
где dw - количество общих букв у образца H0(h) и слова H0(u), с учетом его словоформ, wi - количество общих бит i-й сигнатуры образца и i-й сигнатуры слова.

Если dw меньше предельного значения, зависящего от допустимого количества ошибок, то слово считается не релевантным и далее не рассматривается.

Вариант 4

Для построения сигнатур используются следующие множества символов: все буквы слова и его словоформ H1; общие символы для слова и его словоформ H2; для каждого из первых n наиболее часто употребляемых символов (вычисленных заранее) находится его позиция k в слове и сигнатура вычисляется для k-1, k, k+1 символов. Дополнительно учитываются длины самой короткой Lмин и самой длинной Lмах формы слова.

Для ранжирования оставшихся после фильтрации результатов используется сумма
Dist = |Lh — Lu| +diff+ dw+Σiwi‏ , (i=1,2,3,...,n) (3)
Выше использованы следующие обозначения: Lh — длина образца; Lu = Lмин, если длина образца меньше минимальной длины слова и Lсловa = Lмах, если длина образца больше максимальной длины слова; diff - количество символов, которые есть в слове, но нет в образце; dw - количество символов, которые есть в образце, но нет в слове; wi - количество несовпадающих бит i-й сигнатуры образца и i-й сигнатуры слова, если и в образце и в слове существует i-я сигнатура не равная нулю, wi=0, если обе сигнатуры нулевые и wi=1 во всех остальных случаях.

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

Величина ^ Dist возрастает одновременно с расстоянием редактирования, поэтому слова с минимальным значением Dist должны оказаться ближе к образцу.

Оценка качества представленных алгоритмов.

Предложенные выше разработанные алгоритмы сравниваются с известными методами нечеткого словарного поиска: Trie-деревья, n-граммы, частотные деревья, kd-деревья, хеширование по сигнатуре, метрические деревья, расширения выборки, последовательный перебор.

Тестирование производилось на объединенных в одно множество слов из Орфографического словаря под ред. проф. Лопатина, Словаря русской литературы (http://www.serann.ru/vocabuli/) и всех слов из произведений Льва Толстого «Война и мир» и «Анна Каренина». Из этого множества выбирались наборы в 100, 200, 400 тысяч слов.

Образцами служили слова с типичными для русского языка ошибками и опечатками, перечисленные в статье [Лавошникова Э. К. О компьютерной коррекции психологически обусловленных ошибок правописания в текстах на русском языке // http:// lcl.srcc.msu.ru]. Такой набор образцов приводит к поисковым задачам, которые похожи на реальные ситуации и поэтому имеет преимущество перед автоматически сгенерированным.

Результатом работы описанных в данной статье алгоритмов является список слов, которые с некоторой вероятностью могут оказаться релевантными. Средняя точность (см. таб.1) [Introduction to Information Retrieval. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze. Cambridge University Press, 2008, 496 р., 5 b/w illus. 47 tables] полученной выборки показывает процент релевантных слов в результатах поиска. При этом записи, которые точно не удовлетворяют условию поиска, отбрасываются. Таким образом, чем больше доля отброшенных слов, тем качественнее работает алгоритм. Численной характеристикой в этом случае может служить процент слов, которые могут оказаться релевантными — эффективность отбора индекса[Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска Бойцов Леонид Моисеевич Труды 6ой Всероссийской научной конференции “Электронные библиотеки: перспективные методы и технологии, электронные коллекции” - RCDL2004, Пущино, Россия, 2004.]. Такой показатель как полнота [Introduction to Information Retrieval. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze. Cambridge University Press, 2008, 496 р., 5 b/w illus. 47 tables] в данном случае всегда равен 1, кроме n-грамм, и не может служить способом отличить один алгоритм от другого.

Показатели эффективности отбора индекса для сравнения взяты из исследования [Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска Бойцов Леонид Моисеевич Труды 6ой Всероссийской научной конференции “Электронные библиотеки: перспективные методы и технологии, электронные коллекции” - RCDL2004, Пущино, Россия, 2004.]. Такая характеристика как скорость поиска не рассматривается, так как эта величина сильно зависит от програмного и аппаратного окружения работающего кода.
^ Таблица 1 Средняя точность Mean Average Precision (MAP) при максимальном расстоянии редактирования d = 2

Методы

МАР

100 тыс. слов

200 тыс. слов

400 тыс. слов

вариант 1

0.017010199

0.017010199

0.017010199

вариант 2

0.08347977

0.08347977

0.08347977

вариант 3

0.07563387

0.07563387

0.07563387

вариант 4

0.15059458

0.15059458

0.15059458


^ Таблица 2 Показатель эффективности отбора индекса при максимальном расстоянии редактирования d = 2

Методы/ размер словаря

100 тыс. слов

200 тыс. слов

400 тыс. слов

Trie-дерево

0.137

0.078

0.041

n-грамм(2)

0.016

0.016

0.014

част. дерево

0.021

0.021

0.021

n-грамм(1)

0.045

0.045

0.046

kd-дерево

0.081

0.079

0.076

хеш. сигнат.

0.075

0.075

0.074

метр. дерево

0.209

0.165

0.170

расш. выборки

3.538

1.769

0.885

n-грамм част. trie

0.930

0.932

0.933

посл. перебор

1.000

1.000

1.000

вариант 1

0,056

0,028

0,019

вариант 2

0,056

0,028

0,019

вариант 3

0,053

0,027

0,018

вариант 4

0,002

0,001

0,001





Выводы

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

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

Главной особенностью варианта 4 является малая чувствительность к вставке и удалению символов, т.к. при построении сигнатур учитываются только относительные позиции символов. Большое количество сигнатур делает эффективность отбора индекса очень высокой — правильно отвергаются 99,9% и более явно непохожих на образец слов. Этот алгоритм оказался способен находить слова, близкие к образцу, которого нет в словаре (например, слово «крокодительница»). Однако большое количество признаков требует для хранения большего объёма памяти и большего времени для построения поискового индекса.

Список литературы

  1. Бойцов Л.М. Поиск по сходству в документальных базах данных: хеширование по сигнатуре — оптимальное соотношение скорости поиска, простоты реализации и объема индексного файла.

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




Обзоры:
Вычисление расстояния редактирования:

# Navarro G (2001). "A guided tour to approximate string matching". ACM Computing Surveys 33 (1): 31–88. doi:10.1145/375360.375365. http://www.egeen.ee/u/vilo/edu/2002-03/Tekstialgoritmid_I/Articles/Approximate/Navarro_Review_on_Approximate_Matching_p31-navarro.pdf.
Суффиксные деревья, q-граммы

# ^ G. Navarro, Ricardo Baeza-Yates, E. Sutinen and J. Tarhio (2001). "Indexing Methods for Approximate String Matching". IEEE Data Engineering Bulletin 24 (4): 19–27. http://www.dcc.uchile.cl/~gnavarro/ps/deb01.pdf.
Книга есть n-граммы, spellchecker, расстояние редактирования, soundex

Introduction to Information Retrieval. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze. Cambridge University Press, 2008, 496 р., 5 b/w illus. 47 tables

1   2

Похожие:

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

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

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

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

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

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

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

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

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

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

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


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