予測システムの実装（ベクトルグラフィックス系）

予測システムの実装
（ベクトルグラフィックス系）
履歴エントリ
履歴
自由点の更新
依存関係に沿った更新
予測起動時
マッチング
マッチング部分を伸張
伸張部分をコピー
依存木にもとづく予測のまとめ
（作図・ＣＡＤ・プログラム向き）
1.
2.
3.
4.
検索：依存木のパタンマッチ検索
取得情報：類似コマンド木の伸張部分
伸張部分の一般化（λ抽象、汎化履歴）
予測：抽象化伸張部分の実行（β簡約）
グラフの場合
ベクトルグラフィックスの
マッチング
図形グラフ
• 辺---図形
• 辺ラベル---図形種
• 点---図形の頂点（円の場合は中心と円周上
の点）
• 接続された（多種）図形群は（辺ラベルつき）
グラフになる
• グラフのマッチングはとても難しい
– キーの基点を定められる場合は比較的容易
マッチングアルゴリズムの概略
基点
source
target
Source(キー)の基点からスタートして点を端点とする辺各辺反
対側端点を共有する図形を子とする「木」と見なす
• Targetの各点tについて次を行う
– Source(キー)の基点をsとしてスタートし、
– sを端点とする辺eを選び次を行う
• tを端点とする辺でeと同じラベルのものであり、かつ失敗リ
ストにeとペアで入っていないものfを選び(e,f)をマッチング
スタックに追加
– もし選べなければ先代の(e,f)を失敗リストに加えて別のfを試す
（バックトラック）
• 次のeを選び同じことを繰り返す（なくなるまで）
注：次のeは王位継承権と同じ順序（自分→子→返
上）で取得
// General Matching Algorithm
// (src->{trg||next trg||..})&&(src1->{trg||trg||})&&.....
stack matching;
int match_some_target(src){
stack failed_pair;
while(trg){
if(match(src,trg)){ //means success rooted from (src,trg)
return 1;
}else{
failed_pair->push(src,trg) ;
++trg;
//next matching target
}
}
return 0;
}
int match(src,trg){
matching->put(src,trg);
if(match_some_target(++src)) //next src to match //王位継承権
return 1;
else {
matching->pop();//popping (src,trg)
return 0;
}
}

Download Report