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

Ответ 1

С большим набором я бы попробовал что-то вроде индекса Lucene, чтобы найти нужные вам термины, и задал задачу таймера, которая получает reset после каждого нажатия клавиши с задержкой в ​​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 может быть предварительно создан и оптимизирован.

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

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

Ответ 4

Я закончил решение этой проблемы через 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);

Ответ 5

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

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

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

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

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

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

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

Ответ 9

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

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

Ajax Auto Suggest v2

Ответ 10

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

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

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