Хранить/извлекать структуру данных

Я реализовал дерево суффиксов в Python для полнотекстового поиска, и он работает очень хорошо. Но есть проблема: индексированный текст может быть очень большим, поэтому мы не сможем иметь всю структуру в ОЗУ.

IMAGE: Дерево суффикса для слова BANANAS (в моем сценарии представьте дерево в 100000 раз больше).

Итак, немного об этом узнав, я нашел модуль pickle, отличный модуль Python для "загрузки" и "сброса" объектов из/в файлы, и угадайте, что? Он отлично работает с моей структурой данных.

Итак, сделав длинную историю короче: что было бы лучшей стратегией для хранения и извлечения этой структуры на/с диска? Я имею в виду, что решение может состоять в том, чтобы хранить каждый node в файле и загружать его с диска всякий раз, когда это необходимо, но это не лучше всего думает (слишком много обращений к диску).

Сноска: Хотя я отметил этот вопрос как python, язык программирования не является важной частью вопроса, стратегия хранения/извлечения диска на самом деле является основным.

Ответ 1

Если pickle уже работает для вас, вы можете взглянуть на ZODB, который добавляет некоторые функции поверх pickle. Посмотрев на документацию, я увидел этот абзац, в котором рассматривается вопрос о размерах, который у вас есть:

База данных перемещает объекты свободно между памятью и хранилищем. Если объект не был использован некоторое время, он может быть выпущен и его содержимое, загруженное из хранилища, при следующем использовании.

Ответ 2

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

Используя модуль mmap, вы можете сопоставить файл в адресном пространстве и прочитать его так же, как огромную последовательность байтов. ОС заботится о фактическом чтении из файла и управлении файловыми буферами и всеми подробностями.

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

Преимущество файлов с отображением памяти состоит в том, что они не загружаются сразу в память, а только считываются с диска при необходимости. Я сделал это (в 64-разрядной ОС) с файлом размером 30 ГБ на компьютере с установленной только 4 ГБ ОЗУ и работал нормально.

Ответ 3

Как насчет сохранить его в sqlite?

SQLite:

поддерживает до 2 терабайт данных,
поддерживает SQL-запросы,
- отличная замена для хранения данных в приложении,
может поддерживать ~ 100 тыс. посещений в день (если используется для среднего веб-приложения),

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

Ответ 4

Возможно, вы могли бы объединить cPickle и bsddb базу данных, которая позволит вам хранить ваши маринованные узлы в подобном dictionnary объекте, который будет храниться в файловой системе; таким образом, вы можете загрузить базу данных позже и получить от нужных вам узлов с действительно хорошими характеристиками.

Очень простым способом:

import bsddb
import cPickle

db = bsddb.btopen('/tmp/nodes.db', 'c')
def store_node(node, key, db):
    db[key] = cPickle.dumps(node)

def get_node(key, db):
    return cPickle.loads(db[key])

Ответ 5

Попробуйте вместо суффикса сжатое суффикс.

Основная идея заключается в том, что вместо того, чтобы иметь множество узлов с 1 символом, вы можете скомпилировать их в 1 node из нескольких символов, тем самым сохраняя дополнительные узлы.

Эта ссылка здесь (http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml) говорит, что вы можете преобразовать дерево суффикса 160 МБ в сжатое суффикс-дерево 33 МБ. Довольно выигрыш.

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

Я бы хотел найти неоплачиваемую статью, которая лучше объясняет реализацию. (http://dl.acm.org/citation.cfm?id=1768593)