（消去不能正規）パターン言語を和言語に拡張して極小言語戦略する
パターンの和 (OR) を取って高い表現力を得る.
パターンの集合 \(P = \{ p_1, p_2, \ldots, p_k \}\) に対してその言語を \[L(P) = \cup_i P(p_i)\] ある自然数 \(k\) で \(|P| \leq k\) に限るとき, その \(P\) を \(k\)-multiple description という. パターン (description) 全体 \(D\) に対して \(k\)-multiple description 全体を \(D^k\) と書く.
パターンには半順序 \(\leq\) が入っていて \(p \leq q \implies L(p) \subseteq L(q)\) という関係がある. これに相当する関係を \(k\)-multiple description にも入れる. \[P \preceq Q \iff \forall p \in P, \exists q \in Q, L(P) \subseteq L(Q)\]
元のパターンの汎化システムが完全であっても, multiple description のシステムは不完全であることに注意.
文字列 (object) の有限集合 \(S\) についてこれを被覆するもので \(\preceq\) に関して極小なものを与える \(P \in D^k\) を推論したい. kおのような \(P\) のことを \(k\)-minimal multiple generalization (k-mmg) という.
上限 \(k\) が決まってない場合は \(S=P\) というのが自明な解である. これを防ぐために \(k\) を設けるのである.
これの 2-mmg として \(\{ 0001xy, xy0111 \}\) などがある. \(\{ xy01zw \}\) は 1-mmg であるが 2-mmg ではない.
手掛かりとなる性質を延べていく
\(S\) とこれを被覆する \(k\)-multiple \(P\) \((S \subset L(P)\) について, \[\forall Q \subset P, Q \ne P \implies S \not\subset L(Q)\] このとき \(P\) は reduced であるという. 余計なパターンを一つも含まないことを言う.
\(P\) が \(k\)-mmg であるならば reduced である.
なぜなら reduced でないなら \(S\) を被覆する \(Q \subset P\) があって \(Q \prec P\) であるから minimal に反する.
\(P\) が \(S\) について tightest であるとは, 各 \(p \in P\) が \(S \setminus L(P \setminus p)\) の minimal common generalization であることを言う. つまり, \[\forall p \in P, \not\exists q (q \prec p \land S \setminus L(P \setminus p) \subset L(q))\] 各 \(p \in P\) が十分 refine されてることを言う.
\(P\) が tightest であるなら reduced である.
reduced でないならある \(p \in P\) があって \(S \setminus L(P \setminus p)\) なのでそう.
\(S\) に対して \(P\) が reduced でかつ \(|P| = k\) のとき, \(P\) が tightest であることと \(k\)-mmg であることとは同値.
\(S\) を被覆する description \(p \in D\) の \(k\)-division とは次のような multiple description \(P\) のこと
イメージとしては被覆を保ちながら \(k\) 個のパターンに分割する手続きのこと.
\(k\)-division は必ずしも存在しない. 存在する時, その \(p\) は \(k\)-divisible であるという.
\(S\) を被覆する \(k\)-mutliple \(P \in D^k\) が reduced であるとき, \(P\) が \(k\)-mmg であることは次の2つが成立することと同値
もう少し具体的には次のように
def kmmg(k: int, S: List[str]):
P = tightestCovering([top])
while len(P) < k:
d = k - len(P)
for p in P:
T = S - L(P - p)
if divisible(d, p, T):
dP = division(d, p, T)
P = P - p + tightestCovering(dP, T)
def divisible(k: int, p: RegularPattern, S: List[str]) -> bool:
"""p is k-divisible???"""
def division(k: int, p: RegularPattern, S: List[str]) -> Set[RegularPattern]:
"""k-division"""
def tightestCovering(P: Set[RegularPattern], S: List[str]) -> Set[RegularPattern]:
"""
S とその被覆で tightest と限らない P を受け取って,
P を tightest な被覆にしたものを返す
assert len(tightestCovering(P, S)) == len(P)
"""division の方法と tightestCovering の方法は大体貪欲に refine していけばいい.
この2つの操作の合成で実は全ての代入は表現できる. コレに従って探索してけばいい.