技術要約：パリク予算下における置換マッチング

1. 問題定義

本論文は、一般的なアルファベット $\Sigma$ 上の置換（Jumbled/Abelian）パターンマッチング問題を扱う。長さ $m$ のパターン $P$ と長さ $n$ のテキスト $T$ が与えられたとき、古典的なタスクは、$T$ の中に $P$ のシンボル集合（マルチセット）と一致する長さ $m$ の部分文字列が存在するかどうかを判定することである。これは、$T$ 内のウィンドウのパリク・ベクトル（頻度ベクトル）が $P$ のパリク・ベクトルと一致するかどうかを確認することと同義である。

単なる検出を超えて、著者らは以下の2つの最適化バリアントへと範囲を拡張している：

1. パターン供給量下における最大実現可能部分文字列 (MFSP): $P$ のシンボル数をリソース予算（供給ベクトル）として扱い、$T$ の部分文字列 $S$ のシンボル数が $P$ のシンボル数によって成分ごとに抑えられている（すなわち、$freq(S) \preceq freq(P)$）ような、最長の $S$ を見つけることを目的とする。
2. 非重複選択: $T$ 内のすべての置換マッチの集合が与えられたとき、これらのマッチが互いに重複しないような、最大個数の部分集合を選択する。すべてのマッチは長さ $m$ であるため、これは区間パッキング問題としてモデル化される。

2. 手法およびアルゴリズム

本論文は、スライディングウィンドウ・アルゴリズムとパリク・ベクトルの差分維持に基づく統一されたフレームワークを提案している。

2.1 線形時間での置換マッチング（ベースライン）

著者らは、$O(n + \sigma)$ 時間および $O(\sigma)$ 空間（ここで $\sigma = |\Sigma|$）で置換の出現を検出するアルゴリズムを提示している。

• メカニズム: すべてのウィンドウに対して頻度ベクトルを再計算する代わりに、アルゴリズムは現在のウィンドウ $W_i$ に対する差分ベクトル $\Delta_i(c) = freq(W_i)(c) - freq(P)(c)$ を維持する。
• 最適化: 単一の整数カウンタ $nz_i$ が、$\Delta_i$ の非ゼロ項の数を追跡する。ウィンドウがマッチするのは、$nz_i = 0$ の場合のみである。
• 更新: ウィンドウがスライドするとき、$\Delta$ の座標は2つだけ変化する（1つの文字が抜け、1つの文字が入る）。アルゴリズムは、座標がゼロを跨いだかどうかに基づいて、$nz$ を定数時間で更新する。

2.2 MFSP: 最大実現可能部分文字列

パッキング・バリアントを解くために、著者らは2ポインタ（スライディングウィンドウ）アルゴリズムを導入しており、これも $O(n + \sigma)$ 時間で動作する。

• メカニズム: アルゴリズムはウィンドウ $T[\ell..r]$ と、現在のウィンドウのカウント配列 cnt を維持する。違反カウンタ viol は、シンボルが $freq(P)$ によって定義された予算を超過した回数を追跡する。
• ロジック: 右ポインタ $r$ がウィンドウを拡張する。文字の追加によって違反（すなわち cnt が sup を超過すること）が発生した場合、実現可能性が回復するまで左ポインタ $\ell$ を進める。
• 正当性: アルゴリズムは実現可能性の単調性に依存している：左側からウィンドウを縮小しても、シンボルのカウントが増えることはない。証明によれば、すべての右端 $r$ に対して、アルゴリズムは $r$ で終わる最長の実現可能な部分文字列を見つけ、グローバルな最適性を保証する。

2.3 区間パッキングによる非重複選択

すべての置換マッチが列挙された後（ベースライン・アルゴリズムを使用）、選択問題は**貪欲法（Greedy strategy）**によって解決される。

• メカニズム: すべてのマッチは等しい長さ $m$ の区間に対応するため、この問題は最大個数の互いに素な区間を選択する問題に帰着する。
• 戦略: アルゴリズムはテキストを左から右へとスキャンし、最初に見つかった利用可能なマッチを選択した後、次の非重複となる潜在的なマッチに向けて $m$ ポジション分スキップする。
• 証明: この「最も早く終了する（あるいは、等しい長さであるため、最も早く開始する）」貪欲ルールが、最大個数の集合を与えることが交換引数（exchange argument）によって示されている。

3. 主な貢献

1. 統一フレームワーク: パリク差分の維持を用いて、検出、最適化（MFSP）、および選択を扱う簡潔なスライディングウィンドウ・アプローチ。
2. 最適計算量: 提案されたすべてのアルゴリズムは、$O(n + \sigma)$ 時間および $O(\sigma)$ 空間を達成する。これは入力を読み込むための下界と一致しており、一般的なアルファベットに対して最適である。
3. MFSPの定式化: 置換マッチングをリソース制約付きのパッキング問題として再定義するMFSPを導入し、これを正しい2ポインタ・アルゴリズムで解決した。
4. 貪欲法の最適性: すべてのマッチが等しい長さを持つ場合、単純な貪欲スキャンが非重複の置換マッチを選択する上で最適であるという形式的な証明。

4. 結果と実験的観察

著者らは、理論的境界を裏付けるための軽量な実験的観察を報告している：

• スケーラビリティ: 置換マッチングとMFSPはともに、テキスト長 $n$ に対して線形にスケールしており、これは $O(n + \sigma)$ の解析と一致している。
• パフォーマンス要因: 実行時間は、カウンティング配列やマップのメモリ・アクセス・パターン、およびマッチの密度（これは出力の量には影響するが、スキャニング・ロジックには影響しない）によって支配される。
• アルファベットの処理: 大きなアルファベットの場合、アルファベット圧縮（$P$ と $T$ に現れるシンボルを整数 $1 \dots \sigma'$ にマッピングすること）により、メモリ・フットプリントが大幅に削減され、キャッシュの局所性が向上し、$\sigma$ が大きい場合でも効率性を維持できる。
• MFSPの効率性: MFSPにおける違反カウンタ・メカニズムは、完全な実現可能性チェックを回避し、各文字が少なくとも一度しか追加または削除されないことを保証しており、標準的な2ポインタの償却計算量に従っている。

5. 意義と範囲

本論文は、頻度ベースの文字列マッチングを単なる検出タスクとしてではなく、組合せ最適化のプリミティブとしての基礎として位置づけている。

• 理論的貢献: 古典的なJumbled Matching問題をパッキング型の最適化問題へと結びつけ、タイトな境界と簡潔なアルゴリズムを提供している。
• 実用的有用性: 提案されたアルゴリズムはシングルパスのスキャニング用に設計されており、リアルタイム処理やリソース制約下での最適化（テキスト処理におけるトークン予算など）を必要とするアプリケーションに適している。
• 限定事項: 著者らは、彼らの焦点がインデックス構築（複数クエリ用）ではなく、検出および最適化プリミティブにあることを明示している。MFSPの重み付きまたは近似的な拡張については今後の課題とし、現在の貢献は、定義された問題に対する厳密かつ線形時間の解に限定されている。

本研究は、パリク・ベクトルの差分を維持し、単純な貪欲法または2ポインタ戦略を利用することで、複雑な置換マッチングのバリアントを、証明された正当性と最適な線形時間計算量で解決できると結論付けている。