Библиотека автозаполнения в C ++

Question

Мне нужна процедура автозавершения или библиотека на C ++ для 1 миллиона слов. Я думаю, я могу найти рутину в сети, как Рабин-Карп. Вы знаете библиотеку, которая делает это? Я не вижу этого в Boost.

Также сумасшедшая идея использовать SQL-запрос MySql LIKE для этого?

Спасибо

РЕДАКТИРОВАТЬ: Это правда, что мне нужно больше предложений, чем автозаполнение (предложите десять слов, когда пользователь набрал первые 2 буквы). У меня на самом деле также есть выражения «Цифровая камера Nikon». Но для первой версии мне нужны только предложения о Ni от Nikon, а не о «цифровой камере».

Answer 1

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

Как насчет организации (красиво) ваших данных в26-дерево (одна запись на букву, или, если вы поддерживаете не буквы, хорошо выбранное x-дерево).Таким образом, вы организуете свои данные один раз, а затем получите быстрый результат при разборе дерева.если вы хотите ограничить количество результатов, предложенных в вашем автозаполнении, вы можете адаптировать алгоритм анализа дерева.Кажется простым и эффективным (подобный синтаксис в SQL должен будет сравнивать все ваши элементы в вашей таблице каждый раз, в то время как мое решение намного быстрее, если данные заданы правильно)

Другое решение, вы можете посмотреть на Qtреализация QCompleter (может быть, излишне зависеть от Qt вашего кода, я не знаю)

Answer 2

Вы можете использовать три (дерево префиксов) для хранения ваших слов.

struct trie
{
  std::map<char, trie*> next;
  bool is_word;

  void insert(std::string w)
  {  
    trie * n = this;
    for (int i = 0; i < w.size(); ++i) {
      if (n->next.find(w[i]) == n->next.end()) {
        n->next[w[i]] = new trie();
      }
      n = n->next[w[i]];
    }
    n->is_word = true;
  }
};

Тогда вы можете легко получать префиксные совпадения, повторяющиеся на поддеревьях.

Answer 3

Однажды я работал над проектом, который делал что-то подобное, используя CLucene .Работало нормально.

Answer 4

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

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

Например, в C ++ класс std::map имеет член lower_bound, который будет указывать в O (log N) на первый элемент, который может расширить ваше слово.

Answer 5

Вы можете написать свою собственную простую функцию автозаполнения, используя расстояние Дамерау-Левенштейна.