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

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

目次

目的

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

アルゴリズムの概要

• 下記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

動作確認

• 上記2つのアルゴリズムでユニーク判定をした結果の例。
• 大文字と小文字も区別して判定を出来る。