lcs.pl -- Longest common subsequence

Compute a longest common subsequence between two lists. Elements can be compared by means of an arbitrary similarity metric.

lcs(+As:list, +Bs:list, -LCS:list) is det

True if LCS is a longest common subsequence of As and Bs. Elements A and B are can be common if A==B.

Implemented in terms of lcs/5.

lcs(+Cmp:callable, +As:list, +Bs:list, -LCS:list, -Length) is det

True if LCS is a longest common subsequence of As and Bs. LCS is a list of pairs A-B since Cmp allows non-identical elements to be considered common.

Elements of As and Bs are compared by call(Cmp,A,B,Similarity), where larger Similarity values indicate more similar elements. Length is the sum of similarity scores for elements in the subsequence.

Implemented with memoization on top of a naive, exponential algorithm. It performs fairly well, but patches to use a better algorithm are welcome.

equality_metric(+A, +B, -Similarity) is det

Similarity is 1 if A == B, otherwise 0. This predicate is helpful as the first argument to lcs/5.