Я читаю «Классические задачи по информатике в Python» Дэвида Копека, чтобы изучить алгоритмы CS.
Одна из первых задач — сжатие генов, где цель — закодировать строку нуклеотидов («ACGTA…») в двоичный код, чтобы уменьшить ее размер в памяти.
Сжатые данные хороши тем, что меньше нужно скачивать и загружать, получая при этом то же информационное содержание.
Свойство нуклеотидов ограничиваться набором из четырех букв «A», «C», «G» и «T» позволяет кодировать их с помощью простых целых чисел — 0, 1, 2, 3.
Хранение чисел более эффективно с точки зрения памяти, чем хранение строк, которые представляют собой наборы байтов, представляющих уникальные символы в UTF-8 или ASCII.
Хотя в книге алгоритм сжатия/декомпрессии реализован на языке Python, я подумал, что будет хорошим обучающим упражнением написать его на языке Go и представить обзор двоичных чисел.
Основы двоичных чисел
Для представления чисел в большинстве ситуаций мы обычно используем целочисленные значения по основанию 10. Однако основание 10 является громоздким, когда вы хотите моделировать данные с помощью аппаратных средств, таких как переключатели в состоянии «включено/выключено».
Но основание 2 можно легко смоделировать с помощью переключателей, и это естественным образом подходит для компьютеров.
| Десятичная дробь | Расширение основания 2 | Двоичная |
|---|---|---|
| 0 | 0 (20) | 0 |
| 1 | 1 (20) | 1 |
| 2 | 1 (21) + 0 (20) | 10 |
| 3 | 1 (21) + 1 (20) | 11 |
| … | … | … |
| 7 | 1 (22) + 1 (21) + 1 (20) | 111 |
| 8 | 1 (23) + 0 (22) + 0 (21) + 0 (20) | 1000 |
Коэффициенты степеней дают двоичное представление десятичного числа.
Двоичные операции в Go
Мы можем немного поразвлечься с двоичными операциями в Go.
Двоичные литералы записываются с префиксом 0b, например 0b101.
Игровая площадка для двоичных операций
package main
import "fmt"
func main() {
fmt.Println(0b11) // 3
fmt.Println(0b11 == 3) // true
fmt.Println(0b1000 == 8) // true
// Left shift moves the bits to the left, introducing 0s on the right,
// increasing the number
fmt.Println(0b10 << 1) // 4 i.e 100
fmt.Println(0b1 << 2) // also 4
fmt.Println(0b1<<2 == 0b10<<1) // true
// Right shift moves the bits to the right, losing columns and reducing the number.
fmt.Println(0b011>>1 == 1) // true
fmt.Println(0b1111 >> 2) // 3 i.e. 11
fmt.Println(0b1110>>2 == 3) // true
// ANDing with & produces a 1 where both columns are 1, else 0.
fmt.Println(0b110&0b100 == 0b100) // true
fmt.Println(0b01&0b00 == 0) // true
// ORing with | produces a 1 where either column or both are 1, else 0.
fmt.Println(0b11|0b01 == 0b11) // true
fmt.Println(0b100|0b011 == 0b111) // true
// ExclusiveORing with ^ produces a 1 only where columns are unequal, else 0.
fmt.Println(0b11^0b00 == 0b11) // true
fmt.Println(0b100^0b101 == 0b1) // true
}
Алгоритм сжатия генов
Двоичные операции действительно сияют, когда применяются к проблеме сжатия генов.
Давайте приступим.
mkdir geneCompression
cd geneCompression
Создайте файл main.go с типом CompressedGene.
package main
type CompressedGene struct {
bits int
}
Мы создадим функцию-конструктор и частный метод compress, который вызывается внутри конструктора для хранения гена в качестве поля bits.
func (cg *CompressedGene) compress(gene string) error {
cg.bits = 1 // sentinel value so we can store 00 and 01 as first nucleotide
for _, nucleotide := range strings.ToUpper(gene) {
cg.bits = cg.bits << 2 // left shift by 2 to introduce 00
switch nucleotide {
case 'A':
cg.bits |= 0b00
case 'C':
cg.bits |= 0b01
case 'G':
cg.bits |= 0b10
case 'T':
cg.bits |= 0b11
default:
return fmt.Errorf("Invalid nucleotide: %c", nucleotide)
}
}
return nil
}
// NewCompressedGene provides a compressed gene struct reference.
func NewCompressedGene(gene string) (*CompressedGene, error) {
cg := CompressedGene{}
err := cg.compress(gene)
if err != nil {
return nil, err
}
return &cg, nil
}
Для сжатия мы начинаем с 1 в качестве сентинельного значения. Начало с 0 привело бы к потере генов, если бы мы добавили 00 или 01 в качестве первых элементов, поскольку ведущие нули игнорируются в двоичных выражениях.
Для создания двух столбцов для хранения гена выполняется сдвиг влево. С помощью оператора or equals |= изменяем значение крайних правых битов в соответствии с геном и сохраняем его.
Декомпрессия будет обратна методу сжатия.
// Decompress expands the bits into a string.
func (cg *CompressedGene) Decompress() (string, error) {
gene := ""
// bitLength - 1 to ignore sentinel value
for i := 0; i < bitLength(cg.bits)-1; i += 2 {
rightShifted := cg.bits >> i
fmt.Printf("Rightshifted by %d - %bn", i, rightShifted)
// get the two rightmost bits
rightPair := rightShifted & 0b11
switch rightPair {
case 0b00:
gene += "A"
case 0b01:
gene += "C"
case 0b10:
gene += "G"
case 0b11:
gene += "T"
default:
return "", fmt.Errorf("Invalid bits: %d", rightPair)
}
}
return reverse(gene), nil
}
func bitLength(n int) int {
return int(math.Floor(math.Log2(float64(n))) + 1)
}
func reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}
Мы используем вспомогательную функцию bitLength для определения количества бит в целочисленном значении и функцию reverse для обратного преобразования расширенной строки. Поскольку мы идем справа налево, превращая биты в гены, построенная нами строка является обратной исходной. Вот почему необходим последний шаг — реверсирование строки.
Мы можем проверить, что все работает так, как ожидалось!
func main() {
gene := "ACGT"
fmt.Printf("Original gene: %sn", gene)
compressed, err := NewCompressedGene(gene)
if err != nil {
log.Fatalln(err)
}
fmt.Printf("Bits: %bn", compressed.bits)
decompressed, err := compressed.Decompress()
if err != nil {
log.Fatalln(err)
}
fmt.Printf("Matches original gene: %vn", decompressed == gene)
}
go run main.go
Original gene: ACGT
Bits: 100011011
Rightshifted by 0 - 100011011
Rightshifted by 2 - 1000110
Rightshifted by 4 - 10001
Rightshifted by 6 - 100
Matches original gene: true
Единственная проблема с этим алгоритмом заключается в том, что он не работает для больших последовательностей строк.
Если изменить значение gene и повторить запуск — мы получим совершенно неожиданные результаты.
func main() {
gene := strings.Repeat("TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATA", 100)
compressed, err := NewCompressedGene(gene)
if err != nil {
log.Fatalln(err)
}
fmt.Printf("Bits: %bn", compressed.bits)
decompressed, err := compressed.Decompress()
if err != nil {
log.Fatalln(err)
}
fmt.Printf("Matches original gene: %vn", decompressed == gene)
}
Большие генные строки вызовут проблемы с этим алгоритмом, потому что наше поле bits int легко переполнится, как только мы достигнем его 64-битного предела! Тип int в go — это 32 или 64 бита в зависимости от базовой системы. Но мы определенно не хотим такого ограничения, поэтому нам придется использовать могущественный big.Int.
Использование big.Int
Тип big.Int не поддерживает символы двоичных операций, таких как & и <<, но у него есть методы, которые делают то же самое.
Мы можем использовать методы Or, And, Lsh (сдвиг влево) и Rsh (сдвиг вправо) для нашей логики.
// CompressedGene models a compressed format gene sequence
type CompressedGene struct {
bits *big.Int
}
func (c *CompressedGene) compress(gene string) error {
c.bits = big.NewInt(1) // sentinel value
for _, nucleotide := range strings.ToUpper(gene) {
c.bits.Lsh(c.bits, 2)
switch nucleotide {
case 'A':
c.bits.Or(c.bits, big.NewInt(0b00))
case 'C':
c.bits.Or(c.bits, big.NewInt(0b01))
case 'G':
c.bits.Or(c.bits, big.NewInt(0b10))
case 'T':
c.bits.Or(c.bits, big.NewInt(0b11))
default:
return fmt.Errorf("Invalid nucleotide: %c", nucleotide)
}
}
return nil
}
// Decompress expands the compressed bit sequence into
// a string of nucleotides A,C,G,T.
func (c *CompressedGene) Decompress() (string, error) {
gene := ""
// bitlen - 1 to ignore sentinel value
for i := 0; i < c.bits.BitLen()-1; i += 2 {
rightShifted := &big.Int{} // local value to not mutate the original
rightShifted.Rsh(c.bits, uint(i))
// Getting the two, rightmost bits.
rightBits := (rightShifted.And(rightShifted, big.NewInt(0b11))).Uint64()
switch rightBits {
case 0b00:
gene += "A"
case 0b01:
gene += "C"
case 0b10:
gene += "G"
case 0b11:
gene += "T"
default:
return "", fmt.Errorf("Invalid bits: %d", rightBits)
}
}
return reverse(gene), nil
}
Конструктор остается прежним.
Давайте настроим главную функцию на вывод размеров байтов, чтобы мы могли оценить ценность этого алгоритма сжатия.
func main() {
s := strings.Repeat("TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATA", 100)
c, err := NewCompressedGene(s)
if err != nil {
log.Fatalln(err)
}
fmt.Printf("String bytes: %dn", len([]byte(s)))
fmt.Printf("Compressed bytes: %dn", len(c.bits.Bytes()))
d, err := c.Decompress()
if err != nil {
log.Fatalln(err)
}
fmt.Printf("Matches original gene: %vn", d == s)
}
go run main.go
String bytes: 8600
Compressed bytes: 2151
true
Вот так! Мы сэкономили довольно много памяти, закодировав гены в большой int.
Реализовав этот алгоритм в Go, мы узнали о типе Go big.Int и применении двоичных операций для кодирования данных с целью сжатия.
Для меня это была забавная демонстрация того, насколько интересными могут быть вычислительные задачи и какие изобретательные способы их решения существуют.
Мне не терпится найти и реализовать остальные алгоритмы из этой книги!