Рубрики

Стойкий Трие | Комплект 1 (Введение)

Необходимое условие:

  1. Trie
  2. Постоянство в структуре данных

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

Наша цель состоит в том, чтобы применить постоянство в Trie, а также обеспечить, чтобы он не занимал больше, чем стандартный поиск по Trie, т.е. O (length_of_key) . Мы также проанализируем дополнительную сложность пространства, которую вызывает постоянство по сравнению со стандартной пространственной сложностью дерева.

Давайте подумаем с точки зрения версий, то есть для каждого изменения / вставки в нашем Trie мы создадим новую версию этого.
Мы будем считать нашу первоначальную версию версией 0. Теперь, когда мы делаем любую вставку в дереве, мы создадим для него новую версию и аналогичным образом отследим запись для всех версий.

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

Давайте использовать тот факт, что для каждой новой вставки в дереве будут посещаться / изменяться ровно X (length_of_key) узлы. Таким образом, наша новая версия будет содержать только эти X новых узлов, а остальные узлы будут такими же, как и в предыдущей версии. Таким образом, совершенно очевидно, что для каждой новой версии нам нужно только создать эти X новых узлов, тогда как остальные узлы Triee могут использоваться совместно с предыдущей версией.

Рассмотрите ниже рисунок для лучшей визуализации:

Теперь возникает вопрос: как отслеживать все версии?
Нам нужно только отслеживать первый корневой узел для всех версий, и это будет служить для отслеживания всех вновь созданных узлов в разных версиях, поскольку корневой узел дает нам точку входа для этой конкретной версии. Для этой цели мы можем поддерживать массив указателей на корневой узел дерева для всех версий.

Let’s consider the below scenario and see how we can use Persistent Trie to solve it !
Given an array of strings and we need to determine if a string exists in some
range [l, r] in the array. To have an analogy, consider the array to be a
list of words in a dictionary at ith page(i is the index of the array) and
we need to determine whether a given word X exists in the page range [l, r]?

Ниже приведена реализация C ++ для вышеуказанной проблемы:

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Различное количество символов в ключе

const int sz = 26;

  
// Постоянная структура узла Trie

struct PersistentTrie {

  

    // Сохраняет все дочерние узлы, где ih потомки обозначают

    // i-й алфавитный символ

    vector<PersistentTrie*> children;

  

    // Отмечает окончание ключа

    bool keyEnd = false;

  

    // Конструктор 1

    PersistentTrie(bool keyEnd = false)

    {

        this->keyEnd = keyEnd;

    }

  

    // Конструктор 2

    PersistentTrie(vector<PersistentTrie*>& children, bool keyEnd = false)

    {

        this->children = children;

        this->keyEnd = keyEnd;

    }

  

    // обнаруживает наличие ключа в три

    bool findKey(string& key, int len);

  

    // Вставляет ключ в Trie

    // возвращает новый узел после вставки

    PersistentTrie* insert(string& key, int len);

};

  
// фиктивный узел PersistentTrie
PersistentTrie* dummy;

  
// Инициализируем манекен для легкой реализации

void init()

{

    dummy = new PersistentTrie(true);

  

    // Все дети манекена как манекена

    vector<PersistentTrie*> children(sz, dummy);

    dummy->children = children;

}

  
// Вставляет ключ в текущий файл
// возвращает вновь созданный узел trie после вставки

PersistentTrie* PersistentTrie::insert(string& key, int len)

{

  

    // Если достигнут конец ключевой строки

    if (len == key.length()) {

  

        // Создаем новый узел с текущим узлом

        // помечены как keyEnd

        return new PersistentTrie((*this).children, true);

    }

  

    // Извлекаем текущие дочерние узлы

    vector<PersistentTrie*> new_version_PersistentTrie = (*this).children;

  

    // Вставляем в ключ [len] дочерний и

    // обновляем новый дочерний узел

    PersistentTrie* tmpNode = new_version_PersistentTrie[key[len] - 'a'];

    new_version_PersistentTrie[key[len] - 'a'] = tmpNode->insert(key, len + 1);

  

    // Возвращаем новый узел с измененным ключом [len] дочерний узел

    return new PersistentTrie(new_version_PersistentTrie);

}

  
// Возвращает наличие ключа в текущем трие

bool PersistentTrie::findKey(string& key, int len)

{

    // Если достигнут конец ключа

    if (key.length() == len)

  

        // Возвращаем, если это keyEnd в trie

        return this->keyEnd;

  

    // Если мы не можем найти ключ [len] child в trie

    // мы говорим, что ключ не существует в дереве

    if (this->children[key[len] - 'a'] == dummy)

        return false;

  

    // Рекурсивно ищем остаток

    // длина ключа в дочернем [key] trie

    return this->children[key[len] - 'a']->findKey(key, len + 1);

}

  
// обход dfs по текущему файлу
// печатает все ключи, присутствующие в текущем дереве

void printAllKeysInTrie(PersistentTrie* root, string& s)

{

    int flag = 0;

    for (int i = 0; i < sz; i++) {

        if (root->children[i] != dummy) {

            flag = 1;

            s.push_back('a' + i);

            printAllKeysInTrie(root->children[i], s);

            s.pop_back();

        }

    }

    if (flag == 0 and s.length() > 0)

        cout << s << endl;

}

  
// Код драйвера

int main(int argc, char const* argv[])

{

  

    // Инициализируем PersistentTrie

    init();

  

    // Клавиши ввода

    vector<string> keys({ "goku", "gohan", "goten", "gogeta" });

  

    // Кешируем для хранения корни записи trie после каждой вставки

    PersistentTrie* root[keys.size()];

  

    // Помечаем первый корень как фиктивный

    root[0] = dummy;

  

    // Вставляем все ключи

    for (int i = 1; i <= keys.size(); i++) {

  

        // Кешируем новый рут для i-й версии trie

        root[i] = root[i - 1]->insert(keys[i - 1], 0);

    }

  

    int idx = 3;

    cout << "All keys in trie after version - " << idx << endl;

    string key = "";

    printAllKeysInTrie(root[idx], key);

  

    string queryString = "goku";

    int l = 2, r = 3;

    cout << "range : "

         << "[" << l << ", " << r << "]" << endl;

    if (root[r]->findKey(queryString, 0) and !root[l - 1]->findKey(queryString, 0))

        cout << queryString << " - exists in above range" << endl;

    else

        cout << queryString << " - does not exist in above range" << endl;

  

    queryString = "goten";

    l = 2, r = 4;

    cout << "range : "

         << "[" << l << ", " << r << "]" << endl;

    if (root[r]->findKey(queryString, 0) and !root[l - 1]->findKey(queryString, 0))

        cout << queryString << " - exists in above range" << endl;

    else

        cout << queryString << " - does not exist in above range" << endl;

  

    return 0;

}

Выход:

All keys in trie after version - 3
gohan
goku
goten
range : [2, 3]
goku - does not exist in above range
range : [2, 4]
goten - exists in above range

Сложность времени: как обсуждалось выше, мы будем посещать все X (длина ключа) числа узлов в дереве при вставке; Итак, мы будем посещать число состояний X и в каждом состоянии мы будем выполнять объем работы O (sz), сравнивая дочерние элементы sz предыдущей версии с текущей версией для вновь созданных узлов trie. Следовательно, Сложность Времени вставки становится O (length_of_key * sz) . Но поиск по-прежнему является линейным по длине ключа, который нужно искать, и, следовательно, временная сложность поиска ключа по-прежнему равна O (length_of_key), так же, как и у стандартного дерева.

Сложность пространства: Очевидно, что постоянство в структурах данных сопровождается обменом пространства, и мы будем использовать больше памяти для поддержки различных версий дерева. Теперь давайте представим наихудший случай — для вставки мы создаем узлы O (length_of_key), и каждому вновь созданному узлу потребуется место O (sz) для хранения его дочерних элементов. Следовательно, сложность пространства для вставки вышеуказанной реализации составляет O (length_of_key * sz).

Рекомендуемые посты:

Стойкий Трие | Комплект 1 (Введение)

0.00 (0%) 0 votes