MNTSQ Techブログ

リーガルテック・カンパニー「MNTSQ（モンテスキュー）」のTechブログです。

トップ > Pythonで省メモリに大量の文字列を扱う工夫

Pythonで省メモリに大量の文字列を扱う工夫

MNTSQ Tech Blog TOP > 記事一覧 > Pythonで省メモリに大量の文字列を扱う工夫

f:id:mntsq:20210519194058p:plain

たくさんの文字列（や離散的な符号列）をメモリに載せないといけないんだけど、いろんな制約があって通常のList[str]では載らない…ということありませんか？（まぁあんまりなさそうですね） たまたまそういうことがあったので、その際に検討した内容をまとめておきます

TL;DR

  • メモリをもっと増やしましょう
    • 富豪的に解決できるならいつでもそれが最高です

しかし、世の中それでなんとかならんこともたくさんあります

  1. 用途があうのであれば専用のデータ構造を採用する

    • 例えばもし共通のprefixやsuffixが存在し、順序に興味がなければtrie treeなどが使えます
      • 例えば、弊社であれば、法人名をメモリに持ちたいなんてときもあります。そういうときに法人名の辞書をtrieで持ったりすることがあります
        • 「株式会社」「一般財団法人」や「銀行」といった共通語がたくさんでてくるのでtrie treeでごりごり削れます
    • pygtrieとかmarisa-trieとかが簡単に使えます
    • 他にも様々なデータ構造はあるので、そういうものが使える場合もあるかもしれません

  2. 短い文字列が大量にある場合は、とりあえず結合し、各文字列の始点のindexをnumpyのint arrayで持つ

    • Pythonでは1つobjectを作るために50byte程度が消費されます。そしてPythonの配列はobjectのポインタの配列であり、配列の要素の数だけメモリ上の別の場所にobjectが存在しています
    • したがって、短い文字列を大量に配列で抱えていると、配列内のobjectのポインタ(8byte) + objectを作るためのオーバーヘッド(50byte程度) で大量のメモリが浪費されます
    • 長大な1つのstringのobjectと、indexを持つnumpy array配列であれば、これらの浪費は起きません
      • numpy arrayは要素も含めて1つのobjectになっています

  3. 固定長であれば、numpyのmatrixで持つ

    • 固定長の文字列であれば、numpyの2次元配列が活用できるかもしれません。
      • この場合、固定長であることを利用して、indexの配列が不要になります

  4. str型/bytes型の範囲で工夫する

    • Python3.3以降のstrは含まれる文字の範囲によって、1,2,4byte/文字を使い分けてくれます
      • たとえば、ASCIIであらわせる範囲の文字列だけしか含まれない場合、すべての文字が1byte/文字になりますし、ひらがな等の範囲の文字が含まれれば、すべての文字が2byte/文字になります。絵文字が含まれると4byte/文字になるイメージですね
    • したがって、絵文字などを削除してstrを作り直せば、日本語が含まれていても多くの文字列は2byte/文字にはできる可能性があります
    • さらに、bytes型にencodeする手法でもっと圧縮できる場合があります
      • strのエンコーディングはUTF-8であると思いがちですが、strはunicodeのコードポイントをそのまま保存しているのでUTF-8/16/32のどれにも直接対応しているわけではありません。UTF-8やUTF-16は可変長エンコーディングであり、strのように1文字でもASCIIでない文字が入ったら全部2byte or 4byte / 文字になります、みたいなことはなくいい感じに圧縮して出してくれます
      • 扱う文字列にあったencodingを選択することで、圧縮が可能です

  5. 使われる文字が決まっている場合は、bit単位での表現を用いることでメモリを削減できる

    • さらに、出現する文字列の範囲を制限すればメモリを削減できるというアイデアは、1byte単位ではなくbit単位で適用することができます
    • このような場合にはbitarrayを使えます。例えば、塩基配列であれば2bitで1文字を表すことができますが、bitarrayでは(変換処理が入るために)CPU時間を犠牲にコレを実現できます
      • この記事では、ここのコードを載せます

細かく見ていくと…

さて、まとめとしてはこれくらいなのですが、以下、2,3,4,5のところについて詳しくみていきます

モチベーション: PythonのList / numpyの文字列型は意外とメモリを食う

まず、いろいろな形式で保存した際のメモリサイズを測定してみましょう。

突然ですが、Pythonにおいて以下の文字列のメモリサイズは何byteでしょうか？ナイーブに考えると、char型で表現するとして、”a”は1byte、[“a”,”b”]は2byteですね

クイズ
  1. "a"
  2. ["a","b"]
  3. np.array(["a","b])
  4. np.array(["a","bc"])
こたえ
  • 1: 50byte
>>> import sys 
>>> sys.getsizeof("a")
50

でっかいですね！これはPythonにはGCなどもついているので、各オブジェクトにそのための参照カウンタなどがついていたりするからです

  • 2: 172byte
>>> sys.getsizeof(["a","b"]) + sys.getsizeof("a") + sys.getsizeof("b")
172

超でかいですね！ なぜこの計算になるかというと、PythonのListはそれぞれのオブジェクトへのポインタの配列となっているからです。 以下のように、普通にgetsizeofをすると72byteに見えるのですが、先述の通り、ポインターの配列なので、これには”a”や”b”といった中身のメモリが含まれてないんですよね。

なので、文字を増やしても同じ長さです

>>> sys.getsizeof(["a","b"])
72
>>> sys.getsizeof(["alphabet","beta"])
72

要素数に合わせて、PyObjectへのポインター(8byte)が増えていっているのがわかりますね

>>> sys.getsizeof([])
56
>>> sys.getsizeof([0])
64
>>> sys.getsizeof([0,1])
72
  • 3: 112byte

numpyのarrayは1つのobjectとしてまるっと測定できます

>>> import numpy as np
>>> sys.getsizeof(np.array(["a","b"]))
112

1つの要素を増やすごとに4byte = 32bitを使ってますね

>>> sys.getsizeof(np.array(["a","b","c"]))
116
>>> sys.getsizeof(np.array(["a","b"]))
112
>>> sys.getsizeof(np.array(["a"]))
108

numpyの配列は、要素数を増やせばほとんどPythonのobjectのオーバーヘッドは考えなくて良くなりそうです

  • 4: 112byte

かといってなんでもnumpyにstrをつっこめばいいかというとそうではありません。 1文字増やしただけなのに、8byte = 64bit増えました。

>>> sys.getsizeof(np.array(["a","bc"]))
120

なぜかというと、実は、dtypeが”<U1”から”<U2”に変わっているからです。UはUnicodeという意味で、1は文字数です。numpyは行列演算ライブラリですから、各要素のメモリ上のサイズは一緒になるようにレイアウトすることが前提になっています。今まではUnicodeを1文字扱えるメモリを確保して各要素を扱っていたのが、2文字のデータが入ってくるようになったので、すべての要素を2文字でようにしているわけですね。結果として、4byte x 2要素分 = 8byte確保されたメモリが増えたのでした。ASCIIの文字列の範囲でも1文字が4byteなのは、冒頭に述べたようなPython3.3以降の工夫などを採用せず、numpyではすべての文字をコードポイントそのまま、つまりint32的に扱っているからのようですね。行列演算ライブラリとしての設計上の要請だと思いますが。

データによって型が決まるのはこのときだけで、この後に長い文字列を追加しても自動的に型が変わるわけではありません。以下のようにU2の配列だと3文字目は落ちてしまいますね

>>> arr = np.array(["a","b","cd"])
>>> arr[0] = "aaa"
>>> arr
array(['aa', 'b', 'cd'], dtype='<U2')

さて、長々書いてきましたが、こういう感じなので、すっと思いつくコンテナはこういう欠点がありそうなことがわかります

  • Listで持つとPythonのObjectのオーバーヘッドが大きいため、要素数が多いとメモリを浪費する(1objectあたり50byteとかそういうオーダー)
  • numpyの文字列型は文字列の最大長x4byteのメモリを確保する

Listに関しては、長文であればまぁ別に良いとも言えますが、文ごとに配列に持っているみたいな場合だと、実は数十パーセントがPython関連のメモリに使われてしまいます。心理学の日本語論文の1文は平均72字らしいですが、例えばこの記事の冒頭の75字の文は224byteになりますが、このうちの50byte近くがPythonのわちゃわちゃなわけで、20%以上のメモリが浪費されていそうです

>>> sys.getsizeof("学生の作文を添削した際、僕が「1文ずつが長い」と指摘すると、彼は「『何文字程度』というような基準はあるのでしょうか？」と尋ねて（反駁して？）きました。")
224

numpyの場合は、文字数が揃ってないと相当メモリ量が厳しそうです。また、ナチュラルにやると1文字4byteになってしまいます。コレを防ぐには、文字列表現の型をちゃんといじればよさそうですね。

適切な型やencodingを選択する

str型の1文字が何byteなのかというのは実は1,2,4byteの3通りがあります。含まれる文字のunicodeコードポイントの最大値が1,2,4byteのどの範囲に入るかによって変わります。そのため、こんな挙動になります

>>> sys.getsizeof("a")  # asciiのみなら1byte/文字
50
>>> sys.getsizeof("aa")
51
>>> sys.getsizeof("aaa")
52
>>> sys.getsizeof("あ") # ひらがなが入ると2byte/文字
76
>>> sys.getsizeof("ああ")
78
>>> sys.getsizeof("あああ")
80
>>> sys.getsizeof("ああa") # ascii範囲の文字も2byte/文字になる
80
>>> sys.getsizeof("💫") # 絵文字が入ると4byte/文字
80
>>> sys.getsizeof("💫💫")
84
>>> sys.getsizeof("💫💫💫")
88
>>> sys.getsizeof("💫💫a") # ascii範囲の文字も4byte/文字になる
88

ですから、絵文字みたいな文字を削除するとさくっとメモリ専有量が半分になるかもしれません。

さらに、UTF-8のような可変長エンコーディングを使うとより圧縮できます。1文字にXbyte使う、ということを先に決めず、適応的に変更するためより効率よく表現できる場合があります。

>>> sys.getsizeof("今日はいい天気ですね。It's nice weather today.")
144
>>> sys.getsizeof("今日はいい天気ですね。It's nice weather today.".encode("UTF-8"))
90
>>> sys.getsizeof("今日はいい天気ですね。")
96
>>> sys.getsizeof("今日はいい天気ですね。".encode("UTF-8"))
66

この場合、型がbytes型になることに注意が必要です

>>> "今日はいい天気ですね。".encode("UTF-8")
b'\xe4\xbb\x8a\xe6\x97\xa5\xe3\x81\xaf\xe3\x81\x84\xe3\x81\x84\xe5\xa4\xa9\xe6\xb0\x97\xe3\x81\xa7\xe3\x81\x99\xe3\x81\xad\xe3\x80\x82'
bitarrayを使う

特定のユースケースでは文字種別がもっと少ない場合がありそうです。

例えば、英語の大文字とスペースだけしか入ってこないテキストであれば、28種類しかトークンは存在しないわけで、これは2^5=32>28なので本当は5bitで表記できそうです。塩基配列のようなデータの場合、トークンはATCGの4種類、つまり2bitで表せます。ここまでくると、いい感じの型が用意されてないですね。こういうときにbitarrayが便利です。

github.com

より頑張る方法として、複数の文字を1つの単位にpackする方法がありますが、そこまではだるいので今回はやりません。本当は例えば、5種類のトークンであれば、何も工夫しなければ、3bit (2^3=8>5) をそれぞれのトークンに割り当てることになりますが、5x6 =30 < 32 = 2^5なので、2つのトークンを3bit x 2 = 6bitではなく、5bitであらわせます(2トークン目として6をかけているのは、2トークン目が存在しない場合を表さないといけないので)。また、トークンの出現頻度に応じてビット列を割当てるHuffman Codingもできるのですが、これも今回はやめときましょう。

では、ここではbitarrayを用いて大量の塩基配列データを持つことを考えましょう。bitarrayのobjectをたくさん持つと、Pythonのobjectがいっぱい生成されてしまうので、長いbitarrayのobjectを用意し、各stringのindexを別の配列に持つようにします

from random import choice, randint
from bitarray import bitarray
import numpy as np

# 文字種をさだめます。塩基配列を例に取ります
alphabets = ["A","T","C","G"]
alphabet_size = len(alphabets)
# 何bitを1文字に割り当てればよいかを決め、bit列(bitarrayクラスのインスタンス)と実際の文字の対応関係をdict型で作ります
bits_per_char = int(np.ceil(np.log2(alphabet_size)))
dictionary: Final[Dict[str, bitarray]] = {
    ch: bitarray(bin(idx)[2:].zfill(bits_per_char))
    for idx, ch in enumerate(alphabets)
}

dictionaryの中身はこんな感じです

>>> dictionary
{'A': bitarray('00'), 'T': bitarray('01'), 'C': bitarray('10'), 'G': bitarray('11')}

変換するデータを用意します。ここでは1文字以上最大長100文字の一様分布の長さの塩基配列を10000シーケンス用意します

max_len = 100
n = 10000
data_to_convert = ["".join([choice(alphabets) for _ in range(randint(1,max_len)) ]) for x in range(n)]

変換しましょう。indicesに各シーケンスの開始地点を持っておきます

converted_data = bitarray()
indices = []
for seq in data_to_convert:
    indices.append(len(converted_data))
    converted_data.encode(dictionary,seq)
indices = np.array(indices,dtype=np.int32) # numpyのint32arrayに変換しておきましょう

これで、変換ができました。bitarrayのindex accesorを直接叩くとbit列が得られますが、

>>> converted_data[:100]
bitarray('1001011001011011100111000110110111100100101000010011000100101011010000111111000111110011000101001010')

さきほどの辞書を用いて復号すると、きちんと文字列が得られます

>>> seq = converted_data[indices[0]:indices[1]]
>>> "".join(seq.decode(dictionary))
'CTTCTTCGCTGATCGTGCTACCATAGATACCGTAAGGGATGGAGATTACCCCTATCGCGCACCTA'

一致しますね。

>>> data_to_covert[0]
'CTTCTTCGCTGATCGTGCTACCATAGATACCGTAAGGGATGGAGATTACCCCTATCGCGCACCTA'

メモリ使用量を確認してみると…

>>> sys.getsizeof(converted_data) + sys.getsizeof(indices)
170282
>>> sys.getsizeof(data_to_convert) + sum([sys.getsizeof(x) for x in data_to_convert])
1082618

1,082,618byte - 170,282 = 912,336byte

20%弱くらいになってますね！うれしーい。

ここでは、冒頭で書いた2,5の工夫を両方取り入れていますが、寄与分を試算してみると、だいたいこんな感じっぽいですね

  • 2bitで表現した分の寄与 (もともとのstr(ascii範囲)は1byte/文字=8bit/文字ぐらい)

    • 10,000シーケンス x 平均50文字 x -6bit = -3,000,000bit = -375,000byte

  • 10,000object -> 1objectになったことの寄与

    • 減少分: -50byteぐらい x 10,000シーケンス = -500,000byte
    • numpy配列の追加分: 4byte (int32) x 10,000シーケンス = +40,000byte

実際には、さまざまなユースケースでどの工夫がどれくらいきくかはデータ依存かと思いますが、これくらい削減できることもあるということを知っておくともしかしたら役立つことがあるかもしれません

MNTSQ株式会社(モンテスキュー)では大量の文字列を扱うエンジニアを募集しています！（が、実際あんまりこういうことはしませんね…）

www.mntsq.co.jp

この記事を書いた人

f:id:mntsq:20201113152310j:plain

堅山耀太郎

MNTSQ社で取締役として機械学習・自然言語処理に関わるもろもろをやっています。好きな食べ物は担々麺です。

記事一覧へ