Построение суффиксного дерева в иерархической памяти: различия между версиями

Прежде чем рассуждать об алгоритмах и структурах данных на основе иерархической памяти, необходимо ввести модель вычислений, отражающую реальные ситуации, чтобы алгоритмы, успешно проявившие себя на модели, оказались бы столь же успешными на практике. Мы будем рассматривать модель с внешней памятью [ ], ставшей весьма популярной благодаря своей простоте и достаточной точности. Будем считать, что компьютер содержит два уровня памяти: внутреннюю память размера M и дисковую память неограниченного объема, действия над которой производятся в виде записи или чтения блоков данных размера B (называемых страницами дисковой памяти). Эффективность алгоритмов оценивается при помощи подсчета: (б) количества обращений к диску (операций ввода/вывода), (б) внутреннего времени выполнения (времени работы процессора), (в) количества страниц дисковой памяти, занятых структурой данных или использованных алгоритмом в качестве своего рабочего пространства. Это простая модель корректно предполагает, что хороший алгоритм для работы с внешней памятью должен использовать как пространственную, так и временную локальность. Разумеется, понятия «ввод/вывод» и «двухуровневое представление» распространяются на два любые уровня иерархи памяти при правильной установке параметров M и B.