Каков наиболее эффективный способ кодирования символа? (что касается памяти) - PullRequest
Новая
       7

Каков наиболее эффективный способ кодирования символа? (что касается памяти)

0 голосов
/ 08 ноября 2019

У меня есть 4 символа, которые я хочу закодировать: есть ли способ дать им «закодированную версию» вместо ASCII? Двоичный файл был бы лучшим, но у меня есть только 0 и 1 для двоичного файла, и если бы я тогда использовал последовательность, было бы непонятно, какой символ равен 0, а какой 1, а какой 11, например. Есть ли другой способ эффективно кодировать с минимальным количеством битов? Спасибо

1 Ответ

1 голос
/ 08 ноября 2019

Есть 4 разных значения. 2 бита могут кодировать 4 значения. 

00
01
10
11

Это означает, что каждый байт может кодировать 4 различных значения. 

+---+---+---+---+---+---+---+---+
| 4 | 4 | 3 | 3 | 2 | 2 | 1 | 1 |
+---+---+---+---+---+---+---+---+

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

T = 00
G = 01
A = 10
C = 11

110 (0b01101110), следовательно, будет означать ACAG (при условии, что первое значение найдено в младших значащих битах). 

+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
+---+---+---+---+---+---+---+---+
 ---G--- ---A--- ---C--- ---A---

Это означает, что строка будет использовать только 25% отпространство, используемое при использовании ASCII.

За исключением того, что это не совсем работает. Нет способа узнать длину последовательности. Например, как бы вы кодировали ACA с использованием приведенной выше схемы?

Существуют варианты:

  1. Каким-то образом префикс последовательности по ее длине.

    Это может привести к удвоению длины закодированной строки, если она действительно короткая.

  2. Введите 5-е значение часового значения, указывающее конец строки.

    Thisусложняет кодирование (поскольку у нас больше нет степени 2). Это также уменьшает коэффициент сжатия (8 значений на 3 байта, что составляет всего лишь 37,5% пространства, используемого при использовании ASCII).

  3. Используйте первые 2 бита каждого байта для указаниясколько значений на самом деле присутствует в байте. Это уменьшает коэффициент сжатия (3 значения на байт, так что всего лишь 33% пространства используется при использовании ASCII).

  4. Вы можете использовать реальные методы сжатия (например, использовать частотный анализиспользовать более короткие последовательности для более распространенных подпоследовательностей), возможно, используя zlib или более современный эквивалент. Этот метод очень эффективен (возможно, даже используя 1/10 от того, что было бы в ASCII), но он эффективен, только если у вас очень длинные последовательности. Это также предотвращает произвольный доступ. Это означает, что не может получить значение Nth без предварительного чтения всего предыдущего. Короче говоря, вам нужно будет декодировать строку в ASCII, чтобы найти ее.

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

...