Создание легко обновляемых текстовых индексов

Содержание

Слайд 2

Задача

Поиск слов и фраз в большой текстовой коллекции

Задача Поиск слов и фраз в большой текстовой коллекции

Слайд 3

Инвертированные файлы

Часто используются для поиска
Сложно добавлять новые данные

Инвертированные файлы Часто используются для поиска Сложно добавлять новые данные

Слайд 4

Инвертированные файлы

Для каждой словоформы сохраняется информация о том, в каких документах и

Инвертированные файлы Для каждой словоформы сохраняется информация о том, в каких документах
где в документах она встречается

Слайд 5

Пример информации о вхождении
1) Номер (ID) файла
2) Позиция словоформы в файле (порядковый

Пример информации о вхождении 1) Номер (ID) файла 2) Позиция словоформы в
номер словоформы, номер предложения, и т. д. )

Слайд 6

Задача

Нужно сделать индекс, который бы позволял легко добавлять в него новые данные

Задача Нужно сделать индекс, который бы позволял легко добавлять в него новые данные

Слайд 7

CLB-дерево

B-дерево, в нем хранятся слова

Информация о вхождениях слова сохраняется в списке блоков

CLB-дерево B-дерево, в нем хранятся слова Информация о вхождениях слова сохраняется в списке блоков

Слайд 8

Морфология

Морфологический анализатор
Для каждой словоформы из словаря выдается набор базовых форм.
Базовых форм ~

Морфология Морфологический анализатор Для каждой словоформы из словаря выдается набор базовых форм.
200 тысяч.
Словоформ ~ 4 млн.

Слайд 9

Кэширование

Храним в B-дереве не словоформы, а базовые формы. Можем хранить в памяти

Кэширование Храним в B-дереве не словоформы, а базовые формы. Можем хранить в
последний блок для каждой базовой формы.

Слайд 10

Плюсы

Можно быстро добавлять новые данные. Информация о новых вхождениях слова добавляется в

Плюсы Можно быстро добавлять новые данные. Информация о новых вхождениях слова добавляется
последний блок списка. Когда он заполняется - создается новый блок.

Слайд 11

Минусы

1) Фрагментация – блоки могут располагаться в разных местах
2) Неэффективное использование дисковой

Минусы 1) Фрагментация – блоки могут располагаться в разных местах 2) Неэффективное
памяти, блоки могут быть слабо заполнены
3) Требует много памяти для использования большого размера блока (200 000 x <Размер блока>).

Слайд 12

Проблема фрагментации

Пусть в списке блоков k блоков.
Выберем число m = 2C
Разделим весь

Проблема фрагментации Пусть в списке блоков k блоков. Выберем число m =
список блоков на группы, размером m блоков в каждой, за исключением последней.

Слайд 13

Пример

У нас есть 25 блоков и m = 8.
Разбиваем 25 блоков

Пример У нас есть 25 блоков и m = 8. Разбиваем 25
на группы следующих размеров 8, 8, 8, 1.

Слайд 14

Проблема фрагментации

Информация о вхождениях слова сохраняется в списке блоков

Проблема фрагментации Информация о вхождениях слова сохраняется в списке блоков

Слайд 15

Алгоритм

Пусть есть k заполненных подряд расположенных блоков B1, …, Bk, в частности

Алгоритм Пусть есть k заполненных подряд расположенных блоков B1, …, Bk, в
последний блок также заполнен, и нам требуется взять где-то новый блок.

Слайд 16

k = 2x, x < c

ищем 2k подряд располагающихся блоков N1, …

k = 2x, x ищем 2k подряд располагающихся блоков N1, … N2k.
N2k.
Затем копируем информацию из старых k блоков в первую половину новых блоков, т. е. в блоки N1, … Nk соответственно.
B1, …, Bk помечаются как свободные.
Запись далее осуществляется в Nk+1.
Nk+2, …, N2k, помечаются как зарезервированные

Слайд 17

k = 2x, x = c

Заканчиваем текущую группу блоков, в ней уже

k = 2x, x = c Заканчиваем текущую группу блоков, в ней
есть m = 2c блоков.
Начинаем формировать новую группу блоков.

Слайд 18

Остальные случаи

Используем зарезервированные ранее блоки (в случае k = 2x, x <

Остальные случаи Используем зарезервированные ранее блоки (в случае k = 2x, x
c)

Слайд 19

Эффективное использование дисковой памяти

B-дерево, в нем хранятся слова

Информация о вхождениях слова сохраняется

Эффективное использование дисковой памяти B-дерево, в нем хранятся слова Информация о вхождениях
в списке блоков

Слайд 20

Эффективное использование памяти

Все базовые формы разделяются на n групп. Используем n временных

Эффективное использование памяти Все базовые формы разделяются на n групп. Используем n
файлов. Вначале читаем документы, записываем информацию о вхождениях для i-й группы в i-й временный файл.
При создании индекса обрабатываем отдельную группу. Кэш используется только для одной группы.

Слайд 21

Сравнение с существующими разработками

Общий объем 35,2 гб, 191 074 файла
Все файлы были

Сравнение с существующими разработками Общий объем 35,2 гб, 191 074 файла Все
в кодировке Windows-1251 (CP1251).
Язык документов – русский.
Все файлы представляли собой обычный текст.

Слайд 22

Описание конфигурации оборудования

Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш:

Описание конфигурации оборудования Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш:
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 гб. Создание
время 3 часа, 32 мин., размер 24 гб.
Для CLB индекса использовался размер блока 16 КБ.

Слайд 24

Добавление в индекс одного файла среднего размера

Время добавления одного документа 1,2

Добавление в индекс одного файла среднего размера Время добавления одного документа 1,2
мб. для CLB индекса: 9 мин.
Время добавления одного документа 1,2 мб. в инвертированный файл: 57 мин.

Слайд 25

Добавление в индекс одного файла малого размера

Время добавления одного документа размером

Добавление в индекс одного файла малого размера Время добавления одного документа размером
534 байта для CLB индекса: 22 с.
Время добавления одного документа размером 534 байта в инвертированный файл: 57 мин (т. е. такое же, как при размере файла 1,2 мб).

Слайд 26

Время поиска

Время поиска в инвертированном файле и CLB-индексе практически совпадают.

Время поиска Время поиска в инвертированном файле и CLB-индексе практически совпадают.

Слайд 27

Выводы

Проведенные эксперименты показывают высокую эффективность CLB индекса при добавлении в него данных

Выводы Проведенные эксперименты показывают высокую эффективность CLB индекса при добавлении в него данных небольшого размера.
небольшого размера.

Слайд 28

Сравнение с существующими разработками

Процессор: Intel Pentium 4, 3.0 GHz, кэш: L1

Сравнение с существующими разработками Процессор: Intel Pentium 4, 3.0 GHz, кэш: L1
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
размер блока 16 КБ.

Слайд 30

SearchInform Desktop (http://www.searchinform.com)

Размер индекса 16,15 гб.
Время создания 9 часов.

SearchInform Desktop (http://www.searchinform.com) Размер индекса 16,15 гб. Время создания 9 часов.

Слайд 31

Архивариус 3000 http://www.likasoft.com/

Размер индекса 24,83 гб.
Время создания 6 часов 46 мин.

Архивариус 3000 http://www.likasoft.com/ Размер индекса 24,83 гб. Время создания 6 часов 46 мин.

Слайд 32

Google Desktop

Размер индекса ~ 5 гб
Время создания 31 час 25 минуты

Google Desktop Размер индекса ~ 5 гб Время создания 31 час 25 минуты

Слайд 33

Выводы

Эксперименты показывают высокую скорость создания CLB индекса.

Выводы Эксперименты показывают высокую скорость создания CLB индекса.

Слайд 34

Эксперименты

Общий объем 86 гб, 400 049 файла
Все файлы были в кодировке Windows-1251

Эксперименты Общий объем 86 гб, 400 049 файла Все файлы были в
(CP1251).
Язык документов – русский.
Все файлы представляли собой обычный текст.

Слайд 35

Описание конфигурации оборудования

Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш: L1

Описание конфигурации оборудования Процессор: Intel Core 2 Duo E6700, 2.66 GHz, кэш:
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
блока 64 КБ.

Слайд 37

Инвертированные файлы

Размер индекса 117,7 гб.
Время создания 20 часов 6 минут.

Инвертированные файлы Размер индекса 117,7 гб. Время создания 20 часов 6 минут.

Слайд 38

Архивариус 3000 http://www.likasoft.com/

Размер индекса 62,65 гб.
Время создания 6 часов 10 минут.

Архивариус 3000 http://www.likasoft.com/ Размер индекса 62,65 гб. Время создания 6 часов 10 минут.

Слайд 39

Инструментарий

Автором разработана библиотека для создания индексов и поиска в текстах, в которой

Инструментарий Автором разработана библиотека для создания индексов и поиска в текстах, в
реализована описанная структура данных и алгоритмы.

Слайд 40

Форматы файлов

Библиотека может индексировать файлы в различных форматах, например RTF, PDF, CHM,

Форматы файлов Библиотека может индексировать файлы в различных форматах, например RTF, PDF,
HTML, DJVU и кодировках, например UNICODE, UTF8, CP1251, ASCII, KOI8.

Слайд 41

Архивы

Поддерживается обработка архивов форматов ZIP, CAB, RAR, 7Z, ARJ, TAR, и др.

Архивы Поддерживается обработка архивов форматов ZIP, CAB, RAR, 7Z, ARJ, TAR, и др.

Слайд 42

Архитектура

Библиотека реализована в виде COM сервера для операционных систем Windows
Написана на C++.

Архитектура Библиотека реализована в виде COM сервера для операционных систем Windows Написана на C++.

Слайд 43

Архитектура

Ядро, осуществляет создание индекса и поиск.
Модуль поддержки морфологии
Модуль распознавания кодировки. При

Архитектура Ядро, осуществляет создание индекса и поиск. Модуль поддержки морфологии Модуль распознавания
распознавании кодировки также учитывается морфология.

Слайд 44

Форматы файлов

Модуль поддержки форматов файлов. Поддержка форматов файлов и архивов реализована с

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

Слайд 45

Архитектура

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

Архитектура Модуль атрибутов документов, для сохранения описания документов. Модуль репозитария, для сохранения
Создается для того, чтобы при поиске можно было быстро получать фрагмент текста, содержащий найденную фразу.

Слайд 46

Архитектура

Модуль COM осуществляет доступ к остальным модулям извне с помощью COM, что

Архитектура Модуль COM осуществляет доступ к остальным модулям извне с помощью COM,
позволяет использовать библиотеку в различных языках программирования.

Слайд 47

Системные требования

Реализованные алгоритмы достаточно нетребовательные к ресурсам компьютера. Для создания индекса достаточно

Системные требования Реализованные алгоритмы достаточно нетребовательные к ресурсам компьютера. Для создания индекса
иметь 300–400 мегабайт свободной оперативной памяти.
Автором проводились эксперименты по созданию индексов на машине с оперативной памятью размером 512 мб.

Слайд 48

SSD

Эффективность описанных в данном алгоритмов значительно возрастет с применением дисков SSD (Solid-state

SSD Эффективность описанных в данном алгоритмов значительно возрастет с применением дисков SSD
drive), за счет более быстрого чтения блоков малого размера. При этом эффективность таких структур данных как инвертированные файлы возрастет менее, т. к. для добавления в инвертированный файл информации его все равно придется практически переписать целиком.
Имя файла: Создание-легко-обновляемых-текстовых-индексов.pptx
Количество просмотров: 110
Количество скачиваний: 0