Implementacja drzew trie w języku Python

Drzewo trie jest to drzewo poszukiwań, które w węzłach przechowuje fragmenty kluczy. Wszyscy potomkowie węzła mają wspólny prefix klucza związanego z danym węzłem. Drzewa trie wspierają następujące operacje: wstawianie, usuwanie, wyszukiwanie klucza, wyszukiwanie wszystkich kluczy o podanym prefiksie. W wielu zastosowaniach drzewa trie mogą zastępować tablice hashowalne lub słowniki.W pracy przedstawiono implementację drzew trie w języku Python. Klucze przechowywane w drzewie trie są stringami, a wartości mogą być dowolnymi obiektami pythonowymi. W kodzie drzewo trie występuje w reprezentacji na lewo syn, na prawo brat, która konwertuje drzewo z wieloma potomkami do drzewa binarnego. Jest to rozwiązanie wydajne pamięciowo z wolniejszym wyszukiwaniem potomka danego wezła.W pracy zaimplementowano także skompresowane drzewa trie, zwane drzewami Patricia. Są to drzewa trie o zredukowanym rozmiarze, w których węzły będące jedynymi dziećmi zostają złączone ze swoim rodzicem. Przez to węzły muszą przechowywać fragmenty kluczy o różnej długości, ale ścieżki w drzewie są skrócone, co zmniejsza liczbę koniecznych porównań.Przygotowane moduły posiadają dokumentację zgodną z regułami Pythona i stylem pakietu NumPy. Testy jednostkowe stworzono przy użyciu modułu unittest. Klasy dla drzew trie dziedziczą z abstrakcyjnych klas bazowych dla zmiennych odwzorowań, dlatego kod może zastępować słowniki pythonowe, o ile klucze są stringami.

A trie or a prefix tree is a search tree where the tree nodes store parts of keys. All the descendants of a node have a common prefix of the key associated with that node. Tries support insertion, deletion, searching, finding all keys with common prefix. Tries can replace hash tables or dictionaries in many applications.Python implementation of tries is presented. Keys stored in a trie are strings, values can be any Python objects. Left-child right-sibling representation is used which converts a multi-way trie in a binary tree. This is a memory efficient solution with a slower looking up a node’s children.Compressed tries or Patricia trees are also implemented. They are tries reduced in size because each node that is the only child is merged with its parent. As a result nodes store parts of keys with variable lengths, tree paths are shorter, and the number of necessary comparisons is lower.Prepared modules are documented according to Python rules and the NumPy package style. Unit tests are created using the unittest module. Trie classes inherit from the abstract base class for mutable mappings and that is why the code can replace Python dictionaries if keys are strings.