Структура данных Trie с шаблонами проектирования

В этом посте я собираюсь показать, как вы можете реализовать структуру данных Trie, используя различные принципы проектирования и шаблоны. Эта идея пришла мне в голову после реализации структуры данных Trie и опробования различных алгоритмов.

Конечный результат демонстрирует очень хороший пример применения различных шаблонов и принципов проектирования, а также преимущества их использования.

Полный код доступен на github: Структура данных Trie

Структура данных Trie также называется деревом префиксов, так как основная цель этой структуры данных – обеспечить простой способ поиска строк на основе символов строк, выполняя поиск по одному, в основном, по префиксу.

Эта структура данных имеет множество приложений, таких как автозаполнение и проверка орфографии. Я нахожу очень хорошее объяснение возможных вариантов использования решения leetcode: Решение с древовидным кодом .

Я не собираюсь заострять внимание на реализации самого алгоритма. Вы можете найти реализацию практически в любом месте. В случае, если вы хотите сделать это самостоятельно, я рекомендую Тушара Роя на YouTube: Тушар Рой – Пытался . Я основал свое решение на его объяснении (а не на его решении). Так что вы даже можете увидеть его реализацию, если хотите сравнить.

Код организован в 3 различных пакетах:

пробовать
узел
алгоритм

Интерфейс нитрида

Структура данных trie представлена с помощью интерфейса, Нитрид интерфейс.

Этот интерфейс определяет базовое поведение структуры данных trie:

алгоритм проверки недействительного набора (ITrieAlgorithm triealgorithm);
Я пробую алгоритм getTrieAlgorithm();
Древовидный узел getRoot();
пустое вставляемое слово(строковое слово);
логическое слово удаления (строковое слово);
логическое значение содержит слово (Строковое слово);
логическое значение containsPrefix(строковый префикс);

Эти абстрактные методы должны быть реализованы любым классом, который хочет действовать как Trie.

Первые 3 метода предоставляют средства для составления и отделения Trie от алгоритмов trie.

Обратите внимание на метод “setTrieAlgorithm”, который позволяет изменять алгоритм Trie во время выполнения.

Реализации Trie

Существует 2 различных реализации интерфейса, который я пробовал:

Trie Array: Использует узел на основе массива
Древовидная карта: Использует узел на основе карты

Название реализаций происходит от того факта, что они используют определенный тип TrieNode. Например, реализация массива Trie использует TrieNodeArray в качестве типа узла для структуры данных trie.

Эти узлы используют определенную структуру данных, такую как массив и Карта, для хранения различных символов в каждом узле.

Интерфейс I Tried определяет метод изменения алгоритма trie во время выполнения. Это достигается с помощью composition классов. Реализация trie состоит из алгоритма trie, который отвечает за фактическое выполнение различных операций.

При этом реализации методов, обеспечивающих поведение интерфейса, довольно просты:

 @Override
    public void insertWord(String word) {
        trieAlgorithm.insertWord(this, word);
    }

    @Override
    public boolean deleteWord(String word) {
        return trieAlgorithm.deleteWord(this, word);
    }

    @Override
    public boolean containsWord(String word) {
        return trieAlgorithm.containsWord(this, word);
    }

    @Override
    public boolean containsPrefix(String prefix) {
        return trieAlgorithm.containsPrefix(this, prefix);
    }

Реализации используют делегирование , чтобы передать ответственность за действие составному древовидному алгоритму. Это имеет смысл, поскольку фактическая операция зависит от алгоритма.

Алгоритм trie вводится в конструктор:

    public TrieArray(ITrieAlgorithm trieAlgorithm) {
        setTrieAlgorithm(trieAlgorithm);
        this.root = new TrieNodeArray();
    }

    @Override
    public void setTrieAlgorithm(ITrieAlgorithm trieAlgorithm) {
        this.trieAlgorithm = trieAlgorithm;
    }

Это конструктор массива Trie, и тот, что находится в Treemap, аналогичен.

Конструктор получает алгоритм с типом интерфейса I Trie Algorithm и присваивает полю “trieAlgorithm”, используя соответствующий метод.

Использование интерфейса в качестве типа алгоритма и назначение его в конструкторе позволяет использовать dependency injection , который представляет собой механизм для реализации Принципа инверсии зависимостей . Обратите внимание, что мы также применяем принцип проектирования: “программа для интерфейсов, а не для реализаций” .

Это обеспечивает средства для отделения структуры данных Trie от внутренних деталей алгоритма. Реализации интерфейса Nitride на самом деле не знают или не заботятся о реализациях интерфейса ITrieAlgorithm. Все, о чем заботится Trie, – это поведение этих реализаций.

Вы должны попытаться инкапсулировать и группировать вещи в соответствии с осью изменений. Вы группируете вещи, которые меняются по одним и тем же причинам и с одинаковой скоростью. В этом случае структура данных Trie является очень стабильным компонентом, и ее интерфейс вместе с реализациями вряд ли будет меняться так часто. С другой стороны, у нас есть различные реализации алгоритмов, которые могут довольно часто меняться. Например, вы решаете изменить некоторые внутренние детали алгоритма, такие как рекурсивные вызовы или использование некоторой внутренней структуры данных в алгоритме. Эти изменения вообще не должны влиять на структуру данных Trie.

Шаблон стратегии Это определение взято из книги Шаблоны проектирования Head First (отличная книга!):

” Шаблон стратегии определяет семейство алгоритмов, инкапсулирует каждый из них и делает их взаимозаменяемыми. Стратегия позволяет алгоритму изменяться независимо от клиенты, которые им пользуются.”

В этом случае мы определяем семейство алгоритмов с интерфейсом алгоритма I Trie.

Различные реализации: Итеративная, рекурсивная, Рекурсивная 2, могут использоваться взаимозаменяемо. Это здорово! Мы инкапсулировали части, которые изменились, в определенный интерфейс. Теперь клиент или тот, кто использует структуру данных Trie, не зависит от какой-либо конкретной реализации. Если вы придумаете новый лучший способ реализации алгоритма, вам просто нужно реализовать интерфейс, и все. Вы можете заменить метод сеттера, и ваш новый алгоритм будет использоваться проверенным. Не нужно абсолютно ничего менять в классе Trie!

Интерфейс алгоритма I Trie

Этот интерфейс определяет общее поведение, которым должен обладать любой алгоритм trie:

public interface ITrieAlgorithm {

    void insertWord(ITrie trie, String word);

    boolean deleteWord(ITrie trie, String word);

    boolean containsWord(ITrie trie, String word);

    boolean containsPrefix(ITrie trie, String prefix);
}

Важная вещь, на которую следует обратить внимание в сигнатуре метода, – это аргумент ITrie. Алгоритмам не нужно знать или заботиться о фактических деталях реализации структуры данных Trie, все, что их волнует, – это то, что они реализуют интерфейс ITrie, и, более конкретно, что они обеспечивают реализацию метода getRoot , как мы увидим в следующем разделе.

Реализации алгоритма I Trie

Существуют 3 различные реализации нитридного интерфейса:

Древовидный итеративный алгоритм
Истинный Рекурсивный Алгоритм
Истинный Рекурсивный Алгоритм 2

Названия являются самоописательными. У нас есть 1 алгоритм, который использует итеративный подход с использованием циклов. А другие используют рекурсивный подход.

Давайте рассмотрим реализацию метода “insertWord”:

    /**
     * Insert a word in the trie
     *
     * @param trie The Trie where the word will be inserted
     * @param word The word to insert
     */
    @Override
    public void insertWord(ITrie trie, String word) {
        insertWord(trie.getRoot(), word);
    }

    /**
     * Helper method that inserts the word in the Trie.
     * This algorithm sets the "isEndOfWord" flag to the trieNode that the last character points.
     *
     * @param trieNode The trieNode to insert the character
     * @param word     The word to insert
     */
    private void insertWord(ITrieNode trieNode, String word) {
        char currentChar;
        for (int i = 0; i < word.length(); i++) {
            currentChar = word.charAt(i);
            if (!trieNode.containsCharacter(currentChar)) {
                trieNode.addCharacter(currentChar);
            }
            trieNode = trieNode.getTrieNodeForChar(currentChar);
        }
        trieNode.setEndOfWord(true);
    }

Метод вставить слово принимает trie в качестве аргумента с типом нитрида. Алгоритм не заботится о внутренней реализации, он просто получает корневой узел с помощью метода getRoot и продолжает операцию.

Теперь взгляните на вспомогательный метод. Он получает узел с типом интерфейса Treenode . Опять же, алгоритму на самом деле все равно, как на самом деле реализованы узлы. Независимо от того, использует ли он массив или карту, алгоритм один и тот же. Это очень важная деталь, потому что алгоритм полностью отделен от реализаций Дерева и узлов. Он может работать с любой реализацией. Это означает, что мы можем повторно использовать один и тот же алгоритм для разных экземпляров реализации Trie.

Инкапсулируйте то, что меняется: Фактическая реализация алгоритма.
Предпочтение композиции перед наследованием: Структура данных Trie использует “составленный” алгоритм, который передается в конструкторе.
Программа для интерфейсов, а не для реализаций: I Trie, Trienode и ITrieAlgorithm – это интерфейсы, которые используются в разных реализациях. Никаких ссылок или зависимостей от каких-либо конкретных реализаций. Это означает, что различные компоненты разъединены и могут быть изменены независимо.
Принцип открытия/закрытия: Всякий раз, когда в вашем алгоритме происходят изменения, структура данных Trie на самом деле не имеет значения, поскольку это не зависит от реализации, вы можете изменить или создать совершенно новый алгоритм, и вам не придется ничего менять в классе структуры данных Trie! То же самое относится и к обратному пути. Вы можете изменить структуру данных в Trie, и алгоритм все равно будет работать на вашей новой шине. Очевидно, что все это возможно через интерфейсы, определенные для каждого класса. До тех пор, пока реализация соответствует этим контрактам, все должно быть хорошо.
Зависеть от абстракций. Не зависят от конкретных классов: Мы применили принцип инверсии зависимостей, поскольку мы инвертировали зависимость исходного кода от Trie к конкретным реализациям алгоритма. Теперь и Trie, и Алгоритмы зависят от абстракций. Племя не знает о какой-либо конкретной реализации Алгоритма, оно просто использует интерфейс. То же самое относится и к Алгоритмам. Любая реализация алгоритма не зависит от какой-либо конкретной реализации Trie/TrieNode, она зависит только от абстракций, ITRIE и ITrieNode.

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

Оригинал: “https://dev.to/marcelos/trie-data-structure-with-design-patterns-4cbn”

Интерфейс нитрида

Реализации Trie

Интерфейс алгоритма I Trie

Реализации алгоритма I Trie

Читайте ещё по теме: