ブロックソートによる符号化

ブロックソートによる符号化 - みずぴー日記 にインスパイヤされて、Burrows-Wheeler Transform の符号化を行います。

ブロックソートによる符号化 (または Burrows-Wheeler Transform の符号化) はデータ圧縮の前処理として用いられていることが ブロックソート - Wikipedia などに記載されていますが、あまり awk で実装された例を見たことはありません。 awk で圧縮するということ自体がレアなケースなのですが、awk はアルゴリズムの実装テストにも便利な言語ですので、awk で実装してみます。

今回は、ブロックソート - Wikipedia に記載されている手順にしたがって符号化していますので、説明とコードを比較すると理解を深めることができると思います。

ただ、コードの短縮のため、ソートを gawk で実装されている asort() 関数を用いていますので、nawk, mawk 等で使うには自前でソートを実装する必要があります。 もっとも、nawk, mawk で使えるソートは今まで何度も出ていますので、sort - Google Search を参考にしてみてください。

#! /usr/local/bin/gawk -f
# bwt.awk
# Burrows-Wheeler Transform の符号化
# usage: gawk -f bwt.awk foo.txt

{
    print bwt($0);
}

# bwt():    Burrows-Wheeler Transform の符号化
#   in:     文字列 str
#   out:    Burrows-Wheeler Transform の符号化されたもの
function bwt(str,    len_str, i, arr, ret_str, num) {

    len_str = length(str);

    # 巡回行列の作成
    for (i = 1; i <= len_str; i++) {
        arr[i] = substr(str, i, len_str - i + 1) substr(str, 1, i - 1);
    }

    # sort (gawk のみ)
    asort(arr);

    # 末尾の文字の拾い上げと元の文字列の位置の拾い上げ
    for (i = 1; i <= len_str; i++) {
        ret_str = ret_str substr(arr[i], len_str);

        # 同順の場合には最初のものをカウント
        if (arr[i] == str && num == 0) {
            num = i;
        }
    }

    return num ",\"" ret_str "\"";
}

特に難しいところはありませんが、同順の場合には最初のものをカウントするところに注意してください。

では、実行してみます。

$ echo 'cacao' | gawk -f bwt.awk
3,"ccoaa"

さて、この元になっているのは、anarchy golf - BWT の問題ですが、ここに書かれている Sample input を試します。

$ cat test_1.txt
ABCABC
abracadabra
BurrowsWheelerTransform

$ gawk -f bwt.awk test_1.txt
1,"CCAABB"
3,"rdarcaaaabb"
1,"mrsrhelsWerafreToruwnBo"

$ cat test_2.txt
gaattcctgggcctggggctgtggcagctgcctcgtccct
tcacctcctggcttattctctccctccatatcttagcaat
ctcatgcctgtaatcccagcattttggtaggccaaggcgg
gtcggatcacctgaggtcaggagttcgagggccagcctga
tgaccatggtgaaaccccatctctactaaaaatacaaaat
taatcgggcatggtggcacatgcctgtaatcccagctact
ctgaggcaggagaatcgcttaaacccaggaagtggaggtt
tcagtgagctgagattgtgccattgcactccagcctgggt
aacaagagcaaaactccatcaaaaaaaataatatatgtat
atatatattacaattttatatatatatacacattatgtaa
taccattttatatatatacattacgtaatggtaaatgttt
gatcgtctccctggagaataatccccaatgtgaaattact
ctaagtggtgggattacaggcgtgtgcccaacttttcctg
agccttttgaggctgacaccagaggtagaagcccagcctc
tccccactggccatgtggggagaggctccagcctgcagca
accagggatctggcctcaagtgatgccccaacagtgggcg

$ gawk -f bwt.awk test_2.txt
17,"gcagtgctgtccgccgtgtgagtggtgtctgtcccgccca"
29,"cctctatgtcttcatctctctgagttattcccctacccaa"
18,"ctctaacccctggctgggcagtggaacttgggcaatctta"
32,"cccgggggtctgagttcccttgggaacgaagaaagtgccg"
38,"tacgaaaaatgataccaacccacaatttttgcaccagtaa"
32,"ttctcaaccgcagctgtgcaggtatgcttggtcaaagacc"
18,"taggagccggaacgcattggagtggcaataaagtatcgcg"
30,"cgcgccggctctggagcttattaatgatgtccgtgctgaa"
9,"caaacaaatacataaagtaatcttgactaaataagaaaca"
12,"tacttctttttattttcaaaatgtaaaaataataaatata"
26,"ttatttttttaaccacaatgctggattaaataatatttga"
26,"ggtcatgaagaacccttcttactagttctatacaggccaa"
14,"cttacagcacgtggcagtgtgatttgaccttgcgggattc"
8,"ggctcaccggacctacgggcgcattaaaagaaggcctttc"
36,"cgccgcccgcgcctgctggcagatagaggtagttcaccga"
4,"ccagcacggctcacacgggctcgttgggtgataacagacg"

$ cat test_3.txt
1001110010001111110101011101101110010100
1100111011000100110110010000011011100111
1000100001000001010101101000010110000011
0000000000111111000100100001011010100011
0011011000001111001010010001001011101111
0010110110101011100100010011000000010000
1101011110010100001000111001000100011001
0011001010001001001110100000101001001101
1110110100001001100110001010101001100100
1110001011101110110000110100011011100001

$ gawk -f bwt.awk test_3.txt
22,"1111100100111011001010010110111100010110"
31,"1010101011001100100011011111001110010010"
31,"1110100100000000001010111001001100000100"
1,"1000001010101000001010010101000100101110"
9,"1010101110010001010110010101010110111000"
14,"1010000010010010001010111100101010001000"
36,"1101110010011000010001000011101011010100"
10,"1010011101111110100000000000100010010100"
40,"1010101111110011000010011100010001000010"
37,"1110100000101001110111011110011010101000"

ここで anarchy golf - BWT に記載されているものと数値がずれていますが、これは 1 からカウントするか 0 からカウントするかの違いによるものです。

tag_gawk.png tag_gawk.png