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

A Trie(також відоме як дерево префіксів) - це особливий тип дерева, що використовується для зберігання асоціативних структур даних

Трі (вимовляється спроба) отримує свою назву від 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. 

Цього тижня мені поставили цей виклик в Make School's Product Academy.

Слова в текстовому файлі розділені новими рядками. Його форматування значно полегшує введення слів у структуру даних. Наразі я зберігаю їх у списку - кожен елемент - це одне слово з файлу.

Одним із підходів до цього виклику є:

  • випадковим чином перемішати символи в рядку
  • потім перевірте його зі всіма словами, які були в / 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". Створюється новий вузол, який представляє букву "е", що відгалужується від інших слів у трие. Створюються також нові вузли для наступних літер.

Щоб згенерувати триє з файлу слів, цей процес відбуватиметься для кожного слова, поки не будуть збережені всі комбінації для кожного слова.

Ви можете подумати: «Зачекайте, чи не буде тривати дуже довго, щоб згенерувати тріє з цього текстового файлу, в якому 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 Ренда Вендерліха, якщо вам цікаво.

Це перша публікація мого ряду алгоритмів та структур даних. У кожному дописі я викладу проблему, яку можна краще вирішити за допомогою алгоритму або структури даних, щоб проілюструвати саму структуру алгоритму / даних.

Позначте моє алгоритми репо на Github і підпишіться на мене у Twitter, якщо хочете продовжити!

Чи здобули ви цінність, прочитавши цю статтю? Натисніть тут, щоб поділитися ним у Twitter! Якщо ви хочете частіше бачити подібний вміст, слідкуйте за мною на Medium і підписуйтесь на мій щомісячний бюлетень нижче. Не соромтеся купувати мені каву теж.