Dnia 9 lip 2013 o godz. 00:46 Michael Paquier <michael.paquier@xxxxxxxxx> napisał(a): > On Tue, Jul 9, 2013 at 5:04 AM, Robert James <srobertjames@xxxxxxxxx> 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 > Your best bet on that would be to implement using either a procedural > language (plpython, plperl that are in core, or even another one), or > a C function and install it on server side with an extension. I'll do > the latter if I were you. Roughly such a function would take in > arguments the OIDs of the functions to compare (or their relation > name), and return a set of rows describing the longest sequence found. > Also if you only need the length of lcs, you can derive it using the built in levenshtein with costs function -- Sent via pgsql-general mailing list (pgsql-general@xxxxxxxxxxxxxx) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
