Byte Pair Encoding (wikipedia)

バイトペアエンコーディング[1][2]またはダイグラムコーディング[3]は，データ圧縮の単純な形態で，データの連続するバイトの最も一般的な対を，そのデータ内に発生しないバイトに置き換えるものである。 元のデータを復元するためには，置換されたバイトの表が必要となる。 このアルゴリズムは 1994 年 2 月の C Users Journalの記事 A New Algorithm for Data Compression で Philip Gage が初めて公に説明した[4]。

この手法は Google の SentencePiece[5] や OpenAI の GPT-3[6] など，いくつかの自然言語処理 (NLP) アプリケーションで有用であることが示されている。

BPE の例

以下のデータを符号化することを考える 

aaabdaaabac

バイト対 “aa” は最も出現頻度が高いので，データで使われていないバイト “Z” に置き換わることになる。 これにより，次のようなデータと置換表ができる: 

ZabdZabac
Z=aa

次にバイト対 “ab” を Y に置き換えて，この処理を繰り返す: 

ZYdZYac
Y=ab
Z=aa

リテラルなバイト対は 1 回しか発生しないので，ここでエンコードを止めてもよい。 あるいは “ZY” を “X” に置き換えて，再帰的にバイト対符号化を続けることもできる。 

XdXac
X=ZY
Y=ab
Z=aa

このデータは 2 回以上出現するバイト対が存在しないため，バイトペアエンコーディングではこれ以上圧縮できない。

このデータを伸長するには，単純に逆順に置換を行う。

文献

  1. Gage, Philip (1994). A New Algorithm for Data Compression. The C User Journal.
  2. A New Algorithm for Data Compression. Dr. Dobb’s Journal. 1 February 1994. Retrieved 10 August 2020.
  3. Witten, Ian H.; Moffat, Alistair; Bell, Timothy C. (1994). Managing Gigabytes. New York: Van Nostrand Reinhold. ISBN 978-0-442-01863-4.
  4. Byte Pair Encoding. Archived from the original on 2016-03-26.
  5. google/sentencepiece. Google. 2021-03-02. Retrieved 2021-03-02.
  6. Brown, Tom B.; Mann, Benjamin; Ryder, Nick; Subbiah, Melanie; Kaplan, Jared; Dhariwal, Prafulla; Neelakantan, Arvind; Shyam, Pranav; Sastry, Girish; Askell, Amanda; Agarwal, Sandhini (2020-06-04). “Language Models are Few-Shot Learners”. arXiv:2005.14165 [cs.CL].