Сохранить / получить структуру данных

Question

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

ИЗОБРАЖЕНИЕ: Дерево суффиксов для слова BANANAS (в моем сценарии представьте, что дерево в 100000 раз больше).

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

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

---

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

Answer 1

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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])

Answer 5

Как насчет , сохраняющего его в sqlite ?

SQLite:

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

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