« 第7回Wikiばな〜Wikiの起源へ〜@日本オラクル青山センター | トップページ | PL/SQL で Python Challenge Level 18 解けた »

2009年8月31日 (月) / Author : Hiroshi Sekiguchi.

PL/SQL de O(ND) Difference Algorithm

かなり久々ですが、まあ、シリーズもののネタを毎日アップするのもなかなか難しい状況なので単発ネタでも。

ということで今回は、PL/SQLでAn O(ND) Difference Algorithmを実装して頭の体操。

文書比較のアルゴリズムとしてはAn O(NP) Sequence Comparison Algorithmが効率は良いのだが、先日javascriptで書かれたO(ND)のコードを見つけたことをキッカケにPL/SQLで写経したくなったというわけ。

文書比較アルゴリズムは2、3年くらい前、文書比較アブゴリズムdiff(1)/diff(2)/diff(3)等をみたことがあったが、最近pyhthonやらjavascriptのコードを目にするようになり (^^) な顔して眺めていて時間があったらPL/SQLで遊んでみようと思っていた。。他の言語でやってもMac De Oracle的にはおもしろくないので。

ちなみに、pythonだどdifflib使えば文書比較はできるので実際新たに書く必要はそんなにないんじゃなかろうかとも思うわけですが、私のようにわざわざPL/SQLで書いてみようと思う人間もいるわけで、頭の体操にはいいと思います!。理解するのは大変だったけど。wwww

最近見つけたO(ND)やO(NP)に関するブログ等のリンクは以下。

レコメンデーションとエディットグラフ
diff O(np) javascript implementation
"An O(NP) Sequence Comparison Algorithm" with Python
"An O(NP) Sequence Comparison Algorithm" with Python の添削
Javascriptでdiffる ( with 形態素解析 )
google-diff-match-patch


今回はレコメンデーションとエディットグラフにあるO(ND)コードを写経してPL/SQLでやってみた。O(NP)も集中できる時間があったらやってみたい。。。脳トレにも丁度いいかもよ。。。
※Oracle11g 11.1.0.7.0を使ったが、Oracle10g 10.1.0.3.0以上なら動作するはず。。。。(^^;;;

まずは、結果からどうぞ。O(ND)をPL/SQLストアドファンクション化し、SQLから実行できるようにしてあります。また、pythonのdifflibにあるdifferクラスで利用されている差異コード('?'を除く)を出力するようにしてあります。)

SCOTT> set timi on
SCOTT> l
1 SELECT
2 '"' || diffs.code || diffs.string || '"' AS "diff O(ND) results"
3 FROM
4 TABLE(
5 SELECT diffOND('BFEABD', 'ABCDA') from dual
6 ) diffs
7 ORDER BY
8* diffs.seq DESC
SCOTT> /

diff O(ND) results
--------------------------------------------------------------------------------
"- B"
"- F"
"- E"
" A"
" B"
"+ C"
" D"
"+ A"

8行が選択されました。

経過: 00:00:00.00

SCOTT>
SCOTT> l
1 SELECT
2 '"' || diffs.code || diffs.string || '"' AS "diff O(ND) results"
3 FROM
4 TABLE(
5 SELECT diffOND('aaebdd ', 'aedajkd') from dual
6 ) diffs
7 ORDER BY
8* diffs.seq DESC
SCOTT> /

diff O(ND) results
--------------------------------------------------------------------------------
" a"
"- a"
" e"
"- b"
" d"
"+ a"
"+ j"
"+ k"
" d"
"- "

10行が選択されました。

経過: 00:00:00.00

SCOTT>
SCOTT> l
1 SELECT
2 '"' || diffs.code || diffs.string || '"' AS "diff O(ND) results"
3 FROM
4 TABLE(
5 SELECT diffOND('ABCDE', 'ABCDE') from dual
6 ) diffs
7 ORDER BY
8* diffs.seq DESC
SCOTT> /

diff O(ND) results
--------------------------------------------------------------------------------
" A"
" B"
" C"
" D"
" E"

経過: 00:00:00.00

SCOTT>
SCOTT> l
1 SELECT
2 '"' || diffs.code || diffs.string || '"' AS "diff O(ND) results"
3 FROM
4 TABLE(
5 SELECT diffOND('あいうえお','かきくけこ') from dual
6 ) diffs
7 ORDER BY
8* diffs.seq DESC
SCOTT> /

diff O(ND) results
--------------------------------------------------------------------------------
"- あ"
"- い"
"- う"
"- え"
"- お"
"+ か"
"+ き"
"+ く"
"+ け"
"+ こ"

10行が選択されました。

経過: 00:00:00.00

SCOTT>

PL/SQLのコードは以下の通り。

SCOTT> !cat ond.sql

CREATE OR REPLACE TYPE vRecType AS OBJECT
(
x NUMBER
,y NUMBER
,parent ANYDATA
);
/
show errors

BEGIN
FOR functionNames
IN (SELECT object_name FROM USER_OBJECTS WHERE object_name='DIFFOND' AND OBJECT_TYPE='FUNCTION')
LOOP
EXECUTE IMMEDIATE 'DROP FUNCTION ' || functionNames.object_name;
END LOOP;

FOR typeNames
IN (SELECT type_name FROM USER_TYPES WHERE type_name='DIFFLISTTYPE')
LOOP
EXECUTE IMMEDIATE 'DROP TYPE ' || typeNames.type_name;
END LOOP;
END;
/

CREATE OR REPLACE TYPE diffType AS OBJECT
(
seq NUMBER
,code CHAR(2)
,string VARCHAR2(32767)
);
/
show errors

CREATE OR REPLACE TYPE diffListType AS TABLE OF diffType;
/
show errors

CREATE FUNCTION diffOND
(
str1 IN VARCHAR2
,str2 IN VARCHAR2
)
RETURN diffListType
IS
STAT_INIT CONSTANT PLS_INTEGER := 0;
STAT_X CONSTANT PLS_INTEGER := 1;
STAT_Y CONSTANT PLS_INTEGER := 2;

TYPE vType IS TABLE OF vRecType;
v vType := vType();

FUNCTION isVRecNotEmpty(
vRec IN vRecType
)
RETURN BOOLEAN
IS
BEGIN
RETURN (CASE WHEN vRec.x IS NULL AND vRec.y IS NULL AND vRec.parent IS NULL THEN FALSE ELSE TRUE END);
END isVRecNotEmpty;

FUNCTION getDirection
(
vMinus IN vRecType
,vPlus IN vRecType
)
RETURN PLS_INTEGER
IS
BEGIN
IF NOT isVRecNotEmpty(vMinus) AND NOT isVRecNotEmpty(vPlus) THEN
RETURN STAT_INIT;
END IF;

IF NOT isVRecNotEmpty(vMinus) THEN
RETURN STAT_X;
END IF;

IF NOT isVRecNotEmpty(vPlus) THEN
RETURN STAT_Y;
END IF;

RETURN (CASE WHEN vMinus.x < vPlus.x THEN STAT_X ELSE STAT_Y END);
END getDirection;

FUNCTION OND
(
str1 IN VARCHAR2
,str2 IN VARCHAR2
)
RETURN vRecType
IS
offset PLS_INTEGER;
kMax PLS_INTEGER;
kMin PLS_INTEGER;
k PLS_INTEGER;
vIndex PLS_INTEGER;
x PLS_INTEGER;
y PLS_INTEGER;
str1Len PLS_INTEGER;
str2Len PLS_INTEGER;
parent vRecType;
BEGIN
str1Len := LENGTH(str1);
str2Len := LENGTH(str2);
v.EXTEND(str1Len + str2Len + 3);
offset:= str2Len + 2;

FOR d IN 0..str1Len + str2Len LOOP
kMax := (CASE WHEN d <= str1Len THEN d ELSE str1Len - (d - str1Len) END);
kMin := (CASE WHEN d <= str2Len THEN d ELSE str2Len - (d - str2Len) END);

k := kMin * -1;
WHILE k <= kMax LOOP
vIndex := offset + k;
CASE getDirection(v(vIndex-1), v(vIndex+1))
WHEN STAT_INIT THEN
x := 0;
y := 0;
parent := vRecType(0, 0, NULL);
WHEN STAT_X THEN
x := v(vIndex+1).x;
y := v(vIndex+1).y + 1;
parent := v(vIndex+1);
WHEN STAT_Y THEN
x := v(vIndex-1).x + 1;
y := v(vIndex-1).y;
parent := v(vIndex-1);
END CASE;

-- snake
WHILE (x < str1Len AND y < str2Len)
AND (SUBSTR(str1, x+1, 1) = SUBSTR(str2, y+1, 1))
LOOP
x := x + 1;
y := y + 1;
END LOOP;
v(vIndex) := vRecType(x, y, ANYDATA.ConvertObject(parent));

IF str1Len <= x AND str2Len <= y THEN
RETURN v(vIndex);
END IF;

k := k + 2;
END LOOP;
END LOOP;
END OND;

FUNCTION diff
(
str1 IN VARCHAR2
,str2 IN VARCHAR2
)
RETURN diffListType
IS
endPoint vRecType;
parent vRecType;
diff_x PLS_INTEGER;
diff_y PLS_INTEGER;
same_len PLS_INTEGER;
isSuccessGetObject PLS_INTEGER;
diffs diffListType := diffListType();
seq PLS_INTEGER := 0;
BEGIN
endPoint := OND(str1, str2);
WHILE endPoint.parent IS NOT NULL LOOP
IF ANYDATA.getObject(endPoint.parent, parent) != DBMS_TYPES.SUCCESS THEN
RAISE_APPLICATION_ERROR(-20000,'DBMS_TYPES.NO_DATA');
END IF;

diff_x := endPoint.x - parent.x;
diff_y := endPoint.y - parent.y;
same_len := CASE WHEN diff_x <= diff_y THEN diff_x ELSE diff_y END;

FOR i IN 0..same_len-1 LOOP
-- common
diffs.EXTEND();
seq := seq + 1;
diffs(diffs.COUNT()) := diffType(seq, ' ', SUBSTR(str1, endPoint.x-i, 1));
END LOOP;

IF diff_y != diff_x THEN
diffs.EXTEND();
seq := seq + 1;
IF diff_y < diff_x THEN
-- del
diffs(diffs.COUNT()) := diffType(seq, '- ', SUBSTR(str1, parent.x+1, 1));
ELSE
-- add
diffs(diffs.COUNT()) := diffType(seq, '+ ', SUBSTR(str2, parent.y+1, 1));
END IF;
END IF;

endPoint := parent;
END LOOP;

RETURN diffs;
END diff;
BEGIN
RETURN diff(str1, str2);
END diffOND;
/
show errors

Enjoy PL/SQL! というより Enjoy Programming! のほうがいいか。。

| |

トラックバック


この記事へのトラックバック一覧です: PL/SQL de O(ND) Difference Algorithm:

コメント

コメントを書く