Как я могу улучшить свою реализацию Trie с точки зрения инициализации? - PullRequest
Новая
       17

Как я могу улучшить свою реализацию Trie с точки зрения инициализации?

2 голосов
/ 02 октября 2011

Я пытаюсь прочитать из огромного списка слов и сохранить их таким образом, чтобы впоследствии я мог быстро их найти.Сначала я подумал об использовании trie, и я признаю, что моя реализация наивна, это в основном вложенные хеш-таблицы, где каждый ключ представляет собой отдельную букву.Прямо сейчас для того, чтобы вставить слово в поле ввода, требуется вечность (запуск этой программы занимает более 20 секунд), и мне было интересно, есть ли у кого-нибудь какие-либо идеи относительно того, что я мог бы сделать, чтобы улучшить мою вставку?Это не для домашней работы. 

import string
import time

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert_word(self, word):
        current_node = self.root
        for letter in word:
            trie_node = current_node.get_node(letter)
            current_node = trie_node

class TrieNode:

    def __init__(self):
        self.data = {}

    def get_node(self, letter):
        if letter in self.data:
            return self.data[letter]
        else:
            new_trie_node = TrieNode()
            self.data[letter] = new_trie_node
            return new_trie_node

def main():
    start_time = time.time()
    trie = Trie()

    with open('/usr/share/dict/words', 'r') as dictionary:
        word_list = dictionary.read()
    word_list = word_list.split("\n")

    for word in word_list:
        trie.insert_word(word.lower())

    print time.time() - start_time, "seconds"


if __name__ == "__main__":
    main()

Ответы [ 2 ]

0 голосов
/ 02 октября 2011

Совершенно бессмысленно работать над ускорением инициализации Trie, прежде чем вы решите, работает ли ваше средство поиска.

В коде, на который ссылается @unutbu, почемувы представляете, что это дерьмо с {'end':False} и pt['end']=True?

Вот некоторые тестовые данные для вас: 

words_to_insert = ['foo', 'foobar']
queries_expecting_true = words_to_insert
queries_expecting_false = "fo foe foob food foobare".split()

И вот еще одна мысль: вы не даете никаких указаний, что вы хотитечто-то большее, чем способность определять, присутствует ли слово запроса или нет.Если это правильно, вам следует рассмотреть возможность сравнения вашего собственного дерева с встроенным set.Критерии: скорость загрузки (подумайте о том, чтобы сделать это с помощью pickle), скорость запроса и использование памяти.

Если вы хотите получить больше, чем bool, то замените dict на set и повторитепрочитайте этот ответ.

Если вы действительно хотите искать слова во входной строке, то вы можете рассмотреть код, на который ссылается @unutbu, с исправленными ошибками и некоторыми ускорениями в функции find (оценка len(input) только один раз, используйте xrange вместо range (Python 2.x)) и удалите ненужные TERMINAL: False записи: 

TERMINAL = None # Marks the end of a word

def build(words, trie=None): # bugs fixed
    if trie is None:
        trie = {}
    for word in words:
        if not word: continue # bug fixed
        pt = trie # bug fixed
        for ch in word:
            pt = pt.setdefault(ch, {})
        pt[TERMINAL] = True
    return trie

def find(input, trie):
    len_input = len(input)
    results = []
    for i in xrange(len_input):
        pt = trie
        for j in xrange(i, len_input + 1):
            if TERMINAL in pt:
                results.append(input[i:j])
            if j >= len_input or input[j] not in pt:
                break
            pt = pt[input[j]]
    return results

или вы можете посмотреть на быструю реализацию Дэнни Ю алгоритма Aho-Corasick .

0 голосов
/ 02 октября 2011

Существует альтернативная реализация Trie здесь .

Сравните Trie.insert_word с build: 

def build(words,trie={'end':False}):
    '''
    build builds a trie in O(M*L) time, where
        M = len(words)
        L = max(map(len,words))
    '''
    for word in words:
        pt=trie
        for letter in word:
            pt=pt.setdefault(letter, {'end':False})
        pt['end']=True
    return trie

С Trie для каждого letter в word, insert_word, звонки current_node.get_node(letter).Этот метод имеет блоки if и else и должен создавать новый TrieNode всякий раз, когда достигается блок else, а затем в ключ self.data вставляется новая пара ключ-значение.

С build само дерево - просто диктат.Для каждого letter в word существует просто один вызов pt.setdefault(...).dict методы реализованы в C и работают быстрее, чем аналогичный код в Python.

timeit показывает примерно двукратную разницу в скорости (в пользу build): 

def alt_main():
    with open('/usr/share/dict/words', 'r') as dictionary:
        word_list = dictionary.read()
    word_list = word_list.split("\n")
    return build(word_list)


% python -mtimeit -s'import test' 'test.main()'
10 loops, best of 3: 1.16 sec per loop

% python -mtimeit -s'import test' 'test.alt_main()'
10 loops, best of 3: 571 msec per loop
...