Подсчет количества слов при разборе дерева Trie

Я пытаюсь решить проблему автозаполнения клавиатуры, описанную здесь. Задача состоит в том, чтобы рассчитать, сколько нажатий клавиш требует слово, учитывая некоторые словарь и правила автозаполнения. Например, для словаря:

data = ['hello', 'hell', 'heaven', 'goodbye']

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

{'hell': 2, 'heaven': 2, 'hello': 3, 'goodbye': 1}

Быстрое объяснение: если пользователь вводит h, затем e автозаполнение, потому что все слова, начинающиеся с h Также есть e как второе письмо. Теперь, если пользователь вводит l, другой l заполнен, давая 2 удара по слову hell, Конечно, hello потребуется еще один удар. Пожалуйста, смотрите ссылку выше для большего количества примеров.

мой Trie код следующий, и он отлично работает (взято с https://en.wikipedia.org/wiki/Trie). Stack Код для парсинга дерева от корня (см. правку ниже):

class Stack(object):
    def __init__(self, size):
        self.data = [None]*size
        self.i = 0
        self.size = size

    def pop(self):
        if self.i == 0:
            return None
        item = self.data[self.i - 1]
        self.i-= 1
        return item

    def push(self, item):
        if self.i >= self.size:
            return None
        self.data[self.i] = item
        self.i+= 1
        return item

    def __str__(self):
        s = '# Stack contents #\n'
        if self.i == 0:
            return
        for idx in range(self.i - 1, -1, -1):
            s+= str(self.data[idx]) + '\n'
        return s

class Trie(object):
    def __init__(self, value, children):
        self.value = value #char
        self.children = children #{key, trie}

class PrefixTree(object):
    def __init__(self, data):
        self.root = Trie(None, {})
        self.data = data

        for w in data:
            self.insert(w, w)

    def insert(self, string, value):
        node = self.root
        i = 0
        n = len(string)

        while i < n:
            if string[i] in node.children:
                node = node.children[string[i]]
                i = i + 1
            else:
                break

        while i < n:
            node.children[string[i]] = Trie(string[:i], {})
            node = node.children[string[i]]
            i = i + 1

        node.value = value


    def find(self, key):
        node = self.root
        for char in key:
            if char in node.children:
                node = node.children[char]
            else:
                return None
        return node

Я не мог понять, как считать количество ударов:

data = ['hello', 'hell', 'heaven', 'goodbye']
tree = PrefixTree(data)
strokes = {w:1 for w in tree.data} #at least 1 stroke is necessary

А вот код для анализа дерева от корня:

stack = Stack(100)
stack.push((None, pf.root))
print 'Key\tChilds\tValue'
print '--'*25

strokes = {}

while stack.i > 0:
    key, curr = stack.pop()

    # if something:
         #update strokes

    print '%s\t%s\t%s' % (key, len(curr.children), curr.value)
    for key, node in curr.children.items():
        stack.push((key, node))

print strokes

Любая идея или конструктивный комментарий помогут, спасибо!

редактировать

Отличный ответ @SergiyKolesnikov. Есть одно небольшое изменение, которое можно сделать, чтобы избежать вызова endsWith(), Я только что добавил логическое поле в класс Trie:

class Trie(object):
    def __init__(self, value, children, eow):
        self.value = value #char
        self.children = children #{key, trie}
        self.eow = eow # end of word

И в конце вставки ():

def insert(self, string, value):
#...
    node.value = value
    node.eow = True

Тогда просто замени curr.value.endswith('$'): с curr.eow, Спасибо вам всем!

Источник

2 ответа

Решение

Trie для вашего примера может выглядеть так

 ' '
|    \
H     G
|     |
E     O
| \   |
L  A  O
|  |  |
L$ V  D
|  |  |
O  E  B
   |  |
   N  Y
      |
      E

Какие узлы в дереве можно рассматривать как маркеры нажатий клавиш пользователя? Существует два типа таких узлов:

  1. Внутренние узлы с более чем одним дочерним элементом, потому что пользователь должен выбирать из нескольких альтернатив.
  2. Узлы, которые представляют последнюю букву слова, но не являются листьями (отмечены $), потому что пользователь должен ввести следующую букву, если текущее слово не то, что нужно.

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

Для слова "ад" это два маркерных узла: ' ' а также E (2 удара).
Для слова "привет" это три узла маркера: ' ', E, L$ (3 удара).
И так далее...

Что необходимо изменить в вашей реализации:

Конец допустимого слова должен быть отмечен в дереве, чтобы можно было проверить второе условие. Поэтому мы меняем последнюю строку PrefixTree.insert() метод из

node.value = value

в

node.value = value + '$'

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

stack = Stack(100)
stack.push((None, tree.root, 0)) # We start with stroke counter = 0
print('Key\tChilds\tValue')
print('--'*25)

strokes = {}

while stack.i > 0:
    key, curr, stroke_counter = stack.pop()

    if curr.value is not None and curr.value.endswith('$'):
        # The end of a valid word is reached. Save the word and the corresponding stroke counter.
        strokes[curr.value[:-1]] = stroke_counter

    if len(curr.children) > 1:
        # Condition 2 is true. Increase the stroke counter.
        stroke_counter += 1
    if curr.value is not None and curr.value.endswith('$') and len(curr.children) > 0:
        # Condition 1 is true. Increase the stroke counter.
        stroke_counter += 1

    print('%s\t%s\t%s' % (key, len(curr.children), curr.value))
    for key, node in curr.children.items():
        stack.push((key, node, stroke_counter)) # Save the stroke counter

print(strokes)

Выход:

Key Childs  Value
--------------------------------------------------
None    2   None
h   1   
e   2   h
a   1   he
v   1   hea
e   1   heav
n   0   heaven$
l   1   he
l   1   hell$
o   0   hello$
g   1   
o   1   g
o   1   go
d   1   goo
b   1   good
y   1   goodb
e   0   goodbye$
{'heaven': 2, 'goodbye': 1, 'hell': 2, 'hello': 3}
Источник

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

  • Начинается с 0 для None.
  • Если текущий узел имеет более 2 дочерних элементов, счетчик дочерних элементов будет на 1 больше текущего счетчика.
  • Если текущее значение является допустимым словом и имеет хотя бы одного дочернего элемента, счетчик дочернего элемента (ren) будет на 1 больше текущего счетчика.

Для документации, вот мой ответ Ruby:

class Node
  attr_reader :key, :children
  attr_writer :final
  def initialize(key, children = [])
    @key = key
    @children = children
    @final = false
  end

  def final?
    @final
  end
end

class Trie
  attr_reader :root
  def initialize
    @root = Node.new('')
  end

  def add(word)
    node = root
    word.each_char.each{|c|
      next_node = node.children.find{|child| child.key == c}
      if next_node then
        node = next_node
      else
        next_node = Node.new(c)
        node.children.push(next_node)
        node = next_node
      end
    }
    node.final = true
  end

  def count_strokes(node=root,word="",i=0)
    word=word+node.key
    strokes = {}
    if node.final? then
      strokes[word]=i
      if node.children.size>0 then
        i+=1
      end
    elsif node.children.size>1 then
      i+=1
    end
    node.children.each{|c|
      strokes.merge!(count_strokes(c, word, i))
    }
    strokes
  end
end

data = ['hello', 'hell', 'heaven', 'goodbye']
trie =  Trie.new
data.each do |word|
  trie.add(word)
end

# File.readlines('/usr/share/dict/british-english').each{|line|
#   trie.add line.strip
# }

puts trie.count_strokes
#=> {"hell"=>2, "hello"=>3, "heaven"=>2, "goodbye"=>1}

Только 60 строк, и это займет менее 3 секунд на 100 000 слов.

Источник
Другие вопросы по тегам