MarriageTheoremのこと

_ 折角なので、一昨日の日記で言及したブロックソート法についての備忘録を記しておく。

ある与えられた文字列 $w$（例えば、141421356）を以下の要領で並び替える。まず、$w$ から出発し、各文字を左に1桁ずつずらして新しい文字列を作っていき（一番左の文字は右端に移る）、$w$ 自身を含めて$w$ の長さと同じ個数の文字列を作り、行列状に並べる（例では

$$\begin{matrix}1&4&1&4&2&1&3&5&6\\4&1&4&2&1&3&5&6&1\\1&4&2&1&3&5&6&1&4\\4&2&1&3&5&6&1&4&1\\2&1&3&5&6&1&4&1&4\\1&3&5&6&1&4&1&4&2\\3&5&6&1&4&1&4&2&1\\5&6&1&4&1&4&2&1&3\\6&1&4&1&4&2&1&3&5\end{matrix}$$

となる）。こうしてできる行列を $X_1$ と書く。次に $X_1$ の行を辞書式順序に従って並び替える（例では

$$\begin{matrix}1&3&5&6&1&4&1&4&2\\1&4&1&4&2&1&3&5&6\\1&4&2&1&3&5&6&1&4\\2&1&3&5&6&1&4&1&4\\3&5&6&1&4&1&4&2&1\\4&1&4&2&1&3&5&6&1\\4&2&1&3&5&6&1&4&1\\5&6&1&4&1&4&2&1&3\\6&1&4&1&4&2&1&3&5\end{matrix}$$

となる）。この結果を $X_2$ と書く。このとき、行列 $X_2$ の左から何列かを取り出してできる部分行列の行たちもまた辞書式順序で並んでいる（＊）という事実が（辞書式順序の定義から当たり前なのだが）実は後で効いてくる。そして、$X_2$ の一番右の列を上から順に読んでできる文字列 $w'$ を並び替えの結果とする（例では 264411135 となる）。

構成法から、 $X_1$（従って $X_2$）の一番右の列はもとの文字列 $w$ を並び替えたものとなっている。この並び替えた結果 $w'$ からもとの文字列 $w$ を復元してみよう。その方法を考えるために、行列 $X_2$ の右側に自身の複製を並べてみる：

$$\begin{matrix}1&3&5&6&1&4&1&4&2&|&1&3&5&6&1&4&1&4&2\\1&4&1&4&2&1&3&5&6&|&1&4&1&4&2&1&3&5&6\\1&4&2&1&3&5&6&1&4&|&1&4&2&1&3&5&6&1&4\\2&1&3&5&6&1&4&1&4&|&2&1&3&5&6&1&4&1&4\\3&5&6&1&4&1&4&2&1&|&3&5&6&1&4&1&4&2&1\\4&1&4&2&1&3&5&6&1&|&4&1&4&2&1&3&5&6&1\\4&2&1&3&5&6&1&4&1&|&4&2&1&3&5&6&1&4&1\\5&6&1&4&1&4&2&1&3&|&5&6&1&4&1&4&2&1&3\\6&1&4&1&4&2&1&3&5&|&6&1&4&1&4&2&1&3&5\end{matrix}$$

さて、 $X_1$ の各行は先頭行（つまり $w$）を左に一つずつずらしていってできたものなので、各 $k$ について「$X_1$ の各行について、左から $k$ 文字を抜き出した文字列」全体の集合と「$X_1$ の各行について、一番右の文字の後に左から $k-1$ 文字めまでを繋げた文字列」全体の集合は重複度を込めて一致する。よって、その行を並び替えた $X_2$ についても同じ性質が成り立つ。換言すると、上記のように二つ並んだ $X_2$ において、境界（「|」）部分の左隣の1列と右隣の $k-1$ 列を抜き出してできる行列 $Y_k$ の各行からなる集合と、$X_2$ の左から $k$ 列を抜き出してできる行列 $Z_k$ の各行からなる集合は重複度を込めて一致する。すると、性質（＊）より $Z_k$ の行たちは辞書式順序で並んでいるので、 $Y_k$ の行たちを辞書式順序で並べると $Z_k$ が得られる。そのため、$X_2$ の一番右の列であるところの $w'$ を辞書順に並べると $Z_1$ が得られ、その左列に $w'$ を並べると $Y_2$ が得られ、その行を辞書順に並べると $Z_2$ が得られ、その左列に $w'$ を…と繰り返していくことで、$w'$ から出発して行列 $X_2$ を復元できることがわかる。

ただし、$w$ を左側にいくつかずらしてできる別の文字列 $u$ から出発しても行列 $X_2$ は同じものになるので、$X_2$ を復元できても $w$ 自身を一意に復元できるとは限らない。その点を解決するためには、予め文字列 $w$ の末尾に文字列の終わりを表す特殊文字（実用上は、例えばファイルの終端文字EOFなど）を付け加えておけばよい。そうすれば、$X_2$ の行のうち、一番右にその特殊文字が現れている唯一の行がもとの $w$ と確定する。上の例では、「6」が終端文字のような立場であり、実際 $X_2$ の行で一番右が6であるものが文字列 $w$ となっている。

というわけで、変換後の文字列 $w'$ から変換前の（末尾に目印を持つ）文字列 $w$ を復元できることがわかった。そして、特定のパターンの繰り返しが頻繁に生じる文字列（例えば、単語単位の繰り返しからなる自然言語の文章はこの性質を満たす）をこの方法で変換すると、変換後の文字列には同じ文字が連続するブロックが多く含まれるようになり、圧縮アルゴリズムの効率を向上させることができる、という塩梅らしい。まこと面白い仕組みであるなぁ。

_ プレプリント確認状況：arXiv:math 11月6日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/120まで