| Крупнейший каталог ресурсов по сжатию! Пополняйте! |
 |
 |
|
|
Сайт о сжатии >>
Новинки |
О сервере
(Compression Catalog! |
ENGLISH)
Книга "Методы сжатия данных" >> Без потерь | Изображений | Видео Разделы >> Cтатьи | Видео | Arctest | Ссылки | Ru.compress | Форум Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | Д.Шкарина |
||
 |
||
 |
|
|
|
|
|
Проект «БВИ»Д.В.Хмелёв
Содержание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) с аналогичными возможностями.
Сайт о сжатии >> Новинки | О сервере | Статистика Книга "Методы сжатия данных" >> Универсальные | Изображений | Видео Разделы >> Download (статьи+исходники) | Ссылки | Ru.compress | Arctest | Видео | Каталог ссылок | Форум Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | А.Филинского | Д.Шкарина | С.Оснача |
|
|
|
|
|
|
||||||||||
 |
||||||||||||||||||||||
 |
Оставьте ваши замечания, предложения, мнения! О найденных ошибках пишите на compression_на_graphicon.ru © Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин, Е.Шелвин, Д.Шкарин и др., текст, состав., 2001-2008 © А.Андреев, оформление, 2002
|
 |
||
|
|
