Dcg状态算法实现
Dcg state implementation of algorithm
长序列和短序列之间的距离，是短序列和长序列中任何与短序列长度相同的子序列之间的最小距离。
我使用的距离是我认为的曼哈顿距离。 （但这应该不重要，因为我希望能够更改距离函数）。
第一个版本展示了一个天真的实现，没有提前放弃。我生成所有相同长度的子序列，映射这些以找到它们与短序列之间的距离，然后使用 aggregate/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]
但在本文中我使用了 assert 和 retract，所以我想要一个执行相同算法但没有这些的版本。我想我应该能够用带有半上下文符号的 dcg 来做到这一点，但发现很难掌握......我如何跟踪我通过回溯生成的子序列，同时跟踪 'state'到目前为止找到的最小距离？
我遇到的问题..
seq_subseq/2 正在通过回溯生成子序列。
测试的第一个子序列需要设置为最小距离。
然后我想循环，所以回溯生成另一个序列。但要回溯我必须失败。但是后来我无法带回到目前为止的最小距离来检查下一个序列。
如果我不想使用回溯，我想我需要定义一个状态转换谓词来按顺序生成子序列。
目前
? 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].
但我需要以一种有效的方式来做到这一点。
更新- 感谢 Mat 的回答，我现在有了这个，我认为这是一个很大的改进。任何人都可以看到对此有任何进一步的改进吗？我有一个双嵌套的 -> 结构和一个！在 accumulate_dis/4 定义中，这两个看起来都很丑陋。我还把它设为 return 长序列的子序列，它距离短序列的距离最短。
它需要处理非整数，所以我认为 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].
一个重要说明：您应该清楚您在谈论列表之间的 Manhatten 距离。这只能从您的代码中清楚地看出，而您的措辞很容易让读者认为您在谈论 edit 距离。
这是一个解决方案，它简单地遍历列表，跟踪最小值，并最终产生找到的最小值。
list_subseq_min(Ls, Subs, Min) :-
prefix_dist(Ls, Subs, D0),
min_sublist(Ls, Subs, D0, Min).
absdiff(X, Y, Z):- Z #= abs(X-Y).
lists_dist(Ls1, Ls2, D) :-
maplist(absdiff, Ls1, Ls2, Ds),
sum(Ds, #=, D).
prefix_dist(Ls, Ps, D) :-
same_length(Front, Ps),
append(Front, _, Ls),
lists_dist(Front, Ps, D).
min_sublist(Ls0, Subs, D0, D) :-
( prefix_dist(Ls0, Subs, D1) ->
D2 #= min(D0,D1),
Ls0 = [_|Ls],
min_sublist(Ls, Subs, D2, D)
; D #= D0
).
示例查询及其结果：
?- list_subseq_min([1,2,3,1,2,5], [1,2,4], D).
D = 1.
这很简单，而且由于簿记仅限于一个谓词，使用半上下文符号并没有真正的回报。当所描述的内容跨越不同的规则并且它们之间的交流会更加困难时，使用半上下文表示法和一般的 DCG 特别有用。
运行时间在O(N×M).
现在重点是，我把它留作练习：如果之前找到的最小值是已经超过了。以 纯粹 方式，或至少尽可能纯粹地这样做：assertz/1 和朋友 绝对 不可能，因为它们会阻止您单独测试这些谓词。传递参数并逐渐增加距离！这可能会帮助您改善平均 运行 时间，但当然不是最坏情况下的复杂性。
对于这种在不同子句之间传递状态的情况，半上下文符号最终可能会变得有用。
编辑：很好，您已经实施了一个进行修剪的解决方案。我现在也会展示我的。我将重用上面的辅助谓词 absdiff/3 和 lists_dist/3，以及以下附加辅助谓词：
same_length_prefix(Ls, Ps, Front) :-
same_length(Front, Ps),
append(Front, _, Ls).
list_subseq_min/3 现在略有不同：
list_subseq_min(Ls, Subs, Min) :-
same_length_prefix(Ls, Subs, Front),
lists_dist(Front, Subs, D0),
phrase(min_sublist(Ls, Subs), [D0-Front], [Min-_]).
现在要点：min_sublist//2 是一个 DCG 非终结符，简明扼要地描述了算法的主要思想：
min_sublist(Ls0, Subs) -->
( front(Ls0, Subs) ->
{ Ls0 = [_|Ls] },
min_sublist(Ls, Subs)
; []
).
从这个描述中，很明显我们正在考虑一个元素一个元素的列表。它使用比以前更少的（明确的）参数。额外的两个参数作为 对 D-Front 隐式传递，它跟踪迄今为止找到的最佳距离和子序列。请注意 DCG 表示法如何暴露计算的核心，并隐藏此处不相关的内容。
其余部分不言自明，类似于您实施的修剪。我强调在这个程序中单独使用半上下文符号，这让我们可以表达到目前为止找到的最佳序列的任何变化。
front(Ls, Subs), [D-Front] -->
[Current],
{ same_length_prefix(Ls, Subs, Front1),
capped_dist(Front1, Subs, Current, 0-Front1, D-Front) }.
capped_dist([], [], _, DF, DF).
capped_dist([L|Ls], [P|Ps], Current, D1-Front1, DF) :-
absdiff(L, P, D2),
D3 #= D1 + D2,
Current = D0-_,
( D3 #> D0 -> DF = Current
; capped_dist(Ls, Ps, Current, D3-Front1, DF)
).
我无法接受当代浮点数的肮脏和原始，所以我保留了整数运算，简单地将你显示的所有数字相乘，使它们成为整数：
?- list_subseq_min([21,34,40,11,20,40,100,120,150], [10,20,30], D).
D = 11.
我不再扩展它，这样它也可以将找到的子序列显示为一个简单的练习。
重要说明：capping只影响距离的计算；请特别注意 运行 时间是 Θ(N×M) 由于 same_length_prefix/3 在 front//2 中的使用方式！我将改进它作为一个稍微困难的练习。
长序列和短序列之间的距离，是短序列和长序列中任何与短序列长度相同的子序列之间的最小距离。
我使用的距离是我认为的曼哈顿距离。 （但这应该不重要，因为我希望能够更改距离函数）。
第一个版本展示了一个天真的实现，没有提前放弃。我生成所有相同长度的子序列，映射这些以找到它们与短序列之间的距离，然后使用 aggregate/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]
但在本文中我使用了 assert 和 retract，所以我想要一个执行相同算法但没有这些的版本。我想我应该能够用带有半上下文符号的 dcg 来做到这一点，但发现很难掌握......我如何跟踪我通过回溯生成的子序列，同时跟踪 'state'到目前为止找到的最小距离？
我遇到的问题.. seq_subseq/2 正在通过回溯生成子序列。 测试的第一个子序列需要设置为最小距离。 然后我想循环，所以回溯生成另一个序列。但要回溯我必须失败。但是后来我无法带回到目前为止的最小距离来检查下一个序列。
如果我不想使用回溯，我想我需要定义一个状态转换谓词来按顺序生成子序列。
目前
? 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].
但我需要以一种有效的方式来做到这一点。
更新- 感谢 Mat 的回答，我现在有了这个，我认为这是一个很大的改进。任何人都可以看到对此有任何进一步的改进吗？我有一个双嵌套的 -> 结构和一个！在 accumulate_dis/4 定义中，这两个看起来都很丑陋。我还把它设为 return 长序列的子序列，它距离短序列的距离最短。
它需要处理非整数，所以我认为 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].
一个重要说明：您应该清楚您在谈论列表之间的 Manhatten 距离。这只能从您的代码中清楚地看出，而您的措辞很容易让读者认为您在谈论 edit 距离。
这是一个解决方案，它简单地遍历列表，跟踪最小值，并最终产生找到的最小值。
list_subseq_min(Ls, Subs, Min) :-
prefix_dist(Ls, Subs, D0),
min_sublist(Ls, Subs, D0, Min).
absdiff(X, Y, Z):- Z #= abs(X-Y).
lists_dist(Ls1, Ls2, D) :-
maplist(absdiff, Ls1, Ls2, Ds),
sum(Ds, #=, D).
prefix_dist(Ls, Ps, D) :-
same_length(Front, Ps),
append(Front, _, Ls),
lists_dist(Front, Ps, D).
min_sublist(Ls0, Subs, D0, D) :-
( prefix_dist(Ls0, Subs, D1) ->
D2 #= min(D0,D1),
Ls0 = [_|Ls],
min_sublist(Ls, Subs, D2, D)
; D #= D0
).
示例查询及其结果：
?- list_subseq_min([1,2,3,1,2,5], [1,2,4], D). D = 1.
这很简单，而且由于簿记仅限于一个谓词，使用半上下文符号并没有真正的回报。当所描述的内容跨越不同的规则并且它们之间的交流会更加困难时，使用半上下文表示法和一般的 DCG 特别有用。
运行时间在O(N×M).
现在重点是，我把它留作练习：如果之前找到的最小值是已经超过了。以 纯粹 方式，或至少尽可能纯粹地这样做：assertz/1 和朋友 绝对 不可能，因为它们会阻止您单独测试这些谓词。传递参数并逐渐增加距离！这可能会帮助您改善平均 运行 时间，但当然不是最坏情况下的复杂性。
对于这种在不同子句之间传递状态的情况，半上下文符号最终可能会变得有用。
编辑：很好，您已经实施了一个进行修剪的解决方案。我现在也会展示我的。我将重用上面的辅助谓词 absdiff/3 和 lists_dist/3，以及以下附加辅助谓词：
same_length_prefix(Ls, Ps, Front) :-
same_length(Front, Ps),
append(Front, _, Ls).
list_subseq_min/3 现在略有不同：
list_subseq_min(Ls, Subs, Min) :-
same_length_prefix(Ls, Subs, Front),
lists_dist(Front, Subs, D0),
phrase(min_sublist(Ls, Subs), [D0-Front], [Min-_]).
现在要点：min_sublist//2 是一个 DCG 非终结符，简明扼要地描述了算法的主要思想：
min_sublist(Ls0, Subs) -->
( front(Ls0, Subs) ->
{ Ls0 = [_|Ls] },
min_sublist(Ls, Subs)
; []
).
从这个描述中，很明显我们正在考虑一个元素一个元素的列表。它使用比以前更少的（明确的）参数。额外的两个参数作为 对 D-Front 隐式传递，它跟踪迄今为止找到的最佳距离和子序列。请注意 DCG 表示法如何暴露计算的核心，并隐藏此处不相关的内容。
其余部分不言自明，类似于您实施的修剪。我强调在这个程序中单独使用半上下文符号，这让我们可以表达到目前为止找到的最佳序列的任何变化。
front(Ls, Subs), [D-Front] -->
[Current],
{ same_length_prefix(Ls, Subs, Front1),
capped_dist(Front1, Subs, Current, 0-Front1, D-Front) }.
capped_dist([], [], _, DF, DF).
capped_dist([L|Ls], [P|Ps], Current, D1-Front1, DF) :-
absdiff(L, P, D2),
D3 #= D1 + D2,
Current = D0-_,
( D3 #> D0 -> DF = Current
; capped_dist(Ls, Ps, Current, D3-Front1, DF)
).
我无法接受当代浮点数的肮脏和原始，所以我保留了整数运算，简单地将你显示的所有数字相乘，使它们成为整数：
?- list_subseq_min([21,34,40,11,20,40,100,120,150], [10,20,30], D). D = 11.
我不再扩展它，这样它也可以将找到的子序列显示为一个简单的练习。
重要说明：capping只影响距离的计算；请特别注意 运行 时间是 Θ(N×M) 由于 same_length_prefix/3 在 front//2 中的使用方式！我将改进它作为一个稍微困难的练习。