【アルゴリズム】文字列照合問題とは

文字列照合問題を理解しているだろうか。
アルゴリズムを学ぶ上で基礎的な内容であるものの
その応用範囲はとても広い。

今回は、文字列照合問題を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

文字列照合問題

ある文字列(テキスト)中で特定の文字列(パターン)が一致する位置を求めること

文字列照合とは、ある文字列(テキスト)中で特定の文字列(パターン)が一致する位置を求めることである。
計算機科学では早い段階に学ぶ内容であるものの。
Web上の情報からの検索やDNA配列の特定パターンの検索に利用されるなど
その応用範囲はとても広い。

文字列照合アルゴリズムの基本的な問題(SimpleSearch)

文字列照合アルゴリズムの基本的な問題として下記のようなものがおおい。

入力値は、テキストSと語W(一文字)の２つ
出力値は、下記３つ
　Sの中にWが出現するか
　出現するのであれば，Wの出現位置はSのどこか
　Wがいくつ出現するか

最初に一致する位置を求める以外にも出現回数を求める問題も多く有る。

Pythonで文字列照合アルゴリズムの基本的な問題を解く

Pythonを使って先程の問題を解いてみると下記のようになる。
(※参考として)

S = "algolithm"
W = 'l'

included = False
countW = 0
indexes = []
for x in xrange(len(S)):
    if W == S[x]:
        included = True
        countW+=1
        indexes.append(x)
if included:
    print("%s is in %s, count: %s, indexes: %s" % (W, S, countW, indexes))
else:
    print("%s is not in %s" % (W, S))

S = "algolithm"

W = 'l'

included = False

countW = 0

indexes = []

for x in xrange(len(S)):

if W == S[x]:

included = True

countW+=1

indexes.append(x)

if included:

print("%s is in %s, count: %s, indexes: %s" % (W, S, countW, indexes))

else:

print("%s is not in %s" % (W, S))

文字列照合問題(Wが２語の場合)

Wが2語の場合は下記のようになる。

Input: テキストS，単語W
Output: テキストSにおける単語Wの最初の出現位置

def main():
    S = "algorithm"
    W = 'th'
    i = 0
    j = 0
    while i+j < len(S):
        if W[j] == S[i+j]:
            j += 1
            if j == len(W):
                print(i)
                return i
        else:
            i += 1
            j = 0
    print(len(S))
    return 0
main()

def main():

S = "algorithm"

W = 'th'

i = 0

j = 0

while i+j < len(S):

if W[j] == S[i+j]:

j += 1

if j == len(W):

print(i)

return i

else:

i += 1

j = 0

print(len(S))

return 0

main()

実行結果

$ python string_maching2.py 
6

1 2	$ python string_maching2.py 6

文字列のSimpleSearchは簡単であるものの、
一度照合に失敗すると、照合対象を0から比較し直すため効率は悪い。
入力値m, nに対する計算量が　O(mn)である。

m: テキストの文字数
n: キーワードの文字数

これをO(m)にしたアルゴリズムを「KMP法」という。
そのうち書き溜めます。

文字列照合問題を説明してください。

さて、先程の説明を読んだ人は、文字列照合問題を説明できますね。
文字列照合問題は応用範囲が広いため、ぜひしかっり理解していきたい。

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。

じゃあね〜〜〜。