Re: Longest Common Subsequence in Postgres - Algorithm Challenge

Поиск
Список
Период
Сортировка
От Robert James
Тема Re: Longest Common Subsequence in Postgres - Algorithm Challenge
Дата
Msg-id CAGYyBgh+0xcKapNm-mG2TdM2eAMuG4O5rGkAyebkO_qrd7uiRQ@mail.gmail.com
обсуждение исходный текст
Ответ на Re: Longest Common Subsequence in Postgres - Algorithm Challenge  (hubert depesz lubaczewski <depesz@depesz.com>)
Ответы Re: Longest Common Subsequence in Postgres - Algorithm Challenge  (Michael Paquier <michael.paquier@gmail.com>)
Re: Longest Common Subsequence in Postgres - Algorithm Challenge  (Darren Duncan <darren@darrenduncan.net>)
Re: Longest Common Subsequence in Postgres - Algorithm Challenge  (Misa Simic <misa.simic@gmail.com>)
Список pgsql-general
On 7/8/13, hubert depesz lubaczewski <depesz@depesz.com> 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


В списке pgsql-general по дате отправления:

Предыдущее
От: Moshe Jacobson
Дата:
Сообщение: Dynamically accessing record elements using EXECUTE
Следующее
От: "Daniel Serodio (lists)"
Дата:
Сообщение: Re: replication stops working