Инкрементный поиск по всей строке

Инкрементный поиск по началу строки

Давайте рассмотрим разновидность инкрементного поиска - поиск по началу строки, который позволяет производить быстрое позиционирование в массиве данных. Предположим, что у нас есть список из 1000 наименований, упорядоченных по алфавиту, и нужно перейти к записям, начинающиеся с буквы "т". В случае инкрементного поиска для этого достаточно один раз нажать клавишу "т". То есть, инкрементный поиск по началу строки позволяет быстро перейти к записи, начало которой полностью или "частично соответствует" введенной к тому моменту строке поиска, что невозможно сделать с помощью обычного поиска. Что значит "частично соответствует"? Предположим, у нас есть 3 записи и выбрана первая запись:

Аспиратор
Прибор 1
Прибор 2
Прибор 3

В пустой строке поиска мы вводим букву "П" - произойдет переход ко 2-й записи, поскольку она начинается с буквы "П". Что произойдет, если мы введем букву "р"? Мы останемся на записи 2, поскольку фрагмент "Пр" в строке ввода соответствует началу названия 2-й записи "Прибор 1". Что будет, если мы теперь введем букву "а"? С фрагмента "Пра" не начинается ни одна запись в нашем примере. Вот здесь все будет зависеть от реализации. В 1С, например, раздается звуковой сигнал и пользователь не сможет ввести символ. А в Google можно спокойно продолжать ввод.

Инкрементный поиск по началу строки особенно эффективен в том случае, когда товар упорядочен по товарным группам, т.е. его название начинается с названия товарной группы, например, "прибор", "модель", "плакат", "карта". Это очень удобно в том случае, когда необходимо произвести поиск нескольких товаров из одной товарной группы, например, "приборы".

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

Вы заметили, что до сих пор мы рассматривали поиск с точки зрения Windows-программирования и говорили о пользователях? Это позволяет абстрагироваться от технологий и ограничений, присущим web-среде, и сосредоточить внимание на рассмотрении эффективных алгоритмов поиска. Если бы мы начали рассматривать данные вопросы с точки зрения Web, то вместо решения задачи разработки удобной системы поиска мы завязли в проблемах реализации поиска на сайте, что и демонстрируют многочисленные web-ресурсы, на которых поиск реализован непонятно как. Часто бывает, что найти решение в какой-то области "внутри нее" очень трудно. В таких случаях я рекомендую выйти за ее пределы, и обратиться к областям, которые являются родительскими, и, возможно, в них уже разработаны алгоритмы для решения похожих задач. Поскольку традиционное программирование является родителем web-программирования, то и ответы на проблемы Web нужно искать в программировании, где наработано огромное количество различных алгоритмов. Я бы сказал так, - что для Web является проблемой, то для программирования является лишь задачей, а с задачу, как известно, решить проще, чем пытаться справиться с проблемой.

История

Термин «информационный поиск» был впервые введён Кельвином Муром в 1948 в его докторской диссертации, опубликован и употребляется в литературе с 1950.

Сначала системы автоматизированного ИП, или информационно-поисковые системы (ИПС), использовались лишь для управления информационным взрывом в научной литературе. Многие университеты и публичные библиотеки стали использовать ИПС для обеспечения доступа к книгам, журналам и другим документам. Широкое распространение ИПС получили с появлением сети Интернет. У русскоязычных пользователей наибольшей популярностью пользуются поисковые системы Google, Яндекс и Рамблер.