WEB上で打刻できるタイムカードサービスを作った

タイトルで落ちてるんですが、WEB上で打刻できるタイムカードサービスを作りました。

Time Card

アクセスすると、ログインダイアログが表示されます。

f:id:bamch0h:20190504212756p:plain

Sign-Up ボタンを押すと、ユーザー登録画面になります。

f:id:bamch0h:20190504212933p:plain

ユーザー登録してもらうと、仮登録状態になります。

f:id:bamch0h:20190504213334p:plain

登録したメール宛にメールが送信されるのでメール上のリンクを 押してもらって、本登録を完了してください。

f:id:bamch0h:20190504213529p:plain

リンクをクリックすると、以下のページが表示されます。 このページはこれ以上なにも起こらないので閉じてください。

f:id:bamch0h:20190504213608p:plain

上記のページが表示されると、ユーザー検証中のページが以下のページに遷移します。

f:id:bamch0h:20190504213809p:plain

名前を入れてもらうと、タイムカードページになります。

f:id:bamch0h:20190504213943p:plain

オレンジのボタンを押してもらうと、出社状態になります。

f:id:bamch0h:20190504214036p:plain

退社ボタンで退社します。

はい、それだけです。

時間が自動で計算されたりもしないし、管理者モードみたいなものもないので使い勝手は微妙ですが、もしよかったら使ってみてください。

ソースは こちら にありますので、PRもお待ちしております。

自然順ソート(マルチバイト対応改良版 & Windows エクスプローラー準拠)

何度も同じようなブログを連投してしまいますが、先のブログには大きな数字を使うとちゃんと動かないという欠点がありました。今回はそれを改良したバージョンになります。

先のバージョンでは、strconv.Atoi を使用している関係で どうしても数値が int の範囲を超えることができませんでした。

今回はstrconv.Atoi を使用せずに、文字列比較のみで数字を順番に並べます。

Windows エクスプローラーを色々触って確かめていると、どうもゼロサプレスした値を右寄せ比較しているだけなのではないか?ということに気付きました。

なので、数字比較の処理の中で頭の 0 は読み飛ばした後、右寄せ比較を行うようにしました。

そうすると、WIndows エクスプローラーのソートに近づけることができました。

package main

import (
    "fmt"
    "sort"
    "unicode"
)

func getRune(ru []rune, i int) (rune, int) {
    for x := i; x < len(ru); x++ {
        if unicode.IsSpace(ru[x]) {
            continue
        }
        return ru[x], x
    }
    return rune(0), len(ru)
}

func compareNumber(a, b []rune, ai, bi int) int {
    aj := ai
    for len(a) > aj {
        if a[aj] != '0' {
            break
        }
        aj++
    }

    bj := bi
    for len(b) > bj {
        if b[bj] != '0' {
            break
        }
        bj++
    }

    bias := 0

    for {
        if (len(a) <= aj || !unicode.IsNumber(a[aj])) && (len(b) <= bj || !unicode.IsNumber(b[bj])) {
            return bias
        }

        if len(a) <= aj || !unicode.IsNumber(a[aj]) {
            return -1
        }

        if len(b) <= bj || !unicode.IsNumber(b[bj]) {
            return 1
        }

        ca := a[aj]
        cb := b[bj]

        if ca < cb {
            if bias == 0 {
                bias = -1
            }
        }

        if ca > cb {
            if bias == 0 {
                bias = 1
            }
        }

        aj++
        bj++
    }
}

func natualSort0(a, b []rune) int {
    var ca, cb rune
    var ai, bi int
    for {
        if len(a) <= ai && len(b) <= bi {
            return 0
        }

        if len(a) <= ai {
            return -1
        }

        if len(b) <= bi {
            return 1
        }

        ca, ai = getRune(a, ai)
        cb, bi = getRune(b, bi)

        if unicode.IsNumber(ca) && unicode.IsNumber(cb) {
            if ret := compareNumber(a, b, ai, bi); ret != 0 {
                return ret
            }
        }

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }

        ai++
        bi++
    }
}

func naturalSort(strings []string) func(i, j int) bool {
    return func(i, j int) bool {
        return natualSort0([]rune(strings[i]), []rune(strings[j])) <= 0
    }
}

func dumpByNaturalSort(strings []string) {
    sort.Slice(strings, naturalSort(strings))
    for i, s := range strings {
        if i != 0 {
            fmt.Print(" < ")
        }
        fmt.Printf("%+v", s)
    }
    fmt.Println()
}

func main() {
    dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"})
    // a < a0 < a1 < a1a < a1b < a2 < a10 < a20

    dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8", "x01-y09"})
    // x01-y09 < x2-g8 < x2-y7 < x2-y08 < x8-y8

    dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"})
    // 1.001 < 1.1 < 1.002 < 1.02 < 1.3 < 1.010

    dumpByNaturalSort([]string{"001_a", "001", "01", "1", "10", "010", "2", "002"})
    // 001 < 001_a < 01 < 1 < 002 < 2 < 010 < 10

    dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"})
    // a001 < a01 < a1 < a002 < a2 < a010 < a10

    dumpByNaturalSort([]string{"3", "1", "10", "2", "20"})
    // 1 < 2 < 3 < 10 < 20

    dumpByNaturalSort([]string{"4294967294", "1", "4294967296", "4294967299", "11111111111111111222222222222222"})
    // 1 < 4294967294 < 4294967296 < 4294967299 < 11111111111111111222222222222222
}

自然順ソート(マルチバイト対応)

2019/4/17 追記

改良版書きました!!

自然順ソート(マルチバイト対応改良版 & Windows エクスプローラー準拠) - bamch0h’s diary

前回前々回 の続きですが、マルチバイトの数字には対応できていなかったので対応させました。こちら を参考にしつつ、Windows エクスプローラー準拠の動作を実現させました。

前回のコードのままだと strconv.Atoi() でマルチバイト数字はパースエラーとなってしまうので、その前段に golang.org/x/text/width パッケージを挟むことで、全角数字を半角数字にしてから数字に変換しています。golang にはこういうパッケージが標準/準標準でたくさんあるのでありがたいですね。

package main

import (
    "fmt"
    "sort"
    "strconv"
    "unicode"

    "golang.org/x/text/width"
)

func getRune(ru []rune, i int) (rune, int) {
    for x := i; x < len(ru); x++ {
        if unicode.IsSpace(ru[x]) {
            continue
        }
        return ru[x], x
    }
    return rune(0), len(ru)
}

func natualSort0(a, b []rune) int {
    var ca, cb rune
    var ai, bi int
    for {
        if len(a) <= ai && len(b) <= bi {
            return 0
        }

        if len(a) <= ai {
            return -1
        }

        if len(b) <= bi {
            return 1
        }

        ca, ai = getRune(a, ai)
        cb, bi = getRune(b, bi)

        if unicode.IsNumber(ca) && unicode.IsNumber(cb) {
            aj := ai + 1
            for len(a) > aj {
                if !unicode.IsNumber(rune(a[aj])) {
                    aj--
                    break
                }
                aj++
            }

            bj := bi + 1
            for len(b) > bj {
                if !unicode.IsNumber(rune(b[bj])) {
                    bj--
                    break
                }
                bj++
            }

            sa := a[ai:aj]
            if len(sa) == 0 {
                sa = []rune{a[ai]}
            }
            ia, err := strconv.Atoi(width.Narrow.String(string(sa)))
            if err != nil {
                panic(err)
            }

            sb := b[bi:bj]
            if len(sb) == 0 {
                sb = []rune{b[bi]}
            }

            ib, err := strconv.Atoi(width.Narrow.String(string(sb)))
            if err != nil {
                panic(err)
            }

            if ia < ib {
                return -1
            }

            if ia > ib {
                return 1
            }

            // Windows エクスプローラーの仕様と合わせるために
            // 今回は削除
            // if len(a[ai:aj]) < len(b[bi:bj]) {
            //     return -1
            // }

            // if len(a[ai:aj]) > len(b[bi:bj]) {
            //     return -1
            // }

            // ai = aj
            // bi = bj
        }

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }

        ai++
        bi++
    }
}

func naturalSort(strings []string) func(i, j int) bool {
    return func(i, j int) bool {
        return natualSort0([]rune(strings[i]), []rune(strings[j])) <= 0
    }
}

func dumpByNaturalSort(strings []string) {
    sort.Slice(strings, naturalSort(strings))
    for i, s := range strings {
        if i != 0 {
            fmt.Print(" < ")
        }
        fmt.Printf("%+v", s)
    }
    fmt.Println()
}

func main() {
    dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"})
    // a < a0 < a1 < a1a < a1b < a2 < a10 < a20

    dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"})
    // x2-g8 < x2-y7 < x2-y08 < x8-y8

    dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"})
    // 1.001 < 1.1 < 1.002 < 1.02 < 1.3 < 1.010

    dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"})
    // 001 < 01 < 1 < 002 < 2 < 010 < 10

    dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"})
    // a001 < a01 < a1 < a002 < a2 < a010 < a10

    dumpByNaturalSort([]string{"3", "1", "10", "2", "20"})
    // 1 < 2 < 3 < 10 < 20
}

自然順ソート別実装(Windows エクスプローラー準拠?)

2019/4/17 追記

改良版書きました!!

自然順ソート(マルチバイト対応改良版 & Windows エクスプローラー準拠) - bamch0h’s diary

前の記事 の最後に、ゼロパディングされた数値とそうでない数値が存在した場合に数値順に並んでくれないという問題があると書きました。今回はそれを解消したいと思います。

考え方としては単純で、文字列中の数値の部分を取り出して数値に変換したのちに大小比較をするだけです。もし数値が同じであれば桁数で比較して大小を決定します。

Goでの実装

今回もGoで実装しました。前回の記事から変更している部分は naturalSort0 の 数値かどうかを判定するif文の中のみです。数値の始まりと数値の終わりのインデックスを取得して、部分文字列を作成し、部分文字列を数値に変換したのち大小比較を行っています。初めは、比較結果がイコールだった場合は桁数も比較していたのですが、Windowsエクスプローラーの仕様と合わせるために削除しました。

package main

import (
    "fmt"
    "sort"
    "strconv"
    "unicode"
)

func getRune(s string, i int) (rune, int) {
    for x := i; x < len(s); x++ {
        if unicode.IsSpace(rune(s[x])) {
            continue
        }
        return rune(s[x]), x
    }
    return rune(0), len(s)
}

func natualSort0(a, b string) int {
    var ca, cb rune
    var ai, bi int
    for {
        if len(a) <= ai && len(b) <= bi {
            return 0
        }

        if len(a) <= ai {
            return -1
        }

        if len(b) <= bi {
            return 1
        }

        ca, ai = getRune(a, ai)
        cb, bi = getRune(b, bi)

        if unicode.IsDigit(ca) && unicode.IsDigit(cb) {
            aj := ai + 1
            for len(a) > aj {
                if !unicode.IsDigit(rune(a[aj])) {
                    aj--
                    break
                }
                aj++
            }

            bj := bi + 1
            for len(b) > bj {
                if !unicode.IsDigit(rune(b[bj])) {
                    bj--
                    break
                }
                bj++
            }

            sa := a[ai:aj]
            if sa == "" {
                sa = string(a[ai])
            }
            ia, _ := strconv.Atoi(sa)

            sb := b[bi:bj]
            if sb == "" {
                sb = string(b[bi])
            }
            ib, _ := strconv.Atoi(sb)

            if ia < ib {
                return -1
            }

            if ia > ib {
                return 1
            }

            // Windows エクスプローラーの仕様と合わせるために
            // 今回は削除
            // if len(a[ai:aj]) < len(b[bi:bj]) {
            //     return -1
            // }

            // if len(a[ai:aj]) > len(b[bi:bj]) {
            //     return -1
            // }

            // ai = aj
            // bi = bj
        }

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }

        ai++
        bi++
    }
}

func naturalSort(strings []string) func(i, j int) bool {
    return func(i, j int) bool {
        return natualSort0(strings[i], strings[j]) <= 0
    }
}

func dumpByNaturalSort(strings []string) {
    sort.Slice(strings, naturalSort(strings))
    for i, s := range strings {
        if i != 0 {
            fmt.Print(" < ")
        }
        fmt.Printf("%+v", s)
    }
    fmt.Println()
}

func main() {
    dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"})
    // a < a0 < a1 < a1a < a1b < a2 < a10 < a20

    dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"})
    // x2-g8 < x2-y7 < x2-y08 < x8-y8

    dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"})
    // 1.001 < 1.1 < 1.002 < 1.02 < 1.3 < 1.010

    dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"})
    // 001 < 01 < 1 < 002 < 2 < 010 < 10

    dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"})
    // a001 < a01 < a1 < a002 < a2 < a010 < a10
}

まとめ

自然順ソートでゼロパディングされた数値とそれ以外の数値が混在していたとしても数値順に並ぶようなアルゴリズムを考え、Go言語で実装しました。 しかし、この実装だと、小数点の場合に順番に並んでくれないため、小数点を使うようなソートには向いていません。 ただ、ファイル名等を順番に並べるようなケースでは重宝すると思います。

自然順ソートをGoで実装

文字列の中に数値があるような場合、ソートの時にその数値の桁がそろっていないと意図しない順番になることがあります。

a1
a10
a2

のようなケースです。実際には

a1
a2
a10

のように数字順に並んでほしいですよね、それを実現するのが自然順ソート(Natural Sort) です。

アルゴリズム

以下のURLに詳細なアルゴリズムが記述されています。

Natural Order String Comparison

ただ、いかんせん英語なのであまり理解ができませんでした。

同ページにC言語で記述されたソースコードへのリンク(http://sourcefrog.net/projects/natsort/strnatcmp.c) があったので、それをもとに私の理解を以下に記します。

文字列を1文字ずつ走査して数値が出現したタイミングで数値比較を行います。ゼロパディング(数値の頭をそろえるために0埋めすること)をされている場合は左寄せ比較(文字列比較とほぼ等価の比較)を行い、それ以外の場合は右寄せ比較を行います。右寄せ比較では桁数が判明するまで1文字ずつ数値比較を行い、桁数が判明した段階で、大小関係を確定させます。また、空白は無視します。結構単純なアルゴリズムですが、これだけのことで数値があべこべにならずにソートされます。

左寄せ比較

左寄せ比較では、文字が数値以外になるまで左から順番に文字比較を行います。数値がイコールなら次の文字を比較し、大小関係が判明すればその時点で比較は終了します。もし、数値以外の文字がどちらかの比較文字に現れた場合は、もう片方の数値より桁が小さいということになり、その時点で大小関係が判明するので比較は終了します。もし同時に数値ではない文字が現れた場合は数値部分はイコールとなり、文字列比較を続けます。

例1 : ゼロパディングされた数値

A: 0012
B: 0135

A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
A[1] -> 1, B[1] -> 0 : A[1] < B[1] なので A < B となり比較終了
例2 : 数値以外の文字が後ろにつくケース

A: 01a
B: 015

A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
A[1] -> 1, B[1] -> 1 : 数値がイコールなので次の文字を比較
A[2] -> a, B[2] -> 5 : A[2]が文字なので、Bのほうが数値の桁数が多いと
                       判断できるため、A < B となり比較終了
例3 : 数値が文字列中に複数回存在する場合

A: 0a03a
B: 0a02b

A[0] -> 0, B[0] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
                       数値はイコールなので次の文字を比較
A[1] -> a, B[1] -> a : 数値以外の文字が出現したので左寄せ数値比較は行わず
                       文字比較を行う。比較の結果イコールであるため
                       次の文字を比較
A[2] -> 0, B[2] -> 0 : 数値なので数値比較, 数値が0なので左寄せ比較
                       数値はイコールなので次の文字を比較
A[3] -> 3, B[3] -> 2 : A[3] > B[3] なので A > B となり比較終了

右寄せ比較

右寄せ比較では、左寄せ比較と同様に左から一文字ずつ数値比較を行いますが、大小関係が判明しても比較を終了せず、桁数が判明するまで大小関係を保持します。桁数が同じだった場合、保持していた大小比較でもって大小判定を行い、桁数が違った場合は桁数で大小判定を行います。

例1 : 桁数が同じ場合

A: a20
B: a15

A[0] -> a, B[0] -> a : 文字列比較、イコールなので次の文字を比較
A[1] -> 2, B[1] -> 1 : A > B となるが、桁数が確定しないので、大小比較結果を保存し、次の文字を比較
A[2] -> 0, B[2] -> 5 : 数値の続きなので、比較をスキップし次の文字を比較
A[3] -> *, B[3] -> * : 両方が終端に達し、桁数が同じなので、保存していた大小結果を最終結果とする
例2 : 桁数が違う場合

A: a2b
B: a15c

A[0] -> a, B[0] -> a : 文字列比較、イコールなので次の文字を比較
A[1] -> 2, B[1] -> 1 : A > B となるが、桁数が確定しないので、次の文字を比較
A[2] -> b, B[2] -> 5 : Aが終端に達したので 桁数が A < B となり、大小判定が確定

Goでの実装

2019/4/16 AM 8:00 追記

すでに実装があるので、そちらを見ていただいたほうがいいと思います。 mattn.kaoriya.net せっかくなので以下のソースは残しておきます。

2019/4/17 追記

改良版書きました!!

自然順ソート(マルチバイト対応改良版 & Windows エクスプローラー準拠) - bamch0h’s diary

Goでの実装はこんな感じになります。もうちょっとうまく書く方法がありそうですが、さしあたってはうまく動いているようです。

package main

import (
    "fmt"
    "sort"
    "unicode"
)

func compareLeft(a, b string) int {
    var ai, bi int
    for {
        if (len(a) <= ai || !unicode.IsDigit(rune(a[ai]))) && (len(b) <= bi || !unicode.IsDigit(rune(b[bi]))) {
            return 0
        }

        if len(a) <= ai || !unicode.IsDigit(rune(a[ai])) {
            return -1
        }

        if len(b) <= bi || !unicode.IsDigit(rune(b[bi])) {
            return 1
        }

        ca, cb := rune(a[ai]), rune(b[bi])

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }

        ai++
        bi++
    }
}

func compareRight(a, b string) (bias int) {
    for ai, bi := 0, 0; ; ai, bi = ai+1, bi+1 {
        if (len(a) <= ai || !unicode.IsDigit(rune(a[ai]))) && (len(b) <= bi || !unicode.IsDigit(rune(b[bi]))) {
            return bias
        }

        if len(a) <= ai || !unicode.IsDigit(rune(a[ai])) {
            return -1
        }

        if len(b) <= bi || !unicode.IsDigit(rune(b[bi])) {
            return 1
        }

        ca, cb := rune(a[ai]), rune(b[bi])

        switch {
        case ca < cb:
            if bias == 0 {
                bias = -1
            }
        case ca > cb:
            if bias == 0 {
                bias = 1
            }
        }
    }
}

func getRune(s string, i int) (rune, int) {
    for x := i; x < len(s); x++ {
        if unicode.IsSpace(rune(s[x])) {
            continue
        }
        return rune(s[x]), x
    }
    return rune(0), len(s)
}

func natualSort0(a, b string) int {
    var ca, cb rune
    for ai, bi := 0, 0; ; ai, bi = ai+1, bi+1 {
        if len(a) <= ai && len(b) <= bi {
            return 0
        }

        if len(a) <= ai {
            return -1
        }

        if len(b) <= bi {
            return 1
        }

        ca, ai = getRune(a, ai)
        cb, bi = getRune(b, bi)

        if unicode.IsDigit(ca) && unicode.IsDigit(cb) {
            if ca == '0' || cb == '0' {
                if ret := compareLeft(a[ai:], b[bi:]); ret != 0 {
                    return ret
                }
            } else {
                if ret := compareRight(a[ai:], b[bi:]); ret != 0 {
                    return ret
                }
            }
        }

        if ca < cb {
            return -1
        }

        if ca > cb {
            return 1
        }
    }
}

func naturalSort(strings []string) func(i, j int) bool {
    return func(i, j int) bool {
        return natualSort0(strings[i], strings[j]) <= 0
    }
}

func dumpByNaturalSort(strings []string) {
    sort.Slice(strings, naturalSort(strings))
    for i, s := range strings {
        if i != 0 {
            fmt.Print(" < ")
        }
        fmt.Printf("%+v", s)
    }
    fmt.Println()
}

func main() {
    dumpByNaturalSort([]string{"a20", "a10", "a2", "a1b", "a1a", "a1", "a0", "a"})
    // a < a0 < a1 < a1a < a1b < a2 < a10 < a20

    dumpByNaturalSort([]string{"x8-y8", "x2-y08", "x2-y7", "x2-g8"})
    // x2-g8 < x2-y08 < x2-y7 < x8-y8

    dumpByNaturalSort([]string{"1.3", "1.1", "1.02", "1.010", "1.002", "1.001"})
    // 1.001 < 1.002 < 1.010 < 1.02 < 1.1 < 1.3

    dumpByNaturalSort([]string{"001", "01", "1", "10", "010", "2", "002"})
    // 001 < 002 < 01 < 010 < 1 < 2 < 10

    dumpByNaturalSort([]string{"a001", "a01", "a1", "a10", "a010", "a2", "a002"})
    // a001 < a002 < a01 < a010 < a1 < a2 < a10
}

まとめ

自然順ソートについて理解し、Goで実装してみました。ある程度はうまく動いているようですが、ゼロパディングされた数値とそうでない数値が混在するような場合や、ゼロパディングされた数値同士でも桁が違う場合などは期待した結果にはなってくれませんでした。これを解決する案はぼんやりあって、ゼロパディングされた数値文字列を取り出して数値比較を行うことで解決できるんじゃないかなぁとは思っていますが、まだ実装するには至っていません。

ブルームフィルタをGoで書く

要約

Turing Complete FM #13 を聞いていると、ブルームフィルタというデータ構造についての話題がありました。ブルームフィルタというものを知らなかったので色々調べてみると面白そうだったのでGoで実装してみました。

ブルームフィルタとは?

誤解を恐れず言うと、存在可否をすごい早く判定できるけど誤判定する可能性があるデータ構造です。ただ「存在しない」という結果の場合は誤判定はせず 100% 存在しませんが、「存在する」という結果の場合は実際は存在しない場合があります。

判定結果 実際
存在しない 存在しない
存在する 存在する or 存在しない

この「存在しなけど存在すると判定する」ことを「偽陽性」というらしいです。

ブルームフィルタの作り方

ブルームフィルタでは存在するもののリストを一つの固定長ビット列に保存します。リストの要素を複数のハッシュ関数でハッシュ化し、そのデータをビット列に重ね書きすることでブルームフィルタが完成します。ただ、ハッシュ化したデータをそのままビット列に書くのではなく、ハッシュ値をインデックスとみなして、インデックスのビットをセットすることで要素を保存していきます。

f:id:bamch0h:20190413140450p:plain

ハッシュ関数は同じ関数でもよいですが、その場合はそれぞれで別々のハッシュ値を取り出すためにそれぞれに別々のシードをつけてあげる必要があります。

要素の検索

ブルームフィルタを作った後、要素を検索します。検索する要素をフィルタを作った時と同じハッシュ関数にかけて、インデックスを算出します。算出したインデックスのビットがすべて1ならその要素は存在していると判断され、インデックスのビットのうち、どれか一つでも0なら存在しないと判断されます。

f:id:bamch0h:20190413143155p:plain

誤判定ケース

存在しない要素でも、計算したインデックスが偶然すべて1になると誤判定になります。

f:id:bamch0h:20190413144039p:plain

誤判定の確率

誤判定の確率はビット配列のサイズ(m)、登録する要素の数(n)、ハッシュ関数の数(k) で決まります。確率を(p)とすると以下の公式になるそうです。

f:id:bamch0h:20190413145510p:plain

僕はビット配列サイズと確率が固定の場合に最大要素登録数となるハッシュ関数の個数が知りたかったので n を左辺とする式に変形しました。

f:id:bamch0h:20190413165400p:plain

例えば、m = 8192 で p = 0.01 の場合の n と k の関係をグラフ化すると以下のようになります。

f:id:bamch0h:20190413165946p:plain

これを見ると、k = 7 の時に n = 854 となり、このラインが 偽陽性 0.01 を超えない最大の格納数となるようです。

使いどころ

誤判定するようなものに使いどころがあるのか?と思ってしまうけど、キャッシュ存在判定によく使われているようです。SQLのテーブル結合でも内部的に使用している場合もあるようです。フィルタというくらいなので、検索要素が多く、その検索が重い場合にその前段にブルームフィルタを置いて、検索要素数を減らしたうえで、本来の検索をする。といったような用途に使うのがいいのかもしれません。

Goで実装してみる。

上記を踏まえて実装したのが以下のコードになります。今回はハッシュ関数に Goの標準パッケージに添付されている hash/fnv を使用しました。また、k個のハッシュ関数を hash/fnv から導くために ダブルハッシュ法を使用しました (参考資料: C++でブルームフィルタを実装する方法 | POSTD) ダブルハッシュ法に関してはよくわかってないですが、ハッシュ値とシード値をダブルハッシュ関数に渡すことでランダムはハッシュ関数がお手軽に手に入れられるもの。という認識です。main() 関数ではランダムな要素を854個登録し、そのあとで、ランダムな要素 百万個を検索したときの偽陽性と登録した要素がすべてマッチするかを調べています。実行の結果、偽陽性に関しては理論値の0.01に近い確率で偽陽性が判定できていて、登録した要素もすべてマッチするので実装としては問題ないかと思っています。

package main

import (
    "fmt"
    "hash"
    "hash/fnv"
    "io"
    "math/rand"
    "time"
)

func NewBloomFilter(msize, hsize int, hfunc func() hash.Hash64) *BloomFilter {
    m := make([]bool, msize)
    return &BloomFilter{
        m,
        hsize,
        hfunc,
    }
}

type BloomFilter struct {
    m     []bool
    hsize int
    hfunc func() hash.Hash64
}

func (b *BloomFilter) Set(data string) {
    hashA, hashB := b.hash(data)
    for i := 0; i < b.hsize; i++ {
        ofs := b.nthHash(hashA, hashB, i, len(b.m))
        b.m[ofs] = true
    }
}

func (b *BloomFilter) IsMatch(data string) bool {
    hashA, hashB := b.hash(data)
    for i := 0; i < b.hsize; i++ {
        ofs := b.nthHash(hashA, hashB, i, len(b.m))
        if !b.m[ofs] {
            return false
        }
    }
    return true
}

func (b *BloomFilter) hash(data string) (uint32, uint32) {
    h := b.hfunc()
    io.WriteString(h, data)
    hash := h.Sum64()
    ha := uint32(hash)
    hb := uint32(hash >> 32)
    return ha, hb
}

func (b *BloomFilter) nthHash(ha, hb uint32, n, size int) uint32 {
    return (ha + uint32(n)*hb) % uint32(size)
}

func main() {
    b := NewBloomFilter(8192, 7, fnv.New64)

    lines := make(map[string]bool, 0)
    rand.Seed(42)
    for i := 0; i < 854; i++ {
        key := fmt.Sprintf("%v", rand.Intn(4294967294))
        lines[key] = true
        b.Set(key)
    }

    rand.Seed(time.Now().UnixNano())
    total := 0
    match := 0
    miss := 0
    for i := 0; i < 1000000; i++ {
        key := fmt.Sprintf("%v", rand.Intn(4294967294))
        total++
        if b.IsMatch(key) {
            match++
            if _, ok := lines[key]; !ok {
                miss++
            }
        }
    }
    fmt.Printf("total:%d, match:%d, miss:%d, p:%v\n", total, match, miss, float64(miss)/float64(total))

    total = 0
    match = 0
    miss = 0
    for key := range lines {
        total++
        if b.IsMatch(key) {
            match++
            if _, ok := lines[key]; !ok {
                miss++
            }
        }
    }
    fmt.Printf("total:%d, match:%d, miss:%d\n", total, match, miss)
}

まとめ

ブルームフィルタとは何かを理解し、Goで実装してみました。実装も予想していたよりも簡単に実装できたのが意外でした。ただ使いどころがいまいち思いついていなくて、実際の業務に使うことはあまりないのかもしれません。あと、Goではboolの配列(スライス)を作ると1要素に1バイト使用するので無駄なビットが出てしまうことが気になっています。無駄をなくすには別途1バイトにビットを詰めるようなクラス(構造体(?))を作るなどして対応する必要がありそうです。

Go製 Felica ライブラリ pasori に MAC付きRead とMAC付きWriteを足した

前回のブログ の続きです。前回はMACをつけないRead/Writeのコマンドを足しましたが、今回はMAC付きのRead/Writeのコマンドを足しました。前回から10日間ずっと、この実装のバグが取れずに悩んでたのでようやくブログにできる程度に実装できたのは素直にうれしいですね。

MAC といっても MAC(Media Control address)アドレスの MACではなく、Message Authentication Code の略で、データが改ざんされていないかをチェックするためのコードのことです。

参考資料

SONYのFelica技術情報 から 『FeliCa Lite-Sユーザーズマニュアル』のPDFを参照。(なぜか直接リンクだと表示されないので、いったん技術情報のページに繊維してから「ダウンロード」を選択すること)

FeliCa - おなかすいたWiki!

[PASMO] FeliCa から情報を吸い出してみる - FeliCaの仕様編 [Android][Kotlin] - Qiita

FeliCa Liteの片側認証 - hiro99ma site

使い方

MAC付き読み出しは2種類あります。MACブロックを使う方法とMAC_Aブロックを使う方法です。MACブロックはFelica Lite からの互換性のために存在していて、Felica Lite-S ではMAC_Aブロックを使うことが推奨されています。MACブロックを使ってMAC付き書き込みはできないので、MAC付き書き込みを行う場合はMAC_Aブロックを使います。

注意点として、MAC付き読み出し/書き込みを行う前に、事前にカード鍵ブロックにカード鍵を書き込んでおく必要があります。また、カード接触後にランダムチャレンジブロックにランダムな値を事前に書き込んでおく必要があります。

MACブロックを使ってのMAC付読み出し

基本的な使い方は cmd/with_mac に例があるのでそれを掲載します

package main

import (
    "fmt"

    "crypto/rand"

    "github.com/bamchoh/pasori"
)

func main() {
    var err error
    fmt.Println("Please touch FeliCa")

    // pasori 初期化
    psr, err := pasori.InitPasori()
    if err != nil {
        panic(err)
    }
    defer psr.Release()

    // ランダムチャレンジデータ生成
    psr.RC = make([]byte, 16)
    _, err = rand.Read(psr.RC)
    if err != nil {
        panic(err)
    }

    // ランダムチャレンジブロックに書き込み
    err = psr.FelicaWriteWithoutEncryption(pasori.RC, psr.RC)
    if err != nil {
        panic(err)
    }

    // カード鍵生成
    // [注意]
    // カード鍵は悪意のある第三者にバレると改ざんされてしまうので
    // 本来はソースコードに記述するのではなく、外部ファイル等で
    // 管理しておくことをお勧めします。
    //
    // あと、カードにいったん同じ鍵を書き込んでおくこと。そうしないと
    // MAC生成時にエラーになります。
    // 書き込みは普通に WriteWithoutEncryption で書き込めばOK
    psr.CK = []byte{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

    // S_PAD0 ブロックに適当に書き込み
    err = psr.FelicaWriteWithoutEncryption(pasori.S_PAD0, []byte{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3})
    if err != nil {
        panic(err)
    }

    // MAC付き読み出し
    // 第一引数にはサービスコード、第二引数以降には読み出し先ブロック番号を指定
    blocks, err := psr.FelicaReadWithMAC(pasori.SERVICE_RO, pasori.S_PAD0)
    if err != nil {
        panic(err)
    }
    fmt.Println("s_pad0", blocks[0])
}

MAC_Aブロックを使ってのMAC付読み出し/書き込み

基本的な使い方は cmd/with_mac_a に例があるのでそれを掲載します

package main

import (
    "fmt"

    "crypto/rand"

    "github.com/bamchoh/pasori"
)

func main() {
    var err error
    fmt.Println("Please touch FeliCa")

    // pasori 初期化
    psr, err := pasori.InitPasori()
    if err != nil {
        panic(err)
    }
    defer psr.Release()

    // ランダムチャレンジデータ生成
    psr.RC = make([]byte, 16)
    _, err = rand.Read(psr.RC)
    if err != nil {
        panic(err)
    }

    // ランダムチャレンジブロックに書き込み
    err = psr.FelicaWriteWithoutEncryption(pasori.RC, psr.RC)
    if err != nil {
        panic(err)
    }

    // カード鍵生成
    // [注意]
    // カード鍵は悪意のある第三者にバレると改ざんされてしまうので
    // 本来はソースコードに記述するのではなく、外部ファイル等で
    // 管理しておくことをお勧めします。
    psr.CK = []byte{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

    // MAC付き書き込み
    // 第一引数には書き込み先ブロック番号、第二引数には書き込みデータ
    err = psr.FelicaWriteWithMAC_A(pasori.S_PAD0, []byte{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3})
    if err != nil {
        panic(err)
    }

    // MAC付き読み出し
    // 第一引数にはサービスコード、第二引数以降には読み出し先ブロック番号を指定
    blocks, err := psr.FelicaReadWithMAC_A(pasori.SERVICE_RO, pasori.S_PAD0, pasori.S_PAD1)
    if err != nil {
        panic(err)
    }
    fmt.Println("s_pad0", blocks[0])
    fmt.Println("s_pad1", blocks[1])
}

MACの計算のハマりポイント

felica のDES暗号をGoで表現するには?

FelicaMAC生成には 2-key Triple DES-CBC が使われています。 DES暗号はGoではdes パッケージで取り扱うことができます。ちょうど Triple DES もパッケージの中にあるので、それを使いました。des.NewTripleDESCiper で初期化しますが、引数の key に渡すバイト配列は 24バイトでなければならず、はじめ、なにを設定すればいいのかわかりませんでした。ただ、『Felica Lite-S ユーザーズマニュアル』には セッション鍵であれば、Key1, Key2, Key3 として CK1[0]-[7], CK2[0]-[7], CK1[0]-[7] と記載があります。それを連結させた値を des パッケージの key に渡すのだと思い当たるのにそれほど時間は要りませんでした。ただ、単純に24バイトの連結した値を指定すればいいのではなくバイト単位で配列を反転させて設定してやる必要がありました。(これは Felica 側の仕様で、Triple DES の仕様ではないようです) つまり、指定する24バイトの配列は、セッション鍵生成時のTriple DESであれば、CK1[7]-[0], CK2[7]-[0], CK1[7]-[0] を連結させた24バイトを指定しなければなりませんでした。

MAC付き読み出し(MACブロック)、MAC付き読み出し(MAC_Aブロック)、MAC付き書き込みで入力パラメータが微妙に違う

全ての方法において、2-key Triple DES-CBC を使用して MACを算出するというのは同じなんですが、KEYに指定するパラメータが違ったり、初期値として代入するデータが違ったりします。(当たり前か)

メソッド key1 key2 key3 入力値
セッション鍵の生成 CK1 CK2 CK1 RC1
MAC付き読み出し(MACブロック) SK1 SK2 SK1 RC1 と ブロックデータ1[0]-[7] との排他的論理和
MAC付き読み出し(MAC_Aブロック) SK1 SK2 SK1 RC1 と ブロック番号との排他的論理和
MAC付き書き込み(MAC_Aブロック) SK2 SK1 SK2 RC1 と 複合ブロック(※1)との排他的論理和

(※1) WCNT と 書き込みブロック番号を8バイトに詰め込んで1ブロックとしたもの

読み出しはMACブロックが値として取得できるので、計算結果との検算がしやすいのだが、書き込みの場合は検算ができないので、正しく書き込めたかどうかぐらいしか情報がなく、デバッグにどえらい時間がかかってしまった。また、KEYが書き込みの時だけ逆だったり、WCNTの値を取得してこなければならなかったりと、書き込みだけ複雑な構造をしているので余計にハマりやすかった。

メモリコンフィギュレーションブロックにMAC付きアクセスの設定をしておかないとエラーになる

メモリコンフィギュレーションブロック(MC) というブロックがあり、各ブロックへのアクセス権限を設定できるようになっている。初期状態では、MAC付きアクセスなしの状態なので、MAC付きアクセスありの状態にしてやる必要がある。また、MAC付きアクセスありの設定にすると元に戻すことはできないらしいので注意が必要。どのビットがどのブロックに対応しているかは『Felica Lite-S ユーザーズマニュアル』を参照のこと。