Skip to Main Content

Deutsche

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Please ask technical questions in the appropriate category. Thank you!

Optimize LCS algorithim written in PL/SQL

3249714Dec 27 2018 — edited Jan 24 2019

Hello Community,

I have currently developed a LCS(Longest Common Subsequence) function using a two-dimensional table type. There are two for loop ,one outer one inner, running each time to insert into 2D table type. I do get the correct length of LCS for two strings. But the biggest challenge here is speed. I have two tables, one with 13 lakh records and another with 28 thousand resords. My requirement is to get LCS between each of the records of table one and two. Can you please suggest how can I optimize this function? Is there any other way I can get the same result faster.

    declare

     TYPE t_number_array IS TABLE OF NUMBER;

    TYPE t_bidimensional_number_array IS TABLE OF t_number_array;

    matrix t_bidimensional_number_array := t_bidimensional_number_array();

BEGIN

BEGIN

    len1 := length(str1);

    len2 := length(str2);

    FOR i IN 1..(len2+1)

    LOOP

      matrix.EXTEND;

      matrix(i) := t_number_array(0);

      FOR j IN 1..(len1+1)

      LOOP

        matrix(i).EXTEND;

        matrix(1)(j) := 0;

      END LOOP;

    END LOOP;

    FOR i IN 2..(len2+1)

    LOOP

      ch1 := SUBSTR(str2,i-1,1);

      FOR j IN 2..(len1+1)

      LOOP

        ch2 := SUBSTR(str1,j-1,1);

        IF ch1 = ch2 THEN

          matrix(i)(j) := matrix(i - 1)(j - 1) + 1;

        ELSE

          matrix(i)(j) := greatest(matrix(i)(j - 1),matrix(i - 1)(j));

        END IF;

      END LOOP;

    END LOOP;

   

    lcs_Dist := matrix(len2+1)(len1+1);

END;

Comments
Post Details
Added on Dec 27 2018
1 comment
367 views