最小有向スパニング木（最小アーボレッセンス）に対するBockのアルゴリズムのための、やさしいチュートリアルと体系的な再定式化

arXiv cs.CL / 2026/3/31

💬 オピニオンIdeas & Deep AnalysisTools & Practical UsageModels & Research

共有:

要点

本論文は、最小有向スパニング木（最小アーボレッセンス）を計算するためのBock（1971）のAlgol手続きを、初心者にも親しみやすい形でチュートリアル化し、体系的に再定式化している。
Bockの表記法に従ってアーボレッセンスの目的を述べ直し、初期化から終了までの、元の10ノード例についての完全な逐次実行トレースを含めている。
著者らは、元の論理を保持したまま、アルゴリズムのフェーズ構造、維持される状態、制御フローを明示するようにアルゴリズムを作り直している。
この手法を、非投影的（nonprojective）な依存関係解析と結び付け、厳密なデコーダとして説明することで示し、さらに2026年の依存関係解析の教科書から適応した実例で実演している。
チュートリアルでは、最大重みアーボレッセンス問題が、アフィン変換によってBockの最小コスト定式化に還元できることを示し、同じ状態変数を用いて追跡する。

Abstract

本論文では、最小有向全域木を構築するためのBockの1971年のAlgol手続きを、穏やかなチュートリアルとして提示し、かつ体系的に言い換えます。私たちの目的は、元のアルゴリズムを現代の読者にとって読みやすく、再現可能な形にしつつ、それが非射影（nonprojective）のグラフに基づく依存構文解析のための厳密なデコーダとして関連性を持つことを強調することです。私たちはBockの記法において最小アルボレス（arborescence）の目的を再述し、元の10ノード例について、出発点から終了までを含む、オリジナルの実行の完全な行ごとのトレースを提示します。これは、元論文に示されている部分的なトレースを拡張したものです。続いて、元の手法の論理を保持しながら、手続きのフェーズ構造、維持される状態、制御フローを明示する体系的な言い換えを導入します。さらに、依存構文解析のために{jurafsky-martin-2026-book}から適応した、解の作業例を含めます。そこでは、最大重みアルボレスの問題が、標準的なアフィン変換によってBockの最小コストの定式化へとどのように還元されるかを示し、同じ状態変数の下で追跡します。