SWI-Prolog中模式识别的滑动窗口方法-解网

问：

从算法上讲，我想找到最有说服力和最有效的方法，来计算SWI-Prolog中某些模式的出现次数。

目前，我的解决方案使用 DCG，如下所示：

count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    length(PatternList, PatternLength),
    length(List, ListLength),
    MaxIndex is ListLength - PatternLength,
    findall(1, (
        between(0, MaxIndex, Index),
        sublist(List, Index, PatternLength, PatternList)
    ), Counts),
    sum_list(Counts, Count).

sublist(List, Index, Length, Sublist) :-
    length(Sublist, Length),
    append(Prefix, Rest, List),
    length(Prefix, Index),
    append(Sublist, _, Rest).

rep(S, L) --> [], {L is 0} | [S], {L is 1} | [S], { L_1 is L - 1 }, rep(S, L_1), !.
open_rep(S, L) --> [v], rep(S, L), [v], !.

结果是这样的：

1 ?- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
Count = 3.

2 ?- count_occurrences(open_rep(n, 3), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
Count = 1.

3 ?- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
Count = 2.

我对这个结果感到满意，但我认为这不是实现它的最有效方法，并希望得到一些帮助，使其计算速度更快。我认为使用和计算成本很高，但不知道没有它们如何做同样的事情......appendfindall

这里显示的 DCG 只是一个示例，但我必须计算列表中模式的出现次数并给它们打分。这是在使用 Alpha-Beta 修剪为 Gomoku 实现 AI 的背景下进行的。由于经常对电路板进行评估，因此算法的复杂性很重要，以减少 AI 采取行动所需的时间。

我已经尝试了上面显示的代码的多种变体，但它们都使用谓词，我发现减少计算时间的最佳解决方案是实现早期失败。findall

Prolog 模式匹配滑动窗口 DCG Gomoku

1赞 brebs 3/4/2023

太模糊了。“这里展示的 DCG 只是一个例子”——给我们一个明智的例子。

0赞 René Chenard 3/4/2023

仅涵盖此示例就足够了，因为我的 DCG 表达式用于识别简单的 Gomoku 线模式 sur：（连续闭合四个）、（四个的半开对齐）、（连续打开四个）......──◯─●─●─●─●─────●─●───●─●─────●─●─●─●─────

0赞 Will Ness 3/5/2023

如果是滑动窗口，将返回 5，而不是 2。open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v]

0赞 René Chenard 3/5/2023

@WillNess 使用 on 相当于对 ...这将导致 .然后对这个数组的内容求和，应该得到，而不是 ...open_rep(n, 1)[v,n,v,n,v,v,v,v,v,v,n,n,n,v,v][v,n,v][v,n,v,n,v,v,v,v,v,v,n,n,n,v,v][1,0,1,0,0,0,0,0,0,0,0,0,0,0]25

0赞 TA_intern 3/5/2023

目前还不清楚你为什么要编写所有这些代码来实现如此小的东西。你的问题大概缺少一些东西。

答：

2赞 slago 3/4/2023 #1

我认为，即使使用谓词，您仍然可以有一个有效的解决方案（至少这是使用 swi-prolog 可以观察到的）。append/3

count(Pattern, List, Count) :-
    phrase(Pattern, Sublist),
    count(List, Sublist, 0, Count).

count([], _, Count, Count).
count([X|Xs], Sublist, Count0, Count) :-
    (   append(Sublist, _, [X|Xs])
    ->   Count1 is Count0 + 1
    ;    Count1 is Count0 ),
    count(Xs, Sublist, Count1, Count).

% To compare the two versions with large lists

random_list(0, []) :- !.
random_list(N, [X|Xs]) :- 
    random_member(X, [n,v]), 
    M is N-1, 
    random_list(M, Xs).

使用 swi-prolog 比较和：count/3count_occurrences/3

?- random_list(1000,L), time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 4,648 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 3,003,226 inferences, 1.578 CPU in 1.683 seconds (94% CPU, 1903034 Lips)
L = [v, n, v, v, n, n, n, n, v|...],
C1 = C2, C2 = 116.

?- random_list(2000,L), time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 9,288 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 12,006,431 inferences, 11.812 CPU in 12.421 seconds (95% CPU, 1016417 Lips)
L = [n, n, v, v, n, n, n, v, n|...],
C1 = C2, C2 = 229.

?- random_list(1000000,L), time(count(open_rep(n,3),L,C1)).
% 4,905,979 inferences, 0.109 CPU in 0.146 seconds (75% CPU, 44854665 Lips)
L = [n, v, v, v, n, v, n, n, n|...],
C1 = 31246.

?- L = [v,n,v,n,v,v,v,v,v,v,n,v,v], time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 77 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 571 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 3.

?- L = [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], time(count(open_rep(n,3),L,C1)), time(count_occurrences(open_rep(n,3),L,C2)).
% 99 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 641 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 1.

?- L = [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 86 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 739 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 2.

1赞 René Chenard 3/10/2023

我最终使用了 CapelliC 建议的 clumped，并结合了对解决方案的修改。现在这是一种正确的滑动窗口方法，并且运行良好！谢谢！

1赞 CapelliC 3/4/2023 #2

IMO 您的方法过于具体，从（可重用性）的角度来看，它将是次优的。 SWI-Prolog 提供了一个执行 RLE（运行长度编码）的库谓词，正如我从这个有趣的主题中发现的那样，值得一试：在这里我将发布一个模块，我在其中复制了您的代码，以及一个使用 clumped/2 的替代方案：

/*  File:    x_so_sliding_window.pl
    Author:  Carlo
    Created: Mar  4 2023
    Purpose: https://stackoverflow.com/q/75630809/874024
*/

:- module(x_so_sliding_window,
          [count_occurrences/3
          ,open_rep//2
          ,count_by_clumped/3
          ]).


count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    length(PatternList, PatternLength),
    length(List, ListLength),
    MaxIndex is ListLength - PatternLength,
    findall(1, (
        between(0, MaxIndex, Index),
        sublist(List, Index, PatternLength, PatternList)
    ), Counts),
    sum_list(Counts, Count).

sublist(List, Index, Length, Sublist) :-
    length(Sublist, Length),
    append(Prefix, Rest, List),
    length(Prefix, Index),
    append(Sublist, _, Rest).

rep(S, L) --> [], {L is 0} | [S], {L is 1} | [S], { L_1 is L - 1 }, rep(S, L_1), !.
open_rep(S, L) --> [v], rep(S, L), [v], !.


count_by_clumped(Pattern,List,Count) :-
    clumped(List, R),
    aggregate_all(count, member(Pattern,R), Count).

然后我在 x_so_sliding_window.plt 中有这个代码

:- [x_so_sliding_window].

t(Count) :- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
t(Count) :- count_occurrences(open_rep(n, 3), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
t(Count) :- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).

c(Count) :- count_by_clumped(n-1, [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
c(Count) :- count_by_clumped(n-3, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
c(Count) :- count_by_clumped(n-1, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).

乍一看，这显示了 T/1 和 C/1 调用之间的等价性：

?- t(Count).
Count = 3 ;
Count = 1 ;
Count = 2.

?- c(Count).
Count = 3 ;
Count = 1 ;
Count = 2.

最后，直接在 REPL 中编码的“基准”：

?- time((between(1,1000,_),(t(_),fail))).
% 1,953,001 inferences, 0.234 CPU in 0.234 seconds (100% CPU, 8332804 Lips)
false.
?- time((between(1,1000,_),(c(_),fail))).
% 123,001 inferences, 0.000 CPU in 0.014 seconds (0% CPU, Infinite Lips)
false.

0赞 Will Ness 3/6/2023

不是吗？count_by_clumped(n-1, [v,n,v,n,v,v,v,v,v,v,n], 3)count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n], 2)

0赞 CapelliC 3/6/2023

@WillNess：在我的回答中看到我的编辑，希望对您有所帮助......

1赞 René Chenard 3/10/2023

我最终使用了你提出的和 slago 提出的组合：集群与线性搜索的混合。这有效地给了我一个滑动窗口的方法，计算速度大大提高！谢谢！

1赞 brebs 3/4/2023 #3

下面是子列表的更好方法：

sublist1([H|T], Index, Length, Sublist) :-
    sublist1_start_(T, H, 1, Index, Length, Sublist).

% P = previous
sublist1_start_(L, P, Ind, Index, Length, Sublist) :-
    sublist1_loop_(L, P, Ind, Index, 1, Length, Sublist).
sublist1_start_([H|T], _, Ind, Index, Length, Sublist) :-
    Ind1 is Ind + 1,
    % Go to next element
    sublist1_start_(T, H, Ind1, Index, Length, Sublist).

sublist1_loop_(_, H, Ind, Ind, Len, Len, [H]).
sublist1_loop_([H|T], P, Ind, Index, Len, Length, [P|Sublist]) :-
    Len1 is Len + 1,
    sublist1_loop_(T, H, Ind, Index, Len1, Length, Sublist).

swi-prolog 中的结果：

?- sublist1([a,b,c], Ind, Len, Sub).
Ind = Len, Len = 1,
Sub = [a] ;
Ind = 1,
Len = 2,
Sub = [a, b] ;
Ind = 1,
Len = 3,
Sub = [a, b, c] ;
Ind = 2,
Len = 1,
Sub = [b] ;
Ind = Len, Len = 2,
Sub = [b, c] ;
Ind = 3,
Len = 1,
Sub = [c].

如果希望索引从 0 而不是 1 开始，请将第 2 行中的 1 更改为 0。

我排除了空列表。

0赞 René Chenard 3/10/2023

谢谢你的回答！我最终使用了完全不同的东西，它使用结块，我不知道它是否能变得更好。我认为我的新解决方案具有线性复杂性......总之，现在真的快了！如果您有兴趣，我将很快发布我的 Gomoku 实现。

3赞 TA_intern 3/5/2023 #4

你的问题中缺少一些东西，不知道是什么。我也对答案感到惊讶。

不确定是否必须使用列表，或者是否可以使用原子或字符串。原子和字符串有 sub_atom/5 和 sub_string/5 resp，可用于搜索。喜欢这个：

?- sub_atom(vnvnvvvvvvnvv, Before, Len, After, vnv).
Before = 0, Len = 3, After = 10 ;
Before = 2, Len = 3, After = 8 ;
Before = 9, Len = 3, After = 1 ;
false.

相同但带有字符串适用于 sub_string/5。

如果您已经在使用 SWI-Prolog，则可以使用 library（aggregate）来计算解决方案：

?- aggregate_all(count, sub_atom(vnvnvvvvvvnvv, _,_,_, vnv), N).
N = 3.

?- aggregate_all(count, sub_atom(vnvnvvvvvvnnnvv, _,_,_, vnv), N).
N = 2.

到目前为止，您不需要编写任何程序。如果必须使用列表，则两个附加就足够了：

?- aggregate_all(
      count,
      ( append(_, Back, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v]),
        append([v,n,n,n,v], _, Back)
      ),
      N).
N = 1.

请记住，您还有正则表达式库库（pcre）。如果您使用文档中的示例代码：

:- use_module(library(pcre)).

re_match_count(Regex, String, N) :-
    re_foldl(inc, Regex, String, 0, N, []).

inc(_, V0, V) :- V is V0 + 1.

您还可以使用原子或字符串进行计数：

?- re_match_count('vn{1}(?=v)', vnvnvvvvvvnvv, N).
N = 3.

?- re_match_count("vn{3}(?=v)", "vnvnvvvvvvnnnvv", N).
N = 1.

（注意：这些正则表达式使用“零宽度正展望”。他们最初被我厌烦，并在威尔·尼斯注意到错误后修复）。

在此示例中，有关匹配项本身的所有信息都将被丢弃，并且仅计算匹配项的数量。你可以用第一个参数做任何你觉得re_foldl/6的事情。

注意：您需要衡量什么对您最有效。如果有一种方法可以读取字符串并将其保存为 Prolog 字符串，并使用 library（pcre），这可能比其他方法更快。

最后，如果要使用 DCG 进行模式识别，可以使用以下代码“匹配任意位置”：

match_dcg(G) --> string(_), call(G), remainder(_).

现在，这完全忽略了之前和之后的内容，或者匹配在列表中的位置。你可以像这样使用它，有自己的open_rep//2：

?- aggregate_all(
       count,
       phrase(match_dcg(open_rep(n, 1)), [v,n,v,n,v,v,v,v,v,v,n,v,v]),
       N).
N = 3.

此处定义的 match_dcg//1 与 phrase_from_file/2 文档中示例中的 match//1 之间的区别在于，match_dcg//1 将另一个 DCG 作为参数，而不是模式（子字符串）。

1赞 Will Ness 3/6/2023

是吗？OP 有 .就像你的.re_match_count('vn{1}v', vnvnvvvvvvnvv, N), N=2N=3aggregate_all(count, sub_atom(vnvnvvvvvvnvv, _,_,_, vnv), N)

1赞 TA_intern 3/6/2023

@WillNess 现在我想我明白了。谢谢你指出错误！

0赞 René Chenard 3/10/2023

我结束了使用其他东西，但我发现你的回答非常有启发性！谢谢！我尝试使用正则表达式，但我的 SWI-Prolog 设置似乎没有任何正则表达式库......你知道我怎样才能接触到它们吗？不行...:- use_module(library(pcre)).

0赞 TA_intern 3/10/2023

@RenéChenard 它应该可以工作。您可以通过多种方式安装SWI-Prolog，您应该说出您是如何做到的。我在 MacOS 上使用预编译的二进制文件，在 Linux 上从源代码编译，这两种方法都适合我。

1赞 TA_intern 3/10/2023

@RenéChenard Homebrew 可能是问题所在。不确定您是否使用相同的软件包获得所有东西，也许您需要一个额外的 PCRE 软件包。我一直在去这里：swi-prolog.org/download/devel 并下载带有可重定位应用程序包的映像，该应用程序包包含 intel 和 amd64 的胖二进制文件。这是“手动工作”（从浏览器下载，拖放，拖放......），但至少我知道我得到了一切，并且它应该工作。另一方面，在 Linux 上，自己编译它更容易。

3赞 Will Ness 3/8/2023 #5

应用增长分析的经验顺序，您可以看到您的代码表现出二次行为，而各种答案的代码变体是线性的。

为什么？

这是因为您坚持强制中缀从已知索引开始，逐个增加索引。然后，中缀字符串由一对 s 找到，每次都从输入列表的开头重新开始。append

因此，该工作是以经典的三角形方式完成的（如链接条目中所示），导致有问题的二次行为。

但是两个 s 将自行执行此操作，此外，从上次处理的索引开始，而不是从索引 0 重新开始。他们不会从 0 开始并沿着输入列表到给定的索引，而是直接从继续;因此具有线性执行时间。appendii

为了用你的代码实现这一点，你只需要从中删除处理索引操作的每一位，它就会神奇地变成你在答案中看到的有效变体。

这让你

count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    /*length(PatternList, PatternLength),
    length(List, ListLength),
    MaxIndex is ListLength - PatternLength,*/
    findall(1, (
        /*between(0, MaxIndex, Index),*/
        sublist(List, /*Index, PatternLength,*/ PatternList)
    ), Counts),
    sum_list(Counts, Count).

sublist(List, /*Index, Length,*/ Sublist) :-
    /*length(Sublist, Length),*/
    append(_Prefix, Rest, List),
    /*length(Prefix, Index),*/
    append(Sublist, _, Rest).

正如预期的那样，它检查线性：

167 ?- random_list(1000,L),time(count_occurrences(open_rep(n,3),L,C)).
% 3,094 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
L = [v, n, n, v, v, v, n, n, n|...],
C = 24.

168 ?- random_list(10000,L),time(count_occurrences(open_rep(n,3),L,C)).
% 30,514 inferences, 0.000 CPU in 0.003 seconds (0% CPU, Infinite Lips)
L = [n, n, v, v, v, v, v, n, v|...],
C = 280.

使用此处的另一个答案进行测试。random_list/2

现在，您可以将调用合并到一个谓词中，如该答案所示。不过，请务必使用实际数据测试这两种方法。使用库函数可能仍然更快。因此，也请尝试TA_intern答案中的方法。findallsum_listcountaggregate_all

少需求和控制，多成就！或

过早~~的优化~~实施是万恶之源。

1赞 TA_intern 3/9/2023

很好的答案！小补充：根据必须匹配的模式，可能有比sub_atom或两个附加更好的方法。例如，KMP 算法比在匹配失败后重新开始的线性搜索更有效，并且具有更好的最坏情况性能。不过，它不适用于 DCG 匹配，至少没有一些巧妙的调整。

2赞 Will Ness 3/10/2023

@RenéChenard不，不要使用 RLE“结块”。这是一种错误的方法，并不总是有效，正如我评论中的示例所示。对于 n-1，它会根据需要查找并计算“n”而不是“vnv”。

1赞 slago 3/10/2023

考虑长度为 m 的模式和长度为 n 的列表，在最坏情况下，算法的时间复杂度为 O （ m × n）。因此，复杂度仅对 m 常数是线性的。对于 m 变量且远小于 n（即 m ≪ n），复杂度几乎是线性的。否则，对于 m 变量且接近 n（即 m ≈ n），复杂度仍将是二次的。

1赞 TA_intern 3/11/2023

@RenéChenard 您的问题比问题的标题或内容所暗示的要具体得多（只有在评论中才能清楚地看到您在做什么）。您仍然可以避免使用 clumped/2 然后“模式匹配”;这是列表的两次传递，您实际上只需要一次。我仍然怀疑正则表达式可能是迄今为止实践中最快的。如果你坚持在列表上工作，你可以使用与 clumped/2 相同的方法（参见实现！），但只需一次完成工作。

1赞 TA_intern 3/11/2023

@RenéChenard KMP 算法使用两次传递;但它处理任何模式。您的模式非常简单，不需要第一次传递就知道它可以跳过多远。

上一个：在 checkWin for gomoku 中计数未增加到 2 以上

下一个：为什么 Piskvork 不断向我的机器人发送 END？

SWI-Prolog中模式识别的滑动窗口方法

Sliding window method for pattern recognition in SWI-Prolog

评论

评论

评论

评论

评论

评论