Le plus long préfixe commun (LCP) d'une liste de chaînes
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
).
C'est mon code jusqu'à présent. Comment pourrais-je l'optimiser pour qu'il imprime le préfixe, par exemple:
["interview", "interrupt", "integrate", "intermediate"]
devrait revenir "inte"
Un peu rouillé avec Prolog, ne l'ont pas fait en temps :)
5 réponses
tout d'Abord, commençons par quelque chose de lié, mais beaucoup plus simple.
:- 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.
(Voir réponse, comment l'impression des listes de caractères entre guillemets est fait.)
C'est la partie qui est assez facile en Prolog. Le seul inconvénient est qu'il ne nous donne pas le maximum, mais plutôt toutes les solutions possibles, y compris le maximum. Notez que toutes les chaînes n'ont pas besoin d'être connues, comme:
?- 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.
nous obtenons donc une réponse partielle description du dernier mot inconnu. Maintenant imaginez, plus tard nous réalisons que Xs = "induce". Pas de problème pour le Prologue:
?- commonprefix(Prefix, ["interview", "integrate", Xs]), Xs = "induce".
Prefix = [], Xs = "induce"
; Prefix = "i", Xs = "induce"
; Prefix = "in", Xs = "induce"
; false.
en fait, cela ne fait pas de différence que nous le disions rétrospectivement ou juste avant la requête:
?- Xs = "induce", commonprefix(Prefix, ["interview", "integrate", Xs]).
Xs = "induce", Prefix = []
; Xs = "induce", Prefix = "i"
; Xs = "induce", Prefix = "in"
; false.
pouvons-nous maintenant nous baser sur cette formulation du maximum? Notez que cela nécessite effectivement une certaine forme de quantification supplémentaire pour laquelle nous n'avons pas de dispositions directes dans Prolog. Pour cette raison, nous devons nous limiter à certains les cas que nous connaissons seront en sécurité. La solution la plus simple serait d'insister sur le fait que la liste de mots ne contient aucune variable. Je vais utiliser iwhen/2 à cette fin.
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
l'inconvénient de cette approche est que nous obtenons des erreurs d'instanciation si la liste des mots n'est pas connue.
notez que nous avons fait pas mal de suppositions (que j'espère vraiment retenir). En particulier, nous avons supposé qu'il y a exactement un maximum. Dans ce cas, cela tient, mais dans Généralités il se pourrait qu'il y ait plusieurs valeurs indépendantes pour Prefix. Aussi, nous avons supposé que IPrefix sera toujours au sol. On pourrait vérifier ça aussi, juste pour être sûr. Alternativement:
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).
ici, le préfixe ne doit pas être un seul préfixe (ce qui est dans notre situation).
le meilleur, cependant, serait une version plus pure qui n'a pas besoin de recourir à des erreurs d'instanciation du tout.
Voici comment je voudrais mettre en œuvre ceci:
:- set_prolog_flag(double_quotes, chars).
longest_common_prefix([], []).
longest_common_prefix([H], H).
longest_common_prefix([H1,H2|T], P) :-
maplist(append(P), L, [H1,H2|T]),
( one_empty_head(L)
; maplist(head, L, Hs),
not_all_equal(Hs)
).
one_empty_head([[]|_]).
one_empty_head([[_|_]|T]) :-
one_empty_head(T).
head([H|_], H).
not_all_equal([E|Es]) :-
some_dif(Es, E).
some_dif([X|Xs], E) :-
if_(diffirst(X,E), true, some_dif(Xs,E)).
diffirst(X, Y, T) :-
( X == Y -> T = false
; X \= Y -> T = true
; T = true, dif(X, Y)
; T = false, X = Y
).
la mise en oeuvre de not_all_equal/1cette réponse par @repeat (vous pouvez trouver mon implémentation dans l'historique d'édition).
Nous utilisons append et maplist pour diviser les chaînes de la liste dans un préfixe et d'un suffixe, et où le préfixe est le même pour toutes les chaînes. Pour ce préfixe le plus long, nous devons affirmer que le premier caractère d'au moins deux des suffixes sont différent.
C'est pourquoi nous utilisons head/2,one_empty_head/1 et not_all_equal/1. head/2 est utilisé pour récupérer le premier caractère d'une chaîne; one_empty_head/1 est utilisé à l'état que si l'un des suffixes est vide, alors automatiquement, c'est le plus long préfixe. not_all_equal/1 est utilisé pour vérifier ou déclarer qu'au moins deux caractères sont différents.
Exemples
?- longest_common_prefix(["interview", "integrate", "intermediate"], Z).
Z = [i, n, t, e] ;
false.
?- longest_common_prefix(["interview", X, "intermediate"], "inte").
X = [i, n, t, e] ;
X = [i, n, t, e, _156|_158],
dif(_156, r) ;
false.
?- longest_common_prefix(["interview", "integrate", X], Z).
X = Z, Z = [] ;
X = [_246|_248],
Z = [],
dif(_246, i) ;
X = Z, Z = [i] ;
X = [i, _260|_262],
Z = [i],
dif(_260, n) ;
X = Z, Z = [i, n] ;
X = [i, n, _272|_274],
Z = [i, n],
dif(_272, t) ;
X = Z, Z = [i, n, t] ;
X = [i, n, t, _284|_286],
Z = [i, n, t],
dif(_284, e) ;
X = Z, Z = [i, n, t, e] ;
X = [i, n, t, e, _216|_224],
Z = [i, n, t, e] ;
false.
?- longest_common_prefix([X,Y], "abc").
X = [a, b, c],
Y = [a, b, c|_60] ;
X = [a, b, c, _84|_86],
Y = [a, b, c] ;
X = [a, b, c, _218|_220],
Y = [a, b, c, _242|_244],
dif(_218, _242) ;
false.
?- longest_common_prefix(L, "abc").
L = [[a, b, c]] ;
L = [[a, b, c], [a, b, c|_88]] ;
L = [[a, b, c, _112|_114], [a, b, c]] ;
L = [[a, b, c, _248|_250], [a, b, c, _278|_280]],
dif(_248, _278) ;
L = [[a, b, c], [a, b, c|_76], [a, b, c|_100]] ;
L = [[a, b, c, _130|_132], [a, b, c], [a, b, c|_100]];
…
Voici la variante purifiée du code proposé (et ultérieurement rétracté) par @CapelliC:
:- set_prolog_flag(double_quotes, chars).
:- use_module(library(reif)).
lists_lcp([], []).
lists_lcp([Es|Ess], Ls) :-
if_((maplist_t(list_first_rest_t, [Es|Ess], [X|Xs], Ess0),
maplist_t(=(X), Xs))
, (Ls = [X|Ls0], lists_lcp(Ess0, Ls0))
, Ls = []).
list_first_rest_t([], _, _, false).
list_first_rest_t([X|Xs], X, Xs, true).
méta-prédicatmaplist_t/3 est une variante de maplist/2
qui fonctionne avec le terme égalité / inégalité réification -maplist_t/5 est tout de même avec la plus arité:
maplist_t(P_2, Xs, T) :-
i_maplist_t(Xs, P_2, T).
i_maplist_t([], _P_2, true).
i_maplist_t([X|Xs], P_2, T) :-
if_(call(P_2, X), i_maplist_t(Xs, P_2, T), T = false).
maplist_t(P_4, Xs, Ys, Zs, T) :-
i_maplist_t(Xs, Ys, Zs, P_4, T).
i_maplist_t([], [], [], _P_4, true).
i_maplist_t([X|Xs], [Y|Ys], [Z|Zs], P_4, T) :-
if_(call(P_4, X, Y, Z), i_maplist_t(Xs, Ys, Zs, P_4, T), T = false).
d'Abord, voici un motif de la requête:
?- lists_lcp(["a","ab"], []). false. % fails (as expected)
Voici les requêtes présentées dans @Fatalize fine de réponse.
?- lists_lcp(["interview",X,"intermediate"], "inte").
X = [i,n,t,e]
; X = [i,n,t,e,_A|_B], dif(_A,r)
; false.
?- lists_lcp(["interview","integrate",X], Z).
X = Z, Z = []
; X = Z, Z = [i]
; X = Z, Z = [i,n]
; X = Z, Z = [i,n,t]
; X = Z, Z = [i,n,t,e]
; X = [i,n,t,e,_A|_B], Z = [i,n,t,e]
; X = [i,n,t,_A|_B] , Z = [i,n,t] , dif(_A,e)
; X = [i,n,_A|_B] , Z = [i,n] , dif(_A,t)
; X = [i,_A|_B] , Z = [i] , dif(_A,n)
; X = [_A|_B] , Z = [] , dif(_A,i).
?- lists_lcp([X,Y], "abc").
X = [a,b,c] , Y = [a,b,c|_A]
; X = [a,b,c,_A|_B], Y = [a,b,c]
; X = [a,b,c,_A|_B], Y = [a,b,c,_C|_D], dif(_A,_C)
; false.
?- lists_lcp(L, "abc").
L = [[a,b,c]]
; L = [[a,b,c],[a,b,c|_A]]
; L = [[a,b,c,_A|_B],[a,b,c]]
; L = [[a,b,c,_A|_B],[a,b,c,_C|_D]], dif(_A,_C)
; L = [[a,b,c],[a,b,c|_A],[a,b,c|_B]]
; L = [[a,b,c,_A|_B],[a,b,c],[a,b,c|_C]]
; L = [[a,b,c,_A|_B],[a,b,c,_C|_D],[a,b,c]]
; L = [[a,b,c,_A|_B],[a,b,c,_C|_D],[a,b,c,_E|_F]], dif(_A,_E)
…
dernier, voici la requête montrant le déterminisme amélioré:
?- lists_lcp(["interview","integrate","intermediate"], Z).
Z = [i,n,t,e]. % succeeds deterministically
Cette réponse précédente présenté une implémentation basée sur if_/3.
:- use_module(library(reif)).
Voici une autre de prendre sur elle:
lists_lcp([], []).
lists_lcp([Es|Ess], Xs) :-
foldl(list_list_lcp, Ess, Es, Xs). % foldl/4
list_list_lcp([], _, []).
list_list_lcp([X|Xs], Ys0, Zs0) :-
if_(list_first_rest_t(Ys0, Y, Ys) % if_/3
, ( Zs0 = [X|Zs], list_list_lcp(Xs, Ys, Zs) )
, Zs0 = []
).
list_first_rest_t([], _, _, false).
list_first_rest_t([X|Xs], Y, Xs, T) :-
=(X, Y, T). % =/3
Presque toutes les requêtes dans ma réponse précédente donnent les mêmes réponses, donc je ne les montre pas ici.
lists_lcp([X,Y], "abc"), cependant, ne se termine plus universellement avec le nouveau code.
une version simple:
:- set_prolog_flag(double_quotes, chars).
pref([],_,[]).
pref(_,[],[]).
pref([H|T1],[H|T2],[H|Tr]):-
pref(T1,T2,Tr).
pref([H|_],[H|_],[]).
pref([H1|_],[H2|_],[]):-
dif(H1,H2).
lcf([],[]).
lcf([W],R):-
pref(W,W,R).
lcf([W1,W2|L],R):-
pref(W1,W2,R),
lcf([W2|L],R).
Exemples:
pref("interview","integrate",R).
R = [i, n, t, e] ;
R = [i, n, t] ;
R = [i, n] ;
R = [i] ;
R = [] ;
False.
lcf(["interview", "interrupt", "integrate", "intermediate"],R).
R = [i, n, t, e]
lcf(["interview", "interrupt", X, "intermediate"],R).
R = X, X = [i, n, t, e, r]