Dcg-Status Implementierung des Algorithmus

Question

Der Abstand zwischen einer langen Sequenz und einer kurzen Sequenz ist der minimale Abstand zwischen der kurzen Sequenz und einer beliebigen Untersequenz der langen Sequenz, die dieselbe Länge wie die kurze Sequenz hat.

Die Entfernung, die ich benutze, ist die Manhattan Entfernung. (Aber das sollte unwichtig sein, da ich die Entfernungsfunktionen gerne ändern würde).

Diese erste Version zeigt eine naive Implementierung ohne frühen Verzicht. Ich erzeuge alle Untersequenzen derselben Länge, mappe diese, um den Abstand zwischen ihnen und der kurzen Sequenz zu finden, und verwende dann aggregate/3, um das min zu finden.

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). 

Beispiel query:

?-smallseq_largeseq_dis([1,2,4],[1,2,3,1,2,5],Dis). 
Dis = 1 

Diese nächste Version effizienter sein sollte, da sie im Stich lassen werden, den Abstand zwischen einer Subsequenz der langen Sequenz und der kurzen Sequenz Berechnung, wenn der Abstand über das Minimum ist schon gefunden.

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). 

Abfrage:

?-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] 

Aber in diesem habe ich verwendet assert und einfahren, so möchte ich eine Version haben, die den gleichen Algorithmus tut, aber mit aus diesen. Ich denke, dass ich das mit einem dcg mit Semicontext-Notation machen könnte, aber es ist schwer zu verstehen ... wie behalte ich die Subsequenzen im Auge, die ich durch Backtracking und gleichzeitig den 'Zustand' der Mindestdistanz erzeuge bis jetzt gefunden?

Das Problem habe ich .. seq_subseq/2 erzeugt die Untersequenzen durch Rückverfolgung. Der erste getestete sublive muss auf den Mindestabstand eingestellt werden. Ich möchte dann Schleife, also zurück verfolgen, um eine andere Sequenz zu generieren. Aber um zurückzuverfolgen, muss ich scheitern. Aber dann kann ich die minimale Entfernung nicht zurück bringen, um die nächste Sequenz zu überprüfen.

Wenn ich nicht Backtracking verwenden möchte, muss ich ein Zustandsübergangsprädikat für die Generierung der Untersequenzen in Reihenfolge definieren.

Im Moment

? 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] 

Also ich denke, ich brauche eine Beziehung zu definieren:

subseq0_seq_subseq1(Subseq0,Seq,Subseq1) 

, die wie funktionieren würde:

?-subseq0_seq_subseq1([1,2,3,4],[1,2,3,4],Subseq1). 
Subseq1 = [2]. 

und

?-subseq0_seq_subseq1([1,2,3],[1,2,3,4],Subseq1). 
Subseq1 = [1,2,3,4]. 

Aber ich muss dies auf eine effiziente Weise tun.

Update - Dank der Antwort von Mat habe ich jetzt das, was eine große Verbesserung ist, denke ich. Kann jemand weitere Verbesserungen sehen? Ich habe eine doppelte verschachtelte -> Struktur und ein! in der Definition accumulate_dis/4, die beide hässlich erscheinen. Ich habe es auch dazu gebracht, die Subsequenz der langen Sequenz zurückzugeben, die die kürzeste Entfernung von der kurzen Sequenz ist.

Es muss mit nicht ganzen Zahlen arbeiten, so clpfd ist nicht geeignet, denke ich.

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. 

query:

?- 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]. 

Answer 1

Ein wichtiger Hinweis: Sie sollten clearified, dass Sie über die Manhatten   Abstand zwischen den Listen sprechen. Dies wurde nur aus Ihrem Code klar, während Ihre Formulierung Leser leicht davon ausgehen lassen kann, dass Sie über die Edit   Entfernung sprechen.

Hier ist eine Lösung, die einfach die Liste durchläuft, das Minimum verfolgt und schließlich das gefundene Minimum ergibt.

 
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 
    ). 

Beispiel Abfrage und das Ergebnis:

 
?- list_subseq_min([1,2,3,1,2,5], [1,2,4], D). 
D = 1. 

Es ist ziemlich geradlinig, und da die Buchhaltung nur ein Prädikat beschränkt ist, zahlt sich semicontext Notationen nicht wirklich aus. Es ist besonders nützlich, die Semikontextnotation — und DCGs in   general — zu verwenden, wenn das, was beschrieben wird, sich über verschiedene Regeln erstreckt und die Kommunikation zwischen ihnen ansonsten schwieriger wäre.

Die Laufzeit ist in O (N × M).

Und nun der Punkt, den ich als Übung verlassen: Ändern diese Lösung Prune früher, wenn die zuvor wird Minimum gefunden bereits überschritten. Tun Sie dies in einer reinen Weise oder mindestens so rein wie möglich: assertz/1 und Freunde sind definitiv aus der   Frage, da sie Ihre Prüfung dieser Prädikate in Isolation verhindern. Führen Sie Argumente um und bauen Sie die Entfernung schrittweise auf! Dies kann Ihnen helfen, die durchschnittliche Laufzeit zu verbessern, natürlich nicht die Worst-Case-Komplexität.

Es ist für diese Weitergabe zwischen verschiedenen Klauseln, dass Semicontext-Notation endlich nützlich werden kann.

EDIT: Sehr gut, Sie haben eine Lösung implementiert, die das Beschneiden durchführt. Ich werde jetzt auch meins zeigen.Ich werde wiederverwendet werden die Hilfs Prädikate absdiff/3 und lists_dist/3 von oben, und die folgenden zusätzlichen Hilfs Prädikat:

 
same_length_prefix(Ls, Ps, Front) :- 
     same_length(Front, Ps), 
     append(Front, _, Ls). 

list_subseq_min/3 ist nun etwas anders:

 
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-_]). 

Und nun der Punkt: min_sublist//2 ist ein DCG   Nonterminal, das prägnant die Grundidee des Algorithmus beschreibt:

 
min_sublist(Ls0, Subs) --> 
     ( front(Ls0, Subs) -> 
      { Ls0 = [_|Ls] }, 
      min_sublist(Ls, Subs) 
     ; [] 
     ). 

Aus dieser Beschreibung ist es sehr klar, dass wir die Liste Element für Element betrachten. Es verwendet weniger (explizite) Argumente als zuvor. Die zusätzlichen zwei Argumente werden implizit als ein PaarD-Front weitergegeben, das den besten Abstand und die bisher gefundene Subsequenz verfolgt. Beachten Sie, wie die DCG   Notation den Kern der Berechnung darstellt und verbirgt, was an dieser Stelle nicht relevant ist.

Der Rest ist ziemlich selbsterklärend und entspricht dem von Ihnen durchgeführten Beschneiden. Ich unterstreiche die einmalige Verwendung der Semikontext-Notation in diesem Programm, mit der wir jede Änderung der bisher gefundenen optimalen Sequenz ausdrücken können.

 
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) 
     ). 

Ich kann mich nicht dazu bringen, die Bösartigkeit und Primitivität der zeitgenössischen Gleitkommazahlen zu akzeptieren, so dass ich die Integer-Arithmetik und multiplizieren Sie einfach alle Zahlen beibehalten zeigen, so dass sie ganze Zahlen werden:

 
?- list_subseq_min([21,34,40,11,20,40,100,120,150], [10,20,30], D). 
D = 11. 

Ich lasse diese erweitern, so dass es auch die gefundene Subsequenz als eine einfache Übung zeigt.

Ein wichtiger Hinweis: Die Begrenzung wirkt sich nur auf die Berechnung der Entfernung aus; beachten Sie insbesondere, dass die Laufzeit   Θ (N × M) aufgrund der Art und Weise same_length_prefix/3 in   front//2 verwendet wird! Ich überlasse es, dies als etwas härtere Übung zu verbessern.