【Python】簡単な圧縮（DNA遺伝子を例に）

この記事は、オライリー社の書籍「Python計算機科学新教本」を学習した時の備忘録です。

簡単な圧縮

仮想空間でも実空間でも、空間を節約した方が、効率的でお金もかかりません。

圧縮は、データを符号化（形式を変更）してメモリ使用量を抑えることである。

解凍（展開）は、逆操作で、元の形式にデータを戻すことである。

話を元に戻します。
圧縮は効率的なのに、なぜ、あらゆるデータが圧縮されていないのでしょうか？

その理由は、時間と空間のトレードオフがあるからです。

データを圧縮して元のデータに解凍するには時間がかかります。

よって、データ圧縮は、実行の高速性ではなく、サイズを抑えることが重要な状況の場合に、圧縮する意味があります。

Pythonオブジェクトのメモリ消費量は、関数sys.getsizeof()でわかります。

DNAの遺伝子を構成するヌクレオチドを考えましょう。

ヌクレオチドには、A,C,G,Tの4つの値しかありません。

遺伝子をUnicode文字の集まりである文字列型strとして格納するなら、ヌクレオチド1つは文字で表されるので、一般に8ビット分のメモリ量を必要とします。

バイナリでは、値が4つの型を表すのに2ビットあれば十分です。

ヌクレオチドをstrで表す代わりに、ビット列で表すことができます。

ビット列とは、１と０のシーケンスです。

Python標準ライブラリには、任意長のビット列を扱う適当なものがありません。

str文字列をビット列に

次のコードでは、A,C,G,Tからなるstrをビット列に変換したり、戻したりします。
ビット列はintに格納されます。

strに戻すために、Pythonの特殊メソッド _ _str_ _( )を実装します。

コード：

class CompressedGene:

def __init__(self, gene: str) -> None:
    self._compress(gene)

# _（アンダースコア）は、クラス外部から使用すべきではないメソッドであることを示す。

def _compress(self, gene: str) -> None:
    self.bit_string: int = 1 #番兵で開始
    for nucleotide in gene.upper():
        self.bit_string <<= 2 #2ビット左シフト
        if nucleotide == "A": #末尾2ビットを00に設定
           #ヌクレオチドは、or演算子|=を使って追加する。
           #左シフトの後に、00をビット列に追加する。
            self.bit_string |= 0b00
        elif nucleotide == "C": #末尾2ビットを01に設定
            self.bit_string |= 0b01
        elif nucleotide == "G": #末尾2ビットを10に設定
            self.bit_string |= 0b10
        elif nucleotide == "T": #末尾2ビットを11に設定
            self.bit_string |= 0b11
        else:
            raise ValueError("Invalid Nucleotide:{}".format(nucleotide))

    def decompress(self) -> str:
        #decompressは、ビット列を2ビットずつ読み込みます。
        #その2ビットを使って遺伝子のstr表現の末尾にどの文字を追加するか決定します。
        gene: str = ""
        for i in range(0, self.bit_string.bit_length() - 1, 2): # -1で番兵を除外
            bits: int = self.bit_string >> i & 0b11 #肝心の2ビットだけ
            if bits == 0b00: #A
                gene += "A"
            elif bits == 0b01: #C
                gene += "C"
            elif bits == 0b10: #G
                gene += "G"
            elif bits == 0b11: #T
                gene += "T"
            else:
                raise ValueError("Invalid bits:{}".format(bits))
        return gene[::-1] #[::-1]は、逆向きスライスで文字列を反転

    def __str__(self) -> str: #プリティプリント用の表現
        return self.decompress()

#元データの定義と結果の表示
if __name__ == "__main__":
    from sys import getsizeof
    original: str = "TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAG
GGATTAACCGTTATATATATATAGCCATGGATCGATTATA" * 100
    print("original is {} bytes".format(getsizeof(original)))

    compressed: CompressedGene = CompressedGene(original) #圧縮
    print("compressed is {} bytes".format(getsizeof(compressed.bit_string)))
    print(compressed) #解凍
    print("original and decompressed are the same: {}".format(original == compressed.decompress()))

 

まとめ

関数_compressでは、str型のACGTをビット列に変換しています。

関数decompressでは、ビット列をstr型のACGTへ戻しています。

最後に、originalとcompressedの実行結果を比較できるように、表示しています。