時間が経つにつれて、Pythonはエンタープライズプラットフォームよりも関連性が高くなりました。そのため、Pythonのサブストリング検索アルゴリズムの分析に注目してください。
文字列オブジェクトの実装は、 Objects / stringobject.cにあります。 さまざまなタイプの検索（ find 、 rfind 、 __contains__ ）を担当する関数の定義は、 Objects / stringlib / find.hです。 これらすべての関数は（ split 、 replaceなどとともに） Objects / stringlib / fastsearch.hで実装された検索を使用します。 それらに対処します。
アルゴリズム自体は、作者（ Fredrik Lundh ）によって（ The stringlib Library ） ボイヤー・ムーアとHorspoolアルゴリズムの組み合わせと呼ばれ、いくつかの改善と単純化が行われています。 アルゴリズムはブルームフィルターも使用します 。
それでは、行きましょう。 関数ヘッダー：
fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n, const STRINGLIB_CHAR* p, Py_ssize_t m, Py_ssize_t maxcount, int mode) /* s - , , n - , p - , ( ), m - , maxcount - , , mode - / / */
すべてが明らかなようです。 defineステートメントを見てみましょう：
/* mode */ #define FAST_COUNT 0 #define FAST_SEARCH 1 #define FAST_RSEARCH 2 /* STRINGLIB_BLOOM_WIDTH \( ) 32, 64, 128 */ #define STRINGLIB_BLOOM_ADD(mask, ch) ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1))))) #define STRINGLIB_BLOOM(mask, ch) ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
このブルームフィルターの実装はどのように機能しますか？ 最後のログ（STRINGLIB_BLOOM_WIDTH）ビットに基づいた各文字には番号が割り当てられます。 たとえば、 itの場合は1です。
>>> ord('a') & 31 1
q - 17の場合 ：
>>> ord('q') & 31 17
論理 "OR" STRINGLIB_BLOOM_ADDを使用すると、フィルターマスクに表示される文字に関する情報が蓄積されます。 後で、 STRINGLIB_BLOOMを使用して、フィルターに文字が追加されたかどうかを確認できます。 もちろん、このチェックでは誤検知が発生する可能性があります（ STRINGLIB_BLOOMは0 以外を返しますが、実際には文字は文字列\フィルターにありません）。
>>> ord(']') & 31 29 >>> ord('}') & 31 29
しかし、それは非常に安価であり、比較の回数を減らすのに役立ちます。
これで、アルゴリズム自体に進むことができます。 m> nおよびm <= 1の場合の明らかなロジック：
w = n - m; if (w < 0 || (mode == FAST_COUNT && maxcount == 0)) return -1;
および（コードの一部は、記事を破らないように省略されています）：
if (m <= 1) { if (m <= 0) return -1; if (mode == FAST_COUNT) { /* ... */ } else if (mode == FAST_SEARCH) { for (i = 0; i < n; i++) if (s[i] == p[0]) return i; } else { /* FAST_RSEARCH */ /* ... */ } return -1; }
その後、いくつかの新しい変数が表示され、必要なサブストリングのマスクが埋められます。
mlast = m - 1; skip = mlast - 1; mask = 0; for (i = 0; i < mlast; i++) { STRINGLIB_BLOOM_ADD(mask, p[i]); if (p[i] == p[mlast]) skip = mlast - i - 1; } STRINGLIB_BLOOM_ADD(mask, p[mlast]);
skipは数値で、デフォルトでは検索文字列の最後の文字のインデックスから1を引いたものです。文字列に最後の文字と等しい文字が含まれる場合、 skipは文字列の最後の文字と最後の文字のインデックスの差です。
ウィキペディアの主要なアルゴリズムのアイデアの説明：
左から右にスキャンし、右から左に比較します。 テキスト（行）の先頭とテンプレートが結合され、チェックはテンプレートの最後の文字から始まります。 文字が一致する場合、パターンの最後から2番目の文字が比較されます。パターンのすべての文字が文字列のスーパーインポーズ文字と一致する場合、部分文字列が見つかり、検索が終了します。
パターンの一部の文字が文字列の対応する文字と一致しない場合、パターンは右に数文字シフトされ、最後の文字からチェックが再開されます。
実際には、この説明の実装（上記のw = n-m ）：
for (i = 0; i <= w; i++) { if (s[i+m-1] == p[m-1]) { /* , */ for (j = 0; j < mlast; j++) if (s[i+j] != p[j]) break; if (j == mlast) { /* ! */ if (mode != FAST_COUNT) /* - , */ return i; /* */ count++; if (count == maxcount) return maxcount; i = i + mlast; continue; } /* , */ /* , */ if (!STRINGLIB_BLOOM(mask, s[i+m])) /* , */ i = i + m; else /* , 'skip' */ i = i + skip; } else { /* . , */ if (!STRINGLIB_BLOOM(mask, s[i+m])) /* , */ i = i + m; /* , i++ */ } }
視覚化のビット。 文字列「drum」を操作して、部分文字列「aba」を探しましょう。
skip = 1 i = 0: ______________ |||||||| | - , i++ _______ |||| i = 1: ______________ |||||||| | - , _______ |||| ______________ |||||||| | - . "" "" , skip, for i += 2 _______ |||| i = 3: ______________ |||||||| | - , _______ |||| ______________ |||||||| | - , _______ |||| ______________ |||||||| | - , _______ ||||
まあ、それだけです。
気に入ったとしても、Pythonソースには掘り下げるのに興味深い場所がまだたくさんあります。 たとえば、 Objects / dictobject.cのlist.sortまたはObjects / dictobject.cのdict.getの実装 。
頑張って！:)