Автозаполнение серверной реализации

17

Что такое быстрый и эффективный способ реализации серверного компонента для функции автозаполнения в поле ввода html?

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

Текущая реализация просто загружает все концепции в память в отсортированном наборе и выполняет простой поиск журнала (n) при нажатии клавиши пользователя. Затем tailset используется для обеспечения дополнительных совпадений за ближайшим совпадением. Проблема с этим решением заключается в том, что он не масштабируется. В настоящее время он работает против ограничения пространства кучи виртуальной машины (я установил -Xmx2g, и это примерно то же самое, что мы можем нажимать на наши 32-битные машины), и это не позволяет нам расширять нашу концептуальную таблицу или добавлять дополнительные функции. Переход на 64-разрядные виртуальные машины на машинах с большим объемом памяти не является непосредственной опцией.

Я не решался приступить к работе над решением на основе диска, поскольку я обеспокоен тем, что время поиска диска будет убивать производительность. Существуют ли возможные решения, которые позволят мне масштабироваться лучше, либо полностью в памяти, либо с помощью некоторых быстрых реализаций на диске?

Изменения:

@Gandalf: для нашего случая использования важно, чтобы автозаполнение было исчерпывающим, и это не просто дополнительная помощь для пользователя. Что касается того, что мы завершаем, это список пар понятия-типа. Например, возможные записи: [(«Microsoft», «Software Company»), («Jeff Atwood», «Programmer»), («StackOverflow.com», «Веб-сайт»)]. Мы используем Lucene для полного поиска, как только пользователь выбирает элемент из списка автозаполнения, но я еще не уверен, что Lucene будет хорошо работать для самого автозаполнения.

@Glen: Базы данных здесь не используются. Когда я говорю о таблице, я имею в виду структурированное представление моих данных.

@Jason Day: моей первоначальной реализацией этой проблемы было использование Trie , но память наворотов с этим была на самом деле хуже, чем отсортированный набор из-за необходимости большого количества ссылок на объекты. Я буду читать триниальные деревья поиска, чтобы узнать, может ли это быть полезным.

    
задан toluju 09.06.2009 в 20:41
источник
  • Не могли бы вы рассказать нам немного больше о том, что вы «автозаполняете». Почему так много терминов? Есть ли более очевидные, которые отвечали бы 90% ваших пользовательских запросов, а не загружали бы каждую возможность? –  Gandalf 09.06.2009 в 18:29
  • Я не могу точно сказать, будет ли Lucene соответствовать вашим потребностям, но в этом наборе данных размера я очень сомневаюсь, что вы не получите промежуточные запросы на оптимизированный индекс Lucene. В зависимости от того, как настроен индекс, вы можете даже сохранить его в памяти. –  Gandalf 09.06.2009 в 22:58
  • Стандартное Trie действительно очень интенсивно для памяти, для больших наборов вы хотите использовать Compacted Trie, что значительно уменьшает объем памяти. Дополнительные оптимизации включают ленивую инициализацию значений узлов и правильных структур данных для наборов children / value. Некоторое время назад я создал библиотеку автозаполнения Java, способную обрабатывать очень большие наборы данных (10 000 000+) и эффективно отвечать на точные и приблизительные поисковые запросы. –  Miguel Fonseca 23.06.2015 в 16:36

10 ответов

6

При большом наборе я бы попробовал что-то вроде индекса Lucene, чтобы найти нужные вам термины, и задал задачу таймера, которая сбрасывается после каждого нажатия клавиши с задержкой в ​​0,5 секунды. Таким образом, если пользователь набирает несколько символов быстро, он не запрашивает индекс каждый штрих, только когда пользователь делает паузу на секунду. Проверка работоспособности позволит вам узнать, как долго эта пауза должна быть.

Timer findQuery = new Timer();
...
public void keyStrokeDetected(..) {
   findQuery.cancel();
   findQuery = new Timer();
   String text = widget.getEnteredText();
   final TimerTask task = new TimerTask() {
      public void run() {
         ...query Lucene Index for matches
      }
   };
   findQuery.schedule(task, 350); //350 ms delay
}

Некоторые pseduocode есть, но это идея. Также, если условия запроса установлены, индекс Lucene может быть предварительно создан и оптимизирован.

    
ответ дан Gandalf 09.06.2009 в 18:31
  • , я не думаю, что эти клавиши действительно нужны, так как это не похоже на проблему. Но я согласен с тем, что вы можете включить весь свой контент в индекс lucene. Луцен безумно быстро для такого рода вещей. –  John Gardner 09.06.2009 в 22:08
  • В эти дни Lucene имеет встроенную поддержку автозаполнения. См. Пример stackoverflow.com/questions/24968697/.... –  John Wiseman 14.08.2014 в 09:24
4

У меня было аналогичное требование.

Я использовал реляционную базу данных с одной хорошо проиндексированной синтетической таблицей (избегая объединений и просмотров для ускорения поиска) и кэша в памяти (Ehcache) для хранения большинства используемых записей.

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

Это решение для больших наборов данных, которые нельзя хранить на клиенте, и работает очень быстро (не кэшированный поиск всегда извлекался менее чем за 0,5 секунды в моем случае). Он также масштабируется по горизонтали - вы всегда можете добавить дополнительные серверы и серверы баз данных.

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

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

    
ответ дан Domchi 09.06.2009 в 18:50
3

Для тех, кто спотыкается на этот вопрос ...

Я только что разместил реализацию автозаполнения на стороне сервера в Google Code. Проект включает библиотеку java, которая может быть интегрирована в существующие приложения и автономный сервер автозаполнения HTTP AJAX.

Моя надежда заключается в том, что позволяет людям включать эффективный автозаполнение в свои приложения. Убейте шины!

    
ответ дан Shilad Sen 22.12.2009 в 08:31
  • Как запустить сервер? java -jar autocomplete-server-0.3.jar не работает? Спасибо за информацию –  Alfred 19.01.2010 в 23:34
  • Хороший вопрос. Я добавил пример на домашнюю страницу автозаполнения и добавил новую версию (0.4). –  Shilad Sen 20.01.2010 в 10:29
  • Спасибо за отзыв. –  Alfred 21.01.2010 в 07:58
2

Я закончил решение этой проблемы через Lucene; начальные тесты производительности кажутся достаточными для нашего случая использования. Чтобы заставить запросы с префиксом работать, нужно немного взломать, поскольку я запускал исключение TooManyClauses при расширении запросов, таких как «Jeff At *». Я закончил обертку моего IndexReader с помощью FilterIndexReader и установил жесткую колпачку на количество терминов, возвращаемых при вызове termfix. Вот мой код:

Directory directory = FSDirectory.getDirectory(indexDir);
IndexReader reader = IndexReader.open(directory);
FilterIndexReader filteredReader = new FilterIndexReader(reader) {
  @Override public TermEnum terms(Term t) throws IOException {
    final TermEnum origEnum = super.terms(t);

    return new TermEnum() {
      protected int count = 0;
      @Override public boolean next() throws IOException {
        if (count++ < (BooleanQuery.getMaxClauseCount() - 10))
          return origEnum.next();
        else return false;
      }

      @Override public Term term() {
        return origEnum.term();
      }

      @Override public int docFreq() {
        return origEnum.docFreq();
      }

      @Override public void close() throws IOException {
        origEnum.close();
      }
    };
  }
};

IndexSearcher searcher = new IndexSearcher(filteredReader);
    
ответ дан toluju 12.06.2009 в 00:29
1

Я сделал это для небольших наборов данных, используя Тройное дерево поиска . Код DDJ не так сложно преобразовать в Java, но предполагает, что весь набор данных поместится в память. Существуют встроенные деревья поиска Ternary на диске ( здесь в python), но, конечно, они будут менее результативными. Тем не менее, поскольку тройные деревья поиска превосходят частичные совпадения, производительность может быть подходящей для ваших нужд.

    
ответ дан Jason Day 09.06.2009 в 20:18
1

Я использовал хэш-таблицу и mmap () И список из 10 000 000+ записей не является проблемой. См. Демо здесь: Ссылка

    
ответ дан maxihatop 13.05.2010 в 06:38
0

использовать структуру данных trie здесь wiki Ссылка

    
ответ дан mpadavala 24.06.2014 в 07:42
-1

Если вы не можете физически загрузить все данные в ОЗУ, вам придется иметь дело с наличием на диске.

Какая БД вы используете?

Например, у Oracle есть опция, в которой вы можете сохранить всю таблицу в памяти и выполнить свои запросы против этого.

MySQL также утверждает, что имеет некоторые возможности в памяти, но я мало знаю о MySQL.

Затем вы можете отказаться от своего кеша на основе Java, или вы можете использовать кеш для самых популярных / недавних запросов.

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

Если поиск диска замедляет вас, вы можете исследовать с помощью накопителей SSD, чтобы ускорить чтение.

    
ответ дан Glen 09.06.2009 в 18:31
-1

Возможно, я неправильно понял ваш вопрос, но не мог ли вы использовать плагин JQuery для Ajax для вашего приложения?

Я использовал это раньше:

Ajax Auto Suggest v2

    
ответ дан Antonio Louro 09.06.2009 в 19:12
  • На стороне веб-интерфейса я использую jQuery для обратного вызова ajax. Я говорю о серверной стороне вещей здесь. –  toluju 09.06.2009 в 20:42
-1
  

Существуют ли возможные решения, которые   позвольте мне лучше масштабироваться

Да, Oracle. Это та вещь, для которой созданы базы данных. Просто проиндексируйте соответствующие столбцы. Если вы работаете против стены встроенных решений, то компромисс с временем поиска диска или задержкой сети, вероятно, будет спорным. Особенно если вы вставляете слой кэширования между ними.

Кроме того, вы можете уменьшить количество обращений, если немного измените свой код на стороне клиента. Например, задание минимального количества символов типа перед запуском запроса или установка доли секунды задержки после того, как пользователь перестанет печатать. Если вы уже используете их, установите их немного выше.

    
ответ дан jiggy 09.06.2009 в 21:06