CodeKataをKotlinでやってみた 〜Bloom Filters編〜

今回もCodeKataをKotlinでやっていきたいと思います。
「そもそもCodeKataって何？」と言う方は"CodeKataをKotlinでやってみた 〜Karate Chop編〜"をご参照ください。

トライしてみる

今回の課題は21あるKataのうち5つ目に当たる"Bloom Filters"です。

So, this kata is fairly straightforward. Implement a Bloom filter based spell checker. You’ll need some kind of bitmap, some hash functions, and a simple way of reading in the dictionary and then the words to check.

その名の通り、BloomFilterを実装してみるのが今回の課題です。「そもそもBloomFilterって何ぞ？」という方は吉田慶章さんが作成されたスライド"知っておくと便利なBloom Filter"をご参照ください。自分も最初は何もBloom Filterについて知らなかったのですが、分かりやすくまとまっており非常に助かりました。

ザッッッックリ言ってしまうと、あるデータ群の中に特定の値が存在するか判定を行う際に、判定元の辞書データ群を全て保持するのではなくそれらの各値をハッシュに変換してそのハッシュ値に対応する配列上の位置を"1"としてマークします。特定の単語が辞書データ上に存在するかどうかを判定したい時には同様のハッシュ処理を特定の値に対して行い、そのハッシュ値に対応する配列上の値が"1"であるかどうかを確認することで判定が行えるので、計算量はデータ量に依存せずO(k)の定数で行うことができます。

実装

class BloomFilters(bytes_size: Int, file: File) {
    private val bloomArray = IntArray(bytes_size)
    private val MARKED = 1
    private val HEX_RADIUS = 16

    /**
     * read a file passed when constructing the class
     * and store hash info of words written in the file at bloomArray
     */
    init {
        file.readLines()
            .forEach{
                val(md5HashNum, sha256HashNum) = generateHashes(it)

                bloomArray[md5HashNum] = MARKED
                bloomArray[sha256HashNum] = MARKED
            }
    }

    /**
     * generate hash values in two ways; md5Hex and sha256Hex
     */
    private fun generateHashes(word: String): List<Int> {
        val md5HashNum = DigestUtils.md5Hex(word).firstHexNum()
        val sha256HashNum = DigestUtils.sha256Hex(word).firstHexNum()

        return listOf(md5HashNum, sha256HashNum)
    }

    /**
     * chunk each consecutive hexadecimal numbers and return first one as Int
     */
    private fun String.firstHexNum(): Int {
        return this.chunked(1)[0].toInt(HEX_RADIUS)
    }

    /**
     * check if a passed word is included to a property file by referring bloomArray
     */
    fun includes(word: String): Boolean {
        val(md5HashNum, sha256HashNum) = generateHashes(word)

        return when {
            bloomArray[md5HashNum] == MARKED
                    && bloomArray[sha256HashNum] == MARKED -> true
            else -> false
        }
    }
}

BloomFiltersクラスに各種必要な実装を行っています。クラス作成時に配列のバイト数、包含判定の元になる辞書データに当たるファイルの二つを渡すようにしています。

initブロック内で辞書データに当たるファイルを読み込み、generateHashesメソッドで各単語に対応する16進数ハッシュ値の最初の一つを返却します。その返却される0~16の値に対応する配列上の位置にある値を"0"から"1"へ変更します。本来であればBloom Filterの偽陽性に対応するためバイト長・ハッシュ処理を適切に設定する必要があると思いますが、今回は簡易的に16バイト長の配列を利用することを想定しそのようなハッシュ処理としています（詳しくは上述の"知っておくと便利なBloom Filter"をご参照ください。）。

これらの処理はインスタンス作成時に初期化処理として行われます。作成されたインスタンスから任意の単語についてincludesを呼び出すことで、指定したファイルにその単語が含まれているかどうかを判定することができます。

テストケース整備

意図している通りに動くか、テストケースで確認をしてみます。

class BloomFiltersTest {
    @Test
    fun testBloomFilters() {
        val bloomFilter = BloomFilters(16, File("resources/wordlist.txt"))

        // words written in wordlist.txt
        assertTrue{ bloomFilter.includes("trying") }
        assertTrue{ bloomFilter.includes("engineer!") }

        // words not written in wordlist.txt
        assertFalse{ bloomFilter.includes("noway") }
        assertFalse{ bloomFilter.includes("irrelevant") }
    }
}

まず最初にBloomFiltersクラスのインスタンスを作成しています。参照元辞書データとして指定しているwordlist.txtの内容は下記の通りです。

Hi
I`m
trying
to
become
a
good
engineer!

こちらに含まれている文字がincludesに渡された場合にはtrue、そうでない場合にはfalseが返却されます。テストケで両ケースについて動作を確認してみると、無事に意図通り動いていることが確認できました！

まとめ

浅学ゆえ"Bloom Filter"など全く聞いたことがありませんでした。。。実用に耐えるものとするには圧倒的に考慮不足であるものの（例えばString.firstHexNumでは常に16進数の数字一つを返却するため、これが理にかなっているのは今回のようにBloomFilterの保持配列を16バイト長に設定した場合のみ）、楽しんで実装することができました。

お読みいただきまして、ありがとうございました！

関連記事一覧

• CodeKataをKotlinでやってみた 〜Karate Chop編〜
• CodeKataをKotlinでやってみた 〜Data Munging編〜
• [CodeKataをKotlinでやってみた 〜Bloom Filters編〜]
  (https://qiita.com/Takuyaaaa/items/eaa3848bce3bccdd946f)
• [CodeKataをKotlinでやってみた 〜Anagrams編〜]
  (https://qiita.com/Takuyaaaa/items/df06e24e6f2c7f8ced35)
• [CodeKataをKotlinでやってみた 〜Checkout編〜]
  (https://qiita.com/Takuyaaaa/items/0a4b82e30c977444c0bc)
• [CodeKataをKotlinでやってみた 〜Sorting it Out編〜]
  (https://qiita.com/Takuyaaaa/items/b5210c53bff3ff5f0512)
• [CodeKataをKotlinでやってみた 〜Counting Code Lines編〜]
  (https://qiita.com/Takuyaaaa/items/cb9143fbcb9e0b2a7822)
• [CodeKataをKotlinでやってみた 〜Tom Swift Under the Milkwood編〜]
  (https://qiita.com/Takuyaaaa/items/feccf69d2b9d95196a72)
• [CodeKataをKotlinでやってみた 〜Transitive Dependencies編〜]
  (https://qiita.com/Takuyaaaa/items/9b43473b8feffe1ce9f7)
• [CodeKataをKotlinでやってみた 〜Word Chains編〜]
  (https://qiita.com/Takuyaaaa/items/2539338252ad7e19ba18)
• [CodeKataをKotlinでやってみた 〜Simple Lists編〜]
  (https://qiita.com/Takuyaaaa/items/36ef73522bfe8d054448)