[Swift] NSScanner でハフマンコードを扱う

NSScanner を Swift で便利に扱える extension

文字列をパースする時に便利なのが、NSScanner です。しかし、Swift から使うには意外と面倒臭いです。以下のように、NSString を戻す場所を用意して、NSString を String に変換してとか色々面倒だったりします。特に、NSString を戻す場所を複数必要とする場合は、無駄に行数が増える事になり閉口します。

var string: NSString? = nil
if scanner.scanString("wow", intoString: &string1) {
    let token = string as! String
    // some code
}

今回はそんな NSScanner を使いやすくする NSScanner の extension を紹介します。

public extension NSScanner {
    public func scanString(string: String) -> String?
    public func scanEitherString(strings: [String]) -> String?
    public func scanUpToString(string: String) -> String?
    public func scanCharactersFromSet(set: NSCharacterSet) -> String?
    public func scanUpToCharactersFromSet(set: NSCharacterSet) -> String?
    public func scanInt() -> Int?
    public func scanFloat() -> Float?
    public func scan<T>(pattern: [String : T]) -> T?
}

今回のコードは以下のURLから入手可能となっています。
NSScanner+Z.swift
https://gist.github.com/codelynx/cd592d3a81af8141fd669077799f72e7

使い方

初期化

使いやすくと言っても、NSScanner の extension なので、初期化の部分は同様です。

let string = ...
let scanner = NSScanner(string: string)

指定文字列を scan

指定文字列を scan します。scan できた文字列は戻り値に、scan できなかった場合は nil を戻します。

if let token = scanner.scanString("token") {
   // "token" 文字列を取得
}

指定文字列まで scan

指定された文字列までを scan します。scan できなかった場合は nil を戻します。

if let string = scanner.scanUpToString(";") {
    // ";" の直前までを取得
}

連続した指定文字セットの文字列を取得

指定された連続した文字セットを scan します。scan できた部分は文字列として戻します。scan できなかった場合には nil を戻します。

let characterSet = NSCharacterSet.decimalDigitCharacterSet()
if let digits = scanner.scanCharactersFromSet(characterSet) {
    // 十進数の文字列を取得
}

複数の文字列の候補から取得

scan 候補がいくつかある場合に便利。候補の一つが scan できたらその文字列を、できなかった場合は nil を戻します。

if let string = scanner.scanEitherString(["red", "blue"]) {
    // "red" または "blue" を取得
}

指定した文字セットまでの文字列を取得

指定した文字セットの直前までの文字を取得します。

let characterSet = NSCharacterSet(charactersInString: ",;")
if let string = scanner.scanUpToCharactersFromSet(characterSet) {
   // "," または ";" までの文字列を取得
}

指定したパターンを取得

Generics を使って強力なパターンマッチング機能を提供します。パターンマッチングの情報を Dictionary で用意すると、scan できた文字（キーワード）に対応する値を戻り値として戻す。いずれのパターンにも該当しなかった場合はnilを戻します。

以下の例では、[String: Direction] を辞書として用意します。そしてその任意のキーが scan できた場合はそれに対をなす値を戻します。Generics を利用しているので、Direction のような任意な値を戻り値として処理する事が出来ていい感じに思います。

enum Direction {
    case North, South, East, West
}

let scanner = NSScanner(string: "north")
let pattern: [String: Direction] = ["north": .North, "south": .South, "east": .East, "west": .West]
if let direction = scanner.scan(pattern) {
    print("\(direction)") // "North"
}

実際の実装はこんな感じになっています。key の順序は決まっていませんので、評価される順番に依存するパターンの定義は向いていません。

public func scan<T>(pattern: [String: T]) -> T? {
    for (key, value) in pattern {
        if self.scanString(key, intoString: nil) {
            return value
        }
    }
    return nil
}

地味にサボって、すべての NSScanner の基本 API を wrap している訳ではありません。そのうちやります。

NSScanner でハフマンコードを扱う（応用編）

では、この NSScanner の extension を利用して、ハフマンコードを複合化に挑戦してみましょう。ハフマンコードは、データの出現率に応じて可変長のビットを割り当てて、データを圧縮する手法ですが、ここではその詳細は省略させていただきます。

少し考えると、NSScanner は文字列を対象にしていて bit 列を扱うには適切ではないと思うかもしれませんが、bit 列を "1"と"0"の文字列の置き換えれば、NSScannerでも扱いが便利になるはずです。

さて今回対象とするハフマンコードは、以下の URL を参考にする事にします。

将棋盤面データ圧縮に関する考察　第一回
http://www.geocities.co.jp/CollegeLife-Cafe/8331/shogi/

上記のサイトでは将棋盤の局面を駒の出現率も元にハフマンコードで符号化して圧縮するアイデアが説明されて。ますは、将棋の駒のハフマンコードを転載します。

駒	符号
空白	0
歩	10
香	1100
金	1101
桂	11100
銀	11110
玉	111010
飛	111011
角	111110
馬	11111100
龍	11111101
と	11111110
圭（成桂）	111111110
全（成銀）	1111111110
杏（成香）	1111111111

実際には空白を除く駒の符号の最後に先手なら 0 を、後手なら 1 を付加します。次に局面をハフマン符号化したデータを用意します。以下のデータは先のサイトに記載のある、平手の初期盤面をハフマン符号化したものです。

110011110011111011101111101011101111110111100111001
011101110000011111010
101101101101101101101101101
000000000
000000000
000000000
100100100100100100100100100
011111000000011101100
110001110001111001101011101001101011110011100011000

最も出現率の高い空白を0の1ビットで表現しているので、４〜６段目が効率的に圧縮されているのがよくわかります。

では、Swift で復号を実装してみましょう。まずはハフマンコードを定義してみます。先ほどの空白を除く駒のコードの最後に先手後手に応じて1ビット加えて、先手の▲と後手の▽の記号を加えた駒を表す文字列を用意します。

var decodeTable: [String: String] = [
    "0": "　・",
    "100": "▲歩",
    "11000": "▲香",
    "11010": "▲金",
    "111000": "▲桂",
    "111100": "▲銀",
    "1110100": "▲玉",
    "1110110": "▲飛",
    "1111100": "▲角" ,
    "111111000": "▲馬",
    "111111010": "▲龍",
    "111111100": "▲と",
    "1111111100": "▲圭",
    "11111111100": "▲全",
    "11111111110": "▲杏",
    "101": "▽歩",
    "11001": "▽香",
    "11011": "▽金",
    "111001": "▽桂",
    "111101": "▽銀",
    "1110101": "▽玉",
    "1110111": "▽飛",
    "1111101": "▽角",
    "111111001": "▽馬",
    "111111011": "▽龍",
    "111111101": "▽と",
    "1111111101": "▽圭",
    "11111111101": "▽全",
    "11111111111": "▽杏",
]

そして実際にハフマンコードで符号化された局面を 0 と 1 の文字列で用意します。今回は、先ほどのサイトで掲載されているコードをサンプルにしてみましょう。

let string =
    "110011110011111011101111101011101111110111100111001" +
    "011101110000011111010" +
    "101101101101101101101101101" +
    "000000000" +
    "000000000" +
    "000000000" +
    "100100100100100100100100100" +
    "011111000000011101100" +
    "110001110001111001101011101001101011110011100011000"

そして、実際にハフマンコードをNSScannerとそのextensionでデコードするコードを以下に示します。

let scanner = NSScanner(string: string)
for y in (1 ... 9) {
    var string = ""
    for x in (1 ... 9) {
        if let koma = scanner.scan(decodeTable) {
            string += koma
        }
    }
    print("\(string)")

}

結果はこの通り。等幅なフォントで見ると綺麗に整形されているはずです。

▽香▽桂▽銀▽金▽玉▽金▽銀▽桂▽香
　・▽飛　・　・　・　・　・▽角　・
▽歩▽歩▽歩▽歩▽歩▽歩▽歩▽歩▽歩
　・　・　・　・　・　・　・　・　・
　・　・　・　・　・　・　・　・　・
　・　・　・　・　・　・　・　・　・
▲歩▲歩▲歩▲歩▲歩▲歩▲歩▲歩▲歩
　・▲角　・　・　・　・　・▲飛　・
▲香▲桂▲銀▲金▲玉▲金▲銀▲桂▲香

あとは、実際のバイナリのデータと "0"と"1" の文字列を相互に変換させれば、ハフマンコードの実装でもなんとかなりそうです。

あとがき

NSScanner の extension で Generics を使った scan は個人的には結構いいなと思いました。さらに発展させて、パターンマッチングにclosure なんかを使う手もありかなとも思いながら、面白そうな反面ちょっとやりすぎかなとも思ったりもします。

執筆時点での Swift のバージョンは以下の通りです。

Apple Swift version 2.2 (swiftlang-703.0.18.1 clang-703.0.29)