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: | Whole Thread | Raw Message | 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)
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 |