运行使用 DCG 进行长度编码

Question

问题来自：https://web.archive.org/web/20200718175929/http://www.pathwayslms.com/swipltuts/dcg/

Use a dcg to convert a sparse sequence like
[0,0,0,0,0,0,7,4,3,0,0,0,0,0,0,0,8,9,14,0,0,0,0....]
to
[zero(6), 7,4,3, zero(7), 8,9,14, ...]

我觉得我理解了此页面上的 material，但真的不知道如何开始这个。任何指针将不胜感激

Answer 1

尝试做这样的事情：

code([X|Xs]) --> item(X), code(Xs).
code([])     --> [].

item(X) --> [0], zeros(1, X).
item(X) --> [X], { X \= 0 }.

zeros(M, N)       --> [0], { M1 is M + 1 }, zeros(M1, N).
zeros(N, zero(N)) --> \+ [0].

示例：

?- phrase(code(C), [0,0,0,0,0,0,7,4,3,0,0,0,0,0,0,0,8,9,14,0,0,0,0]).
C = [zero(6), 7, 4, 3, zero(7), 8, 9, 14, zero(4)] ;
false.

Answer 2

替代样式：

% For eos
:- use_module(library(dcg/basics)).

list_rle(Lst, LstRle) :-
    must_be(list, Lst),
    phrase(rle, Lst, LstRle),
    % The first is correct
    !.
    
% Check for list of zeros
rle, [zero(N)] --> [0], zeros(1, N), rle.
% Accept anything otherwise
rle, [C] --> [C], rle.
% Being greedy - check for end last
% eos means no more input - better than [] which can leave a remainder
rle --> eos.

zeros(N, Tot) --> [0], { N1 is N + 1 }, zeros(N1, Tot).
% Being greedy - check for end last
zeros(N, N) --> [].

结果swi-prolog：

?- time(list_rle([0,0,0,0,0,0,7,4,3,0,0,0,0,0,0,0,8,9,14,0,0,0,0], L)).
% 39 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 545073 Lips)
L = [zero(6),7,4,3,zero(7),8,9,14,zero(4)].

另一个也可以用作生成器的小变体：

rle --> eos.
rle, [zero(N)] --> [0], zeros(1, N), rle.
rle, [C] --> [C], { dif(C, 0) }, rle.

zeros(N, Tot) --> [0], !, { N1 is N + 1 }, zeros(N1, Tot).
zeros(N, N) --> [].

结果：

?- length(L, _), list_rle(L, LR).
L = LR, LR = [] ;
L = [0],
LR = [zero(1)] ;
L = LR, LR = [_A],
dif(_A,0) ;
L = [0,0],
LR = [zero(2)] ;
L = [_A,0],
LR = [_A,zero(1)],
dif(_A,0) ;
L = LR, LR = [_A,_B],
dif(_A,0),
dif(_B,0) ;
L = [0,0,0],
LR = [zero(3)] ;
L = [_A,0,0],
LR = [_A,zero(2)],
dif(_A,0) ;

运行 使用 DCG 进行长度编码

run length encoding using DCGs

prolog

dcg

运行使用 DCG 进行长度编码