2009年 秋期 応用情報技術者試験 問2

文字列照合処理

ある文字列（テキスト）中で特定の文字列（パターン）が最初に一致する位置を求めることを文字列照合という。そのための方法として、次の二つを考える。ここで、テキストとパターンの長さは、どちらも1文字以上とする。

【方法1 単純な照合方法】

テキストを先頭から1文字ずつパターンと比較して、不一致の文字が現れたら、比較するテキストの位置（比較位置）を1文字分進める。この方法による処理例を図1に示す。

この手順を基に、テキストとパターンを与えると、最初に一致した文字位置を返すアルゴリズムを作成した。このアルゴリズムを図2に示す。

なお、テキストは配列T、パターンは配列Pに格納されており、T[n]及びP[n]はそれぞれのn番目の文字を、Tlength及びPlengthはそれぞれの長さを示す。

function search1(T,P)
    for i を1から ア まで1ずつ増やす
        for j を1から イ まで1ずつ増やす
            if T[i+j-1]とP[j]が等しい　　　◄── α
                if j と イ が等しい
                    return i
                endif
            else
                break
            endif
        endfor
    endfor
    return -1　　　　// パターンが見つからない場合は-1を返す
endfunction

【方法2 効率的な照合方法】

方法1では、パターンとテキストの文字が不一致となった場合、比較位置を1文字分進めている。ここでは、比較位置をなるべく多くの文字数分進めることで、照合における比較回数を減らすことを考える。

パターンの末尾に対応する位置にあるテキストの文字（判定文字）に着目すると、次のように比較位置を進める文字数（スキップ数）が決定できる。

(1) 判定文字がパターンに含まれていない場合は、判定文字とパターン内の文字の比較は常に不一致となるので、パターンの文字数分だけ比較位置を進める。また、判定文字がパターンの末尾だけに含まれている場合も、同様にパターンの文字数分だけ比較位置を進める。

(2) 判定文字がパターンの末尾以外に含まれている場合は、判定文字と一致するパターン内の文字が、テキストの判定文字に対応する位置に来るように比較位置を進める。ただし、パターン内に判定文字と一致する文字が複数ある場合は、パターンの末尾から最も近く（ただし、末尾を除く）にある判定文字と一致するパターン内の文字が、判定文字に対応する位置に来るように比較位置を進める。

この方法による処理例を図3に示す。

パターンが与えられると、判定文字に対応するスキップ数を一意に決定することができる。例えば、パターンHIJに対して判定文字とスキップ数の対応表を作成すると表1のようになる。

この考え方を基に作成したアルゴリズムを図4に示す。

なお、テキストは配列T、パターンは配列P、スキップ数を決める表の判定文字は配列C、スキップ数は配列Dに格納されており、T[n]、P[n]、C[n]、D[n]はそれぞれのn番目の文字又は数値を、Tlength及びPlengthはテキストとパターンの長さを示す。

このアルゴリズムは、三つの主要部分から成っている。一つ目は、与えられたパターンについて判定文字とスキップ数の対応表を作成する処理である。ここでは、配列Cに格納される空白文字は表1の"その他の文字"及びパターンの末尾の文字"J"を表現するために使用している。テキストとパターンは空白文字を含まないものとする。二つ目は、文字を比較する処理である。ここでは、現在の比較位置に対応したテキストとパターンを方法1と同様に1文字ずつ比較して、パターンに含まれる文字と対応するテキストの文字がすべて一致するか、不一致となる文字が見つかるまで繰り返す。三つ目は、判定文字とスキップ数の対応表を引いてスキップ数を決定する処理である。

function search2(T,P)
    for x を1から P.length まで1ずつ増やす
        C[x] ← " "　　　　　　　　　　　// " "は空白文字を表す
        D[x] ← P.length
    endfor
    // (1) : 表の作成
    for j を1から P.length-1 まで1ずつ増やす
        for k を1から j まで1ずつ増やす
            if C[k]とP[j]が等しい or C[k]と" "が等しい
                C[k] ← P[j]
                D[k] ← ウ
                break
            endif
        endfor
    endfor
    // 文字列を照合する
    i ← 1
    while i が ア 以下である
        // (2) : 文字の比較
        for j を1から イ まで1ずつ増やす
            if T[i+j-1]とP[j]が等しい　　　◄── β
                if j と イ が等しい
                    return i
                endif
            else
                break
            endif
        endfor
        // (3) : スキップ数の決定
        for k を1から P.length まで1ずつ増やす
            if C[k] と T[i+P.length-1]が等しい or C[k]と" "が等しい
                d ← D[k]
                break
            endif
        endfor
        i ← i+d
    endwhile
    return -1
endfunction