@ARTICLE{26583204_205283637_2017, 
	author = {М. С. Дворецкий}, 
	keywords = {, Классификатор адресов России, автодополнение, дерево отрезков, поиск минимума на отрезке (RMQ), поиск k наименьших элементов на отрезке (Top-k RMQ)алгоритм},
	title = {<p class="text">Алгоритм нахождения k наименьших элементов на отрезке (Top-k RMQ) на основе дерева отрезков и его применение в задачах автодополнения</p>},
	journal = {Бизнес-информатика},
	year = {2017},
	number = {1 (39)},
	pages = {48-54},
	url = {https://bijournal.hse.ru/2017--1 (39)/205283637.html},
	publisher = {},
	abstract = {М.С.&nbsp;Дворецкий -&nbsp;студент магистратуры, Московский государственный университет им. М.В.&nbsp;Ломоносова;&nbsp;программист, ООО «IQ Systems»Адрес: 119991, г. Москва, Ленинские горы, д. 1E-mail: mike.dvorecky@gmail.com&nbsp; &nbsp; &nbsp; Контроль данных при вводе является важным способом обеспечения их качества. Одним из методов такого контроля является сопоставление вводимых данных, которые должны соответствовать справочной информации, непосредственно с этой информацией в процессе ввода. Это приводит к необходимости решения задачи автодополнения. Поскольку справочная информация, как правило, хранится централизованно, задача автодополнения решается в архитектуре клиент-сервер и к алгоритму ее решения предъявляются жесткие требования по быстродействию.&nbsp; &nbsp; &nbsp; В данной статье на основе существующей декомпозиции задачи автодополнения с использованием задачи поиска минимума на отрезке (RMQ) формулируется задача поиска k минимумов на отрезке (Top-k RMQ) и приводится алгоритм ее решения, использующий дерево отрезков. В то время как классический алгоритм RMQ по дереву отрезков при использовании в задаче автодополнения (в подзадаче Top-k RMQ) требует многократного посещения вершин дерева, близких к корню, предложенный алгоритм Top-k RMQ непосредственно адаптирован к этой задаче и не требует рассмотрения какой-либо вершины дерева отрезков более двух раз. Выполнен анализ сложности как алгоритма Top-k RMQ, так и классического алгоритма RMQ с использованием дерева отрезков. При этом учитываются различные варианты реализации приоритетных очередей, используемых в этих алгоритмах, а именно вариант двоичной кучи и простая приоритетная очередь на основе упорядоченного массива. Новый алгоритм имеет не меньшую вычислительную сложность, чем классический, при любой реализации приоритетной очереди.&nbsp; &nbsp; &nbsp; Для доказательства ценности нового алгоритма произведено экспериментальное сравнение алгоритмов с использованием данных из Классификатора адресов России, представляющего собой реальный примера справочной информации. Во всех проведенных экспериментах новый алгоритм показал лучшие результаты по времени по сравнению с классическим.&nbsp;},
	annote = {М.С.&nbsp;Дворецкий -&nbsp;студент магистратуры, Московский государственный университет им. М.В.&nbsp;Ломоносова;&nbsp;программист, ООО «IQ Systems»Адрес: 119991, г. Москва, Ленинские горы, д. 1E-mail: mike.dvorecky@gmail.com&nbsp; &nbsp; &nbsp; Контроль данных при вводе является важным способом обеспечения их качества. Одним из методов такого контроля является сопоставление вводимых данных, которые должны соответствовать справочной информации, непосредственно с этой информацией в процессе ввода. Это приводит к необходимости решения задачи автодополнения. Поскольку справочная информация, как правило, хранится централизованно, задача автодополнения решается в архитектуре клиент-сервер и к алгоритму ее решения предъявляются жесткие требования по быстродействию.&nbsp; &nbsp; &nbsp; В данной статье на основе существующей декомпозиции задачи автодополнения с использованием задачи поиска минимума на отрезке (RMQ) формулируется задача поиска k минимумов на отрезке (Top-k RMQ) и приводится алгоритм ее решения, использующий дерево отрезков. В то время как классический алгоритм RMQ по дереву отрезков при использовании в задаче автодополнения (в подзадаче Top-k RMQ) требует многократного посещения вершин дерева, близких к корню, предложенный алгоритм Top-k RMQ непосредственно адаптирован к этой задаче и не требует рассмотрения какой-либо вершины дерева отрезков более двух раз. Выполнен анализ сложности как алгоритма Top-k RMQ, так и классического алгоритма RMQ с использованием дерева отрезков. При этом учитываются различные варианты реализации приоритетных очередей, используемых в этих алгоритмах, а именно вариант двоичной кучи и простая приоритетная очередь на основе упорядоченного массива. Новый алгоритм имеет не меньшую вычислительную сложность, чем классический, при любой реализации приоритетной очереди.&nbsp; &nbsp; &nbsp; Для доказательства ценности нового алгоритма произведено экспериментальное сравнение алгоритмов с использованием данных из Классификатора адресов России, представляющего собой реальный примера справочной информации. Во всех проведенных экспериментах новый алгоритм показал лучшие результаты по времени по сравнению с классическим.&nbsp;}
}