Preview

Математика и математическое моделирование

Расширенный поиск

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

https://doi.org/10.24108/mathm.0317.0000077

Полный текст:

Аннотация

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

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

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

Об авторе

Р. В. Хруничев
Рязанский государственный радиотехнический университет, Рязань
Россия

Хруничев Роберт Вячеславович

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



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

1. Национальный корпус русского языка: Сайт. Режим доступа: http://www.ruscorpora.ru/index.html (дата обращения 06.07.2017).

2. Маннинг К.Д., Прабхакар Рагхаван, Шютце Х. Введение в информационный поиск: пер. с англ. М.: Вильямс, 2011. 520 с. [Manning Ch.D., Prabhakar Raghavan, Schutze H. Introduction to information retrieval. Camb.; N.Y.: Camb. Univ. Press, 2008. 482 p.].

3. Цукерт А.Г. Проблемы и перспективы информационного поиска // Изв. Таганрог. гос. радиотехн. ун-та. 2001. Т. 21. № 3(21). С. 194–201.

4. Задачи поисковых систем. Режим доступа: http://asknet.ru/Technology/searchtask.htm (дата обращения 06.07.2017).

5. Зупарова Л.Б., Зайцева Т.А. Аналитико-синтетическая переработка информации: учебник. М.: ФАИР, 2008. 400 с.

6. Сметанин Н. Нечёткий поиск в тексте и словаре. Режим доступа: https://habrahabr.ru/post/114997/ (дата обращения 06.07.2017).

7. Хруничев Р.В. Принципы построения многомерного пространства терминов в процессе анализа предметно-ориентированной коллекции документов // Вестник Астрахан. гос. техн. ун-та Сер.: Управление, вычислительная техника и информатика. 2012. № 1. С. 136-141.

8. Zipf G.K. Selected studies of the principle of relative frequency in language. Camb.: Harvard Univ. Press, 1932.

9. Гиляревский Р.С. Основы информатики: Курс лекций. М.: Экзамен, 2003. 318 с.

10. Мосалев П.М. Обзор методов нечеткого поиска текстовой информации // Вестник Моск. гос. ун-та печати им. И. Федорова. 2013. № 2. С. 87-91.

11. Нгуен Ной Хыу. Обзор некоторых алгоритмов нестрогого сопоставления записей применительно к задаче исключения дублирования персональных данных // Молодой ученый. 2013. № 5. С. 163-166.

12. Бойцов Л.М. Поиск по сходству в документальных базах данных: хеширование по сигнатуре оптимальное соотношение скорости поиска, простоты реализации и объема индексного файла [текст] // 8-я Междунар. конф. «Математика. Компьютер. Образование»: МКО 2001 (Москва, 2-4 октября 2001 г.): Труды. М.: Прогресс-Традиция, 2001. С. 177-183.

13. Панкратов И.В. Одновременный поиск нескольких двоичных шаблонов в потоке с помощью конечного автомата // Прикладная дискретная математика. 2014. № 2(24). С. 119–125.

14. Побитовые операторы. Режим доступа: https://learn.javascript.ru/bitwise-operators (дата обращения 06.07.2017).


Для цитирования:


Хруничев Р.В. Применение метода ветвей и границ при решении задачи нечеткого поиска методом хеширования по сигнатуре в локальных базах данных. Математика и математическое моделирование. 2017;(3):64-76. https://doi.org/10.24108/mathm.0317.0000077

For citation:


Khrunichev R.V. Method of Branches and Boundaries to Solve a Fuzzy Search Problem by Hash Signature Method in Local Databases. Mathematics and Mathematical Modeling. 2017;(3):64-76. (In Russ.) https://doi.org/10.24108/mathm.0317.0000077

Просмотров: 210


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)