自然言語は，多様性・曖昧性，規則性と例外性，広範性・大規模性，語彙・文法の経時変化などの性質を持っている．自然言語解析システムは，これらの性質をアプリケーションが要求するレベルで旨く扱う必要がある．なかでも多様性・曖昧性への対応，すなわち，形態素，構文，意味，文脈などの各種レベルにおける組合せ的な数の曖昧性の中からいかにして正しい解釈を認識するかがシステム構築上，最も重要な課題である．\begin{figure}[b]\begin{center}\epsfile{file=\myfigdir/COM自然言語解析システムのモデル.eps,scale=0.7}\end{center}\myfiglabelskip\caption{自然言語解析システムのモデル}\label{fig:NLAnalysisModel}\end{figure}一般に自然言語解析システム(以下システムと省略する)は，入力文に対して可能な解釈の仮説を生成し（{\bf仮説生成知識}の適用），ありえない仮説を棄却したり({\bf制約知識}の適用)，仮説に対する順位付けを行ったり（{\bf選好知識}の適用）することで，入力文に対する解析結果(文解釈となる構造)を求める．図\ref{fig:NLAnalysisModel}がこのモデルを示している．文の解釈は，仮説記述体系により規定される仮説空間に存在し，それぞれが実世界において，正解解釈（◎:correct），可能解釈（○:plausible），不可能解釈（×:implausible）に分類できる．仮説生成知識が可能な仮説集合を生成する．制約知識は仮説空間内の仮説が可能か不可能かを弁別し，選好知識は仮説空間内の仮説の順位付けを行う\footnote{制約知識は可能性ゼロの選好知識ともいえる．但し，制約知識の適用は解釈の枝仮りであり計算機処理の観点からは大きな差異がある．}．仮説生成・制約知識は，システムが受理可能な文の範囲，すなわち，システムの対象文カバレッジを規定する．仮説生成・制約・選好知識は，形態素，構文，意味といった各レベルにおいて存在し，システムの性能はこれらの総合として決定されると考えられる．例えば，各レベルの選好知識がそれぞれ異なった解釈を支持するという競合が生じるため，精度良く文解釈を行うにはこれらを総合的に判断する必要がある\cite{Hirakawa89a}．このように，システム設計においては，「生成\footnote{簡略のため「仮説生成知識」を単に「生成知識」と表現する．}・制約・選好知識をどのように扱うか」（{\bf知識適用の課題}），「多レベルの知識をどのように融合するか」（{\bf多レベル知識の課題}）という２つの課題が存在する．生成・制約知識は，正文と非文とを弁別(あるいは，正文のみを生成)する，いわゆる，言語学の文法知識に相当する．従来，言語学からの知見を活用しながら計算機処理を前提とした各種の文法フレームワークが研究されてきている．文法フレームワークは，文の構造解釈を記述する解釈構造記述体系を基盤として構築されるが，これらには，句構造，依存構造，意味グラフ，論理式など様々ものが提案されている．一方，選好知識については意味プリファレンスの扱い\cite{Wilks75}を始めとして古くから多くの研究がなされているが，音声認識処理から自然言語処理への導入が始まった統計的手法が，単語系列から文脈自由文法，依存文法などへと適用範囲(解釈記述空間)を拡大・発展させ，広くシステムに利用されるようになってきている．例えば，句構造をベースの枠組みとして，文脈自由文法，LFG\cite{Kaplan89,Riezler02}，HPSG\cite{Pollard94,Tsuruoka04},CCG\cite{Steedman00,Clark03}など\footnote{解析結果として依存構造を出力したりする場合もあるが，ここでは解析のベースとなっている解釈記述空間で分類している．}，また依存構造をベースとした枠組みとして，確率依存文法\cite{Lee97},係り受け解析\cite{Shudo80,Ozeki94,Hirakawa01,Kudo05_j},制約依存文法(以降CDGと記述する)\cite{Maruyama90,Wang04}，LinkGrammar\cite{Sleator91,Lafferty92}など文法フレームワークと統計手法の融合が広範に行われている．このように，文法フレームワークの研究は，生成・制約知識を対象とした研究から統計ベースの選好知識の扱いへと進展し，統計的手法は語系列，句構造，依存構造へと適用範囲を拡大し融合され，生成・制約・選好知識全体の統合のベースが整ってきている．多レベルの知識の融合という観点では，基本的に単一の解釈記述空間に基づくアプローチと複数の解釈記述空間に基づくアプローチがある．単一の文脈自由文法，依存文法などは前者の典型である．DCG\cite{Pereira80}やBUP\cite{Matsumoto83}などは文脈自由文法をベースにしているが，拡張条件が記述可能であり，例えば意味的な制約といった異レベルの知識を句構造という１つの解釈記述空間をベースとしながら融合することができる．CDGでは依存構造をベースにして構文的な制約を含む任意の制約条件を単項制約，２項制約という枠組みで記述できるようにしている\cite{Maruyama90}．LFGは，c-structure(句構造)とf-structure(機能構造)の２種類のレイヤを有し機能スキーマにより機能構造に関する制約条件が記述可能である\cite{Kaplan89}．また，統計ベースのアプローチにおいては，句構造情報だけではなく句のヘッドやその依存関係情報の利用が有効であることが判明し，句構造情報と依存構造情報を統合判断するモデルが利用されている\cite{Carroll92,Eisner96b,Collins99,Charniak00,Bikel04}．PDGは，複数の解釈記述空間に基づくアプローチを取っており，後に述べるように複数の解釈記述空間で対応付けられた圧縮共有データ構造をベースに多レベルの知識の融合を行っている．本稿では，PDGのモデル・概要について述べた後，PDGで採用している句構造と依存構造という２種類の中心的共有データ構造であるヘッド付き統語森(HPF:HeadedParseForest)，依存森(DF:DependencyForest)について構築法を示し，それらに完全性と健全性が成立することを示す．また，例文解析実験により，PDGの振る舞いや特徴についても考察を加える．