[Python] ラビン-カープ法

ラビン-カープ法

テキストの中からパターンを探すときに、パターンのハッシュと検索箇所のハッシュが一致するかどうかを比較して検索を行います。

ハッシュの時間計算量が $O(m)$ の場合は、アルゴリズム全体の計算量が $O(m \times n)$ となりますが、 ローリングハッシュ関数 と呼ばれるハッシュ関数を用いることで、 定数時間でハッシュの計算を行うことができ、計算量を減らすことができます。

ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種^[1][2]。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ローリングハッシュ

A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input.

From Wikipedia, the free encyclopedia

ローリングハッシュ（再帰ハッシュ、ローリングチェックサム）は、入力された値を移動する「ウィンドウ」内で、入力がハッシュされるハッシュ関数です。

例えば、上のwikipedia にはローリングハッシュ関数の例として、以下のような関数が挙げられています。

$$H = c_1 a^{k-1} + c_2 ^{k-2} + c_3 a^{k-3} + \ldots + c_k a^0$$

$a$ は定数、$c$ は 入力値。

より簡単にするため、数値のみの文字列「’1′ ‘2’ ‘3’ ‘4’ ‘5’ ‘6’ ‘7’ ‘8’ ‘9’」を考え、この中で、「’3′ ‘4’ ‘5’」を検索するとします。

ローリングハッシュ関数は、以下のように考えます。

$$H = c_1 \times 100 + c_2 \times 10 + c_3 \times 1$$

まず、検索する文字列のハッシュは、$3 \times 100 + 4 \times 10 + 5 \times 1 = 345$ となります。

その次に、文字列 「’1′ ‘2’ ‘3’ ‘4’ ‘5’ ‘6’ ‘7’ ‘8’ ‘9’」 の最初の3文字「 ‘1’ ‘2’ ‘3’ 」のハッシュは、 $1\times 100 + 2 \times 10 + 3 \times 1 = 123$ となり、これは 345 と等しくないので、次に進みます。

次のハッシュは、$(123 – 100 \times 1) *10 + 4 = 234$ 、その次のハッシュは、 $(234 – 100 \times 2) *10 + 5 = 345$ という計算で、現在のハッシュと最初の数字、新しい数字のみでそれぞれ求めることができ、最終的には検索対象のハッシュと一致する文字列を見つけることができます。

つまり、ローリングハッシュ関数は、検索文字列がどんなに長くとも、 $H(i)$ から$H (i+1)$ を定数時間で計算をすることができます。

以下のスライドは分かりやすいです。

ローリングハッシュとサフィックスアレイ

ord(c)

Python では、ord() という組み込み関数を用いることで、ユニコード文字列を整数に変換できます。

ord(c)

ラビン-カープ法の性能の鍵となるのは、テキストのサブ文字列の逐次的ハッシュ値計算の効率化にある。一般的な効率のよいローリングハッシュ関数は、大きな素数を基数として文字列を数値化するものである。例えば基数を 101、サブ文字列を “hi” とした場合、ハッシュ値は 104 × 101¹ + 105 × 101⁰ = 10609 となる（ASCIIコードで ‘h’ は 104、’i’ は 105）。
…
例えば、テキストとして “abracadabra” があり、3文字のパターンを検索する場合、”bra” のハッシュ値は “abr”（ひとつ前のサブ文字列）のハッシュ値から先頭文字 ‘a’ の値 97 × 101² を減算し（’a’ の ASCII コードは 97で、基数として 101 を使用）、基数をかけてから “bra” の最後の文字 ‘a’ の値 97 × 101⁰ = 97 を加算する。サブ文字列が長ければ長いほど、このハッシュ法は他のハッシュ法よりも効果を発揮する。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

上の引用に書いてあるように、101 を基数としてコードを書きます。

import random
import string

def match_pattern_brobin_karp(text, pattern):

    hash_text = RollingHash(text, len(pattern))
    hash_pattern = RollingHash(pattern, len(pattern))
    for i in range(len(text) - len(pattern) + 1):
        if hash_text.hashed_value() == hash_pattern.hashed_value():
            if hash_text.text() == pattern:
                return i
        hash_text.update()

    return -1

def print_match_pattern_result(target_str, pattern):
    index =  match_pattern_brobin_karp(target_str, pattern)
    if index>=0:
        print(f'"{pattern}"は {index}番目に見つかりました。')
    else:
        print(f'"{pattern}"は見つかりません。')


class RollingHash(object):
    def __init__(self, text, size):
        self.size = size
        self.str = text
        self.hash = 0

        for i in range(self.size):
            self.hash += ord(self.str[i]) * 101 ** (self.size- i -1)

        self.init = 0
        self.end = size

    def update(self):
        if self.end <= len(self.str) - 1:
            self.hash -= ord(self.str[self.init]) * 101 ** (self.size-1)
            self.hash *= 101
            self.hash += ord(self.str[self.end])
            self.init += 1
            self.end += 1

    def hashed_value(self):
        return self.hash

    def text(self):
        return self.str[self.init:self.end]		
                


random.seed(1)
target_str = ''.join(random.choices(string.ascii_letters + string.digits, k=20))
# i0VpEBOWfbZAVaBSo63b
print(target_str)
# "BSo63"は 14番目に見つかりました。
print_match_pattern_result(target_str, "BSo63")
# "BSo6E"は見つかりません。
print_match_pattern_result(target_str, "BSo6E")

想定通りの結果を得ることができました。