Слайд 2Задача
Поиск слов и фраз в большой текстовой коллекции
![Задача Поиск слов и фраз в большой текстовой коллекции](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-1.jpg)
Слайд 3Инвертированные файлы
Часто используются для поиска
Сложно добавлять новые данные
![Инвертированные файлы Часто используются для поиска Сложно добавлять новые данные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-2.jpg)
Слайд 4Инвертированные файлы
Для каждой словоформы сохраняется информация о том, в каких документах и
![Инвертированные файлы Для каждой словоформы сохраняется информация о том, в каких документах](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-3.jpg)
где в документах она встречается
Слайд 5Пример информации о вхождении
1) Номер (ID) файла
2) Позиция словоформы в файле (порядковый
![Пример информации о вхождении 1) Номер (ID) файла 2) Позиция словоформы в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-4.jpg)
номер словоформы, номер предложения, и т. д. )
Слайд 6Задача
Нужно сделать индекс, который бы позволял легко добавлять в него новые данные
![Задача Нужно сделать индекс, который бы позволял легко добавлять в него новые данные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-5.jpg)
Слайд 7CLB-дерево
B-дерево, в нем хранятся слова
Информация о вхождениях слова сохраняется в списке блоков
![CLB-дерево B-дерево, в нем хранятся слова Информация о вхождениях слова сохраняется в списке блоков](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-6.jpg)
Слайд 8Морфология
Морфологический анализатор
Для каждой словоформы из словаря выдается набор базовых форм.
Базовых форм ~
![Морфология Морфологический анализатор Для каждой словоформы из словаря выдается набор базовых форм.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-7.jpg)
200 тысяч.
Словоформ ~ 4 млн.
Слайд 9Кэширование
Храним в B-дереве не словоформы, а базовые формы. Можем хранить в памяти
![Кэширование Храним в B-дереве не словоформы, а базовые формы. Можем хранить в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-8.jpg)
последний блок для каждой базовой формы.
Слайд 10Плюсы
Можно быстро добавлять новые данные. Информация о новых вхождениях слова добавляется в
![Плюсы Можно быстро добавлять новые данные. Информация о новых вхождениях слова добавляется](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-9.jpg)
последний блок списка. Когда он заполняется - создается новый блок.
Слайд 11Минусы
1) Фрагментация – блоки могут располагаться в разных местах
2) Неэффективное использование дисковой
![Минусы 1) Фрагментация – блоки могут располагаться в разных местах 2) Неэффективное](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-10.jpg)
памяти, блоки могут быть слабо заполнены
3) Требует много памяти для использования большого размера блока (200 000 x <Размер блока>).
Слайд 12Проблема фрагментации
Пусть в списке блоков k блоков.
Выберем число m = 2C
Разделим весь
![Проблема фрагментации Пусть в списке блоков k блоков. Выберем число m =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-11.jpg)
список блоков на группы, размером m блоков в каждой, за исключением последней.
Слайд 13Пример
У нас есть 25 блоков и m = 8.
Разбиваем 25 блоков
![Пример У нас есть 25 блоков и m = 8. Разбиваем 25](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-12.jpg)
на группы следующих размеров 8, 8, 8, 1.
Слайд 14Проблема фрагментации
Информация о вхождениях слова сохраняется в списке блоков
![Проблема фрагментации Информация о вхождениях слова сохраняется в списке блоков](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-13.jpg)
Слайд 15Алгоритм
Пусть есть k заполненных подряд расположенных блоков B1, …, Bk, в частности
![Алгоритм Пусть есть k заполненных подряд расположенных блоков B1, …, Bk, в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-14.jpg)
последний блок также заполнен, и нам требуется взять где-то новый блок.
Слайд 16k = 2x, x < c
ищем 2k подряд располагающихся блоков N1, …
![k = 2x, x ищем 2k подряд располагающихся блоков N1, … N2k.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-15.jpg)
N2k.
Затем копируем информацию из старых k блоков в первую половину новых блоков, т. е. в блоки N1, … Nk соответственно.
B1, …, Bk помечаются как свободные.
Запись далее осуществляется в Nk+1.
Nk+2, …, N2k, помечаются как зарезервированные
Слайд 17k = 2x, x = c
Заканчиваем текущую группу блоков, в ней уже
![k = 2x, x = c Заканчиваем текущую группу блоков, в ней](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-16.jpg)
есть m = 2c блоков.
Начинаем формировать новую группу блоков.
Слайд 18Остальные случаи
Используем зарезервированные ранее блоки (в случае k = 2x, x <
![Остальные случаи Используем зарезервированные ранее блоки (в случае k = 2x, x](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-17.jpg)
c)
Слайд 19Эффективное использование дисковой памяти
B-дерево, в нем хранятся слова
Информация о вхождениях слова сохраняется
![Эффективное использование дисковой памяти B-дерево, в нем хранятся слова Информация о вхождениях](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-18.jpg)
в списке блоков
Слайд 20Эффективное использование памяти
Все базовые формы разделяются на n групп. Используем n временных
![Эффективное использование памяти Все базовые формы разделяются на n групп. Используем n](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-19.jpg)
файлов. Вначале читаем документы, записываем информацию о вхождениях для i-й группы в i-й временный файл.
При создании индекса обрабатываем отдельную группу. Кэш используется только для одной группы.
Слайд 21Сравнение с существующими
разработками
Общий объем 35,2 гб, 191 074 файла
Все файлы были
![Сравнение с существующими разработками Общий объем 35,2 гб, 191 074 файла Все](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-20.jpg)
в кодировке Windows-1251 (CP1251).
Язык документов – русский.
Все файлы представляли собой обычный текст.
Слайд 22Описание конфигурации оборудования
Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш:
![Описание конфигурации оборудования Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-21.jpg)
L1 Data – 2 x 32 кб, L1 inst. 2 x 32 кб, L2 – 4096 кб.
Оперативная память: 4 гб, DDR2 800.
Жесткий диск: Seagate Barracuda 7200.10, 7200 RPM, кэш 16 мб., объем 750 гб.
FSB 1066 MHz.
Слайд 23Создание индекса
Создание инвертированного файла: время 9 часов, размер 40 гб.
Создание CLB индекса:
![Создание индекса Создание инвертированного файла: время 9 часов, размер 40 гб. Создание](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-22.jpg)
время 3 часа, 32 мин., размер 24 гб.
Для CLB индекса использовался размер блока 16 КБ.
Слайд 24Добавление в индекс одного файла среднего размера
Время добавления одного документа 1,2
![Добавление в индекс одного файла среднего размера Время добавления одного документа 1,2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-23.jpg)
мб. для CLB индекса: 9 мин.
Время добавления одного документа 1,2 мб. в инвертированный файл: 57 мин.
Слайд 25Добавление в индекс одного файла малого размера
Время добавления одного документа размером
![Добавление в индекс одного файла малого размера Время добавления одного документа размером](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-24.jpg)
534 байта для CLB индекса: 22 с.
Время добавления одного документа размером 534 байта в инвертированный файл: 57 мин (т. е. такое же, как при размере файла 1,2 мб).
Слайд 26Время поиска
Время поиска в инвертированном файле и CLB-индексе практически совпадают.
![Время поиска Время поиска в инвертированном файле и CLB-индексе практически совпадают.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-25.jpg)
Слайд 27Выводы
Проведенные эксперименты показывают высокую эффективность CLB индекса при добавлении в него данных
![Выводы Проведенные эксперименты показывают высокую эффективность CLB индекса при добавлении в него данных небольшого размера.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-26.jpg)
небольшого размера.
Слайд 28Сравнение с существующими
разработками
Процессор: Intel Pentium 4, 3.0 GHz, кэш: L1
![Сравнение с существующими разработками Процессор: Intel Pentium 4, 3.0 GHz, кэш: L1](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-27.jpg)
Data – 16 кб, L1 trace – 12 Kuops, L2 - 2048 кб.
Оперативная память: 4 гб, DDR2 533.
Жесткий диск: Seagate Barracuda 7200.8, 7200 RPM, кэш 8 мб., объем 200 гб.
FSB: 800 MHz.
Слайд 29Создание CLB индекса
Размер индекса 26,2 гб.
Время создания 5 часов 49 мин.
Использовался
![Создание CLB индекса Размер индекса 26,2 гб. Время создания 5 часов 49](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-28.jpg)
размер блока 16 КБ.
Слайд 30SearchInform Desktop (http://www.searchinform.com)
Размер индекса 16,15 гб.
Время создания 9 часов.
![SearchInform Desktop (http://www.searchinform.com) Размер индекса 16,15 гб. Время создания 9 часов.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-29.jpg)
Слайд 31Архивариус 3000
http://www.likasoft.com/
Размер индекса 24,83 гб.
Время создания 6 часов 46 мин.
![Архивариус 3000 http://www.likasoft.com/ Размер индекса 24,83 гб. Время создания 6 часов 46 мин.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-30.jpg)
Слайд 32Google Desktop
Размер индекса ~ 5 гб
Время создания 31 час 25 минуты
![Google Desktop Размер индекса ~ 5 гб Время создания 31 час 25 минуты](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-31.jpg)
Слайд 33Выводы
Эксперименты показывают высокую скорость создания CLB индекса.
![Выводы Эксперименты показывают высокую скорость создания CLB индекса.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-32.jpg)
Слайд 34Эксперименты
Общий объем 86 гб, 400 049 файла
Все файлы были в кодировке Windows-1251
![Эксперименты Общий объем 86 гб, 400 049 файла Все файлы были в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-33.jpg)
(CP1251).
Язык документов – русский.
Все файлы представляли собой обычный текст.
Слайд 35Описание конфигурации оборудования
Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш: L1
![Описание конфигурации оборудования Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-34.jpg)
Data – 2 x 32 кб, L1 inst. 2 x 32 кб, L2 – 4096 кб.
Оперативная память: 4 гб, DDR2 800.
Жесткий диск: Seagate Barracuda 7200.10, 7200 RPM, кэш 16 мб., объем 750 гб.
FSB 1066 MHz.
Слайд 36Создание CLB индекса
Размер индекса 56,5 гб.
Время создания 4 часа 28 минут.
Использовался размер
![Создание CLB индекса Размер индекса 56,5 гб. Время создания 4 часа 28](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-35.jpg)
блока 64 КБ.
Слайд 37Инвертированные файлы
Размер индекса 117,7 гб.
Время создания 20 часов 6 минут.
![Инвертированные файлы Размер индекса 117,7 гб. Время создания 20 часов 6 минут.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-36.jpg)
Слайд 38Архивариус 3000
http://www.likasoft.com/
Размер индекса 62,65 гб.
Время создания 6 часов 10 минут.
![Архивариус 3000 http://www.likasoft.com/ Размер индекса 62,65 гб. Время создания 6 часов 10 минут.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-37.jpg)
Слайд 39Инструментарий
Автором разработана библиотека для создания индексов и поиска в текстах, в которой
![Инструментарий Автором разработана библиотека для создания индексов и поиска в текстах, в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-38.jpg)
реализована описанная структура данных и алгоритмы.
Слайд 40Форматы файлов
Библиотека может индексировать файлы в различных форматах, например RTF, PDF, CHM,
![Форматы файлов Библиотека может индексировать файлы в различных форматах, например RTF, PDF,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-39.jpg)
HTML, DJVU и кодировках, например UNICODE, UTF8, CP1251, ASCII, KOI8.
Слайд 41Архивы
Поддерживается обработка архивов форматов ZIP, CAB, RAR, 7Z, ARJ, TAR, и др.
![Архивы Поддерживается обработка архивов форматов ZIP, CAB, RAR, 7Z, ARJ, TAR, и др.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-40.jpg)
Слайд 42Архитектура
Библиотека реализована в виде COM сервера для операционных систем Windows
Написана на C++.
![Архитектура Библиотека реализована в виде COM сервера для операционных систем Windows Написана на C++.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-41.jpg)
Слайд 43Архитектура
Ядро, осуществляет создание индекса и поиск.
Модуль поддержки морфологии
Модуль распознавания кодировки. При
![Архитектура Ядро, осуществляет создание индекса и поиск. Модуль поддержки морфологии Модуль распознавания](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-42.jpg)
распознавании кодировки также учитывается морфология.
Слайд 44Форматы файлов
Модуль поддержки форматов файлов. Поддержка форматов файлов и архивов реализована с
![Форматы файлов Модуль поддержки форматов файлов. Поддержка форматов файлов и архивов реализована](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-43.jpg)
помощью подключаемых дополнительных модулей, которые могут быть реализованы в виде динамических библиотек или написаны на Java. Модуль поддержки форматов файлов реализован в виде отдельного процесса для повышения надежности системы.
Слайд 45Архитектура
Модуль атрибутов документов, для сохранения описания документов.
Модуль репозитария, для сохранения текстов документов.
![Архитектура Модуль атрибутов документов, для сохранения описания документов. Модуль репозитария, для сохранения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-44.jpg)
Создается для того, чтобы при поиске можно было быстро получать фрагмент текста, содержащий найденную фразу.
Слайд 46Архитектура
Модуль COM осуществляет доступ к остальным модулям извне с помощью COM, что
![Архитектура Модуль COM осуществляет доступ к остальным модулям извне с помощью COM,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-45.jpg)
позволяет использовать библиотеку в различных языках программирования.
Слайд 47Системные требования
Реализованные алгоритмы достаточно нетребовательные к ресурсам компьютера. Для создания индекса достаточно
![Системные требования Реализованные алгоритмы достаточно нетребовательные к ресурсам компьютера. Для создания индекса](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-46.jpg)
иметь 300–400 мегабайт свободной оперативной памяти.
Автором проводились эксперименты по созданию индексов на машине с оперативной памятью размером 512 мб.
Слайд 48SSD
Эффективность описанных в данном алгоритмов значительно возрастет с применением дисков SSD (Solid-state
![SSD Эффективность описанных в данном алгоритмов значительно возрастет с применением дисков SSD](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/420362/slide-47.jpg)
drive), за счет более быстрого чтения блоков малого размера. При этом эффективность таких структур данных как инвертированные файлы возрастет менее, т. к. для добавления в инвертированный файл информации его все равно придется практически переписать целиком.