かなり前に、いわゆるITアカデミーの卒業生のプレゼンテーションの1つで、講演者は、Javaのtoli文字列、.Netのtoli文字列での部分文字列検索の実装の詳細について質問されました。 もちろん、卒業生はわかりやすいものに答えることはできませんでしたが、すでに長いtodoリストに質問を置いておきました。
時間が経つにつれて、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)
すべてが明らかなようです。
defineステートメントを見てみましょう：
#define FAST_COUNT 0 #define FAST_SEARCH 1 #define FAST_RSEARCH 2 #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 { } 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 i = i + skip; } else { if (!STRINGLIB_BLOOM(mask, s[i+m])) i = i + m; } }
視覚化のビット。 文字列「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の実装 。
頑張って！:)