没有必胜的秘籍，没有方程式遵循~~ 要赢~~只有全身心的投入！

晶晶小妹实验二十　hash算法在字符串搜索中的另类使用

上一篇 / 下一篇 2008-03-18 01:38:36 / 个人分类：晶晶oracle实验系列

查看( 440 ) / 评论( 33 )

看到一网友的问题，如下：

表t1中有两个字段NO(NUMBER类型),ST(VARCHAR2类型)
表中有如下值
NO          ST
1       'A1A3BCLKMBNK'
2       'A2A4MBKLDMSK'

注：ST字段中的值长度都是2的整数倍;

有一变量V_E,变量值为'A3MLLKNKDS'

现在将t1表中的ST字符与变量V_E进行比较，比较的方法如下：
V_E变量中每两个字符为一个基本单位，ST字段也是以两个字符为一个基本单位，让V_E与ST字段进行比较，得出ST中与V_E基本单位相同的数量

即：
t1表中的值可以看做
NO          ST

1       'A1  A3  BC  LK  MB  NK'
2       'A2  A4  MB  KL  DM  SK'
---------------------------------------------
变量V_E可以看做
V_E  -->  'A3 ML LK NK DS'
---------------------------------------------

比较之后得出：

NO          ST                      相同值    相同数量
1       'A1A3BCLKMBNK'    A3 LK NK       3
2       'A2A4MBKLDMSK'                         0

使用递归或者循环匹配方式效率太低，希望各路高人能有更好的方法

－－－－－－－－－－－－－完－－－－－－－－－－－－－－－－－－－－

根据网友的要求，使用循环进行匹配的效率的确不高，如果使用HASH算法，效率应该不错。
下面设计一个例子，请大家讨论：

因为每两个字符为一基本单位，而ASCII码最多也只有256个，因此，以第每个ASCII的数字值为HASH值，设定两个HASH表，如，V_E的HASH表状态为：

HASH1[65]='1'  HASH2[51]='1'
HASH1[77]='1'  HASH2[76]='1'
HASH1[76]='1'  HASH2[75]='1'
HASH1[78]='1'  HASH2[75]='1'
HASH1[68]='1'  HASH2[83]='1'

HASH1和HASH2分别是包含256个元素的数组，当做HASH表使用，上面所赋的值可以是任意字符，其余的值可以定为和它不同的其他字符。

现在开始搜索第1行'A1  A3  BC  LK  MB  NK'， A 1的ASCII码分别为65、49，只需比较HASH1[65]和HASH[49]的值是否为1，即可判断A1是否包含在V_E中。

使用这种算法，
为HASH表赋初值：单循环，256次，只需在程序开始时执行一次
向HASH表填入V_E信息：单循环，循环次数随V_E长度而定
在表的某一行ST列中搜索字符串：单循环，循环次数随ST列长度而定
在HASH表中抺去V_E信息：单循环，循环次数随V_E长度而定（我的例子中没包括此段）

本来为N*M的双重循环，变为了三个单循环，在算法上简单了许多。例子程序如下：

建立测试表：
create table itpub1(no number, st varchar(200));
insert into itpub1 values(1,'A1A3BCLKMBNK');
insert into itpub1 values(2,'LKMBNKA1A3BC');
insert into itpub1 values(3,'A2A4MBKLDMSK');
commit;

程序如下：
declare
type marray is table of varchar2(200) index by binary_integer;
hash1 marray;
hash2 marray;
v_e varchar2(200);
cursor it1 is select * from itpub1;
v_e_len number(5);
st_len number(5);
j number(5):=1;
begin
---------为HASH表赋初值----------
for i in 1..256 loop
   hash1(i):=chr(7);
   hash2(i):=chr(7);
end loop;
----------结束----------

v_e:='A3MLLKNKDS';
v_e_len:=length(v_e);

-------向HASH表中填入v_e的信息--------
while j<=v_e_len loop
   hash1(ascii(substr(v_e,j,1))):='1';
   hash2(ascii(substr(v_e,j+1,1))):='1';
   j:=j+2;
end loop;
-------结束--------

for cur in it1 loop
   dbms_output.put(rpad(cur.no,5,' ')||rpad(cur.st,40,' '));
   j:=1;
   st_len:=length(cur.st);

-------根据HASH表进行匹配--------
   while j<=st_len loop
      if hash1(ascii(substr(cur.st,j,1)))='1' and hash2(ascii(substr(cur.st,j+1,1)))='1' then
         dbms_output.put(substr(cur.st,j,2)||' ');
      end if;
      j:=j+2;
   end loop;
-------结束--------

   dbms_output.put_line(' ');
end loop;
end;
/

以下是执行结果：
sid=14 pid=12> @itpub1
1 A1A3BCLKMBNK                         A3 LK NK
1 LKMBNKA1A3BC                         LK NK A3
3 A2A4MBKLDMSK

全部脚印 不留脚印留下脚印:

论坛模式推荐收藏分享给好友推荐到圈子管理

TAG:

netbanker 发布于2008-03-18 04:44:04: sofa

cyt2005发布于2008-03-18 09:15:10: 很执着很勤奋哈~

fly_bug 发布于2008-03-18 09:25:24: 小妹，oracle在data buffer cache中查找数据块也是使用hash算法，那么具体是以什么做为HASH值？

Alienovo 发布于2008-03-18 09:27:14: 每早都能看到晶晶的文章

zuohao_lu 发布于2008-03-18 09:30:09: 晶晶强人.
'~$h!L%fAspace.itpub.net支持.

晶晶小妹发布于2008-03-18 09:30:23: QUOTE:
原帖由 fly_bug 于 2008-3-18 09:25 发表 x7Xq I1q.n
小妹，oracle在data buffer cache中查找数据块也是使用hash算法，那么具体是以什么做为HASH值？
E~i/B8f$gUMspace.itpub.net
#~~+@0T-E'x'R&\TA是以块的文件号、块号（好像还有对象号）为基础，用Oracle的内部HASH函数，生成一个HASH值。

BTxigua 发布于2008-03-18 09:37:00: QUOTE:
原帖由 netbanker 于 2008-3-18 04:44 发表
e(Q)xj1u#WuYQRsofa

2008-3-18 04:44
这个沙发代价还是蛮大的嘛

jimhou 发布于2008-03-18 09:47:40: 好文

rollingpig 发布于2008-03-18 09:52:05: 有明显漏洞哦~~~
'A3MLLKNKDS'
q)kh[9c%P4e[LITPUB个人空间
'w#J!Kup.EvH[3mAL AK AS 都符合你的程序，却不符合要求哦

rollingpig 发布于2008-03-18 09:54:48: 修改两个地方，倒是可以实现
9_/a;? ~6wspace.itpub.net-------向HASH表中填入v_e的信息--------
while j<=v_e_len loop9{"cc;j*x;r4H
   hash1(ascii(substr(v_e,j,1))):=Chr(64+j);space.itpub.net
g"X*`]:m6L[c
   hash2(ascii(substr(v_e,j+1,1))):=Chr(64+j);
eO4{K!z+e9ur^^    j:=j+2;
end loop;

D*__$OU-Weo)E(^
B5]。。。。
9W)mTp$OA({M
bJ       if hash1(ascii(substr(cur.st,j,1)))!=Chr(7) AND hash1(ascii(substr(cur.st,j,1))) =  hash2(ascii(substr(cur.st,j+1,1))) thenD`v1[h3z,v(IU
         dbms_output.put(substr(cur.st,j,2)||' ');
         NULL;
D
}-n Ku%l       end if;

louis_xu 发布于2008-03-18 10:02:13: 又是凌晨发的，小妹注意身体啊

五“宅”一生发布于2008-03-18 10:10:01: 小妹发帖子的时候我刚睡觉。得向小妹学习。

晶晶小妹发布于2008-03-18 10:49:13: QUOTE:
原帖由 rollingpig 于 2008-3-18 09:52 发表 space.itpub.net`
m-ND'g!T
有明显漏洞哦~~~(zL9zZ:{#wiln6F/i
'A3MLLKNKDS'space.itpub.net}[C,]p\z9l
ITPUB个人空间L0u'k8[j)k3lk1Z0}
AL AK AS 都符合你的程序，却不符合要求哦
space.itpub.net.H7@WmA9Ul8l&f.[
ITPUB个人空间6RB9}7l"x,f#n*AK

以下是执行结果：Bq9R$}4L.]M
sid=14 pid=12> @itpub16B
|)bXHc%N
K5{B)P
1 A1A3BCLKMBNK A3 LK NK
8X/?W%O6M1 LKMBNKA1A3BC LK NK A3~[:tz,]MFV~
3 A2A4MBKLDMSK
!H/f`+~KIOqspace.itpub.net ]^w$PF!o
space.itpub.net/__6YVq
j#wQ+^
老大，执行结果里没有AL AK AS 吖？

晶晶小妹发布于2008-03-18 10:51:35: QUOTE:
原帖由 rollingpig 于 2008-3-18 09:54 发表
fE%i$[3MH'l
?.OoC修改两个地方，倒是可以实现uc
}X+Wz@e u6]
-------向HASH表中填入v_e的信息--------
I@9T pH while j

2Z+EX \*D@*Jj:f
f7qY)Jr3GU
　好象咱俩说的不一样．0j^
]4OHg
OGq
ITPUB个人空间'~1nHri3i{
我的hash表只放一个标志，随便放一个值都行．只需要标志在这个桶处有字符或没有字符．

mengzhaoliang 发布于2008-03-18 12:50:59: 晶晶太猛了，年轻有才，很受打击！

rollingpig 发布于2008-03-18 13:02:54: insert into itpub1 values(999, 'ALAKAS')0w TFj/g8[OuC
再运行一遍

adamyang 发布于2008-03-18 14:52:15: 索引表支持字符串的KEY，可以简化一下：ITPUB个人空间.yZOMW[

(CnF&WGxdeclare
RMYlBMr)v(wspace.itpub.net type marray is table of binary_integer index by varchar2(200);
/mFa+e0R7i7p v_index marray;
w m5T
I p`+j+V` v_e varchar2(200);space.itpub.net"L]!M"~FK`2zE
cursor it1 is select * from itpub1;
N*dJ;Y9y#DJ1|b0QBITPUB个人空间 v_e_len int;
st_len int;
*urB6ka8\a,\ j int default 1;
begin
v_e:='A3MLLKNKDS';
v_e_len:=length(v_e);
|#J!~te*i
while j<=v_e_len loopspace.itpub.net1QdH@L3ot
   v_index(substr(v_e,j,2)):=null;
5[T6O]1T/m6fspace.itpub.net    j:=j+2;ITPUB个人空间,WBSy
[6w
end loop;
GG3\-q5H
\
i,e'q!e0R4] for cur in it1 loop
   dbms_output.put(rpad(cur.no,5,' ')||rpad(cur.st,40,' '));
   j:=1;space.itpub.net#Cc'[4@(G&x+H]d
   st_len:=length(cur.st);9p_w({Ko]Rp:B
   while j<=st_len loop
Jv
rhxGDy'mspace.itpub.net       if v_index.exists(substr(cur.st,j,2)) then
+z4y}{-e F3L          dbms_output.put(substr(cur.st,j,2)||' ');
U5GmvI$e8^!ospace.itpub.net       end if;
EuLV:h       j:=j+2;4M*X?1Z&@&t v
m0a
   end loop;
+jq;{ _N2`
tw*Vn[X+P*H8BH
w?/T(B    dbms_output.put_line(' ');Ee3G9[[$G6q
_A0Z
end loop;
T)l.|5D6`ikspace.itpub.netend;:oTRCA4O"s
/

wghxwl12 发布于2008-03-18 15:01:25: 首先佩服楼主的基本工
===========================================================================================ITPUB个人空间0?@'tKC\B
下面的直接处理的函数比较直观，但是可能顾及不了效率/Ku8\"q8Q$SC._?K
------------------------------------------------------------------------------------------------------------------------------------
&h@{$]N4V,Uz1VZCREATE OR REPLACE FUNCTION FUN_MATCH_CNT(P_STR VARCHAR2, P_STR2 VARCHAR2) RETURN VARCHAR2 IS
TS/g#q[X p r,Z'g V_MOTHER VARCHAR2(200);
9z#X'{ UF:MOznITPUB个人空间 V_MATCH  VARCHAR2(20);
V_LENGTH NUMBER;0U%v0eph"N
V_LENM NUMBER :=2;
V_NUM NUMBER := 0;
MlB+we2~
q
]+x V_CNT NUMBER ; space.itpub.netQ D~5}0u
            V_MATCHSTR VARCHAR2(200):=' ';ITPUB个人空间+\'E/P7P3ktn
            V_MATECHED VARCHAR2(200):=' ';
6W%c*G|Dm_  BEGIN
0E:_`#v;u@!VIITPUB个人空间       V_CNT  := 0;
2c;R/zqW V_MOTHER := P_STR;ITPUB个人空间l5`%~Y+v-ye
            --V_MATCH := P_STR2;
--将 V_MOTHER值改变成每两个字符被逗号隔开的值
r
?\{b{%Dspace.itpub.net             V_LENGTH := LENGTH(REPLACE(P_STR,',','')) / 2;;Ne0[;{P4b Wz
V_LENM := LENGTH(P_STR2) / 2;
            IF(INSTR(V_MOTHER,',')= 0 ) THEN
                     FOR X IN 1 .. (V_LENGTH - 1) LOOP,Q3S!\V?q4J%m
      V_MOTHER := SUBSTR(V_MOTHER, 1, (V_LENGTH - X) * 2) || ',' ||2x0lmId/j']
               SUBSTR(V_MOTHER, (V_LENGTH - X) * 2 + 1);space.itpub.netd;F8z9l3B^
   END LOOP;
BU:_9^-tC2C_YITPUB个人空间             END IF;ITPUB个人空间(WH1b-W7i(m
--DBMS_OUTPUT.PUT_LINE(V_MOTHER);ITPUB个人空间/T+CF3lW$_c'A
cD
--针对每个基本单位进行比较$O oi+[`
FOR Y IN 1 .. V_LENM LOOP    space.itpub.net4_%Z#M:do$e2l
               V_MATCH := SUBSTR(P_STR2, Y * 2 - 1, 2);
   SELECT SIGN(INSTR(V_MOTHER,V_MATCH ))
_7M]}}       INTO V_NUMITPUB个人空间g'u1k"b)Rf&xa
      FROM DUAL;space.itpub.netpVHSR6c
                              IF V_NUM = 1 THEN space.itpub.net}7`.J
JEyP.oK
                                    V_MATECHED := TRIM(V_MATECHED||V_MATCH);7Z(MO8t4P)S$` Gq%m
                                    SELECT SUBSTR(V_MOTHER,1,INSTR(V_MOTHER, V_MATCH)-1)||SUBSTR(V_MOTHER,INSTR(V_MOTHER, V_MATCH)+3)
|&Gs5XQv5Espace.itpub.net                                                       INTO V_MOTHER
us|;m/L[i~_.j-Sspace.itpub.net                                                       FROM DUAL;space.itpub.net
ue;^'Mol9ua:FX/P
            V_CNT := V_CNT + V_NUM; ITPUB个人空间I%GeOY!rA
                                                      --V_CNT := V_CNT + FUN_MATCH_CNT(V_MOTHER,V_MATCH);
\'U)a"Q1K(SAxf                                                       V_MATECHED := TRIM(V_MATECHED||NVL(FUN_MATCH_CNT(V_MOTHER,V_MATCH),' '));
&\%u%{e7pITPUB个人空间                         END IF;
?1PI*Hh END LOOP;

W!m,n~m\"]y6N ---DBMS_OUTPUT.PUT_LINE(V_CNT);
-- RETURN V_CNT; 2C4Cms:Fk6] j$Ju
      RETURN TRIM(V_MATECHED);
"BTV3v#r&a-~  END;
m'\o
o,q$nh6L*xITPUB个人空间
Gb0J"df jU4q bbu!k'Q7J SGbO
mkVGK6|
UP7K

eS+DR5Ow({:UwSELECT NO,ST ,fun_match_cnt(ST,'A3MLLKNKDS') AS 相同值,NVl(LENGTH(fun_match_cnt(ST,'A3MLLKNKDS')),0)/2 as 相同数量 FROM T1;ITPUB个人空间:B
GO,m.f
-------------------------------------------------------------------------------------------------------------------
NO          ST                      相同值    相同数量
-U*oUx%N p1       'A1A3BCLKMBNK'    A3LKNK       3
yxU5[l
2       'A2A4MBKLDMSK'                         0
.       ............................       ...             .
&K)L!y'` `%Qspace.itpub.net.       ............................       ...             .
+|1j;a QdHn3|;p6oe)m"q,y
[ 本帖最后由 wghxwl12 于 2008-3-18 15:08 编辑 ]

wghxwl12 发布于2008-03-18 15:04:09: 小妹应该把该贴放到开发论坛或者专题深入讨论板块

晶晶小妹发布于2008-03-18 16:21:10: QUOTE:
原帖由 rollingpig 于 2008-3-18 13:02 发表 "ta@A7A3i3ma-zg&[
insert into itpub1 values(999, 'ALAKAS').Bc!L9`\4Z%k
再运行一遍

0N@+x/Fj
6E*oRJ?kC,f@KD
Y@.?l8}(v

YS a2u-XITPUB个人空间

~)o
@fP}B7EUtITPUB个人空间T)yE#|.g$`"Li P
经过老大的修改果然ＯＫ！

feng_xin 发布于2008-03-18 18:19:29: 晶晶小妹真勤奋呀

louis5421发布于2008-03-18 20:17:35: QUOTE:
原帖由 adamyang 于 2008-3-18 14:52 发表 :i7f3j0J(n,A
索引表支持字符串的KEY，可以简化一下：
FDF"_;}`#_kblspace.itpub.net
6M ET`N#eITPUB个人空间declare
0MZ&o!t'N;d+q type marray is table of binary_integer index by varchar2(200);
N2ecax%u6Q6Mn
jITPUB个人空间 v_index marray;+d.h&bIRsD6M
v_e varchar2(200);
cursor it1 is select * from itpub1;
Rq
zW:dE v_e_len int;
st_len int;#z&^%|KhS
j int default 1;hu-xB|sJ/?h;AMn
begin
t8R@6u)}
v_e:='A3MLLKNKDS';P,x&DN}i
v_e_len:=length(v_e);
5pd,}ibxITPUB个人空间?
?Zv)Z
while j
ITPUB个人空间:iI%].z'R([X

这个不错，不过第二句写错了。

adamyang 发布于2008-03-19 09:44:27: QUOTE:
原帖由 louis5421 于 2008-3-18 20:17 发表 space.itpub.net8\
Y7`}0j&TP%H"U.A
ITPUB个人空间_%c!SB1G

0AHE0N'TJh这个不错，不过第二句写错了。
?%z
k6s2v L

6J*a-FP sBI朋友仔细看，我只是换了个变量名，没有错的。
VC&q&\!YT(AuITPUB个人空间IRw~{@.^er
另外，楼主，oracle索引表结构不是HASH，应该是类似BTREE的结构，呵呵。

晶晶小妹发布于2008-03-19 10:28:15: 我有说索引是hash结构吗？

adamyang 发布于2008-03-19 10:34:06: QUOTE:
原帖由 晶晶小妹 于 2008-3-19 10:28 发表 ITPUB个人空间6ACzD/~/A9H
我有说索引是hash结构吗？
ITPUB个人空间MF?!Y|+a1r
space.itpub.net(]X?,ii,xr
呵呵，你定义的类型命名为HASH，让我误以为你在把索引表和HASH混淆。

晶晶小妹发布于2008-03-19 10:41:37

blue_prince 发布于2008-03-19 11:11:49: 勤快的孩子

d.c.b.a 发布于2008-03-19 11:18:47: 高深，看不懂

晶晶小妹发布于2008-03-19 11:25:44: QUOTE:
原帖由 d.c.b.a 于 2008-3-19 11:18 发表 ITPUB个人空间c2q0|1C!Z
高深，看不懂
m6k8PP&{ITPUB个人空间 ITPUB个人空间zU6LP9R!t2f\

([!am4M
K3\d%hnM 　　损我呢不是