list - 字符串列表的最长公共(public)前缀 (LCP)

Question

lcs([ H|L1],[ H|L2],[H|Lcs]) :-
    !,
    lcs(L1,L2,Lcs).
lcs([H1|L1],[H2|L2],Lcs):-
    lcs(    L1 ,[H2|L2],Lcs1),
    lcs([H1|L1],    L2 ,Lcs2),
    longest(Lcs1,Lcs2,Lcs),
    !.
lcs(_,_,[]).

longest(L1,L2,Longest) :-
    length(L1,Length1),
    length(L2,Length2),
    (  Length1 > Length2
    -> Longest = L1
    ;  Longest = L2
    ).

到目前为止，这是我的代码。我如何优化它以便打印前缀，例如:

["interview", "interrupt", "integrate", "intermediate"]

应该返回 "inte"
Prolog 有点生疏，有一段时间没做过了:)

Answer 1

首先，让我们从一些相关的东西开始，但要简单得多。

:- set_prolog_flag(double_quotes, chars).  % "abc" = [a,b,c]

prefix_of(Prefix, List) :-
   append(Prefix, _, List).

commonprefix(Prefix, Lists) :-
   maplist(prefix_of(Prefix), Lists).

?- commonprefix(Prefix, ["interview", "integrate", "intermediate"]).
   Prefix = []
;  Prefix = "i"
;  Prefix = "in"
;  Prefix = "int"
;  Prefix = "inte"
;  false.

(参见 this 答案，如何打印带双引号的字符列表。)

这是 Prolog 中相当容易的部分。唯一的缺点是它没有给我们最大值，而是所有可能的解决方案，包括最大值。请注意，不需要知道所有字符串，例如:

?- commonprefix(Prefix, ["interview", "integrate", Xs]).
   Prefix = []
;  Prefix = "i", Xs = [i|_A]
;  Prefix = "in", Xs = [i, n|_A]
;  Prefix = "int", Xs = [i, n, t|_A]
;  Prefix = "inte", Xs = [i, n, t, e|_A]
;  false.

所以我们得到最后一个未知单词的部分描述作为响应。现在想象一下，后来我们意识到 Xs = "induce" . Prolog 没问题:

?- commonprefix(Prefix, ["interview", "integrate", Xs]), Xs = "induce".
   Prefix = [], Xs = "induce"
;  Prefix = "i", Xs = "induce"
;  Prefix = "in", Xs = "induce"
;  false.

事实上，我们在事后或在实际查询之前陈述这一点并没有什么区别:

?- Xs = "induce", commonprefix(Prefix, ["interview", "integrate", Xs]).
   Xs = "induce", Prefix = []
;  Xs = "induce", Prefix = "i"
;  Xs = "induce", Prefix = "in"
;  false.

我们现在可以根据这个制定最大值吗？请注意，这实际上需要某种形式的额外 quantor，我们在 Prolog 中没有任何直接规定。出于这个原因，我们必须将我们限制在我们知道是安全的某些情况下。最简单的方法是坚持单词列表不包含任何变量。我将使用 iwhen/2 以此目的。

maxprefix(Prefix, Lists) :-
   iwhen(ground(Lists), maxprefix_g(Prefix, Lists)).

maxprefix_g(Prefix, Lists_g) :-
   setof(N-IPrefix, ( commonprefix(IPrefix, Lists_g), length(IPrefix, N ) ), Ns),
   append(_,[N-Prefix], Ns).   % the longest one

这种方法的缺点是如果不知道单词列表，我们会得到实例化错误。

请注意，我们做了一些假设(我希望真的成立)。特别是我们假设只有一个最大值。在这种情况下，这成立，但一般来说， Prefix 可能有几个独立的值。 .此外，我们假设 IPrefix将永远接地。我们也可以检查一下，只是为了确定。或者:

maxprefix_g(Prefix, Lists_g) :-
   setof(N, IPrefix^ ( commonprefix(IPrefix, Lists_g), length(IPrefix, N ) ), Ns),
   append(_,[N], Ns),
   length(Prefix, N),
   commonprefix(Prefix, Lists_g).

在这里，前缀不必是一个单一的前缀(在我们的情况下就是这样)。

然而，最好的版本是更纯粹的版本，根本不需要诉诸实例化错误。