М.С. Дворецкий - студент магистратуры, Московский государственный университет им. М.В. Ломоносова; программист, ООО «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 с использованием дерева отрезков. При этом учитываются различные варианты реализации приоритетных очередей, используемых в этих алгоритмах, а именно вариант двоичной кучи и простая приоритетная очередь на основе упорядоченного массива. Новый алгоритм имеет не меньшую вычислительную сложность, чем классический, при любой реализации приоритетной очереди.
      Для доказательства ценности нового алгоритма произведено экспериментальное сравнение алгоритмов с использованием данных из Классификатора адресов России, представляющего собой реальный примера справочной информации. Во всех проведенных экспериментах новый алгоритм показал лучшие результаты по времени по сравнению с классическим.