1:- module(ccp_kbest, [graph_nviterbi/4]).
12:- use_module(library(dcg_pair)). 13:- use_module(library(dcg_macros)). 14:- use_module(library(lazy), [lazy_maplist/3, lazy_unfold_finite/4, lazy/4]). 15:- use_module(graph, [graph_fold/4, top_value/2]).
21graph_nviterbi(Graph, Params, Tree, LP) :-
22 graph_fold(kbest, Params, Graph, VGraph),
23 top_value(VGraph, Expls),
24 member(LP-Tree,Expls).
25
26ccp_graph:sr_inj(kbest, P, F, [Q-F]) :- when(ground(P), Q is -log(P)).
27ccp_graph:sr_proj(kbest, G, X, Y, X) :- freeze(Y, lazy_maplist(k_tag(G),X,Y)).
28ccp_graph:sr_plus(kbest, X) --> lazy(k_min,X).
29ccp_graph:sr_times(kbest, X) --> lazy(k_mul,X).
30ccp_graph:sr_zero(kbest, []).
31ccp_graph:sr_unit(kbest, [0.0-[]]).
32
33k_tag(G,L-X,L-(G-X)). 34
35k_min([],Ys,Ys) :- !.
36k_min(Xs,[],Xs) :- !.
37k_min([X|Xs],[Y|Ys],[Z|Zs]) :-
38 ( LX-_=X, LY-_=Y, LX =< LY
39 -> Z=X, freeze(Zs, k_min(Xs,[Y|Ys],Zs))
40 ; Z=Y, freeze(Zs, k_min([X|Xs],Ys,Zs))
41 ).
42
43k_mul(Xs,Ys,Zs) :-
44 empty_set(EmptyS), empty_heap(EmptyQ),
45 enqueue(pos(0-0,Xs,Ys), EmptyS-EmptyQ, TQ1),
46 lazy_unfold_finite(k_next, Zs, TQ1, _).
47
48k_next(L-[XF|YFs]) -->
49 \> pq_get(L,pos(I-J,[X0|Xs],[Y0|Ys])),
50 {_-XF=X0, _-YFs=Y0, succ(I,I1), succ(J,J1)},
51 enqueue(pos(I1-J,Xs,[Y0|Ys])),
52 enqueue(pos(I-J1,[X0|Xs],Ys)).
53
54enqueue(P) --> new_position_cost(P,L) -> \> pq_add(L,P); [].
55new_position_cost(pos(IJ,[X0-_|_],[Y0-_|_]),L) --> \< add_to_set(IJ), {L is X0+Y0}.
56
57pq_add(L,P,H1,H2) :- add_to_heap(H1,L,P,H2).
58pq_get(L,P,H1,H2) :- get_from_heap(H1,L,P,H2).
59add_to_set(X,S1,[X|S1]) :- \+memberchk(X,S1).
60empty_set([]).
Lazy k-best parsing
This module provides a semiring for generating parse trees lazily in best-first order, based on the algorithm of Huang and Chiang [1]. Unlike their method however, this needs no preassigned limit on the number of parses to produce.
[1] Liang Huang and David Chiang. Better k-best parsing. In Proceedings of the Ninth International Workshop on Parsing Technology, pages 53–64. Association for Computational Linguistics, 2005. */