2/28/2025第八章

字符串算法王宏志計算機科學與工程系

2/28/2025

8.1精確字符串匹配

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

T

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

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

s

–

最小的整數(0￡s￡n

–

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

2/28/2025簡單匹配算法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簡單匹配算法的分析最壞情況:外層循環:n–m內層循環:m總計(n–m)m=O(nm)何種輸入產生最壞情況?最好情況:n-m何時?完全隨機的文本和模式:O(n–m)

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

2/28/2025基于指紋的算法令字母表位S={0,1,2,3,4,5,6,7,8,9}令指紋為一個十進制數,即,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]運行時間是2O(m)+O(n–m)=O(n)!

2/28/2025使用Hash函數問題:我們不能假設我們可以對m位數在O(1)時間內進行算術運算解決方案:使用hash函數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”

算術運算:(a+b)modq=(amodq+bmodq)modq(a*b)modq=(amodq)*(bmodq)modq

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

–

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

在預處理中計算一次例:LetT[…]=“5319”,q=7,對應的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

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

2/28/2025應用中的Rabin-Karp算法如果字母表有d個字母，將字母翻譯為d進制數字，即用d代替算法中的10選擇素數q>m

可以利用隨機算法在O(m)時間內完成,或者q

是一個固定大素數且一個計算機字可以容納10*q.Rabin-Karp比較簡單，可以容易地拓展到2維模式匹配.

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

P=“Tweedledum”T=“pappar”

P=“pappappappar”

2/28/2025一般情況算法的狀態:檢查移動s,匹配了P

中的q個字符在T中看到了一個未匹配的字符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自動機搜索算法:預處理:對于每個q(1￡q￡m-1)和每個a?S預先計算一個q的新值，記為s(q,a)

填一個大小為m|S|的表掃描文本

當不匹配發現時(P[q]1T[s+q]):置

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

匹配階段

O(n)

內存過多:O(m|S|),過多的預處理O(m|S|).

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

P

中的q個字符發現了T中不匹配的字符a.需要發現:最大前綴

“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前綴表我們可以預先計算大小為m的前綴表來存儲p[q]的值(0￡q<

m)計算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上執行KMP算法的本質.

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

O(m)空間:O(m)

2/28/2025逆簡單算法如果從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運行時間和簡單算法相同

2/28/2025啟發式方法Boyer和Moore向逆向簡單算法中增加了啟發式規則，得到了

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

，P=“date”T=“teakettle”

，P=“kettle”

2/28/2025偏移表在預處理中,計算大小為|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分析最壞情況運行時間預處理:O(|S|+m)搜索:O(nm)何種輸入達到此界?總計:O(nm)空間:O(|S|)和m獨立在真實數據集合上很快

2/28/2025

8.2字符串查找數據結構

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

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

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

–

從集合中刪除等于x的字符串假設,標記:n

個字符串,N

個字母m

–x的長度子母表的大小d=|S|

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

可以節約空間考慮字符串的比較查找長度為m的字符串的最壞時間是多少？

2/28/2025TriesTrie

–

存儲字符串集合的數據結構(名字來源于

“retrieval”):假設每個字符串以

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

2/28/2025TriesIItrie的性質:多路樹.每個結點有從1到d

個兒子.每條邊有一個字母做標記.每個葉子結點存儲字符串，這個字符串是從根到葉子所有字符的連接.

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])如何執行刪除?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結點結構“實現細節”結點結構是什么？=t.child(c)操作的復雜性是什么?:大小為d的兒子指針數組：浪費空間，但是child(c)是O(1)兒子指針的hash表，較少浪費空間，child(c)的期望是O(1)兒子指針鏈表：空間小但是child(c)在最壞情況下是O(d)兒子指針的二分搜索樹:空間小且child(c)最壞情況下是O(lgd)

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

O(dm),O(mlgd),O(m)和BST比較？觀察:為單個結點建立鏈較為浪費空間

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

2/28/2025緊縮TriesII實現:字符串在結構外用一個數組保存，邊的標記放在一個數組中可以用來做單詞匹配：找到給定的單詞出現在文本的位置.使用緊縮trie存儲文本中所有單詞緊縮trie中的每個兒子保存文檔中對應單詞出現的位置.

2/28/2025利用Tries進行字符匹配查找單詞P:在每個結點上,沿著(i,j)查找,從而P[i..j]=T[i..j]如果沒有這樣的邊,T中沒有P,否則，當到達葉子的時候，找到所有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進行字符匹配II根據給定文本建立緊縮:如何做？運行時間:O(N)單詞匹配的復雜性:O(m)當本文在外存中時?最壞情況下需要O(m)次I/O操作來訪問文本中的單個字母-效率不高

2/28/2025PatriciatriePatriciatrie:

一種緊縮trie其中每個邊的標記用(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在內存)為單詞匹配建立PatriciaTrie:通常使用二分patriciatries:考慮文本和查詢的二進制編碼樹上的每個兒結點有兩個兒子(0和1）邊上僅標記越過的數值(位)12345678910121416182022242628303234363840f?texharhaftenf?dselsdagT:

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

T

=“carrara”模式

P=“ar”輸出t:P

在T

中的所有出現重新定義問題:找到T的所有以P為前綴的后綴我們已經看到了如何處理一個單詞前綴查詢carrara

arrararrararara

araraa

2/28/2025后綴樹后綴樹

–

一種包含文本所有后綴的緊縮trie(或類似的結構)后綴的Patriciatrie有時叫做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樹:分析對P進行的文本搜索是一種前綴查詢.運行時間:O(m+z),其中z

是結果數量僅O(1)次如果文本在外存中(和z獨立)!Pat樹的空間:O(N)Why?壓縮的優點:簡單后綴trie的空間在最壞情況下是N+(N-1)+(N-2)+…1=O(N2)

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

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

2/28/2025全文索引Pat樹不能裝進內存怎么辦?有一些外存結構:SPat數組字符串B-樹字符串B-樹:一個關于字符串的B樹,支持字典操作可以把所有后綴裝到里面支持文本搜索

2/28/2025字符串B-樹原始想法:文本存在樹外，字符用B+-樹表示其在文本中開始的位置這意味著訪問每個結點需要O(lgB)次想法–將每個結點的關鍵字組織成Patriciatrie.全文搜索的時間是: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更好的系統?50/authors/

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

2/28/2025WebSearch/jobs/britney.html查詢的錯誤數據的錯誤使得查詢和有意義結果接近Google搜集的實際查詢52

2/28/2025數據清洗Rinformixmicrosoft……Sinfromix…mcrosoft…53

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

2/28/2025基礎知識55

2/28/2025相似性函數相似性函數:領域相關函數返回字符串間的相似性值例如:編輯距離Hamming距離Jaccard相似性SoundexTF/IDF,BM25,DICE……56

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

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

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;限制:不能處理首字母錯誤:KatherineVSCatherine58

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

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

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

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

2/28/2025編輯操作和gram的關系k

個操作會影響k*q

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

k*

q

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

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

2/28/2025T出現問題查找出現次數≥T的元素遞增順序合并66

2/28/2025例子T=4結果:1313510131013155713131567

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

2/28/2025基于堆的算法Min-heap使用堆計算每個元素的出現次數Pushtoheap……69

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

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

2/28/20257272ScanCount123…135101310131557131315閾值T≥4出現次數00041增加11Stringids1314150200結果

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算法長序列短序列二分搜索MergeSkip76

2/28/2025

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

t:

長度:19長度:10僅依靠長度!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的活動結點exampl$$emplar$t$sample$e前綴距離examp2exampl1example0exempl2exempla2sample2查詢