none
Поиск текста в огромном текстовом файле.

    Question

  • Здравствуйте.

    Суть вопроса:

    Есть невероятных размеров текстовый файл ( > 3Gb ). Этот файл - лог биллинговой системы и является неизменной входной аксиомой.

    Мне необходимо максимально быстро отыскать в нем необходимую информацию, и потом, по необходимости обращаться к тем или иным фрагментам файла. Вот тут и начались проблемы. Из за его огромного размера, о его выгрузке в ОЗУ не может быть и речи (или я заблуждаюсь). А как обратится к строке файла по индексу строки я не знаю.

    Какие будут приложения?

    Tuesday, November 27, 2012 6:25 AM

Answers

  • Совсем забыл отписаться т.к. сейчас отвлекся на другой проект.

    Пока что остановился на следующем алгоритме действий:

    Файл предварительно индексируется, затем поиск ведется в индексе.

    Создание индекса:

    1. Создаем стримридер на чтение файла.

    2. Считываем файл по одной строчке (было бы гораздо грамотнее читать блоками байт, я непременно так и сделаю, но позже, просто быстрее и проще было реализовать построчное чтение да и кодировка позволяет 1 символ = 1 байт).

    3. Т.к. Количество символов и байт в считанной строке идентично, В глобальный счетчик байт плюсуем длину строки + 1 (символ перехода на след. строку).

    4. Считанную строку сравниваем с регекс шаблоном входа в блок данных. Если строка маркер входа - выполняем последующие действия.

    5. Записываем считанную строку в экземпляр класса "Строка" который создали. Отличительная особенность класса - наличие полей "строка", "начало", "окончание" где начало и окончание это глобальная позиция строки в документе исходя из данных глобального счетчика байт.

    6. Записываем "Строку" в коллекцию строк созданного класса "Блок данных" Отличительная особенность класса - наличие полей "Коллекция строк", "начало", "окончание" где начало и окончание это глобальная позиция массива данных в документе исходя из данных глобального счетчика байт.

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

    8. Если "Блок данных" удовлетворяет требованиям проведенного анализа, из него выдергиваются сведения об условии поиска, и его глобальной позиции (смещение) в исходном файле. Сам блок данных после этого затирается, и идет на перезапись.

    9. Получившиеся данные сохраняем в созданный файл "имя_файла + .meta" в виде строки "искомые_данные;начало_байт;окончание_байт", Параллельно записываем эти данные в экземпляр класса который имеет структуру  "искомые_данные", "начало", "окончание". Класс записываем в коллекцию классов.

    10. Продолжаем действия 3-9 пока не прочитаем весь файл.

    Все. На этой стадии индекс готов и сохранен в памяти и на жестком диске. Программа готова к поиску.

    При старте программы - проверка есть ли файл "имя_файла + .meta". Если есть, грузим его в вышеописанную коллекцию, если нет, индексируем файл.

    По поиску особо рассказывать не буду, самый что ни на есть обыкновенный, перебором пробегаем по всему индексу, в сравнивая поле "искомые_данные" с входными параметрами. Совпадения отбрасываем в отдельную коллекцию. Далее по координатам смещения каждого члена получившейся коллекции, побайтно считываем все блоки данных, из исходного файла.

    Выводим результат - отформатированный, оформленный массив найденных блоков.

    Теперь о главном, скорости которых я смог достичь на данном этапе:

    Компьютер - самая обычная рабочая станция Коре2, 3 гига оперативы из которых свободен лишь 1 (2 тестовых сервака на машине висят).

    Индексация файла 3 - 3,5 Gb ~ 60 - 70 sec.

    Поиск в индексе + считывание необходимых блоков данных их исходного файла - менее 40 ms.

    Подгрузка сохраненного индекса: ~ 2 - 3 sec.

    Размер индекса ~ 1,5 - 2 млн. указателей на блоки данных.

    Средний запрос ~ 50 - 100 результатов.

    Объем занимаемый в ОЗУ ~ 150 Mb.

    Исходный код.

    P.S. Это еще не окончание. Проект еще ждет множество оптимизаций и улучшений. Если кому интересно, могу выложить сюда конечный вариант как закончу. Но даже на данной стадии, решая задачу практически "в лоб", я нахожу данные в трехгиговом файле за 40 миллисекунд =)

    • Edited by JusteG Monday, December 03, 2012 8:46 AM
    • Marked as answer by JusteG Monday, December 03, 2012 8:49 AM
    Monday, December 03, 2012 8:08 AM

All replies

  • Огромного размера файл следует загружать в огромного размера ОЗУ. Т.е. по сути, если у Вас достаточно ОЗУ, то почему бы не загрузить его? Правда нужно 64bit систему иметь как минимум. Ну, а дальше, уже можно использовать алгоритмы для быстрого поиска подстроки.
    Tuesday, November 27, 2012 6:50 AM
  • Ну если блочное чтение без загрузки всего файла в память не проблема, то обращение к конкретным частям уже другая история.

    То есть вы циклом идете по блокам текстового файла и проверяете совпадения, то есть ищите необходимую информацию.

    Что до обращения к строке - что понимается под "обратится по индексу"? Что за индекс такой. В чем он выражается? А вообще по изучайте вот это пространство имен, в нем есть все для работы с файлами. как текстовыми так и бинарными.


    Женат на WPF. Тайно встречаюсь с WinRT. Не сложилось с C#!

    Tuesday, November 27, 2012 7:41 AM
    Answerer
  • Обращение к строке в файле по индексу (как я себе это вижу)™

    Если считывать файл в оперативку, все просто:

    string[] FileStrings = File.ReadAllLines(@"D:\LogFile-2012-11-26.log");

    string a = FileStrings[100500];

    А вот как реализовать без предварительного чтения, непонятно:

    StreamReader SR = new StreamReader(@"D:\LogFile-2012-11-26.log");

    string a = SR.ReadLine(100500); //?

    Tuesday, November 27, 2012 8:49 AM
  • Такой вариант мне не подходит.

    За алгоритмы поисков спасибо. Узнал много нового.

    Алгоритм, как я себе его вижу, должен быть следующий:

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

    2. Сохраняем индексы (порядковый номер) найденных строк (тоже не проблема).

    3. Обращаясь по индексу, начинаем читать файл не с начала а именно с нужной строки, считываем массив данных (это и нужно реализовать).

    4. Анализируем полученный массив, выводим результат (ну здесь я как нибудь сам).

    Есть конечно вариант сразу по нахождению считывать необходимый массив данных, тогда в п.п. 2 и 3 необходимость отпадает, но объем информации получается приличный. Хотелось бы решить вопрос красифше™.

    • Edited by JusteG Tuesday, November 27, 2012 9:02 AM
    Tuesday, November 27, 2012 9:00 AM
  • Без предварительного чтения можно обойтись если строки будут фиксированной длины. Т.е. будет известно какое смещение надо взять, чтобы получить i-ю строку.

    А может быть ещё можно обеспечить предварительное сжатие текстового файла. Т.е. в программу уже поступает сжатый файл, который на порядок меньше и, следовательно, быстрее считывается с диска. Расчет в данном случае именно на то, что распаковка делается быстрее, чем чтение с диска.

    Вообще, если исходный формат файла можно изменить это открывает дополнительные просторы для реализации поиска.

    Tuesday, November 27, 2012 10:14 AM
  • Во! В точку!

    Как прочитать массив байтов из файла со смещением относительно начала файла?

    т.е. что то вроде того:

    File.Readbytes(x, y, z);

    или x = File.Readbytes(y, z);

    Где x - результат - массив байтов

    y - Входной параметр, смещение в байтах относительно начала файла.

    z - Входной параметр количество байт.

    Я думаю это решит мою проблему.

    • Edited by JusteG Tuesday, November 27, 2012 10:26 AM
    Tuesday, November 27, 2012 10:19 AM
  • Ответ на этот вопрос нашел достаточно быстро.

            public Form1()
            {
                InitializeComponent();
                byte[] Result = ReadBytes(113, 100, @"F:\LogFile-2012-11-26.log");
                textBox1.Text = CurrentEncoding.GetString(Result);
            }
    
            Encoding CurrentEncoding = Encoding.Default;
            public byte[] ReadBytes(int Offset, int BytesCount, string FileName)
            {
                StreamReader SR = new StreamReader(FileName);
                Stream fileStream = SR.BaseStream;
                CurrentEncoding = SR.CurrentEncoding;
                return ReadBytes(Offset, BytesCount, fileStream);
            }
    
            public byte[] ReadBytes(int Offset, int BytesCount, Stream fileStream)
            {
                byte[] Buffer = new byte[BytesCount];
                fileStream.Seek(Offset, SeekOrigin.Begin);
                fileStream.Read(Buffer, 0, BytesCount);
                return Buffer;
            }

    Решит ли это мою задачу, и если да то - конечный алгоритм, напишу в топике.

    Тема все еще открыта, если кто имеет соображения, делитесь, буду благодарен.

    • Edited by JusteG Tuesday, November 27, 2012 11:31 AM
    Tuesday, November 27, 2012 11:22 AM
  • Привет.

    Спасибо что поделились своим решением проблемы. Еще посмотрите схожую тему - Помогите организовать обработку лога Visual Basic


    Для связи [mail]

    Monday, December 03, 2012 6:55 AM
  • Также зависит от того, что вы ищите - если это выборка между датами, то можно придумать вариант с бинарным поиском, т.к. даты в файле отсортированы, то можно быстро найти нужные даты, запомнить смещение и прочитать после уже блок данных для дальнейшего разбора.


    Для связи [mail]

    Monday, December 03, 2012 7:02 AM
  • Совсем забыл отписаться т.к. сейчас отвлекся на другой проект.

    Пока что остановился на следующем алгоритме действий:

    Файл предварительно индексируется, затем поиск ведется в индексе.

    Создание индекса:

    1. Создаем стримридер на чтение файла.

    2. Считываем файл по одной строчке (было бы гораздо грамотнее читать блоками байт, я непременно так и сделаю, но позже, просто быстрее и проще было реализовать построчное чтение да и кодировка позволяет 1 символ = 1 байт).

    3. Т.к. Количество символов и байт в считанной строке идентично, В глобальный счетчик байт плюсуем длину строки + 1 (символ перехода на след. строку).

    4. Считанную строку сравниваем с регекс шаблоном входа в блок данных. Если строка маркер входа - выполняем последующие действия.

    5. Записываем считанную строку в экземпляр класса "Строка" который создали. Отличительная особенность класса - наличие полей "строка", "начало", "окончание" где начало и окончание это глобальная позиция строки в документе исходя из данных глобального счетчика байт.

    6. Записываем "Строку" в коллекцию строк созданного класса "Блок данных" Отличительная особенность класса - наличие полей "Коллекция строк", "начало", "окончание" где начало и окончание это глобальная позиция массива данных в документе исходя из данных глобального счетчика байт.

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

    8. Если "Блок данных" удовлетворяет требованиям проведенного анализа, из него выдергиваются сведения об условии поиска, и его глобальной позиции (смещение) в исходном файле. Сам блок данных после этого затирается, и идет на перезапись.

    9. Получившиеся данные сохраняем в созданный файл "имя_файла + .meta" в виде строки "искомые_данные;начало_байт;окончание_байт", Параллельно записываем эти данные в экземпляр класса который имеет структуру  "искомые_данные", "начало", "окончание". Класс записываем в коллекцию классов.

    10. Продолжаем действия 3-9 пока не прочитаем весь файл.

    Все. На этой стадии индекс готов и сохранен в памяти и на жестком диске. Программа готова к поиску.

    При старте программы - проверка есть ли файл "имя_файла + .meta". Если есть, грузим его в вышеописанную коллекцию, если нет, индексируем файл.

    По поиску особо рассказывать не буду, самый что ни на есть обыкновенный, перебором пробегаем по всему индексу, в сравнивая поле "искомые_данные" с входными параметрами. Совпадения отбрасываем в отдельную коллекцию. Далее по координатам смещения каждого члена получившейся коллекции, побайтно считываем все блоки данных, из исходного файла.

    Выводим результат - отформатированный, оформленный массив найденных блоков.

    Теперь о главном, скорости которых я смог достичь на данном этапе:

    Компьютер - самая обычная рабочая станция Коре2, 3 гига оперативы из которых свободен лишь 1 (2 тестовых сервака на машине висят).

    Индексация файла 3 - 3,5 Gb ~ 60 - 70 sec.

    Поиск в индексе + считывание необходимых блоков данных их исходного файла - менее 40 ms.

    Подгрузка сохраненного индекса: ~ 2 - 3 sec.

    Размер индекса ~ 1,5 - 2 млн. указателей на блоки данных.

    Средний запрос ~ 50 - 100 результатов.

    Объем занимаемый в ОЗУ ~ 150 Mb.

    Исходный код.

    P.S. Это еще не окончание. Проект еще ждет множество оптимизаций и улучшений. Если кому интересно, могу выложить сюда конечный вариант как закончу. Но даже на данной стадии, решая задачу практически "в лоб", я нахожу данные в трехгиговом файле за 40 миллисекунд =)

    • Edited by JusteG Monday, December 03, 2012 8:46 AM
    • Marked as answer by JusteG Monday, December 03, 2012 8:49 AM
    Monday, December 03, 2012 8:08 AM