では、アルゴリズムの紹介です。例えば変換したいデータが「abraca」だとします。

（１）データを一文字ずつ左側にシフトさせます。（一文字左にやって、左側にはみ出したものは右側から入ってきます。）

　元データ：abraca

　回転した後のデータは次の通り

　1 abraca
　2 bracaa
　3 racaab
　4 acaabr
　5 caabra
　6 aabrac

（２）このように一文字ずつ回転させたら、これを辞書順（普通の国語辞書などのようにAの方がZ
より大きいとか）にソート（整列）します。

　6 aabrac
　1 abraca　←これが元データ
　4 acaabr
　2 bracaa
　5 caabra
　3 racaab

（３）それぞれの文字列の最後の文字を出力します。すると、

　6 aabra[c]
　1 abrac[a]　←これが元データ
　4 acaab[r]
　2 braca[a]
　5 caabr[a]
　3 racaa[b]

　１番目のaabrac の最後はc
２番目のabraca の最後はa
　・
　・

　　というふうにやっていくと、caraabですね。これを出力します。

　それに加え、元データが何番目にあるかを　出力します。この場合だとabracaは２番目なので「２」を出力します。

これで終わりです。

非常に簡単でしょう？　これで、なぜデータが圧縮しやすくなるのかというのは後から説明します。

復元

　　まず、手元のデータには「caraab」と「2」があります。他には何もデータはありません。
　この文字列と番号から元の「abraca」を復元させます。

まずcaraabを一文字ずつソートさせます。

　a
　a
　a
　b
　c
　r

　　次にこのデータをBlockSortingした時のことを思い出しましょう。もちろん復元時は
　このデータのことは考えることはできませんが

　6 aabrac　☆
　1 abraca　←これが元データ
　4 acaabr
　2 bracaa
　5 caabra
　3 racaab

　　こういうふうに並んでいて一番最初のaの前がc、二番目のaの前がaというのが分かるで
　しょうか。具体的に最初の部分☆を見てみましょう。「6 aabrac」このデータの一番最初の
「a」と「c」は文字列ではつながっていることは分かりますよね。（回転しているわけですから
　）つまりaaabcrとソートした後と手元にあるcaraabはつながっているということが分かります。

　この時点でBlockSorting前のデータはどうだったのかというのは

c - a
a - a
r - a
a - b
a - c
b - r

　　という風につながっているというところまで分かりました。この次はこれらがどのように
　つながっていたのかを考えれば復元できるわけです。ここで手元のデータを見てみると、
　「２番目に元データがあったよ」という情報があります。よって

c - a
a - a　←　ここが元データのスタート
r - a
a - b
a - c
b - r

　　ということが分かります。ここまでは何となく分かるでしょうが、ここからが難しくなります。
　これらがどのようにつながっていたのかを調べなければなりません。まず考えられることはb、c、
r　は一文字しかありませんので、つながっているのがわかります

(3)c - a
　a - a　←　ここが元データのスタート
(2)r - a
　a - b　：(1) へつながる
　a - c　：(3) へつながる
(1)b - r　：(2) へつながる

　よってこの段階では

　a - b - r - a a - c - a

　というふうにつながっているのが分かりますね。しかし、これが

　a - b - r - a - c - a とつながっているのか
　a - c - a - b - r - a とつながっているのか分かりません。

　ここでひとまず元に戻って同じ文字には番号を付けてみます。

　c - a1
a - a2　←　ここが元データのスタート
r - a3
a - b
a - c
b - r

　さらに戻ってBlockSorting前のことを考えてみます。（もちろん復元時には想像できない）

　6 [a1]abrac
　1 [a2]braca　←これが元データ
　4 [a3]caabr
-----------（下はあまり関係ない）
　2 bracaa
　5 caabra
　3 racaab

　　すると、ここが復元の一番山場なのですが、ソートする時、最初に同じものが並んだ場合、次の文字の大小関係を調べますよね。

　つまりこの場合だと

　6 [a1] (a) brac
　1 [a2] (b) raca　←これが元データ
　4 [a3] (c) aabr

　　この()で囲まれたところで大小関係を判断します。よって、上のデータが、一つずつ左に
　ずれたものは

　　(a) brac [a1]
　　(b) raca [a2]
　　(c) aabr [a3]

　のようになります。
　つまり、[a1][a2][a3]は最後に出力するとなっても、1,2,3の順番は崩れないのです。
　よって、

　c - a1
　a - a2　←　ここが元データのスタート
　r - a3
　a - b
　a - c
　b - r

　は、

　c - a1
　a1 - a2　←　ここが元データのスタート
　r - a3
　a2 - b
　a3 - c
　b - r

　となります。よって、残りはこれをくっつけるだけ。

　a2 - b - r - a3 - c - a1

　番号は分かりやすいように付けたものですので、くっつけると、

　abraca

　となります。復元できましたね。メデタシメデタシ
　（分からなかった人は何回も見比べたり、実際に自分で試して確かめてください。）

BlockSortingの効果

　　では、なぜこんなことをしてデータが圧縮しやすくなるかを説明します。
　例えば英語には「the」がいっぱい出てきます。これをブロックソーティングすると

　t he・・・・
　t he・・・・
　t he・・・・

　　といろんな場所にあるtheがソートにより集まり、tが並ぶというわけです。

　　もちろんabracaという６文字のデータのソートでは全然揃わないわけですが、
　これが何十万文字のデータでは、ぞろぞろと揃います。

　　実際サンプルを見てもらうといいと思います。次の文章

　I have a cat. The cat is very cute.

　　これをブロックソーティング（完全ソートとは違って後から話す限定ソート）すると

　ThccavicI h ttvaau .r aesy . etee

　　となります。aやeが並んでいるのが分かるでしょう。これが何十万文字のデータとなると、
　同じ文字がズラーっと並びます。そうすると連長圧縮など簡単な圧縮法でLZ法などを越えるよ
　うな圧縮率が得られます。

・BlockSortingの実装の前に

　　このように説明してきたBlockSortingですが、実際プログラミングしてみるといろいろな
　ところに問題が出てきます。まず、最初にメモリを大量に消費するということ、そして処理量が
　非常に多いということです。

　　単純に考えると、１ＭＢのデータを回転させると１ＭＢ＊１ＭＢ　＝１ＴＢ　つまり１ＴＢ必
　要になります。現在のメモリではとても無理な数字ですね。そこで様々な工夫が必要になってき
　ます。

　　まずは、回転させるという話ですが、実際これは仮想的に回転させると考えて実際はポジション
　だけを保持します。具体的に話すと、abracaというデータを変換する場合、abaracaの後ろに同じ
　データ、abracaを付け足します。

　abracaabraca

　　このデータと、どこから始まる位置を指定したデータの二つで、回転したデータを表現することができます。

0 1 2 3 4 5 6 7 8 9 A
a b r a c a a b r a c a

a b r a c a
b r a c a a
r a c a a b
a c a a b r　☆
c a a b r a
a a b r a c

　　例えばポジション3を選ぶと、abr☆(acaabr)aca ですから acaabr　このように、
　ポジションだけを（1〜C)を保持して、データ自体はソートせずポジションだけを
　ソートさせるのです。よって、データの長さの二倍のバッファとポジション分の
　バッファを保持するだけで良いのです。

　　これでメモリの問題は解決しましたが、次はスピードの問題です。ブロックソーテ
　ィングは何より、「ソート」の部分にものすごく時間がかかります。単純に標準最高
　速の「クイックソート」を使用すればいいと考えるかもしれませんが、それだと１時
　間ぐらい余裕でかかってしまいます。そこで使用するのが分布数えソート、挿入ソー
　ト、変形クイックソートなどです。（ソートに関してはここを参照）

　　例えばbzipはまず最初に２文字分布数えソートをします。これで最初の２文字だけ
　を高速にソートして、そのあとソートされてないところ（具体的には二文字一致して
　いるところ）を変形クイックソート、そしてさらに細かくソートしたら挿入ソートに
　切り替えしてソートを繰り返します。このようにソートする量に合わせて、ソートの
　種類を変えたり、最初に二文字分布をやってしまうというのは有効な手段だと思います。

　　また、現在有望な方法にszipが使っている限定ソートという方法があります。
　これは、「ソートに時間がかかるなら、最初からソートをしなければ良い」という方法で
　す。これは非常に高速にできます。なにしろソートを途中まですれば良いのですから。
　途中までソートしてやめても大抵のデータは圧縮がほぼ完全ソートと同じくらいできます。
　しかし、復元にはかなり高度な技術を使用します。

　　他にも様々な方法を用いることにより、十分に使用に耐えうる速度（LZ法に匹敵）にする
　ことができます。

　　次に、ブロックソーティング後のデータに対し有効な圧縮法を紹介したいと思います。
　現在、最も一般的な方法は先頭移動法の後に連長圧縮を行い、そしてハフマン法や算術圧縮等
　で圧縮するという方法です。先頭移動法は、バッファに０から２５５まで番号を付けたデータ
　をおいておきます。そしてあるデータが使われると、それを０番目に移動して、あとをずらします。
　そうすると最初に0:a 1:b と決めておいて

　aaaaaaaaaaaaabbbbbbb　とならんだデータは　0000000000001000000
というふうに０や１が非常に多く出力されるようになります。復元は逆にやればいいだけす。
０や１が並んだデータは連長圧縮を使うと効率よく、しかも高速に処理できます。連長圧縮は
　圧縮アルゴリズムでは一番単純なものの一つで、同じ文字が続いたらそれを文字と長さで表すと
　いうものです。000000とあったら06と出力します。そして最後にハフマン法、算術圧縮で圧縮
　するわけです。

　　これ以外のブロックソーティングの有効な圧縮の方法を説明したいと思います。
　ブロックソーティング後のデータは同じ文字が並びやすいという特徴がありますが、やはり並ん
でいるところと比較的でたらめなところがでてきます。データがきれいに並んでいるところと、で
たらめに並んでいるところで圧縮の設定の切り替えができれば圧縮率は向上します

　　この切り替えのタイミングは、実はソート時に分かります。というのも

aabrac
abraca
acaabr
------
bracaa
------
caabra
------
racaab

　　というふうに最初の文字が変わると、出力する文字が同じ物ばかりなのか、もしくは
　ばらばらなのか、というのは全く変わってしまいます。そこでソート時にソートの結果を保存して
　おきます。具体的には最初に２文字の分布数えソートを行ったら、その分布を数えたものを保存し
　ておき圧縮の時に、利用するわけです。切り替えのタイミングの時に違う文字を出力するなどすれ
　ば良いと思います。次に先頭移動法ですが、これは大きなファイルに対して有効なのですが

　aaaaaaabaaaaaaaaaaa

　というふうに大量にaが並んでいる中、bが一つあったりすると

　0000000110000000000

　　となります。つまりbが一つあるために1が二回出力されてしまうのです。
　そこで、先頭移動法では、一回目では先頭に移動するのではなく、２番目に移動する
　と０が多く出力されるようになります。つまり２番目移動法というわけです。これ
　はszipなどでも使われているようです。そして連長圧縮ですが、全ての文字に次は連
　長圧縮するかどうかを出力するのではなく、次に連長圧縮するという記号に２５６番
　目の文字などで表現するか、４文字以上続いたら出力するなどの方法をとった方が結
　果は良いようです。そして最後のハフマン、算術圧縮ですが、ハフマンでは圧縮の切
　り替え時に時間がかかってしまい、また算術圧縮では時間がかかり、また特許の問題
　もあります。そこでRangeCoderというものをお奨めします。これは算術圧縮に似てい
　るのですが、スピードはハフマン法に匹敵するスピードであり圧縮率は24bit算術圧
　縮よりは良い程度です。（ハフマン法よりはもちろん良い）

BlockSortingの実装

　　実際BlockSortingのプログラム（C++)を説明してみます。
　（bzip等の実装も見て下さい）

　　最初にbuffer[N * 2 + 1]とpos[N]とcount[0x100 * 0x100]を準備します。
　Nというのは最大バッファです。countは二文字分布を数えるもので、分布数えソート
　に使用します。

unsigned char buffer[N * 2 + 1];
unsigned int pos [N];
unsigned int count [0x100 * 0x100];

　//始めに、bufferの ０-Ｎまでに加工したいデータを入れる
　fread(buffer,N,sizeof(unsigned char),infp);

　//そして、後ろに同じ文字コピーする
　memcpy(buffer + N,buffer,N);

　//まず、countを初期化
　memset(count,0,0x100 * 0x100 * 4);

　//次に分布を数える
　for (int i = 0; i < < N; i++)
{
count[(buffer[i] << 8) + buffer[i + 1]]++;

/* count[] は、二文字の分布を数える。つまり、ab だったら　a << 8 + b
bc だったら b << 8 + c */
}

　//そして分布を足す
　for (i = 1; i < 0x100 * 0x100; i++)
{
count[i] += count[i - 1];
}

//最後にposにポジションを入れる
　for (i = N - 1; i >= 0; i--)
{
pos[--count[(buffer[i] << 8) + buffer[i + 1]))]] = (unsigned int)i;
}

//ここまでで始め二文字のソートは完了した。次に残りの文字のソートを行う

　for (i = 0; i < 0x100 * 0x100 - 1; i++)
{
sort(count[i],count[i + 1],2);
}
sort(count[0x100 * 0x100 - 1],N,2);

　//最後に出力

//最初の元データがある場所を出力
for (i = 0; i < N; i++)
{
if (pos[i] == 0)
{
break;
}
}
fwrite(&i,1,sizeof(int),outfp);
　for (i = 0; i < N; i++)
{
fputc(buf[pos] + N,outfp);
}

}

void sort(int start,int last,int number)
{
unsigned char *tmpbuf = buf + number;
int range = last - start;

if (range > 100)
{
//再度分布数えソート
}
else
{
//シェルソートなど
}
}

　復元はinbufferに加工するデータを読み込んでnextに元データの位置を入れてください。
　符号化と違い非常にシンプルなプログラミングになります。

　といってもわからないので具体的には次のプログラムを見て下さい。
　このプログラムでは２文字分布数えソートしたあとに、それ以降の文字列のソートを
挿入ソートと１文字分布数えソートをして処理しています。
　、高速化のために様々なテクニックとして出力すべき文字が全て同じ部分はソートする
必要が無いのでキャンセルします。これもソースに書いてあります。

bsEncoder.hpp 符号化
bsDecoder.hpp 復号
main.cpp
デバッグ用、時間計測。BlockSortingには直接関係ない。

実際に実行ファイルを作りたい場合は、これらをビルドすればいいわけですが、ここにあります。
bs.exe BlockSortingだけ実行する

使い方は test.txtをtest1.bin というファイルに符号化したい場合
e test.txt test1.bin
test1.binをtest2.txtというファイル名に復元したい場合
d test1.bin test2.txt
本当にtest.txtとtest2.txtが合っているのか調べたい場合
c test.txt test2.txt

符号化の時、bsEncoder.hppの様々な設定をいじるとdebug.txtにいろんなdebug情報が出力されます
。なにもしなくてもdebug.txtが作成されます。このへんはご愛敬ってことで。

　最適な方法とかちゃんとコメント書けとかあるかもしれませんが、即席なので、このくらいです。
これを参考にいろいろ改良してください。