ユニークな文字列かを判定するアルゴリズムの概要とJuliaサンプルコード

アルゴリズム図鑑絵で見てわかる26のアルゴリズム

作者:石田保輝,宮崎修一
発売日: 2017/06/05
メディア: Kindle版

目的

ユニークな文字列かを判定するためのアルゴリズムについて理解する。
アルゴリズムを実行するコードを実装してみて動作を確認する。

アルゴリズムの概要

下記2種類のアルゴリズムがある。

Boolean配列を利用したアルゴリズム

最大128文字とか256文字分のBoolean配列を定義し、各文字が文字列内に見つかればTrue、そうでなければFalseとしていく。
既にTrueとされている文字が複数回見つかれば、その文字列はユニークではないと判定する。

ビット演算を利用したのアルゴリズム

上記のアルゴリズムにおけるBoolean配列をビットのON/OFFで表現する。
これにより、配列を定義する場合よりもメモリを節約できるというメリットが得られる。

Juliaサンプルコード

先述した2種類のアルゴリズムをそれぞれJuliaで実装した。
実装したコードは下記のGitHubリポジトリで公開している。

github.com

Boolean配列を利用したアルゴリズム

サンプルコード全体
文字列サイズを128文字分に制限しているが、256文字分などに拡張することも可能。

module UniqueCharChecker
    # parameters
    const max_len = 128

    # methods
    function check_unique(str)
        println("")
        println("Check string $(str) is unique or not")

        if length(str) > max_len
            println("Too long string")
            return false
        end

        char_set = [false for i in 1:max_len]

        for j in 1:length(str)
            ascii = Int(str[j]) # used as idx of char_set
            if char_set[ascii] == true
                println("Not unique string")
                return false
            end
            char_set[ascii] = true
        end
        println("Unique string")
        return true
    end

    function main()
        @time println(check_unique("abcdefg"))
        @time println(check_unique("aaaaaaaaaaaa"))
        @time println(check_unique("aAbBcCdD"))
    end
end

if abspath(PROGRAM_FILE) == @__FILE__
    using .UniqueCharChecker
    UniqueCharChecker.main()
end

True or Falseの2値をとる配列を全てFalseで初期化する。
各文字のASCIIコードの値をとり、その数値をインデックスとして参照した配列要素をTrueにする。
もう既にTrueになっている場合は、同じ文字が複数回含まれるとしてユニークではないと判定する。

function check_unique(str)
    println("")
    println("Check string $(str) is unique or not")

    if length(str) > max_len
        println("Too long string")
        return false
    end

    char_set = [false for i in 1:max_len]

    for j in 1:length(str)
        ascii = Int(str[j]) # used as idx of char_set
        if char_set[ascii] == true
            println("Not unique string")
            return false
        end
        char_set[ascii] = true
    end
    println("Unique string")
    return true
end

ビット演算を利用したのアルゴリズム

サンプルコード全体

module UniqueCharBitChecker
    # methods
    function check_unique(str)
        println("")
        println("Check string $(str) is unique or not")

        checker = 0

        for i in 1:length(str)
            val = str[i] - 'a'
            if (checker & (1 << val)) > 0
                println("Not unique string")
                return false
            end
            checker |= (1 << val)
        end

        println("Unique string")
        return true
    end

    function main()
        @time println(check_unique("abcdefg"))
        @time println(check_unique("aaaaaaaaaaaa"))
        @time println(check_unique("axgilnrewqczpoh"))
    end
end

if abspath(PROGRAM_FILE) == @__FILE__
    using .UniqueCharBitChecker
    UniqueCharChecker.main()
end

小文字のaを基準とした各文字のASCIIコードの差分で何ビット目を立てるかを決める。
各文字に対応したビット同士のORをとっていく。
各文字を参照したとき、その文字のビットと既に立っているビットのANDをとり、その結果が0より大きければ同じ文字が複数回見つかったとしてユニークではないと判定する。

function check_unique(str)
    println("")
    println("Check string $(str) is unique or not")

    checker = 0

    for i in 1:length(str)
        val = str[i] - 'a'
        if (checker & (1 << val)) > 0
            println("Not unique string")
            return false
        end
        checker |= (1 << val)
    end

    println("Unique string")
    return true
end