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

Автор:

Рубрика: Информатика

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

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

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

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

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



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

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

Все алгоритмы были реализованы в 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.
Основные термины (генерируются автоматически): нечеткий поиск, алгоритм поиска, размер словаря, последовательность слов, квадратичная сложность, исходный словарь, использование функции, входной набор, входной запрос, элемент словаря.


Ключевые слова

нечеткий поиск, хэширование, расстояние Левенштейна

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

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

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

Использование алгоритмов нечеткого поиска при решении...

Ключевые слова. Нечеткий поиск; N-gram; релевантность строк; поиск данных

Поиск дубликатов в этом случае ведется по точному совпадению и не вызывает сложностей.

Общий принцип применения функции для поиска дубликатов следующий

Использование сети Хемминга для автоматической коррекции...

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

Рис. 2. График зависимости времени обработки от размеров словаря. Заключение.

Статический анализатор кода на основе взаимодействия...

Ключевые слова: статический анализ, интервальный анализ, анализ указателей, поиск

Каждый объект представлен тремя атрибутами: тип, размер и владелец. Возможные типы

Система уравнений решается с использованием известных алгоритмов теории решеток.

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

Частотный словарьнабор слов данного языка (или подъязыка) вместе с информацией о частоте их встречаемости.

Рис. 2. Алгоритм функции поиска значения по ключу. Также была реализована функция удаления значения по ключу.

Сравнительный анализ алгоритмов сортировки данных в массивах

Ключевые слова: алгоритм сортировки, сравнение алгоритмов сортировки.

Быстрота при условии использования подходящего массива входных данных.

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

Система поиска сходства шаблонизированных строк

Дублирующееся объявление — это не только копия ранее поданного, но и объявление, отличающееся от исходного одним-двумя неключевыми словами.

Далее сформируем список алгоритмов нечеткого поиска, которые могут быть использованы в поиске строк-дубликатов...

Этапы и методы автоматического извлечения ключевых слов

Выделение коллокаций необходимо для того, чтобы алгоритм поиска ключевых слов не разделял семантически связанные

Довольно часто для поиска коллокаций применяют статистические методы, которые в общем случае требуют следующие входные данные

Обзор некоторых алгоритмов нестрогого сопоставления записей...

Рассмотрим следующие алгоритмы нестрогого поиска: - хеширование по сигнатуре; - БК-дерево.

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

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

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

Использование алгоритмов нечеткого поиска при решении...

Ключевые слова. Нечеткий поиск; N-gram; релевантность строк; поиск данных

Поиск дубликатов в этом случае ведется по точному совпадению и не вызывает сложностей.

Общий принцип применения функции для поиска дубликатов следующий

Использование сети Хемминга для автоматической коррекции...

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

Рис. 2. График зависимости времени обработки от размеров словаря. Заключение.

Статический анализатор кода на основе взаимодействия...

Ключевые слова: статический анализ, интервальный анализ, анализ указателей, поиск

Каждый объект представлен тремя атрибутами: тип, размер и владелец. Возможные типы

Система уравнений решается с использованием известных алгоритмов теории решеток.

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

Частотный словарьнабор слов данного языка (или подъязыка) вместе с информацией о частоте их встречаемости.

Рис. 2. Алгоритм функции поиска значения по ключу. Также была реализована функция удаления значения по ключу.

Сравнительный анализ алгоритмов сортировки данных в массивах

Ключевые слова: алгоритм сортировки, сравнение алгоритмов сортировки.

Быстрота при условии использования подходящего массива входных данных.

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

Система поиска сходства шаблонизированных строк

Дублирующееся объявление — это не только копия ранее поданного, но и объявление, отличающееся от исходного одним-двумя неключевыми словами.

Далее сформируем список алгоритмов нечеткого поиска, которые могут быть использованы в поиске строк-дубликатов...

Этапы и методы автоматического извлечения ключевых слов

Выделение коллокаций необходимо для того, чтобы алгоритм поиска ключевых слов не разделял семантически связанные

Довольно часто для поиска коллокаций применяют статистические методы, которые в общем случае требуют следующие входные данные

Обзор некоторых алгоритмов нестрогого сопоставления записей...

Рассмотрим следующие алгоритмы нестрогого поиска: - хеширование по сигнатуре; - БК-дерево.

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

Обсуждение

Социальные комментарии Cackle

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

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

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

Использование алгоритмов нечеткого поиска при решении...

Ключевые слова. Нечеткий поиск; N-gram; релевантность строк; поиск данных

Поиск дубликатов в этом случае ведется по точному совпадению и не вызывает сложностей.

Общий принцип применения функции для поиска дубликатов следующий

Использование сети Хемминга для автоматической коррекции...

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

Рис. 2. График зависимости времени обработки от размеров словаря. Заключение.

Статический анализатор кода на основе взаимодействия...

Ключевые слова: статический анализ, интервальный анализ, анализ указателей, поиск

Каждый объект представлен тремя атрибутами: тип, размер и владелец. Возможные типы

Система уравнений решается с использованием известных алгоритмов теории решеток.

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

Частотный словарьнабор слов данного языка (или подъязыка) вместе с информацией о частоте их встречаемости.

Рис. 2. Алгоритм функции поиска значения по ключу. Также была реализована функция удаления значения по ключу.

Сравнительный анализ алгоритмов сортировки данных в массивах

Ключевые слова: алгоритм сортировки, сравнение алгоритмов сортировки.

Быстрота при условии использования подходящего массива входных данных.

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

Система поиска сходства шаблонизированных строк

Дублирующееся объявление — это не только копия ранее поданного, но и объявление, отличающееся от исходного одним-двумя неключевыми словами.

Далее сформируем список алгоритмов нечеткого поиска, которые могут быть использованы в поиске строк-дубликатов...

Этапы и методы автоматического извлечения ключевых слов

Выделение коллокаций необходимо для того, чтобы алгоритм поиска ключевых слов не разделял семантически связанные

Довольно часто для поиска коллокаций применяют статистические методы, которые в общем случае требуют следующие входные данные

Обзор некоторых алгоритмов нестрогого сопоставления записей...

Рассмотрим следующие алгоритмы нестрогого поиска: - хеширование по сигнатуре; - БК-дерево.

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

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

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

Использование алгоритмов нечеткого поиска при решении...

Ключевые слова. Нечеткий поиск; N-gram; релевантность строк; поиск данных

Поиск дубликатов в этом случае ведется по точному совпадению и не вызывает сложностей.

Общий принцип применения функции для поиска дубликатов следующий

Использование сети Хемминга для автоматической коррекции...

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

Рис. 2. График зависимости времени обработки от размеров словаря. Заключение.

Статический анализатор кода на основе взаимодействия...

Ключевые слова: статический анализ, интервальный анализ, анализ указателей, поиск

Каждый объект представлен тремя атрибутами: тип, размер и владелец. Возможные типы

Система уравнений решается с использованием известных алгоритмов теории решеток.

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

Частотный словарьнабор слов данного языка (или подъязыка) вместе с информацией о частоте их встречаемости.

Рис. 2. Алгоритм функции поиска значения по ключу. Также была реализована функция удаления значения по ключу.

Сравнительный анализ алгоритмов сортировки данных в массивах

Ключевые слова: алгоритм сортировки, сравнение алгоритмов сортировки.

Быстрота при условии использования подходящего массива входных данных.

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

Система поиска сходства шаблонизированных строк

Дублирующееся объявление — это не только копия ранее поданного, но и объявление, отличающееся от исходного одним-двумя неключевыми словами.

Далее сформируем список алгоритмов нечеткого поиска, которые могут быть использованы в поиске строк-дубликатов...

Этапы и методы автоматического извлечения ключевых слов

Выделение коллокаций необходимо для того, чтобы алгоритм поиска ключевых слов не разделял семантически связанные

Довольно часто для поиска коллокаций применяют статистические методы, которые в общем случае требуют следующие входные данные

Обзор некоторых алгоритмов нестрогого сопоставления записей...

Рассмотрим следующие алгоритмы нестрогого поиска: - хеширование по сигнатуре; - БК-дерево.

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

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