Упаковка символов в 5 бит и запись результатов в файл (C ++)
У меня есть вектор, содержащий символы. Эти символы могут быть только 26 прописными буквами алфавита, следовательно, число битов, представляющих эти символы, может быть уменьшено с 8 до 5. Затем мне нужно записать результаты в файл, который будет использоваться позже.
В настоящее время я думаю, что 3 старших значащих бита одинаковы для A..Z, поэтому я мог бы использовать 5 младших значащих бит для уникальной идентификации символов? Однако я изо всех сил пытаюсь записать эти неформатированные данные в файл.
Как мне поступить так и записать результат в файл?
Решение
Чтобы уменьшить символ до 5 бит, вы можете использовать либо ch или же
& 0x1Fch - 'A'; ни один не будет работать с EBCDIC, но это
скорее всего, не проблема. (Если это так: поиск таблицы в строке
все заглавные буквы, возвращающие индекс, могут быть использованы.)
После этого все усложняется. Самое простое решение — это
определить битовый массив, что-то вроде:
class BitArray
{
std::vector<unsigned char> myData;
int byteIndex( int index ) { return index / 8; }
unsigned char bitMask( int index ) { return 1 << (index % 8); }
int byteCount( int bitCount )
{
return byteIndex( bitCount )
+ (bitIndex( bitCount) != 0 ? 1 : 0);
}
public:
BitArray( int size ) : myData( byteCount( size ) ) {}
void set( index )
{
myData[byteIndex( index )] |= bitMask( index );
}
void reset( index )
{
myData[byteIndex( index )] &= ~bitMask( index );
}
bool test( index )
{
return (myData[byteIndex( index ) & bitMask( index )) != 0;
}
};
(Вам нужно больше для извлечения данных, но я не уверен в том, что
формат вам нужен.)
Затем вы перебираете строку:
BitArray results( 5 * s.size() );
for ( int index = 0; index != s.size(); ++ index ) {
for ( int pos = 0; pos != 5; ++ pos ) {
results.set( 5 * index + pos );
}
}
Это будет работать без проблем. Когда я пытался использовать его (или
скорее эквивалент) в далеком прошлом (для Хаффмана
кодирование, в C, так как это было в 1980-х годах), это также было
слишком медленно. Если ваши строки довольно короткие, сегодня это может быть
достаточно. В противном случае вам понадобится более сложный
алгоритм, который отслеживает, сколько битов уже используется
в последнем байте, и делает соответствующие сдвиги и маски для
вставьте как можно больше битов за один раз: максимум две смены и
или операций на вставку, а не 5, как здесь.
Это то, что я в конечном итоге использовал. (Но у меня нет кода
больше, поэтому я не могу легко опубликовать пример.)
Другие решения
Ты можешь сделать это? Конечно.
Я думаю, что вы будете более успешны и просты, просто используя gzip для записи сжатого файла.
У меня есть вектор [символов, которые] могут быть только 26 заглавными буквами алфавита
Вы можете относительно легко его кодировать: разбить текст на блоки из восьми символов и записать закодированный текст в блоки из пяти байтов, например так:
76543210 76543210 76543210 76543210 76543210 76543210 76543210 76543210
ORIGINAL: 000AAAAA 000BBBBB 000CCCCC 000DDDDD 000EEEEE 000FFFFF 000GGGGG 000HHHHH
76543210 76543210 76543210 76543210 76543210
ENCODED: AAAAABBB BBCCCCCD DDDDEEEE EFFFFFGG GGGHHHHH
Если у вас недостаточно символов для вашего последнего блока, используйте символ «pad» (все), который не используется для кодирования любой из 26 букв.
Наименьшая единица данных, с которой вы можете работать, составляет 8 бит. Вам придется использовать сдвиги битов, но вы можете читать / записывать данные только в группах по 8 бит, поэтому вам понадобится дополнительная логика, чтобы справиться с этим. Если ваш ввод содержит не менее 8 5-битных букв, объедините 8 букв за раз, чтобы получить в общей сложности 40 битов, и запишите это в файл как 5 8-битных байтов. Продолжайте по мере необходимости, пока у вас не останется менее 8 5-битных букв, затем объедините их, добавьте остаток к четному кратному 8 и запишите его в файл.
Вы можете дать мой PackedArray код попробовать.
Он реализует контейнер произвольного доступа, где элементы упакованы на уровне битов. Другими словами, он действует так, как если бы вы могли манипулировать, например, uint9_t или же uint17_t массив:
PackedArray principle:
. compact storage of <= 32 bits items
. items are tightly packed into a buffer of uint32_t integers
PackedArray requirements:
. you must know in advance how many bits are needed to hold a single item
. you must know in advance how many items you want to store
. when packing, behavior is undefined if items have more than bitsPerItem bits
PackedArray general in memory representation:
|-------------------------------------------------- - - -
| b0 | b1 | b2 |
|-------------------------------------------------- - - -
| i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 |
|-------------------------------------------------- - - -
. items are tightly packed together
. several items end up inside the same buffer cell, e.g. i0, i1, i2
. some items span two buffer cells, e.g. i3, i6