Проблема с производительностью при получении всех слов с общим префиксом в дереве префиксов

У меня есть дерево префиксов для хранения огромной коллекции слов. Прямо сейчас, если я хочу найти все слова с общим префиксом, скажем, «а», я сначала извлекаю первый узел, содержащий а, а затем исчерпывающе ищу в глубине в дочерних узлах первого узла. Хотя эта идея выглядит наивной и простой, на самом деле она жалко медленная, если возможное количество слов с общим префиксом ОЧЕНЬ ВЫСОКОЕ (> 20K). Есть ли другой способ эффективно получить все слова, начинающиеся с общего префикса? Или я должен принять какую-то другую структуру данных? Заранее благодарю вас.

EDIT1 В основном я создаю полное слово, посещая каждый узел и постепенно добавляя символы. Все слова впоследствии сохраняются в векторном контейнере. И да, у меня рекурсивная реализация.

ИЗМЕНИТЬ2

vector<int> getNonEmptyEdgeIndices(Node* parent) {
    vector<int> indices;
    for(int i=0; i<EDGE; i++) {
        if (parent->edges[i] != NULL) {
            indices.push_back(i);
        }
    }
    return indices; 
}

vector<string> getSubsequentStrings(vector<string> wordsStartingWith, Node* node, string prefix) {
    vector<int> indices = getNonEmptyEdgeIndices(node);

    // push the word to the container if node is a leaf 
    if (indices.empty()) {
        wordsStartingWith.push_back(prefix);
        return wordsStartingWith;
    }

    // if frequency is set in node, push the word but still continue recursion
    if (node->frequency != 0) {
        wordsStartingWith.push_back(prefix);
    }

    // look all the children of the node
    for(unsigned int i=0; i<indices.size(); i++) {
        string newPrefix = prefix + getNodeChar(indices[i]);
        Node* child = node->edges[indices[i]];

        // recursively get the prefix for all children
        wordsStartingWith = getSubsequentStrings(wordsStartingWith, child, newPrefix);  
    }

    return wordsStartingWith;
}

vector<string> Trie::getWordsStartingWith(string prefix) {
    vector<string> wordsStartingWith;
    Node* lastNode = getLastNode(prefix);

    if (lastNode != NULL) {
        wordsStartingWith = getSubsequentStrings(wordsStartingWith, lastNode, prefix);
    }
    return wordsStartingWith;
}

РЕДАКТИРОВАНИЕ 3 РЕШЕНО!!! На самом деле была проблема с моей реализацией. Я передавал этот огромный контейнер векторных строк в рекурсивных вызовах, что на самом деле было проблемой. Спасибо всем за ваши добрые советы.


c++ performance algorithm prefix-tree
person consumer    schedule 23.12.2013    source источник
comment
Некоторые детали реализации были бы хороши. Префиксные деревья должны быть хороши в этом, они могут делать это в линейном пространстве и времени. Потенциально ваша проблема заключается в том, что вы копируете все строки из дерева для создания массива, прежде чем что-либо с ним делать? Возможно, вместо этого вы захотите написать итератор, который позволит вам делать то, что вы хотите, с каждым элементом, не копируя их все?   -  person amnn    schedule 24.12.2013
comment
Можете ли вы поделиться кодом, который вы пробовали? Это может быть код, а не структура данных, которую можно улучшить.   -  person Glenn Teitelbaum    schedule 24.12.2013
comment
Хм, @asQuirrel: ты совершенно прав. Я строю строку, посещая каждое ребро. Вероятно, я должен написать итератор. Я реализую эту часть и вернусь.   -  person consumer    schedule 24.12.2013
comment
@GlennTeitelbaum Меня действительно интересует, является ли исчерпывающий поиск в первую очередь хорошим выбором или нет.   -  person consumer    schedule 24.12.2013
comment
Исчерпывающий поиск в глубину является предпочтительным методом. Как уже говорили другие, дерево префиксов должно делать это очень быстро. Конечно, повторение узлов для 20 000 слов должно быть невероятно быстрым. Построение строк может быть довольно медленным, в зависимости от того, как вы это делаете. Не видя вашего кода, трудно сказать, в чем может быть проблема.   -  person Jim Mischel    schedule 24.12.2013
comment
Ну, чтобы не путать просто со словами, я добавил частичную реализацию. Спасибо.   -  person consumer    schedule 25.12.2013
comment
Хорошо, я только что переставил и запустил код, оказалось, что параметр vector‹string›wordStartingWith был узким местом в моем коде (теперь это выглядит очевидно: D).   -  person consumer    schedule 25.12.2013

Ответы (1)


arrow_upward
0
arrow_downward

На самом деле TRIE+DFT уже является достаточно хорошим решением для вашего случая. Его временная сложность равна O(M+B^M), где M — максимальная длина слова, а B — постоянное количество возможных букв (обычно B=26). Хотя это экспоненциально, но на практике это может быть намного быстрее, чем вы думаете, потому что дерево TRIE очень разреженное, а M — небольшое число.

Более простое (не гарантированно лучшее) решение — сортировать все слова в массив. Затем вы можете получить то, что хотите, путем бинарного поиска в массиве первого и последнего слова, имеющего целевой префикс, точно так же, как вы используете словарь английского языка. Сортировка занимает O(NlogN), а поиск занимает O(MlogN), где N — количество слов. Это полиномиальное.

Если вы действительно Need for Speed, то вы почти всегда можете заплатить место в памяти для обмена. В этом случае вы могли бы связать каждое слово со всеми его префиксными узлами с помощью указателей во время построения дерева TRIE. Тогда временная сложность уменьшится до O(M+N), что очень быстро. Но, с другой стороны, это потребует космической сложности O(NM). Предположим, что у вас есть миллион слов с 5 буквами в среднем, вы потратите около 150 КБ памяти на указатели.

person Skyler    schedule 24.12.2013