Упаковка символов в 5 бит и запись результатов в файл (C ++)

У меня есть вектор, содержащий символы. Эти символы могут быть только 26 прописными буквами алфавита, следовательно, число битов, представляющих эти символы, может быть уменьшено с 8 до 5. Затем мне нужно записать результаты в файл, который будет использоваться позже.

В настоящее время я думаю, что 3 старших значащих бита одинаковы для A..Z, поэтому я мог бы использовать 5 младших значащих бит для уникальной идентификации символов? Однако я изо всех сил пытаюсь записать эти неформатированные данные в файл.

Как мне поступить так и записать результат в файл?

0

Решение

Чтобы уменьшить символ до 5 бит, вы можете использовать либо ch
& 0x1F
или же ch - '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, как здесь.
Это то, что я в конечном итоге использовал. (Но у меня нет кода
больше, поэтому я не могу легко опубликовать пример.)

1

Другие решения

Ты можешь сделать это? Конечно.

Я думаю, что вы будете более успешны и просты, просто используя gzip для записи сжатого файла.

0

У меня есть вектор [символов, которые] могут быть только 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 букв.

0

Наименьшая единица данных, с которой вы можете работать, составляет 8 бит. Вам придется использовать сдвиги битов, но вы можете читать / записывать данные только в группах по 8 бит, поэтому вам понадобится дополнительная логика, чтобы справиться с этим. Если ваш ввод содержит не менее 8 5-битных букв, объедините 8 букв за раз, чтобы получить в общей сложности 40 битов, и запишите это в файл как 5 8-битных байтов. Продолжайте по мере необходимости, пока у вас не останется менее 8 5-битных букв, затем объедините их, добавьте остаток к четному кратному 8 и запишите его в файл.

0

Вы можете дать мой 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
0