Разработка алгоритма нечеткого поиска на основе хэширования | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 28 декабря, печатный экземпляр отправим 1 января.

Опубликовать статью в журнале

Автор:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №13 (117) июль-1 2016 г.

Дата публикации: 26.06.2016

Статья просмотрена: 1457 раз

Библиографическое описание:

Фролов, А. С. Разработка алгоритма нечеткого поиска на основе хэширования / А. С. Фролов. — Текст : непосредственный // Молодой ученый. — 2016. — № 13 (117). — С. 357-360. — URL: https://moluch.ru/archive/117/32158/ (дата обращения: 16.12.2024).



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

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

Все алгоритмы были реализованы в Ruby 2.2.4, графики были выполнены в программе Matlab 2010.

Ключевые слова: нечеткий поиск, расстояние Левенштейна, хэширование

В данной работе будет предложен алгоритм поиска наиболее близких значений из словаря к входному запросу. Некоторые выводы, используемые в работе, были основаны на результатах работ Бойцова Л. М. [1], т. к. в своих статьях он уже проводил сравнения основных алгоритмов и повторение полученных им результатов является нецелесообразным.

Общая проблематика нечеткого поиска.

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

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

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

Выбор метрики сравнения слов.

Наиболее распространенной метрикой является метрика Левенштейна. Расстояние Левенштейна — это наименьшее расстояние редактирования такое, что одна строка переходит в другую. Данная метрика очень популярна и используется повсеместно, поэтому не будем останавливаться на ней подробно.

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

,

где d(S1(i),S2(i)) расстояние Левенштейна, n — кол-во слов в строке (обычно для ФИО n=3); S1,S2 состоят из последовательности слов, поэтому вычисляем расстояние Левенштейна для каждой пары слов; k — показывает схожесть двух последовательностей слов (два ФИО).

Метод индексирования словаря.

Вычисление расстояния Левенштейна имеет квадратичную сложность, поэтому очень важно выбрать в исходном словаре множество, которое могло бы содержать исходный запрос. подобные методы основаны на сэмплировании, т. е. выделении характерных элементов строк. Наиболее подходящим методом для небольшой базы данных (до 500000 тыс. элементов словаря) является хэширование по сигнатуре [1]. Данный подход обеспечивает наилучшее соотношение качества поиска и скорости обработки запроса. Он имеет преимущество по сравнению с другими методами, такими как soundex (метафон), n-грамм, поиск по дереву, так как позволяет допускать ошибки в произвольных частях слова и при этом качество поиска не ухудшиться. Это имеет существенное значение при переводе русских имен на латиницу. Более того, такой метод ускорения поиска подходит для любого языка. Примером такой функции может быть . Такая функция была предложена в статье [5]. Данная функция хорошо подходит при считывании словаря с дискового пространства, но так как в нашем случае весь словарь будет загружен в оперативную память, то наиболее подходящим вариантом будет следующая формула: , u(i) — элемент словаря, k=length(u(i)). Мы просуммируем все уникальные значения кодов символов строки и получим некий образ. Таким образом, мы построим сюръективное отображение множества элементов словаря в некий набор образов и получили вектор столбец , где n — размер словаря

Описание используемого алгоритма исравнение результатов.

Поисковый алгоритм будет реализован следующим образом:

  1. словарь сортируется по возрастанию значений h(i) — значений хэшей
  2. û(1): , где y — образ входного запроса
  3. k=koeff(u(i),a), — вычисляем коэффициенты схожести; если нашли элементы с k=1.0, то поиск завершаем.
  4. û (2)= , t=max(bytes(char)) — максимальное значение кода символа

и так далее. Расширять выборку подмножества мы будем ограниченное число раз, равное максимально допустимому числу ошибок вставки или удаления. Переменная t на каждом шаге увеличивается, т. е. вначале мы ищем на точное совпадение образов (t=0*t), далее t=t*1 и ищем элемент в этом множестве (без элементов предыдущего) и так далее, расширяя максимально допустимое число раз.

Используя подобный метод индексирования и применяя метрику Левенштейна, можно добиться следующих результатов. На рисунке представлено сравнение скорости поиска без индексирования и с использованием метода индексирования предложенного в нашей работе. Для точности результатов использовался входной набор из 20 элементов (20 запросов для каждого размера словаря) и замерялось время.

Рис. 1 Сравнение временных затрат для обычного поиска и поиска с хэшированием

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

Теперь сравним алгоритмы поиска с использованием функции хэширования из статьи Бойцова Л. М. [5] и используемой в работе (при сравнении рассматриваем ситуацию, что элемент в словаре отсутствует и допустимо 3 ошибки, входной набор состоит из 20 запросов).

Рис. 2 Сравнение временных затрат поиска с использованием функции Бойцова и предложенной в статье

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

Литература:

  1. Бойцов Л. М. «Классификация и исследование современных алгоритмов нечеткого словарного поиска» // Труды 6-ой Всероссийской научной конференции “Электронные библиотеки: перспективные методы и технологии, электронные коллекции” — RCDL2004, Пущино, Россия, 2004.
  2. Бондаренко А. В., Визильтер Ю. В., Клышинский Э. С., Силаев Н. Ж., Максимов В. Ю., Мусаева Т. Н. «Формальный метод нечеткого поиска персональной информации», Препринты ИПМ им. М. В. Келдыша, 2009, 064, 25 с. URL: http://library.keldysh.ru/preprint.asp?id=2009–64
  3. Дональд Кнут «Искусство программирования», том 1, Основные алгоритмы, Вильямс, 2015
  4. Фултон Х., Арко А. «Путь Руби», ДМК Пресс, 2016
  5. Бойцов. Л.М. «Использование хеширования по сигнатуре для поиска по сходству», ВМиК МГУ, № 8 стр. 135–154, 2001.
Основные термины (генерируются автоматически): нечеткий поиск, алгоритм поиска, входной запрос, входной набор, использование функции, исходный словарь, квадратичная сложность, последовательность слов, размер словаря, элемент словаря.


Похожие статьи

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

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

Программная реализация алгоритма Левенштейна для устранения опечаток в записях баз данных

В статье описан пример реализации алгоритма Левенштейна на языке PL/SQL для устранения опечаток в записях баз данных.

Модификация алгоритма Смита — Уотермана для задачи автоматического распознавания слитной речи

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

Использование случайного леса для классификации данных

В последние десятилетия алгоритмы машинного обучения стали важным инструментом в различных областях науки и техники. Одним из наиболее популярных и эффективных методов является случайный лес (Random Forest). Этот метод используется для решения задач ...

Разработка двумерных сглаживающих фильтров на основе функции специального вида

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

Разработка алгоритма эффективного кодирования на основе неравенства Крафта

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

Спектральная кластеризация данных

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

Получение оверлеев векторных данных большого объёма

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

Одномерная оптимизация методом Пауэлла и онлайн-реализация метода на скриптовом языке php

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

Применение итерационного алгоритма Шульца в рекуррентных алгоритмах параметрической идентификации

В данной статье рассмотрен процесс исследования и реализации рекуррентных алгоритмов параметрической идентификации (на примере алгоритма Левенберга-Маркварда) в программной среде Unity Pro XL с использованием средств промышленной автоматики, в том чи...

Похожие статьи

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

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

Программная реализация алгоритма Левенштейна для устранения опечаток в записях баз данных

В статье описан пример реализации алгоритма Левенштейна на языке PL/SQL для устранения опечаток в записях баз данных.

Модификация алгоритма Смита — Уотермана для задачи автоматического распознавания слитной речи

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

Использование случайного леса для классификации данных

В последние десятилетия алгоритмы машинного обучения стали важным инструментом в различных областях науки и техники. Одним из наиболее популярных и эффективных методов является случайный лес (Random Forest). Этот метод используется для решения задач ...

Разработка двумерных сглаживающих фильтров на основе функции специального вида

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

Разработка алгоритма эффективного кодирования на основе неравенства Крафта

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

Спектральная кластеризация данных

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

Получение оверлеев векторных данных большого объёма

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

Одномерная оптимизация методом Пауэлла и онлайн-реализация метода на скриптовом языке php

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

Применение итерационного алгоритма Шульца в рекуррентных алгоритмах параметрической идентификации

В данной статье рассмотрен процесс исследования и реализации рекуррентных алгоритмов параметрической идентификации (на примере алгоритма Левенберга-Маркварда) в программной среде Unity Pro XL с использованием средств промышленной автоматики, в том чи...

Задать вопрос