Каков эффективный алгоритм поиска для автозаполнения?

Question

У меня есть список из 10000 ключевых слов. Каков эффективный алгоритм поиска, обеспечивающий автоматическое заполнение этого списка?

Answer 1

Использование Trie - вариант, но он неэффективен в пространстве. Они могут быть более эффективными при использовании модифицированной версии, известной как Radix Tree или Patricia Tree.

Возможно, лучше использовать троичное дерево поиска. Вот статья на эту тему: « Эффективное автоматическое заполнение с помощью троичного дерева поиска. » Еще одна отличная статья об использовании троичного дерева поиска для исправления орфографии (проблема, аналогичная автоматическому заполнению) , " Использование троичных DAG для исправления орфографии. "

Answer 2

Я думаю бинарный поиск отлично работает для 10000 записей.

Answer 3

Три: http://en.wikipedia.org/wiki/Trie дает вам O (N) время поиска всякий раз, когда вы печатаете букву (я предполагаю, что вы хотите новые предложения, когда печатаете букву). Это должно быть достаточно эффективно, если у вас есть маленькие слова и пространство поиска будет уменьшаться с каждой новой буквой.

Answer 4

Был предложен довольно окольный метод SO для кроссвордов.

Здесь можно довольно легко адаптироваться:)

Идея проста, но довольно эффективна: она состоит в индексации слов, построении одного индекса на позицию буквы. Следует отметить, что после 4/5 букв подмножество доступных слов настолько мало, что грубая сила, вероятно, лучше всего ... это, конечно, нужно измерить.

Что касается идеи, вот способ Python:

class AutoCompleter:
  def __init__(self, words):
    self.words = words
    self.map = defaultdict(set)
    self._map()

  def _map(self):
    for w in words:
      for i in range(0,len(w)):
        self.map[(i,w[i])].insert(w)

  def words(self, firstLetters):
    # Gives all the sets for each letter
    sets = [self.map[(i, firstLetters[i])] for i in range(0, len(firstLetters))]

    # Order them so that the smallest set is first
    sets.sort(lambda x,y: cmp(len(x),len(y)))

    # intersect all sets, from left to right (smallest to biggest)
    return reduce(lambda x,y: intersection(x,y), sets)

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

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

• 3 просмотра в хэш-карте
• 2 пересечения множеств (определенно одно место), но упорядочены так, чтобы быть максимально эффективными.

Я бы определенно должен был попробовать это на примере тройного дерева и дерева, чтобы увидеть, как оно поживает.

Answer 5

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