Re: Longest Common Subsequence in Postgres - Algorithm Challenge

From: Misa Simic <misa(dot)simic(at)gmail(dot)com>
To: Robert James <srobertjames(at)gmail(dot)com>
Cc: "depesz(at)depesz(dot)com" <depesz(at)depesz(dot)com>, Postgres General <pgsql-general(at)postgresql(dot)org>
Subject: Re: Longest Common Subsequence in Postgres - Algorithm Challenge
Date: 2013-07-09 08:15:45
Message-ID: CAH3i69=hggCce1Xpby9=2goL148bJb=udY=O-jD0wW8yzT7uOw@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

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)

In response to

Browse pgsql-general by date

  From Date Subject
Next Message Andreas Joseph Krogh 2013-07-09 08:45:34 Re: Why is NULL = unbounded for rangetypes?
Previous Message Darren Duncan 2013-07-09 08:08:44 Re: Longest Common Subsequence in Postgres - Algorithm Challenge