[an error occurred while processing this directive] [an error occurred while processing this directive] Классификация и разметка>>[Введение|Проект БВИ]

Проект «БВИ»

Проект «БВИ»

Д.В.Хмелёв

Содержание

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  Предполагаемые функции

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) с аналогичными возможностями.

[an error occurred while processing this directive]