Open4

競プロネタ帳

toyboot4etoyboot4e

このスクラップは

年末投稿の Book のネタを考えるノートです。今年は投稿が無い可能性も大ですが……。

toyboot4etoyboot4e

Aho–Corasick algorithm [DONE]

Library Checker の Aho Corasick を解きます。 CS 専攻だと習うんでしょうか？　AC automaton っていい響き！

https://judge.yosupo.jp/problem/aho_corasick

概要

Aho–Corasick の典型的な用途は以下です。

パタン文字列の列 \{S_i\}_i が与えられたとき、テキスト文字列 T の連続部分列からパタン文字列をすべて発見せよ。計算量は、前処理 O(\sum_i \{|S_i|\}_i) 時間、検索処理 O(|T| + z) 時間とする (z: マッチ数) 。

HashMap を使うと文字種類数 |\Gamma| は計算量に含める必要が無さそうです。

API のイメージを掴むには、 docs.rs/aho_corasick を見るのが良いかもしれません。

https://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Slides02.pdf

リソース

CP Algorithm, Wiki, 上記のスライド を読みます。特にスライドが分かりやすいです。

コードは以下も参照したいと思います:

Wiki 曰く、ベル研の Corasick さんがコンピュータの利用制限に引っかかって検索アルゴリズムを高速化したそうです。ウケますね。 Aho–Corasick のインクリメンタル版があるらしいのと、もっと速いアルゴリズムも山ほどありそうでした。

アルゴリズム

ある "辞書" (単語列 \{S_i\}_i) を考える。 O(\sum_i |S_i|) の前処理により、辞書を元に trie (retrieval) を構成する (辺が Char を持つ根付き木とする) 。またパタン文字列に相当するノードはマークする。

辞書を元に、文字列 S を走査する。走査に応じて、先頭〜現在位置までの longest suffix に対応する trie node を移動する。ここで、各ノードにおいて、次の 1 文字が来た際にどのノードへ遷移すべきかを持っておく。これは必ずしも木の末端に近づくものではなく、時に根の側へジャンプする場合がある。たとえば "ab" まで読んで次の一字が "c" であるとき、 trie 中に "abc" が無いならば、 "bc", "c" または "" へ飛ぶことになる。したがって、 trie の構成時にこのジャンプ辺 (suffix link, failure link) も構成することとする。

なお各頂点の入次数は高々 1 であるため、 suffix link の配列長は頂点数に等しいです。

Suffix link は再帰的な方法により構成する。根の suffx link は根自身を指す。根の直下の子の suffix link は根を指す。以降は、親の suffix link を辿った後にもう 1 文字辿れば良い。たとえば abc の c に対する suffix link は、 ab に対する suffix link を辿った後に c を辿れば良い。このような suffix link の構築は O(\sum_i |S_i|) 時間で実施できる。なぜなら 1 文字消費する度に suffix link 先の深さは最大 1 しか深くならず、また一気に浅くなる時もこれまでに降った分しか遡れないため。

Suffix link を構築すると、検索は O(|T|) で実施できるようになる。なぜなら T の連続部分列を走査するとき、部分列の左端と右端が単調増加するように走査できるため。ただし suffix link を辿って最長接尾辞にジャンプしたとき、最長接尾辞の連続部分列がパタン文字列である場合を無視してしまう。したがって今度は output link (fast link) を導入する。

Output link は、各ノードに対応する文字列に関して、その接尾辞が構成する最長のパタン文字列を指す。なお output link は単方向連結リストである (パタン文字列に相当するノードが、別のパタン文字列に相当するノードを指す場合がある) 。 Output link は suffix link を省略したようなものであるため、構築は容易である (suffix link 先がパタン文字列であれば output link とする。違う場合は suffix link 先の output link をこのノードの output link とする) 。

コーディング

Trie の構築

ひとまず Nachia さんの提出 を写経してみました。 1,503 ms. 流石に元の提出 (374 ms) と比べて遅いので、可変長配列にしてみましたが、余計に遅い。やはり next[v][c] を sparse に持った方が良さそうです。

https://judge.yosupo.jp/submission/309738

Map で再実装してみると、約倍速の 789 ms になりました。

https://judge.yosupo.jp/submission/309759

IntMap にすると 712 ms になりました。うーん IntMap にします。 HashMap でもいいかも。

https://judge.yosupo.jp/submission/309766

HashMap で 679 ms. HashMap が良いですね。

https://judge.yosupo.jp/submission/309785

Trie の構築 (再実装)

rust-algorithms のコードが非常に良かったです。 Output link (fast link) が実装されているため、辞書マッチングの実装が見れる点も良いです。

https://github.com/EbTech/rust-algorithms/blob/HEAD/src/string_proc.rs

辞書マッチング

同じく rust-algorithms を元に実装します。 |T| 回動いて各頂点毎に output link を辿り、 (endPos, patId) の列を返します。ランダムテストで verify しました。

感想

綺麗なアルゴリズムでした。 ac-library-hs の最後のモジュールとして 追加しました 。

toyboot4etoyboot4e

GHC 9.4.5 → GHC 9.10.3

ジャッジ環境は (今週、無事に安定版がリリースされれば) GHC 9.10.3 になる見込みです。 GHC の更新履歴は mod_poppo 氏のおかげで何も調べなくて良いのです。最高！

9.6

https://zenn.dev/mod_poppo/articles/whats-new-in-ghc-9-6

競プロ的にはそこまで影響ありません。限定継続が何かを知らなくて面白いかも。

https://blog.miz-ar.info/2022/10/delimited-continuations/

9.8

https://zenn.dev/mod_poppo/articles/whats-new-in-ghc-9-8

基礎的な見直しが多めです。

9.10

https://zenn.dev/mod_poppo/articles/whats-new-in-ghc-9-10https://zenn.dev/mod_poppo/articles/playing-with-visible-forall

やはり GHC 2024 が {-# LANGUAGE #-} を省略できて嬉しい！　ghc-internal, ghc-experimental もしっかりジャッジに入ります。使い所は高速化ぐらいかも……？

https://zenn.dev/mod_poppo/articles/playing-with-visible-forall

途中からついて行けてないですが、この記事でもスタートラインを揃えてくださっていて流石です。