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

Question

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

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

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

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

редактирует:

@ Гэндальф: Для нашего случая использования важно, чтобы автозаполнение было всеобъемлющим, а не просто дополнительной помощью для пользователя. Что касается того, что мы заканчиваем, это список пар типа концепт. Например, возможными записями являются [(«Microsoft», «Компания-разработчик»), («Джефф Этвуд», «Программист»), («StackOverflow.com», «Веб-сайт»)]. Мы используем Lucene для полного поиска, когда пользователь выбирает элемент из списка автозаполнения, но я пока не уверен, что Lucene будет работать хорошо для самого автозаполнения.

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

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

Answer 1

С таким большим набором я бы попробовал что-то вроде индекса 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
}

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

Answer 2

У меня было похожее требование.

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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);

Answer 5

Я использовал hashtable и mmap () И список с 10 000 000+ записей не является проблемой. Посмотреть демо здесь: http://olegh.ath.cx/autocomplete.html

Answer 6

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

Answer 7

использовать структуру данных Trie вот вики http://en.wikipedia.org/wiki/Trie

Answer 8

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

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

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

Answer 9

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

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

Ajax Auto Suggest v2

Answer 10

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

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

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

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

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

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

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