算法設(shè)計(jì)與分析 ch8 學(xué)習(xí)課件

2/28/2025第八章

字符串算法王宏志計(jì)算機(jī)科學(xué)與工程系

2/28/2025

8.1精確字符串匹配

2/28/2025字符串匹配問題輸入:文本

T

=“atthethoughtof”n=length(T)=17模式

P=“the”m=length(P)=3輸出:移動(dòng)到

s

–

最小的整數(shù)(0￡s￡n

–

m)滿足T[s..s+m–1]=P[0..m–1].返回–1,如果不存在這樣的s0123…n-1012atthethoughtofthes=3

2/28/2025簡(jiǎn)單匹配算法Naive-Search(T,P)

01fors?0ton–m02j?003//checkifT[s..s+m–1]=P[0..m–1]04whileT[s+j]=P[j]do05j?j+106ifj=mreturns07return–1想法:暴力搜索檢查從0到n–m的所有值令T=

“atthethoughtof”,P=“though”

需要多少次比較？

2/28/2025簡(jiǎn)單匹配算法的分析最壞情況:外層循環(huán):n–m內(nèi)層循環(huán):m總計(jì)(n–m)m=O(nm)何種輸入產(chǎn)生最壞情況?最好情況:n-m何時(shí)?完全隨機(jī)的文本和模式:O(n–m)

2/28/2025指紋想法假設(shè):我們可以在O(m)時(shí)間計(jì)算一個(gè)P的指紋f(P).如果f(P)1f(T[s..s+m–1]),那么P1T[s..s+m–1]我們可以在O(1)時(shí)間比較指紋我們可以在O(1)的時(shí)間從f(T[s..s+m–1])計(jì)算f’=f(T[s+1..s+m])ff’

2/28/2025基于指紋的算法令字母表位S={0,1,2,3,4,5,6,7,8,9}令指紋為一個(gè)十進(jìn)制數(shù),即,f(“1045”)=1*103+0*102+4*101+5=1045

Fingerprint-Search(T,P)01fp?computef(P)02f?computef(T[0..m–1])

03fors?0ton–mdo04iffp=freturns05f?(f–T[s]*10m-1)*10+T[s+m]

06return–1fnewfT[s]T[s+m]運(yùn)行時(shí)間是2O(m)+O(n–m)=O(n)!

2/28/2025使用Hash函數(shù)問題:我們不能假設(shè)我們可以對(duì)m位數(shù)在O(1)時(shí)間內(nèi)進(jìn)行算術(shù)運(yùn)算解決方案:使用hash函數(shù)h=fmodq

例如,如果q=7,h(“52”)=52mod7=3h(S1)1

h(S2)TS11

S2

但h(S1)=h(S2)不意味著S1=S2!例如,如果q=7,h(“73”)=3,但“73”

1“52”但“modq”

算術(shù)運(yùn)算:(a+b)modq=(amodq+bmodq)modq(a*b)modq=(amodq)*(bmodq)modq

2/28/2025預(yù)處理與步驟預(yù)處理:fp=P[m-1]+10*(P[m-2]+10*(P[m-3]+…+10*(P[1]+10*P[0])…))modq同樣地可以從T[0..m-1]計(jì)算ft例如:P=“2531”,q=7,fp是多少?步驟:ft=(ft

–

T[s]*10m-1modq)*10+T[s+m])modq10m-1modq

在預(yù)處理中計(jì)算一次例:LetT[…]=“5319”,q=7,對(duì)應(yīng)的ft是多少?

ftnewftT[s]T[s+m]

2/28/2025Rabin-Karp算法Rabin-Karp-Search(T,P)01q

?aprimelargerthanm02c?

10m-1

modq//

runaloopmultiplyingby10

modq

03fp?0;ft?004fori

?0tom-1//preprocessing

05fp?(10*fp+P[i])modq06

ft?(10*ft+T[i])modq07fors?0ton–m//matching08iffp=ftthen//runalooptocomparestrings09ifP[0..m-1]=T[s..s+m-1]returns10ft?((ft–T[s]*c)*10+T[s+m])modq

11return–1如果T=“2531978”,P=“1978”需要比較字符多少次?

2/28/2025分析如果q

是素?cái)?shù),hash函數(shù)將會(huì)使m位字符串在q個(gè)值中均勻分配因此，僅有s個(gè)輪換中的每第q次才需要匹配指紋(匹配需要比較O(m)次) 期望運(yùn)行時(shí)間(如果q>m):預(yù)處理:O(m)外循環(huán):O(n-m)所有內(nèi)循環(huán):總時(shí)間:O(n-m)最壞運(yùn)行時(shí)間:O(nm)

2/28/2025應(yīng)用中的Rabin-Karp算法如果字母表有d個(gè)字母，將字母翻譯為d進(jìn)制數(shù)字，即用d代替算法中的10選擇素?cái)?shù)q>m

可以利用隨機(jī)算法在O(m)時(shí)間內(nèi)完成,或者q

是一個(gè)固定大素?cái)?shù)且一個(gè)計(jì)算機(jī)字可以容納10*q.Rabin-Karp比較簡(jiǎn)單，可以容易地拓展到2維模式匹配.

2/28/2025n次比較的匹配目標(biāo):文本中的每個(gè)字符僅匹配一次!簡(jiǎn)單算法的問題:沒有利用已有部分匹配中的知識(shí)例:T=“TweedledeeandTweedledum”

P=“Tweedledum”T=“pappar”

P=“pappappappar”

2/28/2025一般情況算法的狀態(tài):檢查移動(dòng)s,匹配了P

中的q個(gè)字符在T中看到了一個(gè)未匹配的字符a.需要尋找:最大前綴

“P-”并且是P[1..q-1]a的后綴:aT[s]qT:P:q’=max{k

￡

q|P[1..k]=P[q–k+1..q]a}aqP[0..q-1]a:P:q’

2/28/2025自動(dòng)機(jī)搜索算法:預(yù)處理:對(duì)于每個(gè)q(1￡q￡m-1)和每個(gè)a?S預(yù)先計(jì)算一個(gè)q的新值，記為s(q,a)

填一個(gè)大小為m|S|的表掃描文本

當(dāng)不匹配發(fā)現(xiàn)時(shí)(P[q]1T[s+q]):置

s=s+q-s(q,a)+1且q=s(q,a)分析:

匹配階段

O(n)

內(nèi)存過多:O(m|S|),過多的預(yù)處理O(m|S|).

2/28/2025前綴函數(shù)Idea:忘記未匹配的字符(a)!算法的狀態(tài):檢查變換s,匹配了

P

中的q個(gè)字符發(fā)現(xiàn)了T中不匹配的字符a.需要發(fā)現(xiàn):最大前綴

“P-”并且是P[1..q-1]的后綴：aT[s]qT:P:q’=p[q]=max{k<q|P[1..k]=P[q–k+1..q]}aqT[s..s+q]:P:q’再比較一次

2/28/2025前綴表我們可以預(yù)先計(jì)算大小為m的前綴表來存儲(chǔ)p[q]的值(0￡q<

m)計(jì)算P=“dadadu”

的前綴表Ppapparq0123456p[q]0001120

2/28/2025Knuth-Morris-Pratt算法KMP-Search(T,P)01p

?

Compute-Prefix-Table(P)02q?0//numberofcharactersmatched03fori

?0ton-1//scanthetextfromlefttoright

04whileq>0andP[q]1T[i]do05

q?

p[q]06ifP[q]=T[i]thenq?q+107ifq=mthenreturni–m+1

08return–1Compute-Prefix-Table是P上執(zhí)行KMP算法的本質(zhì).

2/28/2025KMP的分析最壞運(yùn)行時(shí)間:O(n+m)主算法:O(n)Compute-Prefix-Table:

O(m)空間:O(m)

2/28/2025逆簡(jiǎn)單算法如果從P的后面開始搜索？BoyerandMooreReverse-Naive-Search(T,P)

01fors?0ton–m02j?m–1//startfromtheend

03//checkifT[s..s+m–1]=P[0..m–1]04whileT[s+j]=P[j]do05j?j-106ifj<0returns07return–1運(yùn)行時(shí)間和簡(jiǎn)單算法相同

2/28/2025啟發(fā)式方法Boyer和Moore向逆向簡(jiǎn)單算法中增加了啟發(fā)式規(guī)則，得到了

O(n+m)算法,但其更復(fù)雜Horspool建議僅使用出現(xiàn)啟發(fā)式規(guī)則在不匹配之后，將T[s+m–1]對(duì)齊到模式P[0..m–2]中的最右出現(xiàn)例:T=“detectivedate”

，P=“date”T=“teakettle”

，P=“kettle”

2/28/2025偏移表在預(yù)處理中,計(jì)算大小為|S|的偏移表.例:P=“kettle”shift[e]=4,shift[l]=1,shift[t]=2,shift[k]=5例:P=“pappar”其偏移表是什么?

2/28/2025Boyer-Moore-Horspool算法BMH-Search(T,P)

01//computetheshifttableforP01forc?0to|S|-102shift[c]=m//defaultvalues03fork?0tom-204shift[P[k]]=m–1-k05//search06s?007whiles

￡n–mdo

08j?m–1//startfromtheend

09//checkifT[s..s+m–1]=P[0..m–1]10whileT[s+j]=P[j]do11j?j-112ifj<0returns13s?s+shift[T[s+m–1]]//shiftbylastletter14return–1

2/28/2025BMH分析最壞情況運(yùn)行時(shí)間預(yù)處理:O(|S|+m)搜索:O(nm)何種輸入達(dá)到此界?總計(jì):O(nm)空間:O(|S|)和m獨(dú)立在真實(shí)數(shù)據(jù)集合上很快

2/28/2025

8.2字符串查找數(shù)據(jù)結(jié)構(gòu)

2/28/2025字符串的ADT字符串的ADT存儲(chǔ)字符串集合:search(x)–

查找集合中的字符串xinsert(x)–

向集合中插入新的字符串xdelete(x)

–

從集合中刪除等于x的字符串假設(shè),標(biāo)記:n

個(gè)字符串,N

個(gè)字母m

–x的長(zhǎng)度子母表的大小d=|S|

2/28/2025字符串的BST可以使用二分查找樹一些性質(zhì):Keys是變長(zhǎng)的很多字符串前綴相同–

可以節(jié)約空間考慮字符串的比較查找長(zhǎng)度為m的字符串的最壞時(shí)間是多少？

2/28/2025TriesTrie

–

存儲(chǔ)字符串集合的數(shù)據(jù)結(jié)構(gòu)(名字來源于

“retrieval”):假設(shè)每個(gè)字符串以

“$”(不在S中)結(jié)束bsear$id$ulk$$lunday$$字符串集合:{bear,bid,bulk,bull,sun,sunday}

2/28/2025TriesIItrie的性質(zhì):多路樹.每個(gè)結(jié)點(diǎn)有從1到d

個(gè)兒子.每條邊有一個(gè)字母做標(biāo)記.每個(gè)葉子結(jié)點(diǎn)存儲(chǔ)字符串，這個(gè)字符串是從根到葉子所有字符的連接.

2/28/2025Trie的搜索和插入搜索算法沿著樹向下(從Trie-Search(root,P[0..m])搜索)Trie-Search(t,P[k..m])//insertsstringPintot01iftisleafthen

return

true

02else

ift.child(P[k])=nilthenreturnfalse03elsereturnTrie-Search(t.child(P[k]),P[k+1..m])如何執(zhí)行刪除?Trie-Insert(t,P[k..m])01iftisnotleafthen//otherwisePisalreadypresent02ift.child(P[k])=nilthen03Createanewchildoft

anda“branch”starting withthatchlidandstoringP[k..m]04elseTrie-Insert(t.child(P[k]),P[k+1..m])

2/28/2025Trie結(jié)點(diǎn)結(jié)構(gòu)“實(shí)現(xiàn)細(xì)節(jié)”結(jié)點(diǎn)結(jié)構(gòu)是什么？=t.child(c)操作的復(fù)雜性是什么?:大小為d的兒子指針數(shù)組：浪費(fèi)空間，但是child(c)是O(1)兒子指針的hash表，較少浪費(fèi)空間，child(c)的期望是O(1)兒子指針鏈表：空間小但是child(c)在最壞情況下是O(d)兒子指針的二分搜索樹:空間小且child(c)最壞情況下是O(lgd)

2/28/2025Trie的分析大小:最壞情況下O(N)搜索，插入和刪除(字符串長(zhǎng)度是m):依賴于結(jié)點(diǎn)的結(jié)構(gòu):

O(dm),O(mlgd),O(m)和BST比較？觀察:為單個(gè)結(jié)點(diǎn)建立鏈較為浪費(fèi)空間

2/28/2025緊縮Trie緊縮Trie:用帶有字符串的邊取代一系列單兒子結(jié)點(diǎn)構(gòu)成的鏈每個(gè)非葉結(jié)點(diǎn)最少有兩個(gè)兒子bsear$id$ulk$$lunday$$bsunear$id$ulk$l$day$$

2/28/2025緊縮TriesII實(shí)現(xiàn):字符串在結(jié)構(gòu)外用一個(gè)數(shù)組保存，邊的標(biāo)記放在一個(gè)數(shù)組中可以用來做單詞匹配：找到給定的單詞出現(xiàn)在文本的位置.使用緊縮trie存儲(chǔ)文本中所有單詞緊縮trie中的每個(gè)兒子保存文檔中對(duì)應(yīng)單詞出現(xiàn)的位置.

2/28/2025利用Tries進(jìn)行字符匹配查找單詞P:在每個(gè)結(jié)點(diǎn)上,沿著(i,j)查找,從而P[i..j]=T[i..j]如果沒有這樣的邊,T中沒有P,否則，當(dāng)?shù)竭_(dá)葉子的時(shí)候，找到所有P的起始位置12345678910121416182022242628303234363840(31,34)(14,16)(1,2)(17,18)(19,19)(22,24)(3,3)(8,11)theythinkthatwewerethereandthere(28,30)(4,5)3112625,3511720T:

2/28/2025利用Tries進(jìn)行字符匹配II根據(jù)給定文本建立緊縮:如何做？運(yùn)行時(shí)間:O(N)單詞匹配的復(fù)雜性:O(m)當(dāng)本文在外存中時(shí)?最壞情況下需要O(m)次I/O操作來訪問文本中的單個(gè)字母-效率不高

2/28/2025PatriciatriePatriciatrie:

一種緊縮trie其中每個(gè)邊的標(biāo)記用(T[from],to–from+1)

代替12345678910121416182022242628303234363840(a,4)(a,3)(t,2)(w,2)(_,1)(r,3)(e,1)(i,4)theythinkthatwewerethereandthere(r,3)(y,2)3112625,3511720T:

2/28/2025查詢PatriciaTrie單詞前綴查詢:查找T中的所有單詞,其前綴是P[0..m-1]Patricia-Search(t,P,k)//insertsPintot01iftisleafthen02j?thefirstindexinthet.list03ifT[j..j+m-1]=P[0..m-1]then04returnt.list//exactmatch

05else

ifthereisachild-edge(P[k],s)then06ifk+s<mthen

07return

Patricia-Search(t.child(P[k]),P,k+s)08elsegotoanydescendentleafoftanddothe checkofline03,ifitistrue,return listsofalldescendentleafsoft, otherwisereturnnil

09elsereturnnil//nothingisfound

2/28/2025PatriciaTrie的分析patriciatrie的想法–將文本的比較推遲到最后如果文本在外存，僅需要O(1)次I/O(如果Trie在內(nèi)存)為單詞匹配建立PatriciaTrie:通常使用二分patriciatries:考慮文本和查詢的二進(jìn)制編碼樹上的每個(gè)兒結(jié)點(diǎn)有兩個(gè)兒子(0和1）邊上僅標(biāo)記越過的數(shù)值(位)12345678910121416182022242628303234363840f?texharhaftenf?dselsdagT:

2/28/2025文本搜索問題輸入:文本

T

=“carrara”模式

P=“ar”輸出t:P

在T

中的所有出現(xiàn)重新定義問題:找到T的所有以P為前綴的后綴我們已經(jīng)看到了如何處理一個(gè)單詞前綴查詢carrara

arrararrararara

araraa

2/28/2025后綴樹后綴樹

–

一種包含文本所有后綴的緊縮trie(或類似的結(jié)構(gòu))后綴的Patriciatrie有時(shí)叫做Pat樹

carrara$12345678arr$carrara$rara$a$rara$a$ra$2571643(a,1)(r,1)(r,1)($,1)(c,8)(r,5)(a,2)2571643(r,5)(a,1)(r,3)($,1)

2/28/2025Pat樹:分析對(duì)P進(jìn)行的文本搜索是一種前綴查詢.運(yùn)行時(shí)間:O(m+z),其中z

是結(jié)果數(shù)量?jī)HO(1)次如果文本在外存中(和z獨(dú)立)!Pat樹的空間:O(N)Why?壓縮的優(yōu)點(diǎn):簡(jiǎn)單后綴trie的空間在最壞情況下是N+(N-1)+(N-2)+…1=O(N2)

2/28/2025建立后綴樹簡(jiǎn)單算法一個(gè)接一個(gè)的插入后綴:O(N2)

聰明的算法:O(N)McCreight,Ukkonen從左到右掃描文本，向樹中增加后綴的鏈接Honolulu$123456789

2/28/2025全文索引Pat樹不能裝進(jìn)內(nèi)存怎么辦?有一些外存結(jié)構(gòu):SPat數(shù)組字符串B-樹字符串B-樹:一個(gè)關(guān)于字符串的B樹,支持字典操作可以把所有后綴裝到里面支持文本搜索

2/28/2025字符串B-樹原始想法:文本存在樹外，字符用B+-樹表示其在文本中開始的位置這意味著訪問每個(gè)結(jié)點(diǎn)需要O(lgB)次想法–將每個(gè)結(jié)點(diǎn)的關(guān)鍵字組織成Patriciatrie.全文搜索的時(shí)間是:O((m+z)/B+logBN)

2/28/2025

8.3近似字符串匹配

2/28/2025DBLP作者搜索rmatik.uni-trier.de/~ley/db/indices/a-tree/index.html47

2/28/2025嘗試一下這些名字(goodluck!)rmatik.uni-trier.de/~ley/db/indices/a-tree/index.html48YannisPapakonstantinouMeralOzsoyogluMariosHadjieleftheriouUCSDCaseWesternAT&T--Research

2/28/2025

49

2/28/2025更好的系統(tǒng)?50/authors/

2/28/2025UCIrvine的人名搜索51/

2/28/2025WebSearch/jobs/britney.html查詢的錯(cuò)誤數(shù)據(jù)的錯(cuò)誤使得查詢和有意義結(jié)果接近Google搜集的實(shí)際查詢52

2/28/2025數(shù)據(jù)清洗Rinformixmicrosoft……Sinfromix…mcrosoft…53

2/28/2025問題的定義查找和給定字符串相似的字符串:dist(Q,D)<=δ例:找到和“hadjeleftheriou”相似的字符串性能很重要!10ms:100查詢/秒queriespersecond(QPS)5ms:200QPS54

2/28/2025基礎(chǔ)知識(shí)55

2/28/2025相似性函數(shù)相似性函數(shù):領(lǐng)域相關(guān)函數(shù)返回字符串間的相似性值例如:編輯距離Hamming距離Jaccard相似性SoundexTF/IDF,BM25,DICE……56

2/28/202557一種廣泛使用的字符串相似性測(cè)度Ed(s1,s2)=將s1變化到s2需要的最小操作數(shù)(增加、刪除、修改)例: s1:TomHanks s2:TonHank ed(s1,s2)=2編輯距離57

2/28/2025技術(shù):Oracle10gOracleTextCREATETABLEengdict(wordVARCHAR(20),lenINT);創(chuàng)建文本索引:

beginctx_ddl.create_preference('STEM_FUZZY_PREF','BASIC_WORDLIST');ctx_ddl.set_attribute('STEM_FUZZY_PREF','FUZZY_MATCH','ENGLISH');ctx_ddl.set_attribute('STEM_FUZZY_PREF','FUZZY_SCORE','0');ctx_ddl.set_attribute('STEM_FUZZY_PREF','FUZZY_NUMRESULTS','5000');ctx_ddl.set_attribute('STEM_FUZZY_PREF','SUBSTRING_INDEX','TRUE');ctx_ddl.set_attribute('STEM_FUZZY_PREF','STEMMER','ENGLISH');end;/CREATEINDEXfuzzy_stem_subst_idxONengdict(word)INDEXTYPEISctxsys.contextPARAMETERS('WordlistSTEM_FUZZY_PREF');使用方法: SELECT*FROMengdict WHERECONTAINS(word,'fuzzy(universisty,70,6,weight)',1)>0;限制:不能處理首字母錯(cuò)誤:KatherineVSCatherine58

2/28/202559MicrosoftSQLServerSQLServer2005提供數(shù)據(jù)清洗工具信息集成工具的一部分支持模糊查詢相似性函數(shù):基于TF/IDF的打分59

2/28/2025Lucene使用LevenshteinDistance(編輯距離).先基于前綴過濾，然后執(zhí)行搜索(效率?)60

2/28/2025基于Gram的算法61

2/28/2025“q-grams”universal2-grams62

2/28/2025編輯操作和gram的關(guān)系k

個(gè)操作會(huì)影響k*q

個(gè)gramuniversal固定長(zhǎng)度:q63如果ed(s1,s2)<=k,那么他們公共gram的數(shù)量>=(|s1|-q+1)–

k*

q

2/28/2025q-gram的倒排表idstrings01234richstickstichstuckstatic4230142-gramsatchckicristtatituuc2013012441243364

2/28/2025公共gram的數(shù)量>=3使用倒排表的搜索查詢:“shtick”,ED(shtick,?)≤1idstrings01234richstickstichstuckstatic2-gramsatchckicristtatituuc42301420130124412433tiicckshhttiicck65

2/28/2025T出現(xiàn)問題查找出現(xiàn)次數(shù)≥T的元素遞增順序合并66

2/28/2025例子T=4結(jié)果:1313510131013155713131567

2/28/2025序列合并算法HeapMergerMergeOpt[SK04][LLL08,BK02]ScanCountMergeSkipDivideSkip68

2/28/2025基于堆的算法Min-heap使用堆計(jì)算每個(gè)元素的出現(xiàn)次數(shù)Pushtoheap……69

2/28/2025MergeOpt算法長(zhǎng)序列:T-1短序列二分搜索70

2/28/2025MergeOpt的例子135101310131557131315閾值T≥4長(zhǎng)序列:3短序列:271

2/28/20257272ScanCount123…135101310131557131315閾值T≥4出現(xiàn)次數(shù)00041增加11Stringids1314150200結(jié)果

2/28/2025序列合并算法HeapMergerMergeOptScanCountMergeSkipDivideSkip[SK04][LLL08,BK02]73

2/28/2025MergeSkip算法Min-heap……PopT-1T-1Jump大于or等于74

2/28/2025MergeSkip的例子135101015571315閾值T≥4minHeap10131515Jump15151313171775

2/28/2025MergeSkip算法長(zhǎng)序列短序列二分搜索MergeSkip76

2/28/2025

長(zhǎng)度過濾Ed(s,t)≤2s:

t:

長(zhǎng)度:19長(zhǎng)度:10僅依靠長(zhǎng)度!77

2/28/2025位置過濾ababEd(s,t)≤2st(ab,1)(ab,12)78

2/28/2025基于Trie的方法79

2/28/2025Trieexampl$$emplar$t$sample$e字符串examexampleexemplarexemptsample80

2/28/2025Trie的活動(dòng)結(jié)點(diǎn)exampl$$emplar$t$sample$e前綴距離examp2exampl1example0exempl2exempla2sample2查詢