65.9K
CodeProject 正在变化。 阅读更多。
Home

PL/SQL 中逐行比较 CLOB

Manuel Vidigal
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.60/5 (4投票s)

2011 年 4 月 6 日

BSD

4分钟阅读

viewsIcon

38658

downloadIcon

516

一个在 PL/SQL 中实现的 Longest Common Subsequence (LCS) diff 算法。

引言

我编写这个包是为了能够用 PL/SQL 代码进行比较，纯粹是出于兴趣。 两个包之间的更改保存为 CLOB。 但它可以用于比较任意两个 CLOB，唯一的限制是最大行长度 (4000)。

它基于此处描述的朴素 Longest Common Subsequence 算法

从上面的链接中，我们可以看到，对于长度分别为 *m* 和 *n* 的两个序列 *X* 和 *Y*，这两个序列的最长公共子序列定义为

计算 LCS 矩阵 (M) 的伪代码如下：

function LCS_MATRIX(X[1..m], Y[1..n])
    M = array(0..m, 0..n)
    for i := 0..m
       M[i,0] = 0
    for j := 0..n
       M[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                M[i,j] := C[i-1,j-1] + 1
            else:
                M[i,j] := max(M[i,j-1], M[i-1,j])

基于 LCS 矩阵，我们可以用以下伪代码计算两个序列之间的差异

function printDiff(M[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i > 0 and j > 0 and X[i] = Y[j]
        printDiff(M, X, Y, i-1, j-1)
        print "  " + X[i]
    else
        if j > 0 and (i = 0 or M[i,j-1] ≥ M[i-1,j])
            printDiff(M, X, Y, i, j-1)
            print "+ " + Y[j]
        else if i > 0 and (j = 0 or M[i,j-1] < M[i-1,j])
            printDiff(M, X, Y, i-1, j)
            print "- " + X[i]
        else
            print ""

我这篇文章的目标是在 PL/SQL 语言中实现上面的伪代码，其中序列 X 和 Y 由两个 CLOB 的行定义。

算法实现的工作原理

在该算法的第一步，CLOB 被转换为数组，其中 CLOB 的每一行都映射到数组的每个记录中。 这是在函数 clob_to_array 中完成的，它返回一个 varchar2 数组。

实现此算法的主要困难之一是 PL/SQL 对多维数组不友好。 虽然在其他语言中创建 m *x* n 数组非常容易，但在 PL/SQL 中，这有点复杂。 感谢 Oracle 论坛的 Solomon Yakobson 教我如何做到这一点

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();

FOR i IN 1 .. m + 1
LOOP
  matrix.extend;
  matrix(i) := t_number_array();
  FOR j IN 1 .. n + 1
  LOOP
    matrix(i).extend;
  END LOOP;
END LOOP;

请注意，在 PL/SQL 中，数组从值 1 开始，因此为了能够拥有一个维度为 [0..m,0..n] 的矩阵，我使用的矩阵由 [1..m+1,1..n+1] 定义。

在获得旧文件和新文件数组并初始化 LCS 矩阵后，我们可以开始填充它。 以下过程描述了使用的逻辑

FOR i IN 1 .. m + 1
LOOP
  FOR j IN 1 .. n + 1
  LOOP
    IF old_array(i - 1) = new_array(j - 1) THEN
      matrix(i)(j) := matrix_i(i - 1) (j - 1) + 1;
    ELSE
      matrix(i)(j) := greatest(matrix(i) (j - 1), matrix(i - 1) (j));
    END IF;
  END LOOP;
END LOOP;

我希望逐行显示差异，而不是像 Introduction 中描述的那样只显示一个包含添加和删除行的简单输出。 所以我的主要输出是一个数组 t_differences_array，它并排显示旧行和新行。

CREATE OR REPLACE TYPE t_differences AS OBJECT
(
  old_line_number NUMBER,
  old_file        VARCHAR2(4000),
  status          VARCHAR2(20),
  new_line_number NUMBER,
  new_file        VARCHAR2(4000)
);
CREATE OR REPLACE TYPE t_differences_array as table of t_differences;

例如，给定文件 *OLD_FILE{A,D,E,B}* 和 *NEW_FILE{A,C,B}*，标准算法将像这样显示差异

example1.jpg

而我想要达到的目标是不添加不必要的额外行，这意味着将输出更改为

example2.jpg

这个目标是通过向 get_differences 过程添加额外逻辑来实现的。 主要是通过保存差异开始的行，然后从这个保存的行开始填充另一侧的差异，直到下一行相等。

如果不同的行数不匹配，我们将有一侧显示一个空白行号。 这也有助于区分现有空白行和不存在的行之间的差异。

以下代码优化包含在该算法中

  • 减少问题集：由于在现实生活中，我们通常比较修改很小的文件，如果我们在不改变行的文件的开头和结尾处不考虑，则可以大大减少 LCS 矩阵。
  • 减少比较时间：当行太大时，我们可以通过散列行并仅比较散列值来减少比较时间。

由于减少的问题集优化，实际代码具有三个额外的参数，分别定义了差异开始的第一行和差异停止的两个结束行。 这两个参数使代码更难理解。

使用代码

它包括两个主要的比较函数

FUNCTION compare_line_by_line(old_file_i IN CLOB,
                              new_file_i IN CLOB) RETURN t_differences_array

FUNCTION compare_line_by_line_refcursor(old_file_i IN CLOB,
                                        new_file_i IN CLOB) RETURN SYS_REFCURSOR

唯一的区别是输出类型。

我包含了一个测试表 compare_file_test，因此您可以轻松地针对两个不同的测试用例测试该程序。

在下面，您可以看到一个如何使用测试表来比较两个文件的示例

WITH t AS
 (SELECT *
    FROM compare_file_test
   WHERE id = 1)
SELECT a.*
  FROM t,
       TABLE(clob_compare.compare_line_by_line(t.old_file, t.new_file)) a

clob_compare.jpg

仍然缺少什么

我计划在未来的版本中包含一些额外的选项

  • 仅显示不同的行
  • 忽略大小写
  • 忽略空格
  • 修剪行

最后的说明

我只针对几个测试用例测试了我的实现，可能仍然存在一些错误。

我感谢您的建议/意见，以改进和优化代码。

历史

  • 版本 1.0: 2011/04/05.
© . All rights reserved.