[C#] [VB] ブロックソートを実装する方法

ブロックソートとは

• ブロックソート – Wikipedia

ブロックソートとはデータの可逆変換アルゴリズムの一種です。ソートとついていますが、データのソートを効率よくするため ソートアルゴリズムではありません 。また、データの圧縮アルゴリズムでもありません。Wikipediaには次のようにあります。

ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。

データ圧縮の前処理に応用されるとありますが、どういうことかはブロックソートによって得られるエンコードデータを見ればわかります。ブロックソートは例えば文字列 "papaya" を次のようなソートされた文字列とインデックスの組み合わせに変換します。

“papaya” -> { yppaaa, 3 }

可逆変換なので { yppaaa, 3 } をデコードして “papaya” を求めることができます。

上記エンコード結果を見ると、文字列の中では同じ文字が一つの塊となっているのがわかります。ブロックソートは、変換後の文字列は前の文字列と比較して同じ文字が多く続く性質を持ちます。

こうなると、例えば連長圧縮(RLE)等を用いてデータの圧縮を行う場合、効率の良い圧縮結果が期待できます。

連長圧縮とは連続するデータを「データ+連続する数」で表現することにより圧縮します。例えば “aaabbbccc” というデータを連長圧縮で圧縮すると “a3b3c3” という具合です。

つまり、ブロックソート自体はデータの大きさを変えないのですが、同じデータが固まっていたほうが圧縮効率が良くなるアルゴリズムの前処理で使うことで、圧縮効率をよくしてくれます。

ブロックソートのアルゴリズム

以下、エンコードとデコード、それぞれのアルゴリズムを見ていきます。文字列 “papaya” を処理する例です。

エンコード

エンコードのアルゴリズムは次の通りです。

1. 入力データを1文字ずつ巡回シフトして表を作る。
   • 巡回シフトの例: “papaya” を1文字左にシフトし先頭文字は末尾に加える
2. 巡回シフトで得られた文字列データを辞書順に(安定)ソートする
3. ソート後の表の行順で末尾の文字列を取り出す
4. ソート後の表から入力データの行番号を取り出す
5. 3, 4 で取り出したデータがエンコード結果

文字で説明を読んでもわからないので以下、図を使って説明します。

1. 入力データを巡回シフトする

巡回シフトで表を作ります。巡回シフトは先頭文字を取り出して末尾に付け加える処理です。

入力データ “papaya” を巡回シフトすると “apayap” になります。さらに “apayap” を巡回シフトすると “payapa” になります。このように続けてデータ数分(つまり文字数分)の巡回シフトで得られるデータを作成します。

そして得られるデータが以下のようになります。

巡回シフトしたデータは配列等に入れておきます。

2. 辞書順にソートする

データを辞書順にソートします。この時同一文字の場合はインデックス順になるようにします。つまり安定ソートを使わないといけないということです。

並び変えた結果は次のようになります。

1列目は行番号の連番です。後で使います。

3. 末尾の文字を取り出す

ソートした結果から末尾の文字を順番に取り出します。

表の右端の列を上から並べた文字列が変換結果の文字列です。

yppaaa となります.

4. 入力データの行番号

ソート後の表から入力データの行番号を探します。安定ソートなので上から順に見ていって、最初に見つかる同じデータが入力データだとわかります。

ここでは、3行目に “papaya” があります。したがって、3 となります。

5. エンコード結果

yppaaa, 3 がエンコード結果になります。

デコード

デコードのアルゴリズムは次の通りです。

1. 入力文字列の各文字の位置を保持しつつ辞書順にソートする。
   • “y(0) p(1) p(2) a(3) a(4) a(5)” -> a(3) a(4) a(5) p(1) p(2) y(0)
2. 1で得られたデータを次の手順で並べる
   • 変換結果の行番号 “3” 番目のデータ “p(1)” を取り出して並べる。
   • “p(1)” の添字が 1 なので 1番目のデータ “a(4)” を取り出して並べる。
   • “a(4)” の添字が 4 なので 4番目のデータ “p(2)” を取り出して並べる。
   • 以下、入力データの文字数分並ぶまで続けると、デコードが完了する。

処理の手順的には上の通りにやれば問題なく動くのですが、直観的には理解しづらいです。原理的にはエンコード時に作成した表を復元しているようです。

詳しくは Wikipedia のページを見るといいです。

上で紹介した手順は Wikipedia にある “復号手順の効率化” にある方法です。

サンプルコード

ブロックソート(BWT)を C#, VB.NET でそれぞれ実装してみます。デバッグ用に途中経過を出力するようにしてみました。Wikipediaの例で上がっている文字列が同じ過程で変換されるのが確認できます。

C

using System;
using System.Linq;

public static class BlockSort
{
    // エンコード-------------------------------------------------------------
    public static Tuple<string, int> Encode(string data)
    {
        Console.WriteLine($"ブロックソートエンコード開始: {data}");

        // 1. 入力データを1文字ずつ巡回シフトして表を作る。
        var table = new string[data.Length];
        var rotatedData = data;
        for (int i = 0; i < data.Length; i++)
        {
            // 巡回シフトで得られた文字つを格納
            table[i] = rotatedData;
            // 次の巡回シフト
            rotatedData = Rotate(rotatedData);
        }
        Console.WriteLine("巡回シフトで得られた表");
        DebugPrintTable(table);

        // 2. 巡回シフトで得られた文字列データを辞書順に(安定)ソートする
        table = table.OrderBy(s => s).ToArray();
        Console.WriteLine("ソート後の表");
        DebugPrintTable(table);

        // 3. ソート後の表の行順で末尾の文字列を取り出す
        var encoded = new string(table.Select(s => s.Last()).ToArray());

        // 4. ソート後の表から入力データの行番号を取り出す
        var index = Array.IndexOf(table, data);

        Console.WriteLine($"エンコード結果: [{encoded}, {index}]");

        return new Tuple<string, int>(encoded, index);
    }

    // 文字列を1文字分巡回シフトする
    private static string Rotate(string data)
    {
        var first = data.First();
        var result = data.Substring(1, data.Length - 1) + first;
        return result;
    }

    // デバッグ用
    private static void DebugPrintTable(string[] table)
    {
        foreach (var data in table)
        {
            Console.Write("|");
            foreach (var c in data)
            {
                Console.Write($" {c} |");
            }
            Console.WriteLine();
        }
    }

    // デコード-------------------------------------------------------------
    public static string Decode(string encodedString, int index)
    {
        Console.WriteLine($"ブロックソートデコード開始: {encodedString}, {index}");

        // 1. 入力文字列の各文字の位置を保持しつつ辞書順にソートする。

        // インデックステーブル(0から文字数分の連番)を作る
        var indexTable = Enumerable.Range(0, encodedString.Length).ToList();
        // 文字列を辞書順にソート
        var sortedString = encodedString.OrderBy(c => c).ToArray();
        // 文字列をソートしたときの順序でインデックステーブルをソートする)
        indexTable.Sort((a, b) => { return encodedString[a].CompareTo(encodedString[b]); });

        Console.WriteLine($"ソート結果");
        DebugPrint(sortedString, indexTable.ToArray());

        // 2. 1で得られたデータをインデックスから順に取り出して並べる
        var nextIndex = index;
        var decoded = string.Empty;
        for (int i = 0; i < encodedString.Length; i++)
        {
            // 辞書順にソートした配列からから次の文字を取得し結果に連結
            decoded += sortedString[nextIndex];
            // 次のインデックスを取得
            nextIndex = indexTable[nextIndex];
        }

        Console.WriteLine($"デコード結果: {decoded}");

        return decoded;
    }

    // デバッグ用
    public static void DebugPrint(char[] sortedString, int[] indexTable)
    {
        for (int i = 0; i < sortedString.Length; i++)
        {
            Console.Write($"{sortedString[i]}({indexTable[i]}), ");
        }
        Console.WriteLine();
    }
}

VB.NET

Public Class BlockSort
    ' エンコード-------------------------------------------------------------
    Public Shared Function Encode(ByVal data As String) As Tuple(Of String, Integer)
        Console.WriteLine($"ブロックソートエンコード開始: {data}")

        ' 1. 巡回シフトで得られた文字列の表を作る
        Dim table(data.Length - 1) As String
        Dim rotatedData = data

        For i = 0 To data.Length - 1
            ' 巡回シフトで得られた文字つを格納
            table(i) = rotatedData
            ' 次の巡回シフト
            rotatedData = Rotate(rotatedData)
        Next
        Console.WriteLine("巡回シフトで得られた表")
        DebugPrintTable(table)

        ' 2. 辞書順にソートする(安定ソートでなければならない)
        table = table.OrderBy(Function(s) s).ToArray()
        Console.WriteLine("ソート後の表")
        DebugPrintTable(table)

        ' 3. 巡回シフトで得られた文字列の末尾を行の順番で連結
        Dim encoded As String = New String(table.Select(Function(s) s.Last()).ToArray())

        ' 4. ソート結果から元の文字列が何番目にあるかを取得
        Dim Index As Integer = Array.IndexOf(table, data)

        Console.WriteLine($"エンコード結果: [{encoded}, {Index}]")

        Return New Tuple(Of String, Integer)(encoded, Index)
    End Function

    ' 文字列を1文字分巡回シフトする
    Private Shared Function Rotate(ByVal data As String) As String
        Dim first As String = data.First()
        Dim result = data.Substring(1, data.Length - 1) + first
        Return result
    End Function

    ' デバッグ用
    Private Shared Sub DebugPrintTable(ByVal table As String())
        For Each rstr In table
            Console.Write("|")
            For Each c In rstr
                Console.Write($" {c} |")
            Next
            Console.WriteLine()
        Next
    End Sub

    ' デコード-------------------------------------------------------------
    Public Shared Function Decode(ByVal encodedString As String, ByVal index As Integer) As String
        Console.WriteLine($"ブロックソートデコード開始: {encodedString}, {index}")

        ' 1. インデックステーブル(0から文字数分の連番)を作る
        Dim indexTable As List(Of Integer) = Enumerable.Range(0, encodedString.Length).ToList()

        ' 2. ソートする
        ' 2.1. 文字列を辞書順にソート
        Dim sortedString As Char() = encodedString.OrderBy(Function(c) c).ToArray()
        ' 2.2. 文字列をソートしたときの順序でインデックステーブルをソートする)
        indexTable.Sort(Function(a, b) encodedString(a).CompareTo(encodedString(b)))

        Console.WriteLine($"ソート結果")
        DebugPrint(sortedString, indexTable.ToArray())

        ' 3. エンコードで得られたインデックスから順に取り出す
        Dim nextIndex As Integer = index
        Dim decoded As String = String.Empty
        For i = 0 To encodedString.Length - 1
            ' 辞書順にソートした配列からから次の文字を取得し結果に連結
            decoded += sortedString(nextIndex)
            ' 次のインデックスを取得
            nextIndex = indexTable(nextIndex)
        Next

        Console.WriteLine($"デコード結果: {decoded}")

        Return decoded
    End Function


    ' デバッグ用
    Private shared sub DebugPrint(byval sortedString As char(), ByVal indexTable As Integer())
        For i = 0 To sortedString.Length - 1
            Console.Write($"{sortedString(i)}({indexTable(i)}), ")
        Next
        Console.WriteLine()
    End Sub
End Class

以上。