Oracle 最长公共子串-Ratcliff-Obershelp相似性算法

嗨，汤姆，

有没有办法让我的代码更快？
我正在尝试使用动态编程找到最长的公共子字符串 (short: lcs); 在这方面，我正在构建一个具有x行和Y列的2D数组，其中X-string1的长度，Y = string2的长度。
首先，我用0初始化数组; (这可以避免吗？)
然后，我从左上角开始，一次一个字符 (来自字符串1)，每次与string2中的字符匹配时，我将1放入该单元格
这是一个视觉描述:

https://imgur.com/a/gz8JTms

我已经在使用PL/SQL本机编译。

遵循这个lcs函数，我正在使用Ratcliff-Obershelp相似性算法和我真的被卡在如何迭代地构建一个函数，将使用这个 “lcs” 函数; 任何帮助将不胜感激。

谢谢!

我不熟悉Ratcliff-Obershelp相似算法，但这里有一些想法:

First, i initialize the array with 0; (can this be avoided ?)

是的。您可以在开始时剪切循环以初始化矩阵。

在循环中测试长度，如果两个索引变量都不是1 (i = 1或j = 1的else分支)，则获取先前的索引值 (如果存在)。否则将当前位置设置为一。

这看起来像这样:

if p_matrix.exists ( i-1 ) and p_matrix ( i-1 ).exists ( j-1 ) then
  p_matrix ( i )( j ) := p_matrix ( i-1 )( j-1 ) + 1; 
else 
  p_matrix ( i )( j ) := 1;
end if;

您应该能够构建逻辑以更早地突破循环。如果到目前为止找到的剩余字符串的当前位置长度 <= 最大长度，则其余字符的字符串不能比您已经找到的字符串长。所以你可以在这一点上退出循环。

确切地说，这节省了多少取决于输入字符串。最坏的情况是没有匹配的字符，所以你仍然循环通过两个元素的O (n * m) 运行时。

您可以通过检查循环之前至少有一些匹配的字符来短路。

一种方法是使用translate。将输入字符串作为前两个参数传递，将越界字符作为第三个 (例如 #)。替换结果中的这个越界字符。

select 
  translate ( 'WIKIMEDIA', 'REMEDYA', '#' ) tr1,
  replace ( translate ('WIKIMEDIA', 'REMEDYA', '#'), '#' ) reptr1,
  translate ( 'WIKIMEDIA', 'NOSUB', '#' ) tr2,
  replace ( translate ('WIKIMEDIA', 'NOSUB', '#' ), '#' ) reptr2
from dual;

TR1     REPTR1   TR2         REPTR2      
WIKII   WIKII    WIKIMEDIA   WIKIMEDIA   

如果最终字符串的长度等于第一个输入的长度，则知道没有匹配的字符。所以可以完全绕过循环。

我敢肯定还有其他优化; 其他人可能有一些可以帮助的想法。