On Monday, July 8, 2013, Robert James wrote:
On 7/8/13, hubert depesz lubaczewski <depesz@xxxxxxxxxx> 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@xxxxxxxxxxxxxx)
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)
