Как реализовать автозаполнение массивного набора данных

Question

Я пытаюсь реализовать что-то вроде предложения Google на веб-сайте, который я создаю, и мне интересно, как поступить с очень большим набором данных. Конечно, если у вас есть 1000 предметов, вы кешируете их и просто просматриваете их. Но как вы поступите, если у вас есть миллион предметов? Далее предположим, что предметы не одно слово. В частности, я был действительно впечатлен Pandora.com. Например, если вы ищете «мокрый», он возвращает «Мокрый песок», но также и «Жаба». И их автозаполнение БЫСТРО. Моей первой идеей было сгруппировать элементы по первым двум буквам, чтобы у вас было что-то вроде:

Dictionary<string,List<string>>

где ключ - первые две буквы. Это нормально, но что, если я захочу сделать что-то похожее на Pandora и позволить пользователю видеть результаты, соответствующие середине строки? С моей идеей: Wet никогда не будет соответствовать Toad и Wet Sprocket, потому что он будет в ведре «TO» вместо ведра «WE». Так что, возможно, вы могли бы разделить строку и «Жаба мокрой звездочки» перейти в ведра «TO», «WE» и «SP» (убрать слово «THE»), но когда вы Вы говорите о миллионе записей, которые, возможно, должны сказать несколько слов каждое, возможно, вы быстро начнете расходовать много памяти. Хорошо, это был длинный вопрос. Мысли?

Answer 1

Как я указывал в Как реализовать добавочный поиск в списке , вы должны использовать такие структуры, как Trie или Patricia trie для поиска шаблонов в больших текстах .

И для обнаружения шаблонов в середине некоторого текста есть одно простое решение. Я не уверен, является ли это наиболее эффективным решением, но обычно я делаю это следующим образом.

Когда я вставляю новый текст в Trie, я просто вставляю его, затем удаляю первый символ, вставляю снова, удаляю второй символ, вставляю снова ... и так далее, пока весь текст не будет использован. Затем вы можете обнаружить каждую подстроку каждого вставленного текста только одним поиском из корня. Эта результирующая структура называется Suffix Tree , и существует множество вариантов оптимизации.

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

Answer 2

Не пытайтесь реализовать это самостоятельно (если вы просто любопытны). Используйте что-нибудь вроде Lucene или Endeca - это сэкономит ваше время и волосы.

Answer 3

Не относится алгоритмически к тому, что вы спрашиваете, но убедитесь, что у вас есть задержка (или задержка) в 200 мс или более после kaypress (ов), так что вы гарантируете, что пользователь прекратил печатать перед выполнением асинхронного запроса. Таким образом вы уменьшите избыточные http-запросы к серверу.

Answer 4

Я бы использовал что-то вроде trie , и значение каждого листового узла было бы списком возможностей, которые содержат слово, представленное листовым узлом. Вы можете отсортировать их в порядке вероятности или динамически отсортировать / отфильтровать их на основе других слов, введенных пользователем в поле поиска, и т. Д. Он будет выполняться очень быстро и с разумным объемом оперативной памяти.

Answer 5

если вам не нужен три и вы хотите что-то посередине строки, вы обычно хотите запустить какую-то функцию редактирования расстояния (расстояние Левенштейна), которая даст вам число, показывающее, насколько хорошо 2 строки соответствуют , это не особенно эффективный алгоритм, но он не имеет большого значения для таких вещей, как слова, поскольку они относительно короткие. если вы выполняете сравнения на 8000 символьных строках, это, вероятно, займет несколько секунд. я знаю, что большинство языков имеют реализацию, или вы можете найти код / ​​псевдокод для него довольно легко в Интернете.

Answer 6

Вы сохраняете элементы на стороне сервера (возможно, в БД, если набор данных действительно большой и сложный) и отправляете вызовы AJAX из браузера клиента, которые возвращают результаты, используя json / xml. Вы можете сделать это в ответ на ввод текста пользователем или с помощью таймера.

Answer 7

Я построил AutoCompleteAPI точно для этого сценария.

Зарегистрируйтесь, чтобы получить личный индекс, затем, Загрузите ваши документы.

Пример загрузки с использованием curl в документе «Нью-Йорк»:

curl -X PUT -H "Content-Type: application/json" -H "Authorization: [YourSecretKey]" -d '{
"key": "New York",
"input": "New York"
}' "http://suggest.autocompleteapi.com/[YourAccountKey]/[FieldName]"

После индексирования всего документа, чтобы получить предложения по автозаполнению, используйте:

http://suggest.autocompleteapi.com/[YourAccountKey]/[FieldName]?prefix=new

Вы можете использовать любую клиентскую библиотеку автозаполнения, чтобы показать эти результаты пользователю.