#data-structures #heap-memory #trie
#структуры данных #куча-память #попробуйте
Вопрос:
Мне нужно прочитать файл объемом 10 ГБ и найти наиболее часто встречающиеся фразы в файле. Я считываю файл по частям, используя сканер, и сохраняю фразы в трехуровневой структуре данных. Я буду искать фразы позже, чтобы обновить их количество, и, следовательно, использовал структуру данных trie для эффективного поиска. Я реализовал Trie с использованием Hashmap в java, как показано ниже.
class TrieNode {
char data;
Map<Character, TrieNode> children = new HashMap<>();
boolean isLeafNode;
int positionMinHeap = -1;
int frequency;
TrieNode() {
}
TrieNode(char data) {
this.data = data;
}
}
Но это решение занимает много места в куче. И если бы все фразы в файле были разными, Trie занял бы огромное количество места.Есть ли какой-либо другой способ, которым я могу реализовать Trie эффективным способом для памяти?
Комментарии:
1. Я бы использовал алгоритм сводки потока top-k. Например, используйте CountMinSketch для отслеживания частот, сохраняя только k самых больших в памяти и заменяя по мере обнаружения более высоких частот.
2. Как насчет реализации дерева оснований? en.wikipedia.org/wiki/Radix_tree
Ответ №1:
Если вы не боитесь немного привязок C и JNI, у вас будет больше вариантов для оптимизированных решений. Я бы посоветовал попробовать marisa-trie:
https://github.com/s-yata/marisa-trie/tree/master
Некоторое время назад я попробовал несколько других библиотек (к сожалению, я сейчас не помню другие), и для моего набора данных у marisa-trie был очень хороший баланс между производительностью и использованием памяти по сравнению с другими библиотеками C trie.
Вы также могли бы извлечь выгоду из интерфейса ввода-вывода с отображением в память, когда ваши данные увеличиваются (жертвуя некоторой производительностью, конечно).