アルゴリズムは何を圧縮しているのか ─ Haskell から育った「圧縮代数」というメンタルモデル

関数型まつり2026 の発表資料です #fp_matsuri

Transcript

1. アルゴリズムは何を圧縮しているのか ─ Haskell から育った「圧縮代数」というメンタルモデル 2026.7.12 関数型まつり2026 Naoya Ito (@naoya̲ito)
2. 資料はアップロード済みです • X の #fp̲matsuri から辿るか • Google で「Speaker Deck naoya」で検索
3. 自己紹介 • 株式会社 一休 (ホテル、レストランのWeb予約事業の会社) で働いています • 趣味で競技プログラミングを嗜んでおり、Haskell で参戦しています • 現在のレートは青色 (1602、上位 3.57%) です
5. はじめに • 新しいアルゴリズムや数学的理論を紹介する話ではありません • すでに知っているアルゴリズムが「何を要約 / 圧縮しているのか」を、とある角度から眺め る、見直す話です 「圧縮代数」は既存の数学用語として確立した体系ではありません Haskell、競プロ (アルゴリズムコンテスト)、AI の対話から育ててきた私的なメンタルモデルです
6. Haskell の fold を操作的に読むか、意味的に読むか let x = foldl' (+) 0 [1 .. 10] • 操作的 – アキュムレータつき再帰 – 左から順に、再帰的に (+) を適用していく。足していく • 意味的 – [1 .. 10] という自由な列全体を、「和」という一点の意味へ潰している
7. リストという「自由な構造」から「和」という一点に潰す (圧縮する) リストには順序があり、各要素がそのまま残っていて、自由に 連結できる。情報量が大きい。(自由構造) a₀ a₁ a₂ a₃ a₄ a₅ それを (+) で一つの値に潰す。潰したことで順序や各要素は捨 てられる。このとき「和」という文脈では、元のリストの意味 (+), 0 x は壊していない。保存している。 潰された値を「和による要約 (意味圧縮)」と捉えることはでき ないか?
8. 累積和 A= 0 1 2 3 4 5 6 3 1 4 5 9 2 6 • A2 ･･･ A5 など「連続する部分和 (区間和)」を求めたいとする。 • ナイーブに左から見ていくと O(n) かかる
9. 累積和 S= 0 1 2 3 4 5 6 A= 3 1 4 5 9 2 6 4 + 5 + 9 + 2 = 20 0 3 4 8 13 22 24 30 24 - 4 = 20 0 1 2 3 4 5 6 7 • 累積和 S をあらかじめ事前計算する。左から累積的に和をとるだけ。O(n) • すると、区間和を求める計算は2点の差みるだけで計算できる。O(1)
10. Haskell での累積和 ･･･ scanl で表現できる let s = scanl' (+) 0 [3, 1, 4, 5, 9, 2, 6] -- [0, 3, 4, 8, 13, 22, 24, 30] • リストを元にして、再帰的に関数を適用し、新しいリストを構築する • scanl の結果は foldl の再帰計算の軌跡 (畳み込みの過程) を残したものと同等になる – foldl' (+) 0 [3, 1, 4, 5, 9, 2, 6] は 30 という単一の値が返る
11. 累積和の操作的な解釈例 S= 0 3 4 8 13 22 24 30 0 1 2 3 4 5 6 7 • 左から順番に足していく、相対距離を絶対距離に変換する • Sr - Sl ･･･ 区間和は、Sr から、余計な部分の Sl を引く Sr - Sl
12. 意味的な解釈の出発点 ･･･ 累積和上のある一点 Si は何者なんだろう? S= 0 3 4 8 13 22 24 30 0 1 2 3 4 5 6 7
13. fold の「要約 / 意味圧縮」の文脈と統合する S= 0 3 4 8 13 22 24 30 0 1 2 3 4 5 6 7 • foldl (+) 0 を「リストという自由な構造に対する (和という文脈での) 一点への要約」と意味解釈した • foldl と scanl の計算構造は同じ。最終結果のみを返すのが fold で、軌跡を返すのが scan • scanl の軌跡、一要素も同様に「要約」と解釈することができそう
14. 左累積和の一点は「左区間の和による一点への要約 / 意味圧縮」 A= 3 1 4 5 9 2 6 (+) S= 13 • foldl は入力のリスト全体を一点に圧縮した • scanl の一点は、その途中経過。つまり Sl は、それより左の区間 [0, l) を一点に圧縮している • このとき「和」という文脈では、圧縮しても [0, l) 区間の意味を壊してない。圧縮後の値でも意味が保存 されている • 「位置4より左の和は?」「13」
15. Sr - Sl を要約二点 (Sl, Sr) の合成と捉え直す S= Sl Sr 4 24 • 「それより左の区間を要約 / 代表する値」である累積和の点。それを二つとってきて、合成する • 要約と要約を、どう合成する? → (-) で合成する (逆元によるキャンセル) • この要約と要約の合成は何を意味する? → 区間和
16. 要約 / 意味圧縮の世界へ「持ち上げて」、要約同士を合成している Sl S= 0 3 4 Sr 8 13 22 24 30 要約の世界 9 2 6 自由構造 (+) 0 A= 3 1 4 5 • scanl という関数を適用して、要約 / 意味圧縮の世界に持ち上げる • 要約する、持ち上げるための文脈は (+) 0 、つまり和 • 要約と要約の合成で区間和を表現できる ･･･ 要約、すなわち圧縮表現で合成しているから計算量が下がる。 要約しても和という文脈では意味は保存されているから、持ち上げた世界に閉じて計算しても元の自由構造 で計算しても同じ意味になる
17. 改めて、今日の発表における「圧縮」とは • 「データを小さくすること」ではなく • 問いたいことを壊さない形で、自由度を落とすこと • 圧縮された値は「問いたいこと」の文脈における要約となる a₀ a₁ a₂ a₃ a₄ (+), 0 x a₅
18. foldr や scanr など右畳み込みは「右側の要約」 右累積min S= 1 1 2 2 2 2 6 ∞ scanr min maxBound [3, 1, 4, 5, 9, 2, 6] A= 3 1 4 5 9 2 6 • foldr や scanr などの「右畳み込み」は右からの累積演算、と操作的に捉えると認知負荷🧠 が高い • ある位置における「右側 (右区間) の要約」と意味で考えると、とても分かりやすい💡 • 右累積 min なら「その位置から右の最小値」である
19. ほかのアルゴリズムもみてみる ･･･ ローリングハッシュ s= a b r a c a d a ハッシュ関数 2000050396576098803, 4 (ハッシュ値, 長さ) • 高速な文字列比較のためのアルゴリズム • 文字列 (※) の連続する部分列を、ハッシュ値に変換する ※実際は文字列に限らない • 同じ長さの部分文字列の一致判定をハッシュ値の比較で可能。事前計算 O(N)、一致比較 O(1)
20. 文字列を、連結を保存するハッシュ値へ圧縮する H0 H1 H2 H3 H4 H5 H6 H7 H8 a d a combine, e s= a b r a c • 要約は、元の文字列の「連結 (++) 」という構造を保存している – 文字列の連結を、ハッシュ値同士の計算として再現できる性質を持つハッシュ関数を使う – H(x)=(hash(x),∣x∣) とすると H(x ++ y) = H(x) combine H(y) • 要約二点の合成 ･･･ 部分文字列のハッシュ – このハッシュを「部分文字列一致判定」と意味解釈できる – 要約で比較するから、計算量が下がる (O(1))
21. セグメント木 ･･･ 圧縮を一点まで進めず、木構造に留める 5 8 ･･･ 7 2 26 6 必要な部分要約を合成 元の列 (自由な構造) 部分区間ごとの要約を木構造に保存 • 累積和やローリングハッシュとは異なり、一点だけには潰し切らず、部分区間ごとの要約を木に残す • クエリ時には、必要な部分要約から圧縮を再開し、区間全体を一点に要約する • セグメント木とは、モノイドによる要約を、一点ではなく区間木のノードに途中保存したもの 画像のソース: https://ja.wikipedia.org/wiki/%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8
22. rangeFold (l, r) s ! r - s ! l rangeFold (l, r) s • 操作的に捉えると累積和による区間和は s ! r - s ! l • ここまで見てきたように意味的には区間 [l, r) の要約 「区間 [l, r) を fold したら、どんな意味になるか」という API に統合できる
23. 累積和 (Prefix Table) let s = fromListPT @VU.Vector (1, n) $ map Sum xs x = rangeFoldPT (l, r) s ローリングハッシュ let rh = fromStringRH (1, n) s h = rangeFoldRH (l, r) rh セグメント木 seg <- newListSeg @VUM.MVector (1, n) $ map Min xs x <- rangeFoldSeg seg (l, r)
24. Sparse Table let s = fromListSP @VU.Vector (1, n) $ map Max xs x = rangeFoldSP (l, r) s Zobrist Hash gen <- newStdGen let t = newTableZHMS gen xs z = fromListZHMS (1, n) t xs x = rangeFoldZHMS (l, r) z rangeFold は「区間を、その代数の意味で要約する」インターフェース
25. (a) 要約の文脈 + (b) 評価の方法 写像と合成演算が、要約の意味を決める。合成演算が満たす代数法則が、その要約を扱える評価器を決める (a) 圧縮代数 : 何を意味として残すか (b) 評価器 : その意味をどう取り出すか 要約値へ写す関数、要約同士を合成する演算 評価器、データ構造 結合則、単位元、逆元、可換性、冪等性 ･･･ 評価器ごとに必要な代数法則が異なる どの意味へ fold するか (+), max, min, <> … 区間 [l, r) 要約値 m 評価器: PrefixTable / BIT / SegmentTree / SparseTable / RollingHash … 意味と評価を分離する。意味を決めるのが圧縮代数、計算方法を決めるのが評価器
26. 区間を要約 (rangeFold) する「評価器」 同じ「区間を fold した意味を返す」でも、要約 (圧縮値) に残した代数法則 (すなわち文脈) によってできることが変わる 評価器 圧縮先の代数 利用する法則 その法則でできること PrefixTable / 累積和 群 逆元 区間和 Binary Indexed Tree 可換群 可換性・逆元 一点加算・区間和 Segment Tree モノイド 結合則・単位元 一点更新・区間クエリ Sparse Table 冪等半群 結合則・冪等律 静的・区間クエリ Rolling Hash 連結を保存する準同型 連結を保つ演算 部分文字列の一致判定 Zobrist Hash 可換な演算への確率的準同型 XOR・加算の可逆性、逆元 軽量な同一性判定
27. 圧縮率 ･･･ 累積和は潰し切る 列 • 各 prefix は一点の値まで潰される • 区間は二点差で復元する • その代わり、逆元が必要になる prefix 点列 Sᵣ − Sₗ = 区間 [l, r) の要約 圧縮率は高い。ただし逆演算 (­) が必要になる 圧縮代数に、強い構造が必要とされる 14
28. 圧縮率 ･･･ セグメント木は圧縮を留保する • 全体を一点にしない • 部分区間ごとの圧縮値を木に保持する • 任意区間を O(log n) 個の互いに素な区間に分解し て合成 • その代わり、逆元はいらない。モノイドでよい • 区間 min や区間 max など逆元がない区間◦◦ を実現できる 部分区間の圧縮を木に留保 → 必要な区間だけ合成 潰し切らないことで、逆元のない世界でも計算を続けることができる より弱い構造で要約が可能。ただし、空間 (メモリ) と時間 (計算量) を使う 15
29. なぜこのメンタルモデルが Haskell から育ったのか Haskell はアルゴリズムに潜む代数的構造を露わにする。圧縮代数は、その構造を意味圧縮として読み直すところから生まれた
30. 圧縮代数で見える景色 • 圧縮代数によって、一見無関係にみえたアルゴリズムやデータ構造に一つの共通したメンタ ルモデルを適用できる • 「写像と合成演算による要約」の空間に持ち上げて、そこで計算する • rangeFold (l, r) のように、その統合された概念で API を統一し Haskell のライブラリ 群をより使いやすく、認知負荷の低いものに発展させることができた • 時間の都合上紹介できないが、区間要約以外のアルゴリズムやデータ構造も同様の枠組みで 解釈、実装を再構成することができる – たとえば DP の DP表、BFS の状態なども代数的構造をもった要約だと捉えて云々 https://naoya.dev/wiki/圧縮代数 私はこれで 青色コーダーになれました
31. ここからはただの妄想です
32. 「計算」とは、入力を状態へ要約 / 圧縮すること? let s = foldl' (¥acc x -> acc <> x) mempty xs • 圧縮代数の要は fold の計算構造 ･･･ アキュムレータつき再帰にあった • アキュムレータ acc は、「ここまでに読んだ入力の要約」になっている • ところで、入力を受け取りアキュムレータに結果を積みながら計算していく、というのは状態機械やス トリーム処理にも表れる計算の形ではないか? • ならば計算機も、自由入力を内部状態へ意味圧縮し続ける装置と見られないか? • それは計算機特有のこと? AI が学習して、コンテキストに圧縮して、推論してるのは? 人間の 🧠 は? 「アルゴリズムは何を圧縮しているのか」という問いは、 やがて「計算とは何か」「知性とは何か」という問いにつながる
33. Appendix
34. 観点 累積和 セグメント木 圧縮の仕方 prefix を点へ潰す 部分区間の圧縮を木に留保する 区間取得 二点差 O(log n) 個の区間合成 要求 逆元 結合律と単位元 (モノイド) 更新 苦手 得意 圧縮率 高い 中程度 トレードオフ 強い構造が必要 空間と時間を使う
35. foldMap とモノイド準同型 foldMap f (xs ++ ys) == foldMap f xs <> foldMap f ys • 自由モノイド側の連結 (++) が、意味側の合成 (<>) に写る • 構造の演算を保つ写像 ̶̶ モノイド準同型