что делает битовая карта

Битовая карта

Б́итовая ка́рта (англ. bitmap, bitset, bit array ) — набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов.

Содержание

Применение

В цифровых изображениях

В монохромных мониторах (или монохромных режимах работы цветных мониторов) число битов, соответствующих каждому элементу изображения, определяет количество уровней серого. Если 1 пикселу соответствует 1 бит, изображение будет однобитным бинарным, т. е. строго «чёрно-белым», состоящим из элементов изображения всего двух возможных цветов. Если 1 пикселу соответствует 8 бит (1 байт), то изображение будет полутоновым, имеющим 256 оттенков уровня серого. При этом бинарное изображение может в реальности быть «чёрно-оранжевым», а полутоновое отображать различные по яркости уровни зелёного (всё зависит от реального цвета свечения монитора). На практике же всё равно используются термины «чёрно-белое» и «уровни серого».

Цветное индексированное изображение с палитрой в 16 цветов потребует хранения в битовой карте 4 бит на каждый пиксел.

В файловых системах

Битовая карта — служебная структура в сложных файловых системах, хранящая информацию о наличии и расположении свободного места. Каждому кластеру в файловой системе соответствует один бит. Если сектор занят, то значение соответствующего бита устанавливается в 1, если свободен — в 0.

Подобная организация позволяет операционной системе быстро искать свободное место и определять его количество, не обращаясь к каталогам файловой системы.

Использование битовой карты является отличительной особенностью сложных файловых систем (HPFS, NTFS, UFS и др.). В системе FAT роль карты свободного места выполняет одноимённая структура: таблица размещения файлов (англ. file allocation table ), являющаяся массивом, но не битовым.

В базах данных

См. также

Примечания

Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным.

Полезное

Смотреть что такое «Битовая карта» в других словарях:

битовая карта — битовый массив Образ изображения на графическом устройстве, представленный в специальном виде и хранящийся в памяти ЭВМ или на внешнем устройстве. [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993]… … Справочник технического переводчика

Битовая карта (Bitmap) — Набор двоичных знаков (бит), которые соответствуют элементу издания: странице, отдельному изображению или листу спуска полос целиком … Краткий толковый словарь по полиграфии

ISO 8583 — ISO 8583 стандарт ISO, описывающий процесс передачи и формат финансовых сообщений (транзакций) систем, обрабатывающих данные банковских платёжных карт. Содержание 1 Введение 2 Индикатор типа сообщения 2.1 … Википедия

Битовый вектор — Битовая карта (англ. bitmap, bitset, bit array) набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов. Содержание 1 Применение 1.1 В цифровых изображениях 1.2 … Википедия

Битовый массив — Битовая карта (англ. bitmap, bitset, bit array) набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов. Содержание 1 Применение 1.1 В цифровых изображениях 1.2 … Википедия

ext2 — Разработчик Реми Кард (англ.) Файловая система Second extended file system Дата представления Январь 1993 (Linux) Метка тома Apple UNIX SVR2 (Apple Partition Map) 0x83 (Master Boot Record) EBD0A0A … Википедия

Ext2 — или 2я расширенная файловая система файловая система для ядра Linux. Она была разработана Rémy Card ом в качестве замены для extended file system. Она достаточно быстра для того, чтобы служить эталоном в тестах производительности файловых… … Википедия

Бинарное изображение — Пример бинарного изображения, записанного байтами, где 1 бит представляет 1 пиксель (двоичный, шестнадцатеричный, графический виды) 11111110 01111110 11100011 11000011 00011000 11110011 11111110 00011000 11011011 11000011 00011000 11001111… … Википедия

Двоичное изображение — Пример бинарного изображения, записанного байтами, где 1 бит представляет 1 пиксел (двоичный, шестнадцатеричный, графический виды) 11111110 01111110 11000011 11000011 00011000 11110011 11111110 00011000 11011011 11000011 00011000 11001111… … Википедия

Page bit map — Поразрядная [битовая] карта отображения наборной полосы; Битовая карта полосы набора … Краткий толковый словарь по полиграфии

Источник

СОДЕРЖАНИЕ

Определение

Основные операции

Чтобы получить битовую маску, необходимую для этих операций, мы можем использовать оператор битового сдвига, чтобы сдвинуть число 1 влево на соответствующее количество разрядов, а также побитовое отрицание, если необходимо.

Если мы хотим перебрать биты битового массива, мы можем сделать это эффективно, используя дважды вложенный цикл, который перебирает каждое слово по одному за раз. Требуются только n / w доступы к памяти:

Более сложные операции

Население / Вес Хэмминга

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

Инверсия

Найдите первый

Сжатие

Преимущества и недостатки

Битовые массивы, несмотря на их простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же проблем:

Приложения

Из-за своей компактности битовые массивы находят множество применений в областях, где пространство или эффективность имеют решающее значение. Чаще всего они используются для представления простой группы логических флагов или упорядоченной последовательности логических значений.

Битовые массивы также являются полезной абстракцией для изучения потоков сжатых данных, которые часто содержат элементы, занимающие части байтов или не выровненные по байтам. Например, сжатое представление кодирования Хаффмана одного 8-битного символа может иметь длину от 1 до 255 бит.

Языковая поддержка

Хотя Standard ML не поддерживает битовые массивы, Standard ML из Нью-Джерси имеет расширение, BitArray структуру, в своей библиотеке SML / NJ. Он не имеет фиксированного размера и поддерживает операции с наборами и битовые операции, включая, что необычно, операции сдвига.

В Haskell в настоящее время также отсутствует стандартная поддержка поразрядных операций, но и GHC, и Hugs предоставляют Data.Bits модуль с различными побитовыми функциями и операторами, включая операции сдвига и поворота, а «распакованный» массив над логическими значениями может использоваться для моделирования битового массива, хотя это не поддерживает прежний модуль.

В Perl строки могут использоваться как расширяемые битовые массивы. Им можно управлять с помощью обычных побитовых операторов (

В Ruby вы можете получить доступ (но не установить) бит целого числа ( Fixnum или Bignum ) с помощью оператора скобки ( [] ), как если бы это был массив бит.

Источник

Коты в коробочках, или Компактные структуры данных

Как быть, если дерево поиска разрослось на всю оперативку и вот-вот подопрет корнями соседние стойки в серверной? Что делать с инвертированным индексом, жадным до ресурсов? Завязывать ли с разработкой под Android, если пользователю прилетает «Память телефона заполнена», а приложение едва на половине загрузки важного контейнера?

В целом, можно ли сжать структуру данных, чтобы она занимала заметно меньше места, но не теряла присущих ей достоинств? Чтобы доступ к хэш-таблице оставался быстрым, а сбалансированное дерево сохраняло свои свойства. Да, можно! Для этого и появилось направление информатики «Succinct data structures», исследующее компактное представление структур данных. Оно развивается с конца 80-х годов и прямо сейчас переживает расцвет в лучах славы big data и highload.

А тем временем на Хабре найдется ли герой, способный пересковоговорить три раза подряд
[səkˈsɪŋkt]?

Дверь в мир компактности

Итак, структура данных считается компактной (succinct), если она:

Это означает, что алгоритмы сжатия без потерь никакого отношения к компактным структурам данных не имеют. Ведь они предполагают восстановление данных из сжатого состояния для их обработки.

Привычные, «мейнстримовые» реализации графов, хэш-таблиц и прочего тоже не годятся. Взять хотя бы указатели на дочерние элементы в дереве поиска. Они отъедают порядочно места: , где — длина указателя, а — количество узлов в дереве. Зато succinct реализация дерева позволяет улучшить асимптотику до , что близко к теоретической нижней границе для дерева из узлов. При длине указателя байт это означает переход от к совершенно другому порядку асимптотики — всего лишь , если учитывать, что — пренебрежимо малая величина относительно .

Компактные (succinct) структуры данных — это сжатые представления для битовых векторов, мультимножеств, планарных графов и других всеми любимых классических структур. Зачастую они статические, построенные единожды и не меняющиеся в процессе использования. Есть и исключения — succinct-структуры с быстрыми операциями добавления и удаления элементов.

В основе большинства компактных структур лежит концепция так называемого компактного индексируемого словаря. Это — частный случай битовой карты (bitmap, bitset). Сама по себе битовая карта идеальна для проверки вхождения элементов в некое множество. Если элемент включен в множество, то значение бита по заданному индексу устанавливается в 1, если нет — сбрасывается в 0. Жизненный пример — inode-битмапа ext4, UFS и других юниксовых файловых систем. Она хранит данные о том, какие записи в таблице индексных дескрипторов заняты, а какие — свободны.

Компактный индексируемый словарь — это та же битовая карта, но дополненная двумя операциями: rank и select. Эти операции — слоны, на которых зиждется мир succinct. Грубо говоря, rank — это подсчет количества элементов, а select — поиск элемента:

Допустим, у нас есть индексируемый словарь, в котором 4 из 7 бит установлены. Тогда и примут следующие значения:

Пример индексируемого словаря и расчета для него , .

Внимательный читатель заметит, что select — обратная операция для rank. Если , то .

У кого-нибудь возникло дежавю при виде ? А все потому, что эта операция обобщает Вес Хэмминга — количество ненулевых символов в последовательности. Применительно к бинарным последовательностям Вес Хэмминга также называется popcount (population count).

Rank/select применимы и для сброшенных битов. Вот пример расчета и для битов, равных 0:

Пример компактного индексируемого словаря и расчета для него , .

Распилить дерево на битики

Используем же это знание, чтобы построить компактное префиксное дерево! Префиксные деревья хороши для поиска строк по префиксу. С их помощью зачастую реализуется выпадающий список поисковых подсказок (саджест). Подход к succinct’изации префиксного дерева предельно обобщенный и по максимуму демонстрирует весь изюм компактных структур. В отличие от бинарного дерева, для которого выведены частные формулы, мешающие увидеть общую картину.

Популярнее всего три метода компактного представления деревьев:

Что за подозрительная логическая цепочка перевода «unary degree» в «единично-закодированный узел»? Что ж. Unary degree в этих названиях означает способ кодирования узлов дерева последовательностью единиц по количеству дочерних узлов, обязательно с нулем в прицепе.

Эти три метода представления деревьев объединяет наличие быстрых операций: найти родителя; найти первого потомка; найти последнего потомка; найти левый и правый соседние узлы. Принципиальная возможность и эффективность других операций отличаются от метода к методу.

Остановимся на методе LOUDS. Поняв его, не составит труда разобраться с двумя другими. К тому же, в прошлом году LOUDS-деревья отметили свой 30-й день рождения! Дополнительные полезные операции для LOUDS-деревьев реализуются за : найти количество потомков узла; вычислить номер потомка узла среди всех его потомков (первый потомок, второй, -ый и т.д.); найти -ого потомка. Недостаток LOUDS — отсутствие эффективного алгоритма подсчета количества узлов поддерева.

Суть метода проста: хранить ключи узлов дерева и всю ценную информацию в обычном массиве, а структуру дерева представить как последовательность бит. Итого имеем две статические структуры. Зато не нужно выделять память под указатели на узлы дерева: переходы между ними реализованы по формулам с активным применением rank/select.

Внимание, префиксное дерево:

Префиксное дерево, готовое к сжатию методом LOUDS.

Подготовим дерево к представлению в бинарном виде:

Префиксное дерево с пронумерованными по уровням узлами. Узлы закодированы.

В процессе поуровневого обхода дерева формируется компактный индексируемый словарь — последовательность бит из склеенных сверху вниз и слева направо закодированных узлов. У нас это 21-битная последовательность. Кстати, она называется LBS (LOUDS Bit String).

Компактный индексируемый словарь для префиксного дерева.

Компактное префиксное дерево LOUDS построено. LBS для дерева с узлами (фейковый не в счет) занимает бит. Осталось самое интересное — формулы для обхода дерева, превращенного в битовую карту.

Поиск первого потомка. Переход от узла к его первому дочернему узлу осуществляется по формуле:

— это номер узла, в предыдущей табличке проставленный фиолетовым.

Найдем первого потомка узла с индексом 3 (буква «а»):

Первый дочерний узел находится по индексу 6, и это буква «к». Применим формулу для корня дерева:

Мы нашли лист с индексом 1, букву «и». Сходится! Стало ясно, зачем потребовался фейковый корень: для магии индексации узлов. Во избежание странных ошибок перед переходом к потомкам узла неплохо бы выяснить количество этих потомков. Ведь для листьев дерева, что не удивительно, формула дает неадекватный результат. Чтобы найти следующего за первым потомка, нужно к его индексу прибавить 1. Это логично, потому что потомки одного узла всегда находятся рядом, без промежутков. Но при итерации по ним нужно вовремя остановиться — определить, какой потомок считается последним.

Поиск последнего потомка узла проходит в два этапа: определение индекса последней единицы в коде узла — именно она обозначает данного потомка; а затем определение индекса самого потомка:

Получив индекс последней единицы в коде узла, необходимо проверить, что бит по этому индексу действительно установлен. Если нет, то вывод напрашивается сам собой: это узел без потомков, лист. Если же бит установлен, то действуем дальше:

Найдем последнего потомка узла 2 (буква «к»).

Бит по индексу 8 равен 1, следовательно, узел 2 — не лист, и мы можем найти индекс его последнего потомка:

Количество потомков. Простейший способ определить количество потомков — вычесть из индекса последнего потомка узла индекс его первого потомка и прибавить 1:

Но допустим, у узла существует соседний узел , который располагается на том же уровне дерева, что и . Тогда количество потомков можно определить как разность индексов первых потомков узлов и :

Потомки узла также пронумерованы последовательно. Если первый потомок — это , то второй — и так далее вплоть до потомка соседнего на этом уровне узла (если таковой есть).

Количество потомков листа «и» с индексом 1 ожидаемо нулевое:

Поиск родителя для узла организуется по формуле:

Воспользуемся ей для поиска родителя узла 6 (буква «к»):

Это узел 3, буква «а».

Обладая знанием о формулах для индексов потомка и родителя, не составит труда обойти дерево целиком. Главное — не забывать об обработке граничных условий для корня и листьев.

Пара копеек про методы BP и DFUDS. У обоих методов пространственная асимптотика — бит для дерева из узлов, и оба они схожи представлением узла дерева в виде открывающих и закрывающих скобок.

BP (balanced parentheses) конвертирует дерево в последовательность скобок, по паре на каждый узел. Для этого дерево обходится в глубину; каждый узел посещается дважды. При первом посещении записывается открывающая скобка, при повторном — закрывающая. Между ними оказываются скобки дочерних элементов.

Последовательность скобок удобно представить в виде битовой карты, где 1 — открывающая скобка, а 0 — закрывающая. На быстрый поиск в ней заточены все формулы для работы с BP. В отличие от LOUDS, BP позволяет быстро подсчитать размер поддерева и определить ближайшего общего предка у двух узлов. А вот найти -ого потомка гораздо сложнее, чем в LOUDS.

DFUDS (depth-first unary degree sequence) схож одновременно и с BP, и с LOUDS. С BP его объединяет обход дерева в глубину и его скобочное представление. А принцип расстановки скобок такой же, как принцип кодирования узлов в LOUDS. Перед обходом дерева заранее добавляем в скобочную последовательность одну открывающую скобку. Потом при обходе узлов записываем открывающие скобки по количеству потомков, плюс одну закрывающую. Получается, что локальность хранения потомков у DFUDS выше, чем у BP. Вычисление размера поддерева и поиск ближайшего общего предка осуществляются за . Зато определение высоты поддерева и поиск родителя на -ом уровне — тяжелые для DFUDS операции.

Для наглядности сравним методы LOUDS, BP и DFUDS на примере мини-дерева.

Оранжевым цветом пронумерованы узлы дерева как при обходе в ширину (для LOUDS), синим — как при обходе в глубину (для BP и DFUDS).

LOUDS, BP и DFUDS представления дерева.

Не удивляйтесь, если в англоязычных работах увидите отличия в формулах. Среди математиков встречаются любители индексировать начиная с единицы. А некоторые разработчики считают слова rank и range созвучными, поэтому делают rank на полуинтервале . Из-за необходимости сохранения симметричности rank/select они вычисляют как . Зато некоторые формулы в таком виде выглядят короче.

Разреженный массив: взболтать, но не смешивать

Разреженный массив (sparse array) — еще одна структура, буквально созданная для сжатия. Размер такого массива порой на порядки превышает количество заполненных элементов. А пустые элементы либо принимают значение по умолчанию, либо помечаются чем-то вроде null. Разреженный массив маячит на горизонте всякий раз при необходимости хранить множество объектов и связей между ними. На ум сразу приходят графы друзей в социальных сетях, алгоритмы ранжирования поисковой выдачи, Excel-подобные таблицы, симуляторы электрических схем с миллиардами транзисторов в чипе.

Зачастую такие массивы по-лавкрафтовски циклопические, при наивной реализации не умещаются в оперативку, оставаясь фактически не заполненными. В зависимости от требований к памяти и скорости разреженные массивы превращают в куда более компактные хэш-таблицы, списки смежности, бинарные деревья… или подвергают succinct’изации.

Допустим, у нас есть разреженный массив строк. Прицепим к нему компактный индексируемый словарь. Что это даст?

Разреженный массив с битовой картой.

Теперь, не обращаясь к оригинальному массиву напрямую, легко проверить, присутствует ли в нем элемент по интересующему индексу. Ничто не мешает ужать исходный массив, выкинув все не заполненные элементы:

Массив без пустых элементов.

Вычисление индекса в сжатом массиве. После проверки присутствия элемента неплохо бы получить доступ к его значению в исходном массиве, то есть сопоставить индекс в индексируемом словаре индексу в сжатом массиве. Не сюрприз, что для этого используется rank:

Проверим, как обстоят дела с 8-м элементом: . Значит, в исходном массиве такого элемента нет. А что с элементом 7? . Получим его значение: . По индексу 2 находится «go».

Вычисление индекса в исходном массиве. Наверняка в массиве потребуется искать элементы по значению! Если данные не сортированы, поиск сводится к перебору за , где — количество не пустых элементов. Для найденного элемента может потребоваться получить его индекс , как если бы массив не был ужат. Для этого воспользуемся select — обратной операцией к rank:

Для примера отыщем строку «C++». В компактном массиве она находится по индексу 0. А ее индекс в исходном массиве равен .

Уже на примере со строками заметна экономия памяти. Если массив предназначен для хранения классов со множеством полей, экономия становится куда весомее. Кроме того, поиск в компактном массиве работает быстрее, чем в большом и разреженном: он лучше кэшируется процессором. У битового индексируемого словаря больше шансов уместиться в кэш-линию, чем у обычного массива чисел, строк или навороченных пользовательских типов.

Конечно, для хранения элементов описанный способ не годится. Его применимость заканчивается там, где начинаются проблемы с разрастанием индекса. Но своя ниша у этого способа сжатия массивов и его вариаций, конечно, есть. Будничный пример — это реализация протокола BitTorrent. Битовая карта содержит информацию о скачанных сегментах файлов, и пиры обмениваются индексами имеющихся у них сегментов. Космический пример — варианты сегментированной передачи данных, которые используют марсоходы, Вояджеры и станция «Новые Горизонты», бороздящая транснептуновые просторы.

Описанные примеры succinct’изации префиксного дерева и разреженного массива построены на общем фундаменте. Он основан на несокрушимой вере в эффективность операций rank/select. Без нее вся теория компактных, но достаточно быстрых структур трещит по швам. От скорости rank и select зависит адекватность использования компактных структур за пределами диссертаций.

Эти операции в самом деле можно реализовать крайне эффективно: rank — за ; select — за , что тоже почти константа. И конечно без некоторых уловок не обойдется. А так как в любом произведении с запутанным сюжетом должна витать легкая недосказанность, на этом я и остановлюсь.

Интересные факты

Что такое теоретическая нижняя граница занимаемых ресурсов с точки зрения теории информации? Допустим, структура данных хранит множество из элементов. Чтобы идентифицировать их без коллизий, потребуется количество бит, не меньшее . и есть та самая нижняя граница, определенная по формуле Хартли. В некоторых частных случаях, обладая информацией о природе хранимых данных, структуру удается ужать еще эффективнее.

Считается ли сишная строка succinct структурой данных? Она содержит символов и завершается нулевым символом ASCII. Значит, занимает места, и поэтому… она succinct, а конкретнее, implicit! Что приводит нас к следующему вопросу.

Все ли succinct структуры одинаково компактны? Область исследования succinct определяет аж три вида компактных структур, различающихся пространственной сложностью:

Какие еще компактные структуры используются на практике? В смысле, не для научных публикаций по плану кафедры, а в качестве обкатанных боевых решений. В статье речь шла про succinct-префиксные деревья и разреженные массивы. Но это вершина айсберга, в глубине которого кроются компактные вейвлет-деревья, FM-индексы, RMQ (range minimum queries), LCP (longest common prefix), суффиксные массивы и огромное количество других структур, пригодных к succinct’изации. У каждой из них своя сфера использования и свои соотношения эффективности-компактности.

Эпилог

Компактные структуры данных здорово облегчают жизнь разработчикам поисковых движков, мобильных приложений, высоконагруженных сервисов. И не только. В принципе для любого проекта, работающего с растущими объемами данных, может наступить час X, когда бутылочным горлышком внезапно станут структуры данных в их текущей реализации.

Но succinct — не безвредный подорожник на коленку, от которого «хуже-то уж точно не будет». Succinct — это демон со множеством имен. Призвать и управлять им подвластно лишь искушенному демонологу, имеющему кристальное представление о хитростях, опасностях и могуществе succinct. Достоверно известно, что такие храбрецы живут среди нас. Они приложили руку к редактору метода ввода (IME) в Google, компактному представлению ДНК в Гонконгском университете. В MAPS.ME мы используем succinct-реализацию для обработки географических высот.

Как бы то ни было, знание о компактных представлениях для знакомых структур данных однажды может стать судьбоносным при принятии решений об оптимизации проекта. Ибо как сказал Дональд К., в 97 % случаев лучше забыть о микро-оптимизациях: преждевременная оптимизация корень всех зол. Однако мы не должны упускать наши возможности в оставшихся 3 %.

Что дальше?

Для тех, кто жаждет теоретических подробностей из мира succinct:

Для тех, кто желает поскорее перейти от теории к практике:

Источник