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

Question

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

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

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

EDIT2

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
РЕШИТЬ !!! На самом деле была проблема с моей реализацией. Я передавал этот огромный контейнер векторной строки в рекурсивных вызовах, что на самом деле было проблемой. Спасибо всем за добрый совет.

0

algorithm c++performance prefix-tree

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

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

0