Скрыть
Раскрыть

ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

English version: ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Дворецкий М. С. 1
  • 1 Московский государственный университет им. М.В. Ломоносова, 119991, г. Москва, Ленинские горы, д. 1

Алгоритм нахождения k наименьших элементов на отрезке (Top-k RMQ) на основе дерева отрезков и его применение в задачах автодополнения

2017. № 1 (39). С. 48–54 [содержание номера]

М.С. Дворецкий - студент магистратуры, Московский государственный университет им. М.В. Ломоносова; программист, ООО «IQ Systems»
Адрес: 119991, г. Москва, Ленинские горы, д. 1
E-mail: mike.dvorecky@gmail.com

      Контроль данных при вводе является важным способом обеспечения их качества. Одним из методов такого контроля является сопоставление вводимых данных, которые должны соответствовать справочной информации, непосредственно с этой информацией в процессе ввода. Это приводит к необходимости решения задачи автодополнения. Поскольку справочная информация, как правило, хранится централизованно, задача автодополнения решается в архитектуре клиент-сервер и к алгоритму ее решения предъявляются жесткие требования по быстродействию.
      В данной статье на основе существующей декомпозиции задачи автодополнения с использованием задачи поиска минимума на отрезке (RMQ) формулируется задача поиска k минимумов на отрезке (Top-k RMQ) и приводится алгоритм ее решения, использующий дерево отрезков. В то время как классический алгоритм RMQ по дереву отрезков при использовании в задаче автодополнения (в подзадаче Top-k RMQ) требует многократного посещения вершин дерева, близких к корню, предложенный алгоритм Top-k RMQ непосредственно адаптирован к этой задаче и не требует рассмотрения какой-либо вершины дерева отрезков более двух раз. Выполнен анализ сложности как алгоритма Top-k RMQ, так и классического алгоритма RMQ с использованием дерева отрезков. При этом учитываются различные варианты реализации приоритетных очередей, используемых в этих алгоритмах, а именно вариант двоичной кучи и простая приоритетная очередь на основе упорядоченного массива. Новый алгоритм имеет не меньшую вычислительную сложность, чем классический, при любой реализации приоритетной очереди.
      Для доказательства ценности нового алгоритма произведено экспериментальное сравнение алгоритмов с использованием данных из Классификатора адресов России, представляющего собой реальный примера справочной информации. Во всех проведенных экспериментах новый алгоритм показал лучшие результаты по времени по сравнению с классическим. 

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

Dvoretckii M.S. A segment tree based Top-k RMQ algorithm and its application to the autocomplete problem // Business Informatics. 2017. No. 1 (39). P. 48–54. DOI: 10.17323/1998-0663.2017.1.48.54

BiBTeX
RIS
 
 
Rambler's Top100 rss