Re: Longest Common Subsequence in Postgres - Algorithm Challenge

On Monday, July 8, 2013, Robert James wrote:

> On 7/8/13, hubert depesz lubaczewski <depesz(at)depesz(dot)com <javascript:;>>
> wrote:
> > On Mon, Jul 08, 2013 at 09:09:26AM -0400, Robert James wrote:
> >> I have two relations, where each relation has two fields, one
> >> indicating a name and one indicating a position. That is, each
> >> relation defines a sequence.
> >>
> >> I need to determine their longest common subsequence. Yes, I can do
> >> this by fetching all the data into Java (or any other language) and
> >> computing it using the standard LCS dynamic programming language. But
> >> I'd like to stay within Postgres. Is there any way to do this?
> >
> > I'm not entirely sure I understand. Can you show us some sample data and
> > expected output?
>
> Sure. Borrowing a good example from
> http://wordaligned.org/articles/longest-common-subsequence :
>
> Table A (val varchar primary key, pos integer):
> 1, "C"
> 2, "H"
> 3, "I"
> 4, "M"
> 5, "P"
> 6, "A"
> 7, "N"
> 8, "Z"
> 9, "E"
> 10, "E"
>
> Table B (val varchar primary key, pos integer):
> 1, "H"
> 2, "U"
> 3, "M"
> 4, "A"
> 5, "N"
>
> SELECT LongestCommonSubsequence(A,B):
> 1, "H"
> 2, "M"
> 3, "A"
> 4, "N"
>
> (Common chars are in upper case:
> cHiMpANzee
> HuMAN
> )
>
> The std dynamic programming algorithm is described at
> http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
>
>
> --
> Sent via pgsql-general mailing list (pgsql-general(at)postgresql(dot)org<javascript:;>
> )
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-general
>

To me it looks like:

Selecte distinct val from tablea join tableb using (val)