バローズ・ウィーラー変換

バローズ・ウィーラー変換（BWT）は、文字列を類似文字の連続した部分に並べ替え、元の文字列を復元できるような逆変換を行います。このような連続した文字が存在する場合、先頭移動変換やランレングス符号化などの圧縮技術がより効果的になるため、BWTは圧縮アルゴリズムの効率を向上させるための準備段階として利用でき、bzip2などのソフトウェアでそのように使用されています。このアルゴリズムはサフィックス配列を用いることで効率的に実装でき、線形時間計算量を実現できます。

これは1983年にデビッド・ウィーラーによって発明され、後に1994年に彼とマイケル・バロウズによって発表されました。彼らの論文には、 BWTに続いて先頭移動符号化とハフマン符号化または算術符号化を使用してデータを圧縮する、ブロックソート可逆データ圧縮アルゴリズム（BSLDCA）と呼ばれる圧縮アルゴリズムが含まれていました。^{[ 1 ] [ 2 ]}

変換は、入力テキストの循環シフトを行とする行列（バローズ・ウィーラー行列^{[ 3 ]}として知られる）を辞書順に並べ、その行列の最後の列を取ることによって行われます。

変換を元に戻せるようにするには、もう 1 つの手順が必要です。変換後の文字列とともに、Burrows–Wheeler 行列内の元の文字列のインデックスを返すか (Burrows と Wheeler による元の論文^{[ 1 ]}で示されている方法)、または変換を実行する前に、入力テキストの先頭または末尾に特別なテキスト終了文字を追加する必要があります。^{[ 3 ]}

関数BWT (文字列s) テーブルを作成します。行はsのすべての可能な回転を表します。 行をアルファベット順に並べ替える （テーブルの最後の列を返す）

関数inverseBWT (文字列s) 空のテーブルを作成する 繰り返し回数​ // 最初の挿入で最初の列が作成されます テーブルの最初の列の前にsをテーブルの列として挿入します テーブルの行をアルファベット順に並べ替える （「EOF」文字で終わる行を返す）

元の文字列に頻繁に出現する部分文字列が複数ある場合、BWT変換後の文字列には、同じ文字が連続して何度も繰り返される箇所が複数存在するため、^{[ 4 ]}圧縮しやすいデータが生成されます。たとえば、「the」という単語が頻繁に含まれる英語のテキストを変換する場合を考えてみましょう。

例えば：

このテキストの回転をソートすると、「he」で始まる回転がグループ化され、そのような回転の最後の文字（「he」の前の文字でもある）は通常「t」になります（ただし、テキストに「ache」が含まれている場合など、まれにそうでない場合もあります）。そのため、変換結果には、連続する「t」文字が複数、または複数連なって含まれます。同様に、「e」で始まる回転もグループ化されますが、「e」の前には「h」が付くことが多いため、上記の出力には連続する「h」文字が5つ連なっていることがわかります。

したがって、この変換の成功は、ある値がシーケンスの前に高い確率で出現することに依存するため、一般的には、適切なデータ（テキストなど）のかなり長いサンプル（少なくとも数キロバイト）が必要となることがわかる。

BWTの特筆すべき点は、より簡単にエンコードできる出力を生成することではなく（それは通常のソートでもできることである）、それを可逆的に行うことで、最後の列のデータから元の文書を再生成できる点にある。

逆の操作は次のように理解できます。BWT アルゴリズムの最終テーブルを取り、最後の列以外をすべて削除します。この情報だけがあれば、最初の列を簡単に復元できます。最後の列にはテキスト内のすべての文字が含まれているので、これらの文字をアルファベット順に並べ替えるだけで最初の列が得られます。次に、各行の最後の列と最初の列を合わせると、ドキュメント内の連続する文字のすべてのペアが得られます。ここで、ペアは循環的に取得され、最後の文字と最初の文字がペアを形成します。ペアのリストを並べ替えると、最初の列と 2番目の列が得られます。3 番目の列を取得するには、最後の列を再びテーブルの先頭に追加し、行を辞書順に並べ替えます。この方法を続けると、リスト全体を復元できます。最後に「ファイルの終わり」文字がある行が元のテキストです。上記の例を逆にするには、次のようにします。

出力結果を変えることなく、これらのアルゴリズムをより効率的に実行するための最適化がいくつかあります。エンコーダとデコーダのどちらにもテーブルを表す必要はありません。エンコーダでは、テーブルの各行を文字列への単一のポインタで表し、インデックスを使用してソートを実行できます。デコーダでもテーブルを格納する必要はなく、デコードされた文字列は左から右へ1文字ずつ生成できます。比較ソートを回避して線形ソートを使用することも可能で、パフォーマンスはアルファベットのサイズと文字列の長さに比例します。アルゴリズムにおける「文字」は、バイト、ビット、またはその他の任意の適切なサイズにすることができます。

また、数学的には、エンコードされた文字列は接尾辞配列の単純な変更として計算でき、接尾辞配列は線形時間とメモリで計算できるという点も指摘できる。テキスト T の接尾辞配列 SA に関して、BWT は次のように定義できる（1 ベースのインデックス付け）。

$${\displaystyle BWT[i]={\begin{cases}T[SA[i]-1],&{\text{if }}SA[i]>0\\\$,&{\text{otherwise}}\end{cases}}}$$^{[ 5 ]}

実際の「EOF」文字は必要ありません。代わりに、文字列内に「EOF」が存在する場合の位置を記憶するポインタを使用できます。この方法では、BWTの出力には変換後の文字列とポインタの最終値の両方を含める必要があります。逆変換では、文字列とポインタが渡され、文字列のみが返されます。

アルゴリズムの詳細な説明は、Burrows と Wheeler の論文、または多数のオンラインソースで見つけることができます。^{[ 1 ]}アルゴリズムは、EOF を使用するかどうか、およびソートの方向によって多少異なります。実際、元の定式化では EOF マーカーは使用されていませんでした。^{[ 6 ]}

入力文字列をどの方向に回転させても変換後の文字列は同じになるため、入力文字列の末尾にEOFマーカーを追加するか、あるいはそれと同等の処理を行わない限り、BWTを反転させることはできません。そうすることで、入力文字列とそのすべての回転を区別することが可能になります。アルファベットのサイズを大きくする（EOF文字を追加する）と、後続の圧縮処理が複雑になります。

変換には全単射バージョンがあり、変換された文字列は元の文字列を一意に識別し、両者は同じ長さで、文字もまったく同じだが順序が異なるだけである。^{[ 7 ] [ 8 ]}

全単射変換は、入力をリンドン語の非増加シーケンスに因数分解することによって計算されます。このような因数分解は存在し、Chen–Fox–Lyndonの定理^{[ 9 ]}により一意であり、線形時間と定数空間で見つけることができます^{[ 10 ]} 。アルゴリズムはすべての単語の回転をソートします。Burrows–Wheeler変換と同様に、これによりn個の文字列のソート済みシーケンスが生成されます。変換された文字列は、このソート済みリストの各文字列の最後の文字を選択することによって得られます。ここで重要な注意点は、長さの異なる文字列が通常の方法で順序付けられないことです。2つの文字列は永久に繰り返され、無限の繰り返しがソートされます。たとえば、「ORO」は「OR」の前に来ます。なぜなら「OROORO...」は「OROROR...」の前に来るからです。

例えば、元の文字列「^ BANANA $」は、これらの手順を経て「ANNBAA ^ $」に変換されます（赤い「$ 」文字はEOFポインタを示します）。EOF文字は全単射変換では不要なので、変換中に削除され、ファイル内の適切な場所に再度追加されます。

文字列はリンドンワードに分割され、上記の比較方法を使用してシーケンス内の単語が減少します。（' ^ ' を他の文字に続くものとしてソートしていることに注意してください。）" ^ BANANA" は ( ^ ) (B) (AN) (AN) (A) になります。

最後のステップまでは、このプロセスは逆バロウズ・ウィーラー・プロセスと同一ですが、ここでは必ずしも単一のシーケンスの回転が得られるわけではなく、リンドン語の回転が得られます（プロセスが続くと、リンドン語は繰り返されるようになります）。ここでは、4つの異なるリンドン語（A）、（AN）（2回）、（B）、および（^）の繰り返しが見られます。（NANA...はANAN...のサイクルであるため、異なる単語を表しません。）この時点で、これらの単語は逆順にソートされます：（^）、（B）、（AN）、（AN）、（A）。これらを連結して、

^バナナ

バローズ・ウィーラー変換は、この全単射変換の特殊なケースと見なすことができます。文字列の末尾を示すために、従来のようにアルファベット外の新しい文字を導入する代わりに、既存のすべての文字より前に来る新しい文字を文字列の先頭に導入することができます。これで文字列全体がリンドン語となり、全単射処理を施すと、変換された結果が得られます。この変換結果を反転させると、末尾で再構成する必要なく、リンドン語が復元されます。

例えば、全単射変換を適用すると次のようになります。

全 単射変換には、 同一の文字の連続が 8 つ含まれています。これらの連続はXX、 順にII、、、、、、、、 および です 。XXPP..EE..IIII

これらのプレイでは、合計18種類のキャラクターが使用されています。

テキストが編集されると、そのバロウズ・ウィーラー変換は変化します。Salsonら^{[ 11 ]}は、元のテキストのバロウズ・ウィーラー変換から編集後のテキストのバロウズ・ウィーラー変換を推論するアルゴリズムを提案しています。このアルゴリズムでは、元のバロウズ・ウィーラー変換で限られた数の局所的な並べ替えを行うため、編集後のテキストのバロウズ・ウィーラー変換を直接構築するよりも高速になる可能性があります。

このPythonによる実装は、簡潔さを優先して速度を犠牲にしています。プログラムは短いものの、実用的な実装で求められる線形時間よりも多くの時間を要します。基本的には、擬似コードのセクションと同じ処理を実行します。

STX/ETX制御コードを使用してテキストの開始と終了をマークし、を使用しての 番目の回転s[i:] + s[:i]を構築すると、順変換はソートされた各行の最後の文字を取得します。is

from curses.ascii import STX , ETXdef bwt ( s : str , start = chr ( STX ), end = chr ( ETX )) -> str : r """ 入力文字列にバロウズ・ウィーラー変換を適用します。 >>> bwt('BANANA')  '\x03ANNB\x02AA'  >>> bwt('BANANA', start='^', end='$')  'ANNB^AA$'  >>> bwt('BANANA', start='%', end='$')  'A$NNB%AA'  """ assert ( start not in s and end not in s ), "入力文字列には STX および ETX 文字を含めることはできません" s = f " { start }{ s }{ end } " # テキストマーカーの開始と終了を追加# 文字列の回転テーブル table = sorted ( f " { s [ i :] }{ s [: i ] } " for i , c in enumerate ( s )) last_column = [ row [ - 1 :] for row in table ] # 各行の最後の文字return "" . join ( last_column ) # 文字のリストを文字列に変換

逆変換は、rテーブルの左列に繰り返し挿入し、テーブルをソートします。テーブル全体が構築された後、STXとETXを除いた、ETXで終わる行を返します。

def inverse_bwt ( r : str , start = chr ( STX ), end = chr ( ETX )) -> str : r """ 逆バロウズ・ウィーラー変換を適用します。 >>> inverse_bwt('\x03ANNB\x02AA')  'BANANA'  >>> inverse_bwt('ANNB^AA$', start='^', end='$')  'BANANA'  >>> inverse_bwt('A$NNB%AA', start='%', end='$')  'BANANA'  """ str_len = len ( r ) table = [ "" ] * str_len # 空のテーブルを作成for _ in range ( str_len ): table = sorted ( rc + tc for rc , tc in zip ( r , table )) # r の列を追加# 繰り返し処理を行い、最後の文字が ETX で終わるかどうかを確認しますs = next (( row for row in table if row . endswith ( end )), "" )# 配列からデータを取得し、開始マーカーと終了マーカーを削除しますreturn s . rstrip ( end ) . strip ( start )

Manzini の実装ノートに従うと、代わりに単純なヌル文字のサフィックスを使用することと同等です。ソートは共辞書順(文字列を右から左に読む) で行う必要があります。つまり、Python では次のようになります。^{[ 6 ]} (上記の制御コードは実際には EOF が最後の文字であるという条件を満たしていません。2 つのコードは実際には最初の文字です。それでも回転は維持されます。)sorted(...,key=lambdas:s[::-1])

可逆圧縮アルゴリズムであるバロウズ・ウィーラー変換は、その符号化が可逆的であり、結果として得られる圧縮データから元のデータを復元できるという重要な特性を備えています。バロウズアルゴリズムの可逆性は、さまざまな目的を持つさまざまなアルゴリズムに利用されてきました。例えば、バロウズ・ウィーラー変換は、シーケンスアライメント、画像圧縮、データ圧縮などのアルゴリズムで使用されています。以下に、バロウズ・ウィーラー変換のいくつかの用途をまとめました。

• マーク・ネルソンによるBWTの記事（ 2017年3月25日にWayback Machineにアーカイブ済み）
• 全単射文字列ソート変換、GilとScott著、Wayback Machineに2011年10月8日にアーカイブ済み
• Yutaのopenbwt-v1.5.zipには、全単射バージョンのBWTSを含む、さまざまなBWTルーチンのソースコードが含まれています。
• クフライトナー著「バロウズ・ウィーラー変換の全単射変種について」
• Burrows–Wheelerアルゴリズムに基づいたオープンソースの圧縮プログラムとライブラリに関するブログ記事とプロジェクトページ。
• MITのオープンコースウェア講義「BWT（計算生物学およびシステム生物学の基礎）」
• リーグテーブルソート（LTS）またはBWTへの重み付けアルゴリズム（アブデルラヒム・ヘチャチェナ著）