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

Я пытаюсь реализовать что-то вроде Google на веб-сайте, который я создаю, и мне интересно, как это сделать в очень большом наборе данных. Конечно, если у вас 1000 предметов, вы кешируете элементы и просто просматриваете их. Но как вы это делаете, когда у вас есть миллион предметов? Кроме того, предположим, что элементы не являются одним словом. В частности, я был очень впечатлен Pandora.com. Например, если вы ищете "мокрый", он возвращает "Мокрый песок", но он также возвращает Toad The Wet Sprocket. И их автозаполнение FAST. Моя первая идея состояла в том, чтобы сгруппировать элементы по первым двум буквам, поэтому у вас будет что-то вроде:

Dictionary<string,List<string>>

где ключ - это первые две буквы. Это нормально, но что, если я хочу сделать что-то похожее на pandora и позволить пользователю видеть результаты, соответствующие середине строки? С моей идеей: Мокрый никогда не будет соответствовать Жабам Мокрый Звездочке, потому что это будет в ковре "ТО" вместо ведра "МЫ". Итак, возможно, вы могли бы разбить строку и "Жаба влажной звездочки" зайти в ведра "TO", "WE" и "SP" (вырезать слово "THE" ), но когда вы говорите о миллионе записи, которые, возможно, говорят несколько слов, возможно, похоже, что вы быстро начнете использовать много памяти. Хорошо, это был длинный вопрос. Мысли?

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

Пример загрузки с использованием curl в документе "New York":

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

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