Структурата на данни Trie (дърво на префикса)

A Trie, (известен също като дърво на префикс) е специален тип дърво, използвано за съхраняване на асоциативни структури от данни

Trie (произнесено try) получава името си от re trie val - структурата му го прави звезден алгоритъм за съвпадение.

Контекст

Write your own shuffle method to randomly shuffle characters in a string. 
Use the words text file, located at /usr/share/dict/words, and your shuffle method to create an anagram generator that only produces real words.
Given a string as a command line argument, print one of its anagrams. 

Тази седмица бях представен с това предизвикателство в Product Academy на Make School.

Думите в текстовия файл са разделени с нови редове. Неговото форматиране улеснява много поставянето на думите в структурата на данните. Засега ги съхранявам в списък - всеки елемент е една дума от файла.

Един подход към това предизвикателство е:

  • произволно разбъркване на символите в низа
  • след това го проверете спрямо всички думи, които са били в / usr / share / dict / words, за да проверите дали това е истинска дума.

Този подход обаче изисква да проверя дали произволно разбърканите символи в новия низ съответстват на една от 235 887 думи в този файл - това означава 235 887 операции за всеки низ , които искам да проверя като реална дума.

Това беше неприемливо решение за мен. Първо разгледах библиотеки, които вече бяха внедрени, за да проверя дали съществуват думи в даден език, и намерих pyenchant. Първо завърших предизвикателството, използвайки библиотеката, в няколко реда код.

def generateAnagram(string, language="en_US"): languageDict = enchant.Dict(language) numOfPossibleCombinationsForString = math.factorial(len(string)) for i in range(0, numOfPossibleCombinationsForString): wordWithShuffledCharacters = shuffleCharactersOf(string)
 if languageDict.check(wordWithShuffledCharacters): return wordWithShuffledCharacters return "There is no anagram in %s for %s." % (language, string)

Използването на няколко библиотечни функции в моя код беше бързо и лесно решение. Въпреки това не научих много, като намерих библиотека, която да реши проблема вместо мен.

Бях убеден, че библиотеката не използва подхода, който споменах по-рано. Бях любопитен и рових в изходния код - намерих трие.

Трие

Трие съхранява данни на „стъпки“. Всяка стъпка е възел в трие.

Съхраняването на думи е идеален случай за използване на този вид дърво, тъй като има ограничено количество букви, които могат да бъдат събрани, за да се получи низ.

Всяка стъпка или възел в езиково трие ще представлява една буква от дума. Стъпките започват да се разклоняват, когато редът на буквите се отклонява от останалите думи в трие или когато думата завършва.

Създадох трие от директории на моя работен плот, за да визуализирам стъпка надолу през възлите. Това е трие, което съдържа две думи: ябълка и приложение.

Имайте предвид, че краят на думата се обозначава с '$'. Използвам „$“, защото това е уникален знак, който няма да присъства в никоя дума на който и да е език.

Ако трябваше да добавя думата „бленда“ към това трие, щях да обикалям буквите в думата „бленда“, като едновременно с това намалявах възлите в трие. Ако буквата съществува като дъщерна на текущия възел, преминете надолу към нея. Ако буквата не съществува като дъщерна на текущия възел, създайте я и след това се оттеглете в нея. За да визуализирате тези стъпки, използвайки моите директории:

Докато се оттеглям от трие, първите две букви на „отвор“ вече присъстват в трие, така че аз се оттеглям в тези възли.

Третата буква "e" обаче не е дъщерна на "p" възела. Създава се нов възел, който представя буквата „e“, разклонявайки се от останалите думи в трие. Създават се и нови възли за буквите, които следват.

За да се генерира трие от файл с думи, този процес ще се случи за всяка дума, докато се съхраняват всички комбинации за всяка дума.

Може би си мислите: „Почакайте, няма ли да отнеме много време за генериране на трие от този текстов файл с 235 887 думи в него? Какъв е смисълът да циклирам всеки отделен знак във всяка една дума? "

Да, повторяването на всеки символ на всяка дума, за да се генерира трие, отнема известно време. Въпреки това, времето, необходимо за създаване на трие, си заслужава - защото за да проверите дали дадена дума съществува в текстовия файл, са необходими най-много толкова операции, колкото дължината на самата дума . Много по - добре от 235 887 операции, които щеше да предприеме преди.

Написах най-простата версия на трие, използвайки вложени речници. Това не е най-ефективният начин за прилагане на такъв, но е добро упражнение за разбиране на логиката зад трие.

endOfWord = "$"
def generateTrieFromWordsArray(words): root = {} for word in words: currentDict = root for letter in word: currentDict = currentDict.setdefault(letter, {}) currentDict[endOfWord] = endOfWord return root
def isWordPresentInTrie(trie, word): currentDict = trie for letter in word: if letter in currentDict: currentDict = currentDict[letter] else: return False return endOfWord in currentDict

Можете да видите моето решение за генератора на анаграми на моя Github. Откакто проучих този алгоритъм, реших да направя тази публикация в блога една от многото - всяка публикация, обхващаща един алгоритъм или структура на данните. Кодът е достъпен в моето репо за алгоритми и структури от данни - поставете го със звезда, за да бъде актуализиран!

Следващи стъпки

Предлагам да разгледате трие репото на Рей Вендерлих. Въпреки че е написан на Swift, той е ценен източник за обяснения на различни алгоритми.

Подобно на трие (но по-ефективно памет) е дърво на суфикс или радикс. Накратко, вместо да се съхраняват единични символи на всеки възел, краят на думата, нейната наставка се съхранява и пътищата се създават относително.

Радиксът обаче е по-сложен за изпълнение от трие. Предлагам да разгледате radix репото на Ray Wenderlich, ако се интересувате.

Това е първата публикация от моята серия алгоритми и структури от данни. Във всеки пост ще представя проблем, който може да бъде по-добре решен с алгоритъм или структура на данни, за да илюстрира самата структура на алгоритъма / данните.

Поставете моите алгоритми в репо на Github и ме следвайте в Twitter, ако искате да продължите!

Спечелихте ли стойност, като прочетете тази статия? Щракнете тук, за да го споделите в Twitter! Ако искате да виждате подобно съдържание по-често, следвайте ме в Medium и се абонирайте за моя веднъж месечен бюлетин по-долу. Чувствайте се свободни да ми купите и кафе.