Эффективная работа с большими текстовыми файлами
Эффективная работа с большими текстовыми файлами Самым популярным способом хранения информации на внешних запоминающих устройствах является организация ее в файлы. Файл представляет собой совокупность (набор) данных, объединенных по некоторому признаку под одним именем. Внутренняя структура файла зависит от целей, которые ставятся перед выбранным способом хранения информации, и называется форматом файла. На сегодняшний день существует огромное количество форматов фалов, одни из которых стали стандартными (как, например, EXE, DBF, MDB, GIF, DOC и множество других), другие разработаны для решения специфических задач хранения и организации доступа к информации.
Однако одним из самых популярных традиционно остается текстовый формат файлов. Его характерной чертой является организация хранимой информации в строки, которые отделяются друг от друга специальными символами (или последовательностями символов) — разделителями строк. В текстовых файлах хранятся описания и исходные тексты программ, в них, как правило, записываются протоколы работы оборудования (LOG-файлы или журнальные файлы), широко распространены файлы, хранящие программные настройки (INI-файлы или файлы инициализации). Кроме того, многие бухгалтерские и банковские программы позволяют выводить (экспортировать) отчеты и другие сведения в текстовые файлы, а также читать (импортировать) данные из этих файлов.
Заметим, что предложенное выше определение текстовых файлов подразумевает более широкий круг файлов, нежели содержащих удобочитаемые тексты на естественных или алгоритмических языках. Формат текстовых файлов при подходящем выборе разделителя строк позволяет организовать хранение записей, характеризующихся нерегулярным размером и содержащих любые данные, с более экономным расходованием дискового пространства, нежели в файлах, формат которых подразумевает фиксированный размер записей (например, DBF).
В связи с такой распространенностью текстовых файлов, для работы с ними написано множество программ, которые позволяют просматривать и исправлять их содержимое, а также преобразовывать их в другие форматы. Однако часто возникают задачи анализа информации, которые требуют реализации специфических алгоритмов обработки текстовых данных. Если поставленная задача требует организовать произвольный доступ к строкам, хранящимся в текстовом файле (как, например, при реализации алгоритма быстрого поиска в упорядоченном наборе строк), разработчик может оказаться в затруднительном положении.
В силу своей специфики (строки, как правило, имеют различную длину) текстовые файлы допускают лишь последовательный доступ к хранимой информации. Таким образом, невозможно вычислить позицию начала N-й строки без того, чтобы не перебрать последовательно N-1 строк с самого начала файла. Очевидно, что эффективность такого подхода крайне низка, что и ограничивает его практическое использование.
Одним из путей решения возникшей проблемы является перенос содержимого текстового файла в оперативную память. Однако, этот подход неприемлем в случае больших текстовых файлов (состоящих из нескольких десятков тысяч строк) из-за нерационального использования оперативной памяти (содержимое большинства строк, скорее всего, неинтересно).
Можно отказаться от запоминания в памяти содержимого строк, а хранить только позиции их начала в файле. Это уже намного лучше, так как память расходуется только на индексную таблицу, которая содержит порядковый номер строки и соответствующее ей смещение относительно начала файла. Таким образом, решается проблема произвольного доступа к строке: при необходимости содержимое требуемой строки можно быстро прочитать из файла. И все же зачастую нет необходимости знать позиции начала каждой строки. Достаточно разбить файл на несколько примерно одинаковых участков, и хранить сведения о первых строках каждого участка в глобальной индексной таблице (ГИТ), отсортированной по возрастанию номеров строк. Эта таблица позволит по номеру нужной строки определить, к какому участку она относится, и, быстро найдя начало участка по его смещению в файле, перебором найти требуемую строку.
Глобальная индексная таблица
Как мы видим, перебор при указанной схеме все же имеет место. Однако он не будет оказывать существенной роли на быстродействие программы (естественно, при разумном выборе размера ГИТ), так как современные устройства хранения информации и операционные системы реализуют кэширование с упреждающим чтением данных, и, скорее всего, область последовательного поиска будет ограничена зоной кэширования.
Как же построить таблицу ГИТ? Можно, конечно, один раз просмотреть весь файл единственно с целью ее построения. Однако, возможно, что для всего файла строить ГИТ нет необходимости, если отсутствует потребность в рассмотрении последних строк текстового файла. Можно сэкономить много времени, если осуществлять формирование ГИТ одновременно с обработкой файла.
Это выглядит следующим образом. Пусть наша таблица характеризуется четырьмя параметрами:
— dMin — минимальное расстояние между элементами таблицы;
— iMin — номер элемента таблицы, соответствующего dMin;
— pLast — позиция начала последней зарегистрированной строки.
Допустим, нам требуется получить доступ к содержимому строки с порядковым номером k (kі(0). Сначала найдем последнюю запись i ГИТ, номер строки ni в которой меньше или равен k. После этого установим файловый указатель на позицию pi и последовательно просмотрим (k-i) строки, определяя для каждой необходимость ее регистрирования в ГИТ, как описано ниже. Таким образом, начало k-й строки будет найдено.
Теперь посмотрим, нужно ли регистрировать сведения о k-й строке в ГИТ. Здесь возможны два варианта:
1. Если pk Ј pLast, значит, этот диапазон уже рассматривался ранее и k-я строка либо зарегистрирована в ГИТ, либо не зарегистрирована.
2. Если pk> pLast (то есть k-я строка лежит за пределами зарегистрированных ранее строк), то необходимо оценить полезность информации, которую может принести регистрация k-й строки.
Если в таблице еще есть незаполненные элементы, то, очевидно, вреда от дополнительных сведений не будет. Если же таблица заполнена, нужно определить, является ли информация о k-й строке более важной, чем какая-нибудь другая. Критерием в данном случае выступает равномерность разбиения текстового файла на участки, о которой говорилось выше.
Вычислим расстояние от последней зарегистрированной до k-й строки:
d = pk – pLast.
Если d> dMin, значит, регистрация k-й строки позволит более эффективно выполнять поиск на участке, который больше того, что обеспечивает элемент ГИТ, соответствующий dMin, то есть элемент iMin. Значит, имеет смысл занести в запись iMin информацию о k-й строке и переупорядочить таблицу. После внесения изменений в таблицу ГИТ необходимо заново определить ее параметры iMin, dMin и pLast.
Таким образом, построение и модификация таблицы глобальных индексов будет осуществляться одновременно с ее использованием для обеспечения быстрого произвольного доступа к строкам текстового файла.
Следует отметить, что расстояние между элементами таблицы ГИТ принимается равным разности позиций начала строк, а не их порядковых номеров. Это существенный момент, так как несколько коротких строк могут занимать меньше места, чем одна большая строка. Именно поэтому после внесения изменений в ГИТ для определения dMin и iMin необходимо попарно просмотреть все элементы таблицы.
Очевидно, что начало файла всегда соответствует строке с номером "ноль" с нулевым смещением. Поэтому решение о целесообразности хранения соответствующей записи в ГИТ следует принимать исходя из удобства практической реализации алгоритма произвольного доступа к текстовому файлу.
В заключение несколько слов о приведенном методе. При его описании использовалось много интуитивных вероятностных понятий ("скорее всего", "зачастую", "возможно") без каких-либо математических выкладок. Дело в том, что определить потребность в использовании таблицы ГИТ и ее конкретные параметры может только разработчик программы на основании анализа специфики обрабатываемых текстовых файлов, характеристик устройств хранения информации и настроек операционной системы. В этой статье лишь предлагается идея, реализация которой способна в ряде случаев помочь найти компромисс между скоростью прямого доступа к строкам текстового файла и затратами оперативной памяти на хранение вспомогательной информации.
Игорь Орещенков
(c) компьютерная газета
Однако одним из самых популярных традиционно остается текстовый формат файлов. Его характерной чертой является организация хранимой информации в строки, которые отделяются друг от друга специальными символами (или последовательностями символов) — разделителями строк. В текстовых файлах хранятся описания и исходные тексты программ, в них, как правило, записываются протоколы работы оборудования (LOG-файлы или журнальные файлы), широко распространены файлы, хранящие программные настройки (INI-файлы или файлы инициализации). Кроме того, многие бухгалтерские и банковские программы позволяют выводить (экспортировать) отчеты и другие сведения в текстовые файлы, а также читать (импортировать) данные из этих файлов.
Заметим, что предложенное выше определение текстовых файлов подразумевает более широкий круг файлов, нежели содержащих удобочитаемые тексты на естественных или алгоритмических языках. Формат текстовых файлов при подходящем выборе разделителя строк позволяет организовать хранение записей, характеризующихся нерегулярным размером и содержащих любые данные, с более экономным расходованием дискового пространства, нежели в файлах, формат которых подразумевает фиксированный размер записей (например, DBF).
В связи с такой распространенностью текстовых файлов, для работы с ними написано множество программ, которые позволяют просматривать и исправлять их содержимое, а также преобразовывать их в другие форматы. Однако часто возникают задачи анализа информации, которые требуют реализации специфических алгоритмов обработки текстовых данных. Если поставленная задача требует организовать произвольный доступ к строкам, хранящимся в текстовом файле (как, например, при реализации алгоритма быстрого поиска в упорядоченном наборе строк), разработчик может оказаться в затруднительном положении.
В силу своей специфики (строки, как правило, имеют различную длину) текстовые файлы допускают лишь последовательный доступ к хранимой информации. Таким образом, невозможно вычислить позицию начала N-й строки без того, чтобы не перебрать последовательно N-1 строк с самого начала файла. Очевидно, что эффективность такого подхода крайне низка, что и ограничивает его практическое использование.
Одним из путей решения возникшей проблемы является перенос содержимого текстового файла в оперативную память. Однако, этот подход неприемлем в случае больших текстовых файлов (состоящих из нескольких десятков тысяч строк) из-за нерационального использования оперативной памяти (содержимое большинства строк, скорее всего, неинтересно).
Можно отказаться от запоминания в памяти содержимого строк, а хранить только позиции их начала в файле. Это уже намного лучше, так как память расходуется только на индексную таблицу, которая содержит порядковый номер строки и соответствующее ей смещение относительно начала файла. Таким образом, решается проблема произвольного доступа к строке: при необходимости содержимое требуемой строки можно быстро прочитать из файла. И все же зачастую нет необходимости знать позиции начала каждой строки. Достаточно разбить файл на несколько примерно одинаковых участков, и хранить сведения о первых строках каждого участка в глобальной индексной таблице (ГИТ), отсортированной по возрастанию номеров строк. Эта таблица позволит по номеру нужной строки определить, к какому участку она относится, и, быстро найдя начало участка по его смещению в файле, перебором найти требуемую строку.
Глобальная индексная таблица
| № п/п | Номер строки | Позиция в файле |
| 0 | 0 | 0 |
| 1 | n1 | p1 |
| 2 | n2 | p2 |
| ... | ... | ... |
| N | nN | pN |
Как же построить таблицу ГИТ? Можно, конечно, один раз просмотреть весь файл единственно с целью ее построения. Однако, возможно, что для всего файла строить ГИТ нет необходимости, если отсутствует потребность в рассмотрении последних строк текстового файла. Можно сэкономить много времени, если осуществлять формирование ГИТ одновременно с обработкой файла.
Это выглядит следующим образом. Пусть наша таблица характеризуется четырьмя параметрами:
— dMin — минимальное расстояние между элементами таблицы;
— iMin — номер элемента таблицы, соответствующего dMin;
— pLast — позиция начала последней зарегистрированной строки.
Допустим, нам требуется получить доступ к содержимому строки с порядковым номером k (kі(0). Сначала найдем последнюю запись i ГИТ, номер строки ni в которой меньше или равен k. После этого установим файловый указатель на позицию pi и последовательно просмотрим (k-i) строки, определяя для каждой необходимость ее регистрирования в ГИТ, как описано ниже. Таким образом, начало k-й строки будет найдено.
Теперь посмотрим, нужно ли регистрировать сведения о k-й строке в ГИТ. Здесь возможны два варианта:
1. Если pk Ј pLast, значит, этот диапазон уже рассматривался ранее и k-я строка либо зарегистрирована в ГИТ, либо не зарегистрирована.
2. Если pk> pLast (то есть k-я строка лежит за пределами зарегистрированных ранее строк), то необходимо оценить полезность информации, которую может принести регистрация k-й строки.
Если в таблице еще есть незаполненные элементы, то, очевидно, вреда от дополнительных сведений не будет. Если же таблица заполнена, нужно определить, является ли информация о k-й строке более важной, чем какая-нибудь другая. Критерием в данном случае выступает равномерность разбиения текстового файла на участки, о которой говорилось выше.
Вычислим расстояние от последней зарегистрированной до k-й строки:
d = pk – pLast.
Если d> dMin, значит, регистрация k-й строки позволит более эффективно выполнять поиск на участке, который больше того, что обеспечивает элемент ГИТ, соответствующий dMin, то есть элемент iMin. Значит, имеет смысл занести в запись iMin информацию о k-й строке и переупорядочить таблицу. После внесения изменений в таблицу ГИТ необходимо заново определить ее параметры iMin, dMin и pLast.
Таким образом, построение и модификация таблицы глобальных индексов будет осуществляться одновременно с ее использованием для обеспечения быстрого произвольного доступа к строкам текстового файла.
Следует отметить, что расстояние между элементами таблицы ГИТ принимается равным разности позиций начала строк, а не их порядковых номеров. Это существенный момент, так как несколько коротких строк могут занимать меньше места, чем одна большая строка. Именно поэтому после внесения изменений в ГИТ для определения dMin и iMin необходимо попарно просмотреть все элементы таблицы.
Очевидно, что начало файла всегда соответствует строке с номером "ноль" с нулевым смещением. Поэтому решение о целесообразности хранения соответствующей записи в ГИТ следует принимать исходя из удобства практической реализации алгоритма произвольного доступа к текстовому файлу.
В заключение несколько слов о приведенном методе. При его описании использовалось много интуитивных вероятностных понятий ("скорее всего", "зачастую", "возможно") без каких-либо математических выкладок. Дело в том, что определить потребность в использовании таблицы ГИТ и ее конкретные параметры может только разработчик программы на основании анализа специфики обрабатываемых текстовых файлов, характеристик устройств хранения информации и настроек операционной системы. В этой статье лишь предлагается идея, реализация которой способна в ряде случаев помочь найти компромисс между скоростью прямого доступа к строкам текстового файла и затратами оперативной памяти на хранение вспомогательной информации.
Игорь Орещенков
(c) компьютерная газета
Компьютерная газета. Статья была опубликована в номере 28 за 2001 год в рубрике soft :: текст
