雪ん子パースペクティヴ

読むとちょっとタメになるエントリー。コメントあると嬉しいです。

基本情報技術者試験のデータ構造及びアルゴリズム問題をPythonで実装する（令和元年度秋期）。

python

手当てが出るからこそ試験を受ける。

 

はろー、yukiです。

クラウドエンジニアをしていた時、取得した資格はほとんど民間のものでした。

例えば、CCNA、LPIC、Google Cloudなど。

IPAの資格はSG（情報セキュリティマネジメント）だけ持っていて、その他は未取得でした。

 

この度、会社から手当てが出ることが分かりましたので、勉強を開始しようと思います。

取得対象はレベルの低いところからで、基本情報技術者試験からにします。

FEを調べてみると、ネックとなるのは午後のアルゴリズム試験とのこと。

確かにアルゴリズム試験は、アルゴリズムやデータ構造が分からないと難しいと思います。

（トレースも途中で分からなくなってしまうかも）

 

せっかく勉強をするので、実装してみようと思います。

プログラミング言語は、僕が多用していたpythonになります。

 

今回は令和元年の秋期試験になります。

テーマは「Bitap法による文字列検索」です。

 

コードは下記。

# R1

Pat = ["A", "C", "A", "B", "A", "B"]
Mask = [0, 0, 0, 0, 0, 0]   # [1]..[26]
tText = ["A", "A", "C", "B", "B", "A", "A", "C", "A", "B", "A", "B", "A", "B"]

def Index(str):
    Alphabet = ["A", "B", "C", "D"] # "A".."Z"
    num = 0
    for i in Alphabet:
        if str == i:
            # To return ordinal number: A -> num = 0, B -> num = 1
            return num
        # If not match Pat and Alphabet, increment ordinal.
        num = num + 1

def GenerateBitMask(Pat, Mask):
    PatLen = len(Pat)
    for i in range(1, 7):   # 1..26
        # Initialize
        Mask[i - 1] = 0
    
    for i in range(1, 7):   # 1..26
        # To binary by using |(vertical bar).
        Mask[Index(Pat[i - 1])] = 1 << (i - 1) | Mask[Index(Pat[i - 1])]

    print("Mask[1]=", bin(Mask[0]))
    print("Mask[2]=", bin(Mask[1]))
    print("Mask[3]=", bin(Mask[2]))

    return PatLen

def BitapMatch(tText, Pat):
    tTextLen = len(tText)
    PatLen = GenerateBitMask(Pat, Mask)
    Status = 0
    Goal = 1 << (PatLen - 1)

    for i in range(1, tTextLen):
        Status = Status << 1 | 1
        Status = Status & Mask[Index(tText[i])]

        if Status & Goal != 0:
            # +1 is for python list' spec
            print(i - PatLen + 1 + 1)
            return i - PatLen + 1 + 1

    return -1

BitapMatch(tText, Pat)

 

Bitap法では、ビット列により文字を定義し、対象文字列と合致する位置を検索します。

実行後、検索文字列（Pat）が対象文字列（tText）内で合致した位置を返します。

コードでは、tTextの7個目からPatの文字列が全て合致するので、求めるべき数は7になります。

 

本来はアルファベットは26字で、配列もその分必要ですが、問題に合わせて省略しています。

また、pythonではビット化（2進数へ変換）にbin()を使いますが、コードではprint()で対象文字列のマスク値を出力するために使っています。

処理内（例えば、左シフトとMask[]の論理和）で使うと、bin()で変換した値はstr型になるため、論理和が求められません。
　※というより、論理和によってビット化される

求めるべき数（配列内で合致する部分の最初の序数）はPatLenに入ります。

PatLenは配列長ですので、最終的にはprint(i - PatLen + 1 + 1)で1を足しています。
　※配列の最初の序数は[0]

 

 

こちらの方の内容が大変参考になります。

 

 

 

以上

 

 

 

Googleアドセンス