BM法(Python)のテキストとパターンが一致しない場合の条件分岐の意味について教えてください

Question

BM法のサンプルコードを参考にしながら、アルゴリズムの意味とコードの動きを照らし合わせています。アルゴリズムの意味は理解できたつもりでいます。ただ、以下のコードの#####をつけた条件分岐のブロックを、アルゴリズムに照らした場合、どう解釈していいのかわかりません。
この#####の部分は、テキストとパターンが一致しない時の処理ですが、
skip[ord(txt[pt])] > len(pat) - pp:
↑この箇所は、どのような状況を評価できることになるのでしょうか。

この条件分岐の式の意味がわからないので、
pt += skip[ord(txt[pt])]　として、
スキップテーブルの値分だけテキストの着目箇所を進める場合と、
pt += len(pat) - pp　と
する場合の違いがわかりません。

def bm_match(txt: str, pat:str) -> int:
    skip = [None] * 256
    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[ord(pat[pt])] = len(pat) - pt - 1

    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        
        #####
        if skip[ord(txt[pt])] > len(pat) - pp:
            pt += skip[ord(txt[pt])]
        else:
            pt += len(pat) - pp
            
    return -1



if __name__ == "__main__":
    txt = "abcxdezaabababac"
    pat = "abab"
    
    print(txt)
    print(pat)
    print(bm_match(txt, pat))

Answer 1

大きい方だけずらしましょう、という意味でしょう。

def bm_match(txt: str, pat:str) -> int:
    skip = [None] * 256
    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[ord(pat[pt])] = len(pat) - pt - 1
    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        #####
        print(f'現在位置:{txt[pt:]}')
        print(f'skip[ord(txt[pt])]:{skip[ord(txt[pt])]}, len(pat) - pp:{len(pat) - pp}]')
        if skip[ord(txt[pt])] > len(pat) - pp:
            print(f'select skip[ord(txt[pt])]:{skip[ord(txt[pt])]}')
            pt += skip[ord(txt[pt])]
        else:
            print(f'select len(pat) - pp:{len(pat) - pp}]')
            pt += len(pat) - pp
    return -1

txt = "abcxdezaabababac"
pat = "abab"
print(bm_match(txt, pat))

実行結果は以下です。

>>> print(bm_match(txt, pat))
現在位置:xdezaabababac
skip[ord(txt[pt])]:4, len(pat) - pp:1]
select skip[ord(txt[pt])]:4
現在位置:aabababac
skip[ord(txt[pt])]:1, len(pat) - pp:1]
select len(pat) - pp:1]
現在位置:abababac
skip[ord(txt[pt])]:1, len(pat) - pp:1]
select len(pat) - pp:1]
現在位置:aabababac
skip[ord(txt[pt])]:1, len(pat) - pp:3]
select len(pat) - pp:3]
現在位置:ababac
skip[ord(txt[pt])]:1, len(pat) - pp:1]
select len(pat) - pp:1]
8

Comments

[fu_3823]

ありがとうございます。「大きい方だけずらす」ことを改めて指摘され、トレースを繰り返してやっと以下の内容と、サンプルコードの関係性を理解できました。
・不一致になった場合、skip表にある値分だけカーソルを進める。
・ただし、ずらした位置が比較開始位置より手前だった場合、比較開始位置の1文字後に カーソルを進める。