目次:
定義-バロウズウィーラー変換（BWT）とはどういう意味ですか？
Burrows-Wheeler変換（BWT）は、文字列などのデータのブロックを取得し、類似した文字の実行に再配置するアルゴリズムです。 変換後、出力ブロックには開始前とまったく同じデータ要素が含まれますが、順序が異なります。 アルゴリズムの性質上、類似した文字が互いに隣接する傾向があるため、結果のデータの順序が圧縮されやすくなります。 したがって、多くの圧縮アルゴリズムで使用されます。
Techopediaは、Burrows-Wheeler Transform（BWT）について説明しています
Burrows-Wheeler変換アルゴリズムは、1994年にMichael BurrowsとDavid Wheelerによって発明された比較的新しいアルゴリズムであり、1983年にWheelerによって発見された未発表の変換に基づいています。
最も基本的な方法では、BWTは文字列などのデータブロックを取得し、EOF文字を追加してから、その文字列のすべての回転を辞書式順序に並べ替えます。 次の擬似コードまたは手順は、アルゴリズムを示しています。
- 文字列の可能なすべての1インクリメント回転を表す行を含むテーブルを作成します。
- すべての行をアルファベット順に並べ替えます。
- テーブルの最後の列を出力します。
たとえば、「バナナ」という単語。 EOF文字を追加すると「banana $」に変わり、アルゴリズムが適用されます。
1.すべての可能な回転を表す行を含むテーブルを作成します。
バナナ$
anana $ b
なな$ ba
ana $ ban
ナバナ
a $ banan
バナナ
2.最初の列に基づいて行をアルファベット順/辞書順でソートします。
バナナ
a $ banan
ana $ ban
anana $ b
バナナ$
なな$ ba
ナバナ
3.最後の列をBWT出力として返します：annb $ aa
結果の文字列は、繰り返される文字が互いに隣り合っているため、圧縮が容易です。 ただし、逆変換を行うには、変換されたデータとともに追加のデータを保存する必要があります。 結果の変換済みデータは元の形式よりも大きくなりますが、その圧縮率特性は何倍にも増加しますが、本質的には圧縮方法の効率を改善する「自由な」方法になります。
