Битовые массивы: компактное хранение и применение

Введение

Структура данных массив битов, которая компактно хранит биты

Битовый массив (также известный как битовая маска,

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

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

Население / вес штыка

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

Найдите первую .

Операция "найти первый установленный бит" или "найти первый единичный бит" определяет индекс или позицию бита со значением 1 с наименьшим индексом в массиве и имеет широкую аппаратную поддержку (для массивов, не превышающих размер слова) и эффективные алгоритмы для его вычисления. При хранении очереди с приоритетами в битовом массиве, операция "найти первый единичный бит" может быть использована для определения элемента с наивысшим приоритетом в очереди. Для расширения операции "найти первый единичный бит" на более длинные массивы можно найти первое ненулевое слово, а затем применить операцию "найти первый единичный бит" к этому слову. Связанные операции "найти первый нулевой бит", "подсчитать ведущие нули", "подсчитать ведущие единицы", "подсчитать замыкающие нули", "подсчитать замыкающие единицы" и "логарифм по основанию 2" (см. "найти первый установленный бит") также могут быть расширены на битовый массив простым способом.

Сжатие

Битовый массив – это наиболее плотный способ хранения "случайных" битов, то есть, когда каждый бит с одинаковой вероятностью равен 0 или 1, и каждый из них независим. Однако большинство данных не являются случайными, поэтому их можно хранить более компактно. Например, данные типичного факсимильного изображения не случайны и могут быть сжаты. Кодирование длин серий обычно используется для сжатия таких длинных последовательностей. Тем не менее, большинство сжатых форматов данных не обеспечивают удобный произвольный доступ; кроме того, чрезмерное сжатие битовых массивов может привести к потере преимуществ, связанных с параллелизмом на битовом уровне (векторизацией). Поэтому вместо сжатия битовых массивов как потоков битов, можно сжимать их как потоки байтов или слов (см. Индекс битовой карты (сжатие)).

Приложения

Из-за своей компактности битовые массивы находят применение в областях, где важны экономия пространства или эффективность. Чаще всего они используются для представления простой группы булевых флагов или упорядоченной последовательности булевых значений. Битовые массивы применяются в приоритетных очередях, где бит с индексом k устанавливается тогда и только тогда, когда k присутствует в очереди; эта структура данных, например, используется в ядре Linux и значительно выигрывает от аппаратной реализации операции поиска первого нулевого бита. Битовые массивы могут использоваться для выделения страниц памяти, inode, секторов диска и т. п. В таких случаях может применяться термин «битовая карта». Однако этот термин часто используется для обозначения растровых изображений, которые могут использовать несколько бит на пиксель. Другим применением битовых массивов является фильтр Блума — вероятностная структура данных для представления множеств, позволяющая хранить большие множества в небольшом объеме памяти, жертвуя небольшой вероятностью ошибки. Также возможно построение вероятностных хеш-таблиц на основе битовых массивов, допускающих ложноположительные или ложноотрицательные результаты. Битовые массивы и операции над ними также важны для создания компактных структур данных, использующих почти минимально необходимое пространство. В этом контексте важными становятся операции, такие как поиск n-го установленного бита или подсчет количества установленных битов до определенной позиции. Битовые массивы также служат полезной абстракцией для анализа потоков сжатых данных, которые часто содержат элементы, занимающие части байтов или не выровненные по границе байта. Например, сжатое представление кодирования Хаффмана для одного 8-битного символа может иметь длину от 1 до 255 бит. В информационном поиске битовые массивы хорошо подходят для представления списков вхождений очень частых терминов. Если вычислить разности между соседними значениями в списке строго возрастающих целых чисел и закодировать их унитарным кодированием, результатом будет битовый массив, в котором n-й бит равен 1 тогда и только тогда, когда n присутствует в списке. Подразумеваемая вероятность разрыва длиной n равна 1/2n. Это также частный случай кодирования Голомба, где параметр M равен 1; этот параметр обычно выбирается только при выполнении условия −log(2 − p) / log(1 − p) ≤ 1, или, приблизительно, когда термин встречается как минимум в 38% документов.

Because of their compactness, bit arrays have a number of applications in areas where space or efficiency is at a premium. Most commonly, they are used to represent a simple group of boolean flags or an ordered sequence of boolean values. Bit arrays are used for priority queues, where the bit at index k is set if and only if k is in the queue; this data structure is used, for example, by the Linux kernel, and benefits strongly from a find first zero operation in hardware. Bit arrays can be used for the allocation of memory pages, inodes, disk sectors, etc. In such cases, the term bitmap may be used. However, this term is frequently used to refer to raster images, which may use multiple bits per pixel. Another application of bit arrays is the Bloom filter, a probabilistic set data structure that can store large sets in a small space in exchange for a small probability of error. It is also possible to build probabilistic hash tables based on bit arrays that accept either false positives or false negatives. Bit arrays and the operations on them are also important for constructing succinct data structures, which use close to the minimum possible space. In this context, operations like finding the nth 1 bit or counting the number of 1 bits up to a certain position become important. Bit arrays are also a useful abstraction for examining streams of compressed data, which often contain elements that occupy portions of bytes or are not byte aligned. For example, the compressed Huffman coding representation of a single 8 bit character can be anywhere from 1 to 255 bits long. In information retrieval, bit arrays are a good representation for the posting lists of very frequent terms. If we compute the gaps between adjacent values in a list of strictly increasing integers and encode them using unary coding, the result is a bit array with a 1 bit in the nth position if and only if n is in the list. The implied probability of a gap of n is 1/2n. This is also the special case of Golomb coding where the parameter M is 1; this parameter is only normally selected when −log(2 − p) / log(1 − p) ≤ 1, or roughly the term occurs in at least 38% of documents.

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

Язык программирования APL полностью поддерживает битовые массивы произвольной формы и размера как булев тип данных, отличный от целых чисел. Все основные реализации (Dyalog APL, APL2, APL Next, NARS2000, Gnu APL и т. д.) плотно упаковывают биты в размер машинного слова. Биты могут быть доступны индивидуально через обычную индексирующую нотацию (A[3]), а также через все обычные примитивные функции и операторы, где они часто обрабатываются с использованием специального алгоритма, например, суммирования битов через табличный поиск байтов. Битовые поля языка программирования C, псевдообъекты, находящиеся в структурах с размером, равным некоторому числу битов, фактически являются небольшими битовыми массивами; они ограничены тем, что не могут охватывать слова. Хотя они предоставляют удобный синтаксис, биты по-прежнему доступны с помощью побитовых операторов на большинстве машин, и их можно определять только статически (как статические массивы в C, их размеры фиксируются во время компиляции). Также распространена практика среди программистов на C использовать слова как небольшие битовые массивы и получать доступ к их битам с помощью побитовых операторов. Широко доступный заголовочный файл, включенный в систему X11, xtrapbits.h, представляет собой «переносимый способ для систем определения манипулирования битовыми полями массивов битов». Более подробное описание вышеупомянутого подхода можно найти в часто задаваемых вопросах по компиляции.lang.c. В C++, хотя отдельные bool обычно занимают то же пространство, что и байт или целое число, тип STL vector<bool> является частичной специализацией шаблона, в которой биты упаковываются в качестве оптимизации использования памяти. Поскольку байты (а не биты) являются наименьшей адресуемой единицей в C++, оператор [] не возвращает ссылку на элемент, а вместо этого возвращает прокси-ссылку. Это может показаться незначительным моментом, но это означает, что vector<bool> не является стандартным контейнером STL, поэтому использование vector<bool> обычно не рекомендуется. Другой уникальный класс STL, bitset, поддерживает произвольный доступ и побитовые операторы, может быть итерирован, а его свойство Length может быть изменено для увеличения или усечения. Хотя Standard ML не поддерживает битовые массивы, Standard ML of New Jersey имеет расширение, структуру BitArray, в своей библиотеке SML/NJ. Он не имеет фиксированного размера и поддерживает операции над множествами и побитовые операции, включая, в необычном случае, операции сдвига. В Haskell также отсутствует стандартная поддержка побитовых операций, но GHC и Hugs предоставляют модуль Data.Bits с различными побитными функциями и операторами, включая операции сдвига и вращения, и массив "неупакованных" булевых значений может использоваться для моделирования битового массива, хотя это не поддерживается предыдущим модулем. В Perl строки можно использовать как расширяемые битовые массивы. Ими можно манипулировать с помощью обычных побитовых операторов (~ | & ^), а отдельные биты можно проверять и устанавливать с помощью функции vec. В Ruby можно получить доступ (но не установить) к биту целого числа (Fixnum или Bignum) с помощью оператора квадратных скобок ([]), как если бы это был массив битов. Библиотека Core Foundation от Apple содержит структуры CFBitVector и CFMutableBitVector. PL/I поддерживает массивы битовых строк произвольной длины, которые могут быть либо фиксированной длины, либо переменной. Элементы массива могут быть выровнены — каждый элемент начинается с границы байта или слова — или не выровнены — элементы следуют друг за другом непосредственно без отступов. PL/pgSQL и SQL в PostgreSQL поддерживают битовые строки как встроенный тип. Существует два типа битов SQL: bit(n) и bit varying(n), где n — положительное целое число. Языки описания аппаратуры, такие как VHDL, Verilog и SystemVerilog, изначально поддерживают битовые векторы, поскольку они используются для моделирования элементов хранения, таких как триггеры, аппаратные шины и аппаратные сигналы в целом. В языках проверки аппаратуры, таких как OpenVera, e и SystemVerilog, битовые векторы используются для выборки значений из аппаратных моделей и для представления данных, передаваемых на аппаратное обеспечение во время моделирования. Common Lisp предоставляет реализацию одномерного битового вектора как специальный случай встроенного массива, действующего в двойном качестве класса и спецификатора типа. Будучи производным от массива, он полагается на общую функцию make-array для настройки с типом элемента bit, что необязательно позволяет указать битовый вектор как динамически изменяемый по размеру. Однако битовый вектор не имеет бесконечной протяженности. Существует более ограниченный простой тип битового вектора, который явно исключает динамические характеристики. Битовые векторы представлены как и могут быть построены более лаконично с помощью макроса reader #*bits. В дополнение к общим функциям, применимым ко всем массивам, существуют специальные операции для битовых векторов. Отдельные биты можно получать и изменять с помощью функций bit и sbit, а также поддерживается большое количество логических операций.

The APL programming language fully supports bit arrays of arbitrary shape and size as a Boolean datatype distinct from integers. All major implementations (Dyalog APL, APL2, APL Next, NARS2000, Gnu APL, etc.) pack the bits densely into whatever size the machine word is. Bits may be accessed individually via the usual indexing notation (A[3]) as well as through all of the usual primitive functions and operators where they are often operated on using a special case algorithm such as summing the bits via a table lookup of bytes. The C programming language's bit fields, pseudo objects found in structs with size equal to some number of bits, are in fact small bit arrays; they are limited in that they cannot span words. Although they give a convenient syntax, the bits are still accessed using bytewise operators on most machines, and they can only be defined statically (like C's static arrays, their sizes are fixed at compile time). It is also a common idiom for C programmers to use words as small bit arrays and access bits of them using bit operators. A widely available header file included in the X11 system, xtrapbits. h, is “a portable way for systems to define bit field manipulation of arrays of bits.” A more explanatory description of aforementioned approach can be found in the comp. lang. c faq. In C++, although individual bools typically occupy the same space as a byte or an integer, the STL type vector<bool> is a partial template specialization in which bits are packed as a space efficiency optimization. Since bytes (and not bits) are the smallest addressable unit in C++, the [] operator does not return a reference to an element, but instead returns a proxy reference. This might seem a minor point, but it means that vector<bool> is not a standard STL container, which is why the use of vector<bool> is generally discouraged. Another unique STL class, bitset, The class supports random access and bitwise operators, can be iterated over, and its Length property can be changed to grow or truncate it. Although Standard ML has no support for bit arrays, Standard ML of New Jersey has an extension, the BitArray structure, in its SML/NJ Library. It is not fixed in size and supports set operations and bit operations, including, unusually, shift operations. Haskell likewise currently lacks standard support for bitwise operations, but both GHC and Hugs provide a Data. Bits module with assorted bitwise functions and operators, including shift and rotate operations and an "unboxed" array over boolean values may be used to model a Bit array, although this lacks support from the former module. In Perl, strings can be used as expandable bit arrays. They can be manipulated using the usual bitwise operators (~ | & ^), and individual bits can be tested and set using the vec function. In Ruby, you can access (but not set) a bit of an integer (Fixnum or Bignum) using the bracket operator ([]), as if it were an array of bits. Apple's Core Foundation library contains CFBitVector and CFMutableBitVector structures. PL/I supports arrays of bit strings of arbitrary length, which may be either fixed length or varying. The array elements may be aligned— each element begins on a byte or word boundary— or unaligned— elements immediately follow each other with no padding. PL/pgSQL and PostgreSQL's SQL support bit strings as native type. There are two SQL bit types: bit(n) and bit varying(n), where n is a positive integer. Hardware description languages such as VHDL, Verilog, and SystemVerilog natively support bit vectors as these are used to model storage elements like flip flops, hardware busses and hardware signals in general. In hardware verification languages such as OpenVera, e and SystemVerilog, bit vectors are used to sample values from the hardware models, and to represent data that is transferred to hardware during simulations. Common Lisp provides a one dimensional bit vector implementation as a special case of the built in array, acting in a dual capacity as a class and a type specifier. Being a derivative of the array, it relies on the general make array function to be configured with an element type of bit, which optionally permits the bit vector to be designated as dynamically resizable. The bit vector, however, is not infinite in extent. A more restricted simple bit vector type exists, which explicitly excludes the dynamic characteristics. Bit vectors are represented as, and can be constructed in a more concise fashion by, the reader macro #*bits. In addition to the general functions applicable to all arrays, dedicated operations exist for bit vectors. Single bits may be accessed and modified using the bit and sbit functions and an extensive number of logical operations is supported.