Реализация дерева Trie (или Prefix Tree)

Question

Мне нужно хранить много строк на карте C++, чтобы сохранить уникальные строки и когда когда-либо повторяется строка, мне просто нужно увеличить счетчик (пара.секунд). Я использовал карту C++ и хорошо подходит для этой ситуации. Поскольку файл, который теперь обрабатывается до 30gg, я пытаюсь сохранить его в файле, а не в памяти.

Я также столкнулся с trie, который быстрее, чем карта в этом случае. Кто-нибудь знает о поддержке файла trie? Я столкнулся с реализацией Trie, аналогичной той, что я ищу, но не кажется, что это ошибка.

Answer 1

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

Если вы не можете сортировать, тогда рассмотрите digesting строки. MD5 может быть излишним для вашей цели. Вы можете что-нибудь придумать. Для миллиардов строк вы можете использовать 8 байтовых дайджестов. Используйте дерево (возможно, BST) дайджеста. Для каждого дайджеста сохраните смещения файла уникальных строк, которые производят этот дайджест.

Когда вы читаете строку, вычислите ее дайджест и посмотрите. Если вы не найдете дайджест, вы знаете, что строка уникальна. Храните его в дереве. Если вы найдете дайджест, проверьте каждую связанную строку для соответствия и обработайте соответственно.

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

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

Answer 2

Как вы собираетесь загружать 30 ГБ в память сразу? И поскольку это то, что вам нужно на основе словаря, я бы подумал, что каждый раз, когда вы вставляете или увеличиваете, вам нужно загрузить весь файл (даже если по частям) для поиска.

Предлагаю использовать базу данных. Это то, за что они предназначены для ...