Проект «БВИ»
Д.В.Хмелёв
Содержание
1 Общие вопросы1.1 Расшифровка названия
1.2 Цель проекта
1.3 Область применения
1.4 Предполагаемые функции
2 Реализация
2.1 Главная мысль
2.2 Уменьшение объёма текстов в 2-3 раза
2.3 Классификация
2.4 Поиск дубликатов и нетипичных документов
2.5 Поиск подстроки
2.6 Поиск регулярного выражения
2.7 Совместимость с Bzip2
3 Отдалённые планы
1 Общие вопросы
1.1 Расшифровка названия
БВИ - Большой Вселенский Информаторий. Образовано от удачно подвернувшейся английской аббревиатуры BWI (Burrows-Wheeler Index). Звуковая имитация первых букв БУЙ отвергнута за неблагозвучие.
1.2 Цель проекта
Создание системы хранения и извлечения документов в коллекции большого (ограниченного только дисковым пространством) объёма.
1.3 Область применения
Большие коллекции текстов в цифровом формате. Например, сетевые библиотеки. Годятся также коллекции HTML- и, скажем, PS-файлов. Это могут также быть тексты в формате (WORD), хотя вряд ли по ним имеет смысл производить поиск.
1.4 Предполагаемые функции
- Хранение информации в сжатом виде (сжатое преобразование Барроуза-Уилера плюс некоторая индексная информация) с коэффициентом сжатия 30-40%,
- функции по автоматическому определению дубликатов и нетипичных документов в коллекции,
- классификация документов, в перспективе, самоорганизация каталога документов на основе индекса повторяемости.
- Полнотекстовый поиск строк за существенно сублинейное время (доли секунд для гигабайтных объёмов информации),
- Полнотекстовый поиск с использованием регулярных выражений,
- Прозрачная совместимость с форматом Bzip2.
2 Реализация
2.1 Главная мысль
Суффиксный массив легко восстанавливается из преобразования Барроуза-Уилера. Преобразование Барроуза-Уилера на диске хранится в сжатом виде, что позволяет ускорить загрузку суффиксного массива в 7-8 раз по сравнению с хранением его в расжатом виде. Поскольку операции с диском составляют существенную долю времени на современных компьютерах, уже за счёт этого эффекта можно добиться значительного ускорения многих алгоритмов.
2.2 Уменьшение объёма текстов в 2-3 раза
В отличие от других индексных систем, увеличивающих объём хранимого текста за счёт дополнительного индекса, мы уменьшаем совместный объём хранимых данных в 3-4 раза, оставляя 25-40% от исходного текста, увеличивая тем самым вместимость диска.
2.3 Классификация
Индекс повторяемости вычисляется за линейное время от длины анализируемых файлов, при наличии суффиксного массива, который неявно хранится в преобразовании Барроуза-Уилера.
2.4 Поиск дубликатов и нетипичных документов
Опять-таки осуществляется с помощью манипуляций над суффиксными массивами. Требует линейного времени от длины имеющихся файлов.
2.5 Поиск подстроки
Можно просто устроить трубу с fgrep. С другой стороны, можно воспользоваться тем, что восстановленные данные индексируются суффиксным массивом и с лёгкостью определить все вхождения строки без обращения к fgrep.
2.6 Поиск регулярного выражения
Аналогично предыдущему.
2.7 Совместимость с Bzip2
Очень популярная программа Bzip2 уже хранит данные, преобразованные с помощью BWT, на диске. Построенные массивы покрывают довольно объём (исходный текст по умолчанию бьётся на блоки по 900k текста, это больше 90% текстовых файлов, даже книг). Их можно использовать для конструирования суффиксного массива для целого файла «на лету». Предполагается также создание утилиты bz2bwi для перевода в полноиндексный формат БВИ и обратной утилиты bwi2bz. В принципе, можно добиться совместимости формата с распаковщиком bunzip2. Тогда процесс перехода пользователей на БВИ будет лёгким и незаметным.
3 Отдалённые планы
Интерфейс с cgi-скриптами. Сервер, разархивирующий БВИ-файлы «на лету», может работать быстрее, чем обычно: за счёт меньшей задержки загрузки с диска (при работе с HTML-файлами) Создание системы, аналогичной ZIP-папкам под win32, чтобы использование .bwi файлов было прозрачно на уровне пользователя. Под Юникс создать файловую систему (модификацию ext2 или ext3) с аналогичными возможностями.