長いシーケンスと短いシーケンスの間の距離は、短いシーケンスと短いシーケンスと同じ長さの長いシーケンスのサブシーケンスの間の最小距離です。アルゴリズムのDcg状態の実装
私が使っている距離は、マンハッタン距離だと思います。 （しかし、これは距離関数を変更できるようにするためには重要ではありません）。
この最初のバージョンでは、早期放棄のない単純な実装が示されています。私は同じ長さのすべての部分配列を生成し、それらをマップして短い配列との距離を見つけ出し、次に集計/ 3を使って最小値を求めます。
abs(X,Y,Z):-
Z is abs(X-Y).
seq_seq_absdis(Seq1,Seq2,Dis):-
same_length(Seq1,Seq2),
maplist(abs,Seq1,Seq2,Dislist),
sumlist(Dislist,Dis).
seq_subseq(List1,List2):-
append(List2,_,List1),
dif(List2,[]).
seq_subseq([_|T],Subseq):-
seq_subseq(T,Subseq).
smallseq_largeseq_dis(Sseq,Lseq,Dis):-
findall(Subseq, (same_length(Subseq,Sseq),seq_subseq(Lseq,Subseq)),Subseqs),
maplist(seq_seq_absdis(Sseq),Subseqs,Distances),
aggregate(min(D),member(D,Distances),Dis).
例クエリ：
?-smallseq_largeseq_dis([1,2,4],[1,2,3,1,2,5],Dis).
Dis = 1
それは距離が最小終わると長いシーケンスのサブシーケンスと短い系列との間の距離を算出放棄れるように、この次のバージョンは、より効率的であるべきですすでに見つかりました。
ea_smallseq_largeseq_dis(Sseq,Lseq,Subseq,Dis):-
retractall(best(_,_)),
assert(best(initial,10000)),
findall(Subseq-Dis, ea_smallseq_largeseq_dis_h(Sseq,Lseq,10000,Subseq,Dis),Pairs),
append(_,[Subseq-Dis|[]],Pairs).
ea_smallseq_largeseq_dis_h(Sseq,Lseq,BestSofar1,Subseq,Dis):-
same_length(Sseq,Subseq),
seq_subseq(Lseq,Subseq),
best(_,BestSofar2),
( ( BestSofar2 < BestSofar1) ->
accumulate_dis(Sseq,Subseq,BestSofar2,Dis),
retractall(best(_,_)),
assert(best(Subseq,Dis))
;(
accumulate_dis(Sseq,Subseq,BestSofar1,Dis),
retractall(best(_,_)),
assert(best(Subseq,Dis))
)
).
accumulate_dis(Seq1,Seq2,Best,Dis):-
accumulate_dis(Seq1,Seq2,Best,Dis,0).
accumulate_dis([],[],_Best,Dis,Dis).
accumulate_dis(Seq1,Seq2,Best,Dis,Ac):-
Seq1=[H1|T1],
Seq2=[H2|T2],
abs(H1,H2,Dis1),
Ac1 is Dis1 + Ac,
Ac1 <Best,
accumulate_dis(T1,T2,Best,Dis,Ac1).
問合せ：
?-ea_smallseq_largeseq_dis([1,2,3],[1,2,4,5,6,7,8,1,2,3],Subseq,Dis).
Dis = 0,
Subseq = [1, 2, 3]
しかし、これでは、私はアサートを使用して、私は同じアルゴリズムを行いますが、これらのうちでバージョンを持ちたいので撤回しています。私は半文字の表記法でdcgを使ってこれを行うことができるはずだが、把握するのは難しいと思う...私がバックトラックによって生成しているサブシーケンスと、同時に最小距離の '状態'これまで見つかった？
問題があります。 seq_subseq/2は、バックトラッキングによってサブシーケンスを生成しています。 テストされた最初のsubseqを最小距離に設定する必要があります。 私はループしたいので、バックトラックして別のシーケンスを生成してください。しかし、私は失敗する必要があります。しかし、それから次のシーケンスをチェックするために、これまでのmin距離を戻すことはできません。
バックトラックを使用したくない場合は、サブシーケンスを順番に生成するための状態遷移述語を定義する必要があると思います。現時点で
? seq_subseq([1,2,3,4],X).
X = [1]
X = [1, 2]
X = [1, 2, 3]
X = [1, 2, 3, 4]
X = [2]
X = [2, 3]
X = [2, 3, 4]
X = [3]
X = [3, 4]
X = [4]
だから私は、私は関係を定義する必要があると思う：
のように働くだろうsubseq0_seq_subseq1(Subseq0,Seq,Subseq1)
：
?-subseq0_seq_subseq1([1,2,3,4],[1,2,3,4],Subseq1).
Subseq1 = [2].
と
?-subseq0_seq_subseq1([1,2,3],[1,2,3,4],Subseq1).
Subseq1 = [1,2,3,4].
しかし、これを効率的に行う必要があります。
更新 - マットの回答のおかげで、これは私が考える大きな改善です。誰もがこれ以上の改善を見ることができますか？私はダブルネスト - >構造と！両方ともaccumulate_dis/4の定義では醜いようです。また、短いシーケンスから最短距離の長いシーケンスのサブシーケンスを返すようにしました。
これは非整数で動作する必要があるので、clpfdは適切ではないと思います。
abs(X,Y,Z):-
Z is abs(X-Y).
list_subseq_min(Ls, Subs, Min,BestSeq1) :-
prefix_dist(Ls, Subs, 1000, Front, D0),
BestSeq0=Front,
min_sublist(Ls, Subs,BestSeq0,BestSeq1, D0, Min).
prefix_dist(Ls, Ps, Best,Front,D) :-
same_length(Front, Ps),
append(Front, _, Ls),
accumulate_dis(Front, Ps, Best, D).
min_sublist(Ls0, Subs, BestSeq0,BestSeq2, D0, D) :-
( prefix_dist(Ls0, Subs, D0, Front,D1) ->
min_list([D0,D1],D2),
Ls0 = [_|Ls],
( D0 < D1 ->
BestSeq1 =BestSeq0
;
BestSeq1 =Front
),
min_sublist(Ls, Subs, BestSeq1,BestSeq2, D2, D)
; D = D0,BestSeq0 =BestSeq2
).
accumulate_dis(Seq1,Seq2,Best,Dis):-
accumulate_dis(Seq1,Seq2,Best,Dis,0),!.
accumulate_dis([],[],_Best,Dis,Dis).
accumulate_dis(Seq1,Seq2,Best,Dis,Ac):-
Seq1=[H1|T1],
Seq2=[H2|T2],
abs(H1,H2,Dis1),
Ac1 is Dis1 + Ac,
Ac1 <Best,
accumulate_dis(T1,T2,Best,Dis,Ac1).
accumulate_dis(Seq1,Seq2,Best,Dis):-Dis is Best+1.
クエリ：
?- list_subseq_min([2.1,3.4,4,1.1,2,4,10,12,15],[1,2,3],D,B).
D = 1.1,
B = [1.1, 2, 4].
もう一度有益な答えをありがとう。私は今、私が今あるものを更新しましたが、それは良いですが、まだそれが偉大であることを確信していません！私はハミング距離ではなくマンハッタン距離を使用していると思います - 残念ですが、これははっきりしていませんでした。 [1,2,3,4]から[5,2,3,4]までのマンハッタンの距離は4で、ハミング距離が1であると私は思いますか？ – user27815
もちろん、Manhatten距離！ – mat
本当に助けていただきありがとうございます。 – user27815