Доступ к динамически генерируемому вложенному словарю

Question

Цель состоит в том, чтобы иметь возможность как можно быстрее сравнивать слова в документе со словами в наборе документов (создать матрицу терминологического документа).Если возможно, можно ли это сделать (и будет ли это быстро) с помощью Lucene?

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

Позиции

1
 2
  3
   4
    5
     6

Например, при использовании образца строки «Это тест» дерево будет выглядеть как

t
 h
  i
   s
 e
  s
   t
i
 s
a

Обратите внимание, что 't' на первом уровне встречается только один раз.Первый словарь будет содержать ключи {'t', 'i', 'a'}.Было бы три словаря второго уровня, содержащие ключи {'h'} {'e'} {'s'}.

Это должно сделать поиск очень быстрым.Максимальное количество шагов в цикле будет количеством символов в самом длинном слове.Часть, которая заставляет мой мозг складываться сама по себе, это то, как я динамически создаю словарь, подобный этому, с определенным доступом к правильному уровню

Пока у меня есть кое-что с эффектом

def addTerm(self, term):
   current_level = 0;
   for character in list(term):
      character = character.lower()
      if re.match("[a-z]",character):
         self.tree[character] = {}
         current_level += 1 

Answer 1

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

http://ejohn.org/blog/javascript-trie-performance-analysis/

Answer 2

Я вижу несколько проблем с вашей текущей реализацией.Как пометить, если узел в trie является словом?Лучшей реализацией было бы инициализировать дерево, например, tree = [{}, None], где None указывает, является ли текущий узел концом слова.

Тогда ваш метод addTerm может иметь вид1008 * Вы можете установить node[1] в True, если вам не важно, какое слово находится в узле.

Поиск, если слово находится в дереве, будет выглядеть примерно так:

def findTerm(self, term):
    node = self.tree
    for c in term:
        c = c.lower()
        if re.match("[a-z]",c):
            if c in node[0]:
                node = node[0][c]
            else:
                return False
    return node[1] != None