Though people talk about doing this in other languages, I think you can solve it
in plain SQL if you wanted to.
For one thing, you could start off using unordered set operations to make the
problem space smaller, such as using set intersection to see what the common
subSETs of values there are from each of the sequences, which SQL does quickly
and easily, and then you can eliminate any subsequences from the original whose
set of values don't match one of these common subsets, and only those would you
then have to compare for order.
-- Darren Duncan
On 2013.07.08 1:04 PM, 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
