Pythonにおける文字列検索の実装¶

検索用メソッドの実装¶

CPythonでは文字列操作のうち__contains__やfindの実装に、Boyer-Moore法をベースとしたアルゴリズム (BMHBNFS) を使用している。
実装はfastsearch.hを参照。
これにより、文字列検索を平均計算量 \(\mathcal{O}(n/m)\)、最悪計算量 \(\mathcal{O}(nm)\) で行うことが可能となっている。

[1]:

has_string = "ssi" in "mississippi"
print(has_string)

True

辞書の実装と文字列検索¶

Python の dict の実装詳解

pythonの辞書型の実装 - stackoverflow

CPythonにおいては、辞書はハッシュテーブルとして実装されている。

辞書のキーには文字列を使うことを前提として高速化が図られており、文字列用のハッシュがpyhash.cで実装されている。

例えば同一部分文字列の出現判定をdictで実装する際に、ローリングハッシュの代わりに文字列そのものをキーに指定することで、同程度の検索性能を得ることができる場合がある。

[2]:

from pprint import pprint
from collections import defaultdict

S = "mississippi"
N = len(S)
# 長さ3の文字列を検索
size = 3

d = defaultdict(list)
for i in range(N-size+1):
    d[S[i:i+size]].append(i)
pprint(d)

defaultdict(<class 'list'>,
            {'ipp': [7],
             'iss': [1, 4],
             'mis': [0],
             'ppi': [8],
             'sip': [6],
             'sis': [3],
             'ssi': [2, 5]})