Skip to main content

Full text of "USPTO Patents Application 10670332"

See other formats


esp@ceTiet docmnent view 



Page 1 of 2 



METHOD AMD FOR S£ARCHII^0 Fpt STiXN^S 



PSibffcBtion numbaf! JP2006519445T 
S»ubticaKon date: 2006-08-24 
Inventor; 



-Earopeaft: G08F17/30P2 

Appfi«3ti«>R ftymban JP2Q06050S64 IT 20040225 

Priority nttmber($)! EP20030100517 20030303; WO2004 18601 48 20040225 



WO'>0040?9531 {A3) 
VVO20a4079e31 (A2) 
US20061 79052 (A1) 
KR20060002792 {A) 
CN1 761958 (A) 



R-sjsssrt a ^sJ^ks 



Abstract not avaiiabie for .JP2006519445T 
Abstract of corresponding document; WO200407dS31 
This inventfon relates to methods of searching for 
a final number of result strings (30-33) having a 
partia! or an exact match witJ\ a query string (34) 
in a database (80) comprised of many long 
strings or a long stjing , said methoti meludes the 
steps of partitioning the query string in a first 
number of input query strings (35. 36, 37); 
deienDlning a second niimber of neightjoring 
strings (33-41 , 42-45. 44-'''9, respectively) for 
each string in said firs;; number- of input query 
strings, wherein eacri string in said second 
number of neighboring sir ^ngs ha^ a 
predetermined firsi number o; en'ors; seof-ching 
the database for a third number of ex;r:ci rnrirches 
(50-61, 70-74) for each su:i;g iri said second 
number of neighboring stririgs based on a search 
method; concatenating said searched exact 
matched strings from The database into a fourth 
number of intermediate strings (29, 30, 32, 33, 
34) wherein said searched exact matched strings 
(50-61 , 70-74) comprised m eadi of said 
intermediate strings are in succession to one 
another in said database; and determinins the 
fsnsi nun-iber of result strings (30-33) based in 
said fourth number of intem^ediate strings, 
wherein each stririg in the finai number of result 
strings lias a maximum of predeteiiivne.J second 
number of errors compared to saic ui.iei > sttiog 
(34). Tiiis enables for a perfect match or a partia! 
matcii containing only minor errors With respect 
to said query string, and for a fast ssarr;h sn 
iarger databases with a relative iow use of 
processing power. 




Data supplied from the esp@ce(iet database - Woridvv-fde 



http://v3xspacenetxoin,'textdoc?DB-BiWG<^&IDX-JP2006519445T&F=0 



immm 



HP 2006-519445 A 2006.8.24 



(19)B*BI«»B=(JP) (I2)ia H *l 1^ 4i S(A) (iDltfFtfiliSIIS^ 

!^a2006-519445 
(P2006-519445A) 
(43) 2fS B ¥I«18#8H24B (2006. 8. 24) 



(51) Int. CI. Fl (#^) 

G06F 17/30 0)08.01) G0 6F 17/30 35 OC 5B075 



(21) tamm^ 


^112006-506641 (P2006-506641) 


(71) JBliA 


590000248 


(86) (22) iUME 


¥e!cl6¥2H25B (2004. 2.25) 






(85)^iK^iiffiB 


¥m7¥9^ IB (2005.9.1) 






(86)B^tfill#^ 


PCT71B2004/050148 




Koninklijke Philips 


(87) B^aiflS^ 


W02004/079631 




Electronics N. V. 


(87)B^^&liB 


¥^6^9^163 (2004. 9.16) 




^y>^m 56 2 1 ^-T- 


(31)ffi5tffi±5gS^ 


03100517.6 






(32)ffi5tB 


¥)|1£15¥3^ 33(2003.3.3) 




1 


(33)fE5t«±Sgll 






Groenewoudseweg 1, 5 








62 1 BA E i ndhoven, T 








he Netherlands 








100070150 
















100091214 



















(54) 5!:¥?il«l5R0:55S*jj:i;ts« 



(57) mm] 

Sl^3^WJ^W-r^r"^?-^-7. (8 0) cpfCisW^, 

mi^^t)-ii^^n (3 4) isu^-i^sfca^^-i^T 
i>p^m^i^-^&i>mi^mj:mmcDi^^ic?m 00-3 
3) ;&^^-r^:WiKMT€.feo-cs,s„ m 

?ij ( 3 5 , 3 6. 3 7 ) icmw. m$im-(Dmm(DA 

rcDffii^©iai?is:^?ij (3 8-4 K 42-45. 44 
-4 9) im.b. ccv. mtm-(Dmm(D-Am^^ 

tio^^-^mm-r^^^-^-^'^m (50-61. 70 

-7 4) ^SM^^jffi{cS-:3'lvr. ^SUZOfil^ 

§ n ^ -gc ^ -3 i& r ifc S ^0 © « CD 4J FbI 
^?|J(29. 30. 32. 3 3. 34)fCL. CCV 

5S^-i^3t¥?'J (50-61. 70-74) Um^T- 




(2) 



HP 2006-519445 A 2006.8.24 



m^M 1 ] 

mt^r- ^^<-:^^xmmv>xv^^iiCot l. 

• trmmm'Dmm'r)^mx^mi^^<^^'XMtm^j:m%k<7^^-^^.ic^m^i^mL. ^^-e, 
to lamt q^^y^-fyry^^ y,mx^^ t tt^mMm i mm<^ijmo 

[mt^m. 3 ] 

mtJn 4 ] 
m^sM 5 ] 

lu ia:fc*?Ui3 J: MISt' - ^-<~y. i)^^ii^~iimm<r)^^^n'^ U^t^ i t t 

m^M 7 ] 
m^M 8 ] 

mfi-x^mis X wist ^ ^^-7. i}^^it^'fi r<y mmm s ;t d n a / r n a^* 

m^m 9 ] 

10 J; c>'io Ex - y - 7^ ij^^K^ii e > , /^^^ ^ ^ fz (iigco^J ^^tl"^ i 

t 1 . M^iM 1 L 4 ^ Ttt55^-«IS«<^^&o 
[»« 1 0 ] 

1 1 ] 

[IS« 1 2 ] 

• mtm-<DmW'r)Xijm^^-^^t>-^X'^n<D^^i^K<r)X'^m^nLx^i>my-'r)mw^ 
'o&^x^n^ik&L. ^:lx\ mmm^(^mw(^^T&^x^nco^iir^'7^ic^nim^'^ 



(3) 



]P 2006-519445 A 2006.8.24 



[IS^Jl 1 3 ] 

mtM 1 4 ] 

[ 0 0 0 1 ] 

[ 0 0 0 2 ] 

\t tfz^^.x. y V (I ^ W1- ;§> o 
[ 0 0 0 3 ] 

[ 0 0 0 4 ] 

^I^B^ S ;t Hfria:^fe**tf 1-^ rr :/ e ji - v^;^ t a n ^ o 

[ 0 0 0 5 ] 

[ 0 0 0 6 ] 

[WMM] 
[ 0 0 0 7 ] 

*S#lt^5, 9 6 3, 9 5 7 ^^i:^^f^^-^--<-7^=^^1-^1f»^Iv■:^TA^|F1^ 

%^W.l^-^y7.\±-f^xmm%r^^^-f^tzt>Y^immi:m^m.W (scale d e 
g r e e) Y^'m\t^^X\^^^^ AiJ ? tifc^^^^ij t#^(D#M^J (7)M(7?-|S:$-^tii-r 

fz mum'^i^hm-s~^^^<^ t'^^-m ^^^^ ^tir^^^ it isit >^ ^ a {± -lit-r 

^ # HSr^ - ^ > I M 51 1- S » ^ 'If $R * ^ ffi 1- <7) ^ o 
[ 0 0 0 8 ] 

Du, D. W. and Chang, S. C. (1994) "An Approach to Designing Very F 
ast Approximate String Matching Algorithms" \M^\Z-%W£''-&.^'X%'f\'^ -yf- y 
^'cOsf TJVa'U XAiglt(7)|^<i9>] , IEEE Transactions on Knowledge and Data En 
gineering, 6 (4) , 620-633-eii 'fo ^ -0(7)@M(7):i^¥^?!lv f-:/ i5^:^)S^ t^li^? 

[ 0 0 0 9 ] 

^mmx\t^ m%-}^mt'^^-%%'j^T )^^') xi.^m'.^^, wm<r>m%-^mtmkm 

^y ^^^\in(r>X%^o 
[##Bt:^K 1 ] Myers, E. (1994) . A Sublinear Algorithm for Approximate 
Keyword Searching. Algorithmica, 12 (4/5) , 345—374 



(4) 



HP 2006-519445 A 2006.8.24 



[0010] 

[0 0 11] 

[0012] 

[0013] 
[0014] 

(7) II - c7) |g 19 ^ c7) |g 19 ;t t T V ^ ;i> o 
[0015] 

^m-sc^mKis\^^xff^ii^m^(ommi^^'^xmi>o 

[0016] 

-isi', mtim-'7^mwL'r)Xtjr'n^^^^'^x^m'^^fi^^ii<^-x^nKnLx. mtm 

[0017] 

\±. W^niSm±q.VyJ^ (q-gram) (suffix tree) -^S, 

■ mmr~^^<~7.:^^hm^.^fifz^±-wcic^m^^^^ifx$)&mm(DmWi<D^mic^ 
mzt^o ---e. mm^mx^n<^^^'^iu^^tfix\^^:hm^^^fz^^-^-x^n 

immr- ^^~7.fpxmwiv^xv^:hiiCo t-r^o 

xM^^&m'^(Dm^(^m^mtk(Dm^^^Lx\^^^o 

[0018] 

#|^c7)-oc7):^^ ^7 7°Hov^Tt±. El 5 c?)^,^ ^7 7° 4 0 0 *5 i ?7 5 0 0 i3 V^TEBJ^I" 



(5) 



HP 2006-519445 A 2006.8.24 



[0019] 

[ 0 0 2 0 ] 
[ 0 0 2 1 ] 

[ 0 0 2 2 ] 

[ 0 0 2 3 ] 

^mMltiii.TKSs\^^xnt Lv^^»|it(7)W^T% t7t|lIffl^#MLooJ; VjMt; 
[ 0 0 2 4 ] 

-ftL^^ii^c^ (k=i) m>^-^^x^m(om'o<r}'AU-%Xjc^m<r)r-^^-^^x-co 

ii.Ui^^^^flX^>i>o r«1V^-^^-^jt^^J (#Mf^3 4) c^abacababcli 3:i:^?/ilt<0 7 
)Vy7^yV I 'a' , 'b' , 'C i 3$^^,Sg!(;?ttTv^i>o ^ ^) ^^^--^ L/5^lt ? ^^^v^ 
(k=l) . JfA^ti;tfa^^-^t/Sia-SS: (7t<tx.(f#m^3 O cT^abacababbc) , 
mB^fifzm^^^t^^m-^ (tzt^imm^^^S IcT^abcababc) . m^^fifzm^'t 
ttfmi-^i (^ct^{f#Mf^3 2(7)abacabcbc) . ^UT^^-JS: (1"^^^,. #M 
t^^3 3 c?5abacababc) ^^'<;?^ott tl-^ o MmmiK^^^-C-m^ii. m\^^^h^X^m 

[ 0 0 2 5 ] 

mij-mit. ^^-s6:itt. -rt£io^m^^-^<^^^£^^ (k=o) ;itt(7)7ti6(7)i^iST;v3' 

i>o «b t^c t ^{fx- ^^^-7,^^":fc^^Jabababcabcabacab. . . t^h^J: ^ (O tT ^ t . 
q^^y^ii^^ 4C0^h^^35yX^¥^}<^f^iai^LWt^>!t)& ^tK7£&o abab, baba, ab 
ab, babe, abca, t '^^ -d fzM,^X$, ^ o ^iti^(DWj^1C^n\m^i:i^'DX^yryi^y 

abab<DX^^J:mkcom-com5yiC^mimZ-( yry y {/^^ y t\\fi^:Ki>) Kfzt^^ 
q^-yAKX-^X, ^^m^q(Dm^-^^-^(r)7^'^-^XK-o\^^Xii.t^X. ^yr 

y ymw^tmLx y (D^^^M^^^-r ^ ^ t K X ^x r- ^ y^(Dim^'^^^ 



(6) 



HP 2006-519445 A 2006.8.24 



^'yl.<7:>m-n^j:it\y^l5mers (1994) ti^-^f^tLTV^i,^ 
[0 0 2 6 ] 

[ 0 0 2 7 ] 

ttc7)T;^7 r^^y h I 'a' , 'b' ( t^i^X^M3hba.(7ymv^^h^^m^kLfzt-fi>t^ 

ba, mW^^^h^i^^^-X'^msScto, aba, bba, ff A^^Ij'*) -I) jt*?!Jaabba, babba 
abbba., ababa^ abbaa^ abbab, LT§^^#tf ^ jt^^Jbbba, aaba^ abaa^ ab 

bbi:^-6o 
[ 0 0 2 8 ] 

^^<7^X^VW-&^mmmK^)k-fh:Lti)^X-^h (Myers, 1994) ^ i^LZ^^h^D 
[ 0 0 2 9 ] 

[ 0 0 3 0 ] 

r«1v^^fe-iJ:jt^?!j^ 3 jt^/i^t<^T;^7 r ^-7 h I 'a' , 'b' , 'C | /j^^)fffi,)t^ 
tt;S>abacababc<i: V-^^Ki 3 t -el^#T^ (k=3) ^^(DtLX^o m^^t>^K 

• ^g^^^'^S^M' (fzt^ (±\ ^ tit; J: t ccccababc5^)>'^^(7);^t-e<J?^-^35^2)) 

• ^$^^^"f^§M; {fzt^ ff ababbcabc) 

• (fztk. (f abacabbca) 

• fa^\,^^ib^X^m K t A.^A.ti <5^m {tztk. ff abccacabb) 
f»'\^,^^t>^%^mi)^3-:>(DW^5yK^n^^^tfht (p=3; ^(Dmx<Df^ 

v^^^^-iJ:t:^^0abacababct::i3(t^^|5^:t^^iJ{iaba, cab, abct^^l)) . ^f|5^t;ov^T 

■1^ jt^^Uabacababctov^T, ^ j£#^^?^^!j(7)9S-^— Ifc/^j^Eo^^o t T ^) , 

^m\^^^-^^^mi^-rhfz^'T)yiif^yj:mmtE^£Lx^^tz'T)T$)i>o ^kkmlx. 

7.i^VT^yf (cross- cutting) d^mWt. S^f Sl^^tl ^^t1-'g> K t^. (M^cT)) fu 



(7) 



HP 2006-519445 A 2006.8.24 



[ 0 0 3 1 ] 
[ 0 0 3 2 ] 

m (edit- distance) oo^S^i'emT'e^-i) . i) vMijf^^^v^T 3 (A, B) <ki:Ti)o 

= (K, k,, k,) ^m.<Ty^mm,<r^m\'^ 

[ 0 0 3 3 ] 
[^1] 

C = XJt,+/7-jfc>l 



[ 0 0 3 4 ] 
[^2] 



5](jfe^_+l-5(4^,5^^))>C 



[0 0 3 5 ] 

BJ =3 (A, B) Cffl{±i = l>5^^ptT] J: ^ i;pfi(7)?^5> 

A? tl'S)^ t(i'^V^4><7)t1-;i>o ^(7)J; 0 '^B(7)^f[I^®a=\ k,+1^8 (A,, B,) ht^h 

[0 0 3 6 ] 



C^f^k,+p-k<f^ik, + \-d(A,,B,))<Zik^^+\-diAj,BJ) 



(8) 



]P 2006-519445 A 2006.8.24 



[ 0 0 3 7 ] 
[ 0 0 3 8 ] 

m 2 Kt^-TX ^ rp1^/^^^^^i^?!Jabacababc (#Mf^ 3 4) ii 3 
Kjym^^^ (P=3) o ff^ii^W:^i}^3^i'zif'X:i):h (k=3) it'^lBJaL, k, =floo 
r (k/p) =1 [-noor^mmm j3J:CJ^X=2k,+p-k=3 [^n(ii = l^-^P.P^ -c] t'mm 

1. 42~45> 46-49) ^<^ic^mt^^±-W:K X 9 7 

fsm^M^w ^ . mmt & }&^ic^n * o ^ If 7t ^ ^^fp^ am- t 

^ i^^^^t--^ ti;6o ia#:fc^^Jabaj3j;t/cab(7)ro(7)-Jj: (El2c7)#HB^^ 

-^3 0^#M) {i. ^c75rp^i/>-^^5-^::fc^^J(7);ft^0cDro(7)fP^:fc^^Ji;oi/^Tc7)^t)c7);^ 
V^-gfc^^UTV^-i) (-f^^tJifc,. e=0-e2 (k,+l) -e=4^C=3 C#n{ii = l>d^'^2Sir] 

figi^-fS c7)T^^So i£#:t^?!Jabci3 J: O^caaic^^-r^ — -0(7)-^: (HI 2 (7) 3 1 #M) (i- 
oc7)|ei5^^-^;|>^'^^^LTV^& (T'^^*,. 6=2-^2 (k,. +1) -e=2 (fn li i = 1:$^ 2 

2c7)#Hg|f^3 2 ^#HS) ^J:i--e^3 4o(7)^^9^#^-ev^;l, e=4-es (k,- + 

1) -e=o mii'^=U'h2tT) ) o :Li(ix-rxK^(D'A^x^m'7^nim'^^^^'^<yy^A 

[0 0 3 9 ] 

qiJ^9A§-fflV^tl,ff. q^0X.'^V^ft?cD5:^^J(7)4|2@^-r-<T$'#tti;^iSt^^o 
[ 0 0 4 0 ] 

2^c^fe^cD«0^^t,a-l-^(7)^#|t^$-#;ii>o ri^^StiMs^?! (Pa) = a i> 
(P) +^ (a) KX ':>X^mK^^nKt}A^^X^7^o ^:iX\ Pii2±<7)±^m. ali2lZ. 
^t^i>tl'^X$,i>o b= [0, o'-l] KULX. Bucket (b) = |i : ^5 (a,-a,.^ ^-a,. 
+ , - i) =bi t1-&o 1-=^=b^. Bucket (b) it <^mi)^\^xa> X ^ ^^mmi^^^h^J: i> 

[ 0 0 4 1 ] 

lriia^;^^(d::?!^C0j: ^ H tT4)3fe;?ti-2.o 95i=?S (a,a,+ ,-a^+ „_ J t?)^'^, ^ 



(9) 



]P 2006-519445 A 2006.8.24 



ii:=^fiJfflTtitf\ k^t£i6^0 (n) 60»i; J: oT^tr-ei -So ^^Jtli^ 0 (nlog (n) 
) CO^'-Y '7 V- h ^-fflV^T ?5i [ <?5,-[j+i] i: '^i) ct ^ 5^ 'J 7. Mndices= <n\, 
12, -, in> ^^^fefiitT^^^o ftm^^. E^JHeader [b] =min )j : ^Si.dnc.. [ j] =^ 
Indices^T^i^^O (n) coftfl^ti J; o T^fiK^ tL^o ffi^Indicesis J; i^Header^^Bucketco 
^^^'^MLtzi,(rytti:ho -f^£^%. Bucket [b] = llndices [j] : jG [Header [b 
] , Header [b+1] -1] | ttj:^^ 
[0 0 4 2 ] 

be (P) a''-", (^i (P) +1) a"-"-!] Bucket (b) 4^ 1 -i. o 

[ 0 0 4 3 ] 

f^^^^^h^-X^m^<n^^i)^<A^mtX\^^h1^^K\t. Pco^|a@3f<^ft^{iBucket 
(PJ ) (DU^^m^^-^^^^tt^h^^^o ---C% Pqf±P(7)m^!J(7)cHicO|S-^3^^e,?^-&:fc^ 

-^^UTSa-eg&o 1-'^^^*). 1^ (P) = IQ: a (a p) o 

[ 0 0 4 4 ] 

X^m?(0'^^ (cotxiensed) ki5#{i p c7)^^?^ki£#tcM-r ^ T^T(7)t:^7^^0(7) ^ ^ 
^m^i&m^'f^^y ^ y ^ :^-^^tz^£^^^'D<D^^x-^ho -f^^hh. ^ (P) = IQ:QeN 

k (P) ^^oQ(iN, (P) ftH7°V-7 ^ 7 ^X^^Tt'^vM o 
[ 0 0 4 5 ] 

tf^U (dynamic programning matrix) (7)^t)S1"^^J ?-lt*i"^ i I- J: o Sfe^M^^'il 
o 4)LT'^Tc7)a:.>hiJ- ^a^'k J; 19 § ft ti fi\ T ;P 'J X i^ (± 4) t K n^^t t^X^ § h 

[ 0 0 4 6 ] 

ti: , - ^ ;^ ^ (D-$>ib^h ^^-Ifc ^ S ;t 46 II :i^^J 
[ 0 0 4 7 ] 

0 3 (± Pp^ V^-^ S:*^J (D'^mt^ (T^mcD^t (7)^^^ J: CO #ffl t T -i, 

[ 0 0 4 8 ] 

[ 0 0 4 9 ] 

A:t7r«1V^^^^-i^:t^^0^l)!tLT{i. )!tJS1-S 4 0(75a#jt^^J (#M^^3 8 . 3 9 . 4 

0.41) t^'^m^ 

[ 0 0 5 0 ] 

<D'£.^X^m (#M^4 2 . 4 3 . 4 4 . 4 5) t^'m.^^tl^o 



(10) 



HP 2006-519445 A 2006.8.24 



[ 0 0 5 1 ] 

^(T^i&WIC^m 4 7 . 4 8 . 4 9) i)^'^m^fl^o 

[ 0 0 5 2 ] 

^x^m (#m^3 8 - 4 9 ) (D^^^nt^ m5^x^n'^) ^-^-^^^-^if^tznb 

[ 0 0 5 3 ] 
[ 0 0 5 4 ] 

*c7)^t^^'tl^i. >j^^t\ ^'$i^iifc^mm(^^Vjyx^m (#m^5 0-53) t^-^, 

mt^tL^cf^^^(7)§^3^^i?:^!J (#M^^^5 4-5 7) c7)-o. 1tt?ti;t r*M§l5J c7)^R 
5yiC^m (#0S^^^ 5 8 ~ 6 1 ) c?)-o;5^?,^-i>o J: ^ IC^I^i^V^TSB^tl-g) 

[ 0 0 5 5 ] 
[ 0 0 5 6 ] 

[ 0 0 5 7 ] 
[ 0 0 5 8 ] 

m (#M^^3 4) tW^~^tfz\tX^M^^-^\.tz^<DX^^o ( 
[ 0 0 5 9 ] 

^-1^:^^^^ (#M^^ 3 5 . 3 6 . 3 7 ) tlMJ^tL^o "T^t^^. to IS^-(^f@mf± - 



Cli) 



HP 2006-519445 A 2006.8.24 



[ 0 0 6 0 ] 
[ 0 0 6 1 ] 

^(DMTlt. m^^i^-i^-^lC^m (#M:|^^3 4) aba. . cab. . abc. . M|SS|-co 

o 1-^=b*.. Xtim^^^^X^mi (#m^3 5) aba. . . xtif'^^\^^^t>^x^m 
2 (0m^^3 6) cab. . , XM\^^-^t>^X^m3abc. . -e$,;g>o 
[ 0 0 6 2 ] 

V^^^oii::^^^!] (#Mf^^3 5) t::(±#M^-^3 8-4 1. ^rcT), t^^hib^^'^Xtl 
(#M^^3 6) ti{±#HS^^4 2 -4 5 . ^H<7). l-^^^T^^mcoA 

^rBlV^^^:.-^:i:^^lJ (#HS^^-^3 7) Kltmm^i 6-4 9-C*;6o 
[ 0 0 6 3 ] 

[ 0 0 6 4 ] 

l5»rcr)j@i:1-^^7*> 3 X 4 = 1 2. l-^ifc**) (3ocr)) Aijrp1v^-^^9-^:fc^^U>e:Jt-e~ti 

[ 0 0 6 5 ] 
[ 0 0 6 6 ] 

mm\fi>t.X^mv^ith^1C^m3b3i. . (#M^^-^3 5) tli4o(7)3£^jt 

• 1 ^c7)p 19 ^^trabc. . mm^^-^ 3 9 ) 

• 1 jic^p^) 9-oc7:)abb. . (#ssif^4 0) 

• 2 jicoM^) ^-^tfacb. . (#HS^^-^4 1) 

[ 0 0 6 7 ] 
[ 0 0 6 8 ] 
[ 0 0 6 9 ] 

loia||H(7)ji|^c7)5S:^^Sfct±#f!B^f-^5 0-6 1 ^ Xlf 7 0 - 7 4 K X ^XMtt^^ ^-X 



(12) 



HP 2006-519445 A 2006.8.24 



Saba. . co^^—^iK-o^^^^^o 

• HHH. abb. . (#Mf^4 0) (±-|fcH{ioJ^^^^^j^V^o 1-'^feS#Mf^7 0 c7)a 

bd. . 

■mm^. acb. . mWM^^ D ^-i:i::{io)^^^'ib'^v^o fii^^^WM^l 1 <7)a 

be. . 

[ 0 0 7 0 ] 

^tttiLT. #M^5 3-6 1*3J;?^7 2 - 7 4 'b#M-t4 2 - 4 9 I' JioT:^^ 
[ 0 0 7 1 ] 

^^is* (#0S|-f-^ 5o-6ii3j;o^^7o--74) mm-f^^x-^f^m 

[ 0 0 7 2 ] 

# .fc 1/ ^ T ffl -^^S) ;g) t ^ tLT ;i) ;i) ^ig!^ ;t @J1?^3K&^ /^ 

V V J: v^o 

[ 0 0 7 3 ] 

[ 0 0 7 4 ] 

tt7t^^-i::fc^f?!j (#m^5 0-6 l*3j;a=^7 0 - 7 4tlJ:oT^$tL-g,) {i. tufS 
[ 0 0 7 5 ] 

m<r)%W,^X%^) aba. . (#M^-t 3 5 ) {imTi.^®f^(7)i£#:t^?iJ 
3 8-4 1) ^:tt. ^^^S1--i)^Mg|5(7)§|5^i^S:*^J 5 0 - 3 3 ) $-«<o 

[0 0 7 6 ] 

) cab. . (#M^^3 6) (i^ttSI-^ (#M^^^4 2 - 4 5 ) ^ 

^L. ^t)J;i-^+f^«OS&M^^y (#m-^5 4 - 5 7) =^#<o 
[0 0 7 7 ] 

^) abc. . (#M^f-t3 7) (±mT-g) r*M§M ooiS^it:*?!! (#M^^-^4 6-4 9 
) ^^tt. >ftSS1-:i> r*M$|5J (7)$|S^5:^^J mWM^^ 8-6 1) ^^<o 
[ 0 0 7 8 ] 

M^#5 0-6 1. 70-74) t^mty'-9^-'^^Xim\tk\^XM%-tho t^^^^ 

. '^mux^nKnmti>i^(D (#M^-^5o-5 3) . ^ux'f-m^nmt^i^(^ m 

M^^5 4 - 5 7 ) . MJ^UX'^^nKMB-r^^CO (#Mf^^5 8-6 1) 

xwmmm(7ymw'^^mx^m (#0^^^ 2 9 - 3 3 ) co— ^^^^i-tT^-es^^o 

[0 0 7 9 ] 



(13) 



]P 2006-519445 A 2006.8.24 



[ 0 0 8 0 ] 
[ 0 0 8 1 ] 

^c^) M^J^^#1-r^7ti6i;«$:n-^o #M^^-^ 3 0 - 3 3(iV>f tL^j^tLj; J9 

[ 0 0 8 2 ] 

LT. f]fE»6<]^fli:c7)g«^?U (#m^3 0-3 3) d^^^^ 
(#M^^^3 4) (D%^-^Atfz\tW^--ltX%^o 

[ 0 0 8 3 ] 
[ 0 0 8 4 ] 

(7)rpiv^^fe-i^ii?:^!j (#m-^3 4) ^(7)af:i-i:*-^^9 ^=fo(75<7)*^#;ti> tv^ai& 

[ 0 0 8 5 ] 

[ 0 0 8 6 ] 
[ 0 0 8 7 ] 

m^\.fz^nr-. %%m^-%-i^^xx^\j^^\^^X'^n (#m-^3 4) ^mi-^s^o wm. 

^3 0 . 3 1 . 3 2 . 3 3 ) ^^"^ott^^t^o •7^yf->^^^;fjfic7)^^^7 7°=^^tf1-Sft# 
[ 0 0 8 8 ] 

#M^^ 6 6 2 (±n>'ii:x-^^-/n^'9A7°n^\^' milS^ > ti :x - ^ 7°n 

7 A 7°n ^' h 3 t: ^ - §5^^^ ^) nrt^ii#± HISS? 7° n 7 A ^ - F^S ^ 
^ L . ^ ^ - 9 -^u ^' ^ Ui)^ny M - 9 i-e^f ? ti/:: t lu Ifi^fi ^ 1" 



(14) 



HP 2006-519445 A 2006.8.24 



[0 0 8 9 ] 

t {f V ^ - ^ ^ J|i#:c7) :t - r t .IS ^) V 3 >' J: H ^ tL /t ^) ct) ^ — 
-7.x^;;^^#^/i4)6o-e^i J:v^o ifflE^ffitiS /t. Tttx-tf-^ >^-#-7 h^-7s^-± 

[ 0 0 9 0 ] 

V 7 h 7 .r. Tt^'^v 'y - .'i^ io T ^1^^^^ Lfci9l"^7t«^05b </)— t:: A±i ^ 7. 
^CEffl^lf t^l3V^T. ?*U>fS!') ^^m(i:^)f?/^^i:a6Sa$tL. tiT v^;g) coT' ^) 

75 DNA/RNA. ^?^^:') ij-^t^X-^m^-f^^tii^X-^^:, T^7.}-X(Dmm 

KmLX\t^ ffilk7;v7 7^7 h(^2 6^^^^^ ^tt^x^^o mtr-. ;^#(±9gt 

/5-^f,>^^>^fS7;V7 r ^7 Yi}^'hm^'f^^ti}^X^i>o ^^i^^tl^^^lf 2 Oc7)7 5 
[ 0 0 9 1 ] 

hmm^^z>o tzt^ii. m^xi^x^^L. ^^^mmm^ij^^t^^%mx^£t-'Dfz^ 

. fzt^\f&^m^mhLX'^m'k1^'^Ltzi)-^'Dtzy)^ 

J: o T jt^^J ^ 5^ T f ? S (iO -e ^ -g) o 
[ 0 0 9 2 ] 

DVD) . n77N°7hTV7^' (ISfiort^CDS fc(i»§E^nrt^CD) . 5::itV7^^ 

, /N- Kf'VT^^'. 7n'ye- (M®^) r^T.^^ IC*-K, PCMCIA*-K 

[ 0 0 9 3 ] 

#itfi^<7)itHnjov^T. ^m^x^xmm'^t^^^fzthxi,. ^^\mtmi^<r) 
mm^u^-rz>i,<7^tm^hx\±fj:ibtii\^^o \^-t^\ (Dm\±m^m^-i5^^xmfh^x 
v^hm^a}mm^:^^y^(D^^^m^.-r^^<^x\tts:^^o m^<^^m^<^umt't<D 

[ 0 0 9 4 ] 

y°u^'y\ y ^'^^fzny\ia.-9Ki.-^X%^^fi^::.ti)^x^^^ < o;^^(7)^S^ 



(15) 



]P 2006-519445 A 2006.8.24 



[ 0 0 9 5 ] 

[0 2] m^^h^x^m^^^m-r^m^^^^-rmx-^&o 
[0 6] m^(Dfci>b(Dmm^^'rmx^^o 



[0 1] 



[02] 



(17) 



HP 2006-519445 A 2006.8.24 



INTERNATIONAL SEARCH REPORT 



A, CLASStFICATlOW OF SUBJECT MATTER 

IPC 7 G06F 17/30 






Aocoming to Intsriutional Patent Ctassntealloh {IPC) orlp boU 




atlontmcllPC 


a FIELDS SEARCHED 


Minimum documentallon eearched (daesincallon system mvaed by dassflicalbn symbolsl 

IPC 7 G06F 









PCT/IB2004/050148 



Elecffonlc ds 

EPO-Internal , WPI Data, INSPEC 



DOCUMENTS CONSIDeRED TO BE RELEVAKT 



Caiegory- Cmhn of dDciiraent, wWi IndiatiDn, w 



MYERS E. W. : "A Sublinear Algorithm for 
approximate keyword searching" 

ALeoRITHWCA, 

vol. 12. no. 4-5, October 1994 (1994-10), 

pages 345-374, XP008033755 
GERMANY 

dted In the application 
the whole document 




' ttie same patent famly 



Date or tli« ictcial compMini or tha mtematlonel seareb 

9 August 2004 



European Patent Office, PA S»t8 Pdenttaan 

NL-aasoHVRijswijk 

TeL (+3T-70) 34(HW0, Tx. 31 851 «po nl, 
Fa» (+31-70) 340-3016 



DE CASTRO PALOHARES 



(18) 



HP 2006-519445 A 2006.8.24 



INTERNATIONAL SEARCH REPORT ZTuTowT^^^^^^^ 


Categoiv' 


citation of dscuiBem, wllh Hdkaton, ii*wiaappropriala of tne reievani passage;: 




A 


LUIS ERAVANO AND OTHERS: "Using q-grams 
in a DBMS for Approximate String 
Processing" 

IEEE DATA ENGINEERING BULLETIN , 'Online! 
vol, 24, no, 4, 2001, pages 28-34, 
XP00Z291636 

Retrieved froni the Internet: 

URL : http : //ci teseer . i st . psu .edu/cache/pape 

rs/cs/27618/http:zSz2Szwwwl.cs.co1umbia.ed 

uzSz{pi rotzSzpubl i cati onszSzcleb-dec2001 . pd 

f/gravano01using.pdf> 

'retrieved on 2004-08-06! 

the whole document 


1-14 



(19) 



:P 2006-519445 A 2006.8.24 



7t3> h'^-i>©^t 

(81)jgsffl ap(bw,gh,gm,ke,l5,i«,mz,sd,sl,sz,tz,ug,zm,zvv),ea(am,az,by,kg,i<z,n^ 
at,be,bg,ch,cy,cz,de,dk,ee,es,fi,fr,cb,cr,hu,ie,it,lu,mc,nl,pr,ro,se,si,sk,tr),oa(bf,b],cf,cg,ci,cm, 
g^,gn,gq,gw,ml,l*l,ne,sn,td,tg) ,ae,ac,al ,am,at,au ,az, ba, bb, bg , br, bw, by, bz,ca,ch ,cn,co,cr,cu ,cz, de, dk, 
[w,dz,ec,ee,eg,es,fi,gb,gd,ge,gh,gm,hr,hu,id,il,in,is,:p,ke,kg,kp,kr,kz,lc,lk,lr,ls,lt,lu,lv,w\,md,m 

G,IVK,IVN,l«,MX,MZ,l^,ra,ND,l^,QM,PG,PH,PL,Pr,RO,RU,SC,SD,SE,S^ 
,VC,VN,YU,ZA,Z1VI,ZVI/ 



(74)f-<;SA 100107766 

fyy^m, 5 6 5 6 r-r- r^'> • ij^jv;^ b7-> 

mmn^ :3;L'Xh, 

:t^>^ffl, 5 6 5 6 r-T- r -l' > x >, 7*07 • h 

t'yyf'm. 5 6 5 6 T-T- T-r > x >, :7'a:7 • ^^J^7^ h 

t'yym, 5 6 5 6 r--r" r-OF-^x^. • 4^ji'Xh^-> 

F$-A(##) 5B075 ND03 NK02 NK45 NK49 NR05 PR06 CtJa2 



3) ^Wi^b. ccv. mmM.mmj:mm<D^^xw\(Diti^ri<DX^mitt, mMimi^-^h^^^m (3 4) Kit