數(shù)據結構（從概念到算法）課件

第4章字符串、多維數(shù)組與廣義表01020304目錄CONTENTS05字符串多維數(shù)組廣義表應用實例本章小結01PART字符串4.1.1字符串的定義字符串是由零個或者多個字符組成的有限序列，一般記為：S="a1

a2…an"（n≥0）其中S是字符串的名稱；雙引號（""）括起來的字符序列為串值，雙引號本身不屬于串值，只是代表串的起止標記；序列中的ai（1≤i≤n）可以是字母、數(shù)字和其他字符，i稱為字符ai

在該串中的位置；n表示串的長度，即串中包含的字符個數(shù)，當n=0時，稱為空串（nullstring）；僅含若干個空格的串稱為空格串。將字符串中任意個連續(xù)字符組成的子序列稱為該串的子串，對應地，將包含子串的串稱為主串。子串在主串中的位置是指子串的第一個字符在主串中的位置。字符串4.1.1字符串的定義串是線性表的一個特例，其特殊性體現(xiàn)在每一個數(shù)據元素就是一個字符，因此完全可以沿用線性表定義的操作、線性表的存儲方案。然而，在實際應用中，對字符串的處理較少涉及對單個字符的處理，一般都是涉及對串進行整體操作?；谶@個原因，給出如下串的抽象數(shù)據類型定義。字符串4.1.2字符串的存儲結構及其基本運算的實現(xiàn)與線性表類似，通常字符串也有順序存儲和鏈式存儲兩大類，對應的有順序串和鏈串。而順序存儲又可以細分為靜態(tài)存儲分配和動態(tài)存儲分配，這樣字符串的存儲結構就可以分為3類。1．靜態(tài)存儲分配的順序串該存儲結構就是通過字符數(shù)組的方式分配連續(xù)的存儲空間來保存串值。數(shù)組的存儲空間是在編譯時確定的，并且運行時不能改變連續(xù)空間的大小，這樣能表示的字符串長度最大值就固定下來了，所以這種形式表示的串也稱為串的定長順序存儲表示。示例如下：字符串4.1.2字符串的存儲結構及其基本運算的實現(xiàn)由這個定義可知，S就是一個大小為256的字符數(shù)組，最多能存放256個字符。如果用它來表示串，我們就需要明確指示串的尾部在什么位置。一般需要1個字符的單元來表示這個邊界，還剩下255個字符單元，所以S能夠表示的串最大長度就是255，如果超過這個最大值，我們就必須截取，丟棄超長部分，造成數(shù)據的丟失。不同高級語言中會采用不同的方式表示這個邊界，如C語言中以“\0”表示串的結束；再如，Pascal語言用第一個字符的單元記錄長度，即用S[0]記錄串長。這樣分別對應方式一和方式二兩種形式的順序串，如下圖所示。字符串4.1.2字符串的存儲結構及其基本運算的實現(xiàn)2．動態(tài)存儲分配的順序串由于定長順序串的空間是在編譯階段就確定的，運行階段不能夠改變空間大小，這樣就會出現(xiàn)一些常見的問題：預留空間太大、串長較小而造成空間的浪費；如果空間不是足夠大，在做插入、聯(lián)接操作時可能會舍棄超長部分，造成數(shù)據的丟失。為此，我們可以考慮采用線性表中動態(tài)存儲分配的順序表，利用動態(tài)分配函數(shù)malloc，根據串長來申請分配串需要的空間，并用free函數(shù)來釋放串空間。由于使用malloc函數(shù)申請內存空間時是在程序運行時邏輯空間中的堆空間（heapspace）進行的，所以動態(tài)存儲分配的順序串也被稱為串的堆存儲分配表示。其數(shù)據類型的定義如下：字符串4.1.2字符串的存儲結構及其基本運算的實現(xiàn)這樣，通過HStringS定義的變量S來表示串“Iamastudent”時，就可以根據串長在堆空間分配內存單元，地址保存在S.ch，串長記錄在S.length中，如下圖所示。字符串4.1.2字符串的存儲結構及其基本運算的實現(xiàn)3．串的鏈式存儲與線性表類似，串也可以采用鏈式存儲結構來表示，如使用單鏈表，串的鏈式存儲結構也稱為鏈串，如下圖（a）所示。使用鏈式存儲結構能方便地進行插入與刪除等操作，且能避免大量移動字符。鏈式存儲結構類型定義如下。字符串4.1.2字符串的存儲結構及其基本運算的實現(xiàn)如果在一個結點存放1個字符，占1字節(jié)，在32位系統(tǒng)中指針需要占4字節(jié)，所以鏈串的存儲密度為20%，存儲密度是相當?shù)偷?；如果?4位系統(tǒng)，存儲密度會更低。為了提高存儲密度，這里可以考慮在一個結點中存放多個字符，比如放4個字符，如圖（b）所示。通常將一個結點數(shù)據域存放的字符數(shù)定義為結點大小。對于一個非空串，由于串的長度不一定正好是結點大小的整數(shù)倍，因此在最后一個結點需要填充特殊的符號，代表串的結束。對于結點大小大于1的鏈式存儲，其類型定義的一般形式如下。字符串4.1.2字符串的存儲結構及其基本運算的實現(xiàn)雖然通過調大結點能夠提高存儲密度，但同時串的操作會變得復雜，串的插入和刪除操作同樣會移動大量的字符。例如，在圖（b）所示的串位置3之前插入串"XYZ"，就需要將位置3后續(xù)所有結點中的字符進行移動，其中一些字符還是跨結點移動，結果如圖4.3（c）所示。由此可見，當使用結點大小大于1的鏈式串存儲時，對一些串的操作會變得不太方便，不如順序串的操作簡單和靈活。字符串4.1.3字符串的模式匹配算法子串定位操作StrIndex(S,T,pos)，求串T在S中第pos個字符后第一次出現(xiàn)的位置。子串定位操作也稱為串的模式匹配，其中主串S稱為目標串，子串T稱為模式串。假定目標串S的長度為n，模式串T的長度為m，S和T分別表示如下。在實際應用中，通常m遠小于n，即m?n。S="s1s2…sn"T="t1t2…tm“串模式匹配操作就是在目標串S中找到一個與模式串T相等的子串"sisi+1…si+m-1"，這里i取符合條件的最小值（pos≤i≤n-m）。如果存在這樣的i，表示匹配成功，否則表示匹配失敗，模式串T不是目標串S的子串。字符串4.1.3字符串的模式匹配算法1．樸素的模式匹配算法假設目標串S和模式串T都采用定長順序存儲結構，用指示變量i來表示每次進行匹配時目標串S的起點位置，初始值為pos。每次匹配從目標串S第i個字符開始，與模式串T的字符依次比較，如果S[i]……S[i+m-1]與T[1]……T[m]依次對應相等，則匹配成功，返回i值，否則i加1，測試下一個匹配起點，進行下一次匹配。如果所有可能的匹配起點測試后都沒有匹配成功，返回0。字符串4.1.3字符串的模式匹配算法該算法采用的是暴力求解方式，該算法也稱為樸素的模式匹配算法。其中，模式匹配算法如下。字符串4.1.3字符串的模式匹配算法2．一種改進的模式匹配算法采用樸素的模式匹配算法進行匹配的過程中，一旦出現(xiàn)S[i]≠T[j]，就結束本次匹配過程，將模式串T向后滑動1個字符的位置，j回到1，i回到下一輪匹配的起點，開始新的一輪匹配。這種算法思想簡單明了，很容易理解。但由于沒有充分地分析模式串T的特征，所以該算法的效率不高。不少學者在模式匹配算法優(yōu)化方面做了大量的研究工作，提出不少效率較高的算法，其中KMP算法就是一個有代表性的改進算法。字符串4.1.3字符串的模式匹配算法在模式匹配過程中，一旦S[i]≠T[j]，就會出現(xiàn)一次失敗的模式匹配如下圖所示。為了表示方便，下圖中用si表示S[i]，tj表示T[j]。對于模式串T

的字符tj，如果存在一個

k（1<k<j），使“t1t2…tk-1”=“tj-k+1tj-k+2…tj-1”，即模式串T

的前

k-1

個字符組成的子串與T

[j]之前k-1

個字符組成的子串是相等的，根據匹配過程，有“sj-k+1sj-k+2…sj-1”=“tj-k+1tj-k+2…tj-1”，所以可以推導出“sj-k+1sj-k+2…sj-1”=“t1t2…tk-1”。就沒有必要讓j恢復到1，i回到本次匹配的起點之后，需要做的就是將k賦予j實現(xiàn)滑動模式串T，使T[k]（對應tk）與S[i]（對應si）對齊；將模式串T的第k個字符（也是T[j]）與S[i]繼續(xù)比較即可，避免了對模式串T的前k-1個字符做重復比較。這個處理方式中，i沒有回退動作，j也不一定回到模式串T的起點，顯然提高了匹配效率。字符串4.1.3字符串的模式匹配算法

基于上述思想，在進行匹配之前，首先需要對模式串T進行分析，對模式串T的每一個位置j需要求出一個滿足上述性質的k值，記作next[j]=k。這樣，在匹配過程中，一旦出現(xiàn)S[i]≠T[j]，就可以通過修改j值為k，實現(xiàn)滑動模式串T的動作，繼續(xù)進行比較。next[j]的公式如下。

next[j]的本質，就是求解滿足"t1t2…tk-1"="tj-k+1tj-k+2…tj-1"的最大真子串"t1t2…tk-1"，即最大k值，使得一旦出現(xiàn)S[i]≠T[j]時，通過賦值操作j=k，將模式串T向后滑動j-k字符的位置，T[k]與S[i]對齊，最大限度減少重復比較次數(shù)，從而提高算法效率。字符串4.1.3字符串的模式匹配算法

其中，KMP算法如下。字符串4.1.3字符串的模式匹配算法

下面是對模式串T進行分析，求next[j]值的算法。該算法采用遞推的思想，根據next[1],…,next[j]的值來求解next[j+1]。02PART多維數(shù)組4.2.1多維數(shù)組概念的引入

多維數(shù)組4.2.2多維數(shù)組的順序存儲本小節(jié)介紹分配連續(xù)的存儲單元，保存全部的數(shù)組元素，即數(shù)組的順序表示。在順序表示中，要考慮的有這樣幾個問題：①需要多大的空間；②如何來放置數(shù)組的元素；③如何管理這個連續(xù)的空間；④如何訪問數(shù)組元素。一維數(shù)組A=(a1,a2,…,an)需要一個能存儲n

個元素的連續(xù)空間，并依據元素的邏輯次序a1到an，將元素依次存放到這個連續(xù)空間中。為了管理這些數(shù)據元素，還需要一個結構變量A，如下圖所示。該結構變量中要包含連續(xù)空間起始地址、數(shù)組的維數(shù)、每一維的下界和上界。多維數(shù)組4.2.2多維數(shù)組的順序存儲假定b為連續(xù)單元的起始地址，每個元素占L個存儲單元，則元素ai前面有i-1個元素，占有的單元數(shù)為(i-1)L，所以元素ai的地址計算公式為：LOC(i)=b+(i-1)L=LOC(1)+(i-1)L這個公式也稱為尋址公式或映像函數(shù)。通過尋址公式，當下標i合法時，可以隨機地訪問元素ai。至于存放方式，二維以上的多維數(shù)組就會涉及一個存放次序的問題。第一種方式稱為行序優(yōu)先，即將二維數(shù)組的元素逐行地保存在連續(xù)存儲空間中，存放結果如左圖所示。多維數(shù)組4.2.2多維數(shù)組的順序存儲第二種方式稱為列序優(yōu)先，即將二維數(shù)組的元素逐列地保存在連續(xù)存儲空間中，存放結果如下圖所示。同理分析出列序優(yōu)先時aij的地址計算公式為：LOC(i,j)=b+((j-1)×m+i-1)L=LOC(1,1)+((j-1)×m+i-1)L多維數(shù)組4.2.3矩陣的壓縮存儲對于一些規(guī)模不大的矩陣，使用二維數(shù)組的順序存儲方式，通常是能夠有效地完成計算的。但在實際應用中，往往會出現(xiàn)一些階數(shù)很高的矩陣，同時矩陣中可能會出現(xiàn)很多值相同的元素或零元素，這時，如果還采用順序存儲方式，存儲開銷就會很大，甚至系統(tǒng)無法滿足存儲要求。基于這個原因，我們對這類矩陣需要進行壓縮存儲。對值相同的元素只分配一個元素的存儲單元，對零元素則不需要保存，這種存儲方式稱為矩陣的壓縮存儲。矩陣的壓縮存儲有兩類：一類是特殊矩陣的壓縮存儲；另一類是稀疏矩陣的壓縮存儲。多維數(shù)組4.2.3矩陣的壓縮存儲1．特殊矩陣的壓縮存儲在特殊矩陣中值相同的元素或零元素，其分布都有著一定規(guī)律?？紤]其特殊性，不一定要保存全部的數(shù)據元素，如只保存部分數(shù)據元素，沒有保存

的數(shù)據元素可以通過分析它們與已保存數(shù)據元素之間的關系進行訪問。這種矩陣的存儲方式稱為特殊矩陣的壓縮存儲。（1）對稱矩陣一個

n

階方陣

A

中的元素如果滿足

aij=aji（1≤i，j≤n），則稱方陣

A

為對稱矩陣。右圖所示為一個6

階方陣且為對稱矩陣。考慮圖中元素之間的對稱性，這里可以保存約一半多的數(shù)據元素；剩下未保存的利用其對稱性進行訪問。多維數(shù)組4.2.3矩陣的壓縮存儲首先，需要明確對一個對稱矩陣需要保存哪些數(shù)據元素，以及有多少個元素。由其對稱性可知aij等于aji，所以對稱元素只需要保存其中一個，訪問aij等價于訪問aji，反之亦然。這樣就只需保存對角線以下的所有數(shù)據元素（含對角線），即下三角部分；或者只需保存對角線以上的所有數(shù)據元素（含對角線），即上三角部分。如圖所示，以行序優(yōu)先的方式將下三角存儲到一維數(shù)組SA中，其中aij對應存儲在SA[k]。多維數(shù)組4.2.3矩陣的壓縮存儲（2）三對角矩陣右圖所示為三對角矩陣。除其對角線上的元素外，其他元素值都是0（也可以都是取某一個特殊值的數(shù)）。三對角矩陣，只需要存儲3條對角線上的元素，零元素不需要保存或只保存一個。下圖以行序優(yōu)先的方式將對角線上元素存儲到一維數(shù)組SA中，其中aij對應存儲在SA[k]，零元素（或某一個特殊值的數(shù)）存儲在SA[0]中。多維數(shù)組4.2.3矩陣的壓縮存儲2．稀疏矩陣的壓縮存儲實際應用中，常常會遇到一種矩陣，其零元素很多，非零元素很少，且非零元素在矩陣中的位置沒有特定的規(guī)律，稱這種矩陣為稀疏矩陣。稀疏矩陣沒有一個明確的定義，只是從形式上看，非零元素的個數(shù)占元素總數(shù)的比例低于某特定的閾值。下圖中矩陣M和其轉置矩陣N各有42個數(shù)組元素，其中只有8個是非零元素。多維數(shù)組4.2.3矩陣的壓縮存儲由于圖中非0元素很少，因此只需保存這些非零元素，沒有保存的都是零元素。為了標明每個非零元素在矩陣中的位置，可以用(行,列,值)的三元組形式來表示非零元素。將所有的非零元素，按行序優(yōu)先的方式排列起來，就得到一個三元組的線性表，再加上稀疏矩陣的行數(shù)和列數(shù)這兩個屬性值組成的二元組，得到的這種特殊線性表稱為三元組表。由三元組表能唯一地確定稀疏矩陣。三元組表這種特殊線性表參照線性表的存儲結構，既可以采用順序存儲結構，也可以采用鏈式存儲結構。多維數(shù)組4.2.3矩陣的壓縮存儲（1）三元組順序表以順序存儲結構來表示三元組表，得到稀疏矩陣的一種壓縮存儲方式，我們稱這種存儲方式為三元組順序表。數(shù)據類型定義如下。多維數(shù)組4.2.3矩陣的壓縮存儲有了三元組順序表類型TriSeqList的定義后，就可以使用它定義結構變量來表示一個稀疏矩陣的三元組表。下表所示為前面圖中稀疏矩陣M和N的三元組順序表。（a）M

的三元組順序表

（b）N

的三元組順序表行號列號值11101616321234365228638974517566………………768行號列號值11102312252836894336475157666116………………678多維數(shù)組4.2.3矩陣的壓縮存儲（2）十字鏈表以鏈式存儲結構來表示三元組表，得到稀疏矩陣的另一種壓縮存儲方式。由于二維數(shù)組元素有行關系和列關系，因此三元組的結點需要兩個指針來維護這兩個關系，于是有了帶兩個指針的三元組結點。采用三元組表的鏈式存儲結構時，首先是每行非零元素的三元組結點構成一個單鏈表，然后需要一個行頭指針數(shù)組來保存所有行的頭指針，同樣需要一個列頭指針數(shù)組。為了管理這兩個頭指針數(shù)組，同時提供完整的矩陣信息，使用一個結構型數(shù)據（包含兩個頭指針數(shù)組的信息及稀疏矩陣的行、列數(shù)等），這種存儲結構稱為十字鏈表。右圖為稀疏矩陣M。多維數(shù)組4.2.3矩陣的壓縮存儲稀疏矩陣M的十字鏈表存儲結構如下圖所示。可見，每行的非零元素結點構成一個單鏈表，其中結點中的列號遞增有序；每列的非零元素結點也構成一個單鏈表，其中結點中的行號遞增有序。多維數(shù)組4.2.3矩陣的壓縮存儲十字鏈表的數(shù)據類型定義如下。03PART廣義表4.3.1廣義表的定義廣義表是線性表的推廣，其也稱為列表。廣義表是n（n≥0）個元素的有限序列，記為：LS=(a1,a2,L,an)其中，LS表示廣義表名；n表示廣義表LS的長度；元素ai（1≤i≤n）或者是數(shù)據元素，或者是廣義表（通常約定用大寫字母表示廣義表的名稱，小寫字母表示數(shù)據元素）。當廣義表的元素是一個數(shù)據元素時，稱其為原子，否則稱該元素為廣義表或子表。廣義表有別于線性表，線性表中的元素僅限于原子項，而廣義表中的元素既可以是原子項，也可以是一個廣義表這樣的數(shù)據結構。當廣義表非空時，稱第一個元素

a1為廣義表

LS

的表頭（head），稱其余元素組成的表(a2,…,an)為廣義表LS

的表尾（tail）。廣義表4.3.1廣義表的定義下面通過一些廣義表的例子，可以幫助理解什么是廣義表。A=()：A

是一個空廣義表，其長度為0。B=(x,y)：B

是一個長度為2

的廣義表。由于其元素都是原子，因此它也是線性表C=(a,(b,c))：C

是一個長度為2

的廣義表。其第一個元素是原子，第二個元素是廣義表。D=(A,B,C)：D

是一個長度為3

的廣義表。其每個元素都是廣義表，將A、B

和C

帶入后，D=((),(x,y),(a,(b,c)))。E=(A,D)：E

是一個長度為2

的廣義表。其每個元素都是廣義表，其中A

也是D

的元素。這個例子表明廣義表允許共享子表。F=(a,F)：F

是一個長度為2

的廣義表。其第一個元素是原子，第二個元素是廣義表自身。展開后，F(xiàn)=(a,(a,(a,…)))就是一個無限的廣義表。這個例子表明廣義表允許遞歸定義。廣義表4.3.1廣義表的定義除了按元素的序列形式定義廣義表外，還可以用圖形的方式表示廣義表，如用小圓圈表示廣義表，如果廣義表有名稱，則將廣義表名稱附在小圓圈內；用小正方形表示原子。廣義表結點用箭頭依次指向它的各個元素。例如，上面給出的D、E、F這3個廣義表對應的圖形表示如下圖所示。稱形狀像一棵倒長著樹的廣義表（如廣義表D）為純表，允許結點共享的廣義表（如廣義表E）為再入表，形如廣義表F的稱為遞歸表。廣義表4.3.2廣義表的存儲由于廣義表的元素既可以是原子也可以是廣義表，每個元素所需的空間大小無法統(tǒng)一，很難用一種有效的順序存儲結構表示，因此通常采用鏈式結構表示。根據元素的類型不同，廣義表中的結點可分為兩種：一種是原子結點，它包括兩個屬性值，即結點類型和原子的值；另一種是廣義表結點，由于廣義表非空時可以分解成表頭和表尾，這樣廣義表結點包括3個屬性值，即結點類型、表頭指針和表尾指針。為了統(tǒng)一管理這兩種結點，可以采用聯(lián)合形式來為這兩種結點定義結點類型。在這個類型中，公共部分是結點類型，用以識別當前結點是原子結點還是廣義表結點。根據結點類型確定對結點的訪問方式，如果是原子結點，聯(lián)合成員atom有效，否則就是聯(lián)合成員ptr有效，它包含表頭和表尾兩個指針。廣義表4.3.2廣義表的存儲廣義表結點數(shù)據結構的定義如下。廣義表4.3.2廣義表的存儲這樣就可以通過GList定義一個廣義表結點的指針變量來表示一個廣義表。根據這個定義，以廣義表A、B、C和D為例，其鏈式存儲結構示意圖如下圖所示。廣義表4.3.2廣義表的存儲當廣義表的存儲結構確定后，就可以實現(xiàn)廣義表的基本操作。下面介紹了幾個常用基本操作的遞歸算法實現(xiàn)。（1）創(chuàng)建廣義表假定將廣義表定義形式表示成一個字符串，根據這個字符串構造廣義表的鏈式存儲結構。該算法有兩個遞歸出口：一個是字符串為“()”時，生成空廣義表；另一個是字符串只包含一個字符時，表示原子元素的值，需要生成原子結點。對非空廣義表形式的字符串進行遞推處理，首先生成一個廣義表結點，取廣義表字符串的表頭和表尾字符串，分別由這兩個字符串構造鏈式存儲結構作為廣義表結點的表頭和表尾。廣義表4.3.2廣義表的存儲（2）廣義表的輸出廣義表的輸出需要根據廣義表的鏈式存儲結構，輸出其字符串的定義形式。該算法有兩個遞歸出口：一個是對空廣義表，輸出字符串“()”；另一個是對原子結點，顯示原子元素值。對廣義表結點，需要采用遞推處理，先輸出表頭，再輸出表尾。

下圖展示了輸出廣義表L的過程。①開始時L指向的是整個廣義表，輸出左小括號；②當廣義表結點表頭指針指向一個原子結點時，輸出原子元素值，如a；③當廣義表結點表頭指針指向廣義表結點時，輸出左小括號（特別地，當廣義表結點表頭指針為空時，對應輸出是一個小括號）；④當廣義表結點表尾指針指向廣義表結點時，輸出逗號；⑤當廣義表結點表尾指針為空時，輸出右小括號。這樣下圖的輸出結果為(a,(b,c,())。廣義表4.3.2廣義表的存儲

04PART應用實例4.4.1最大匹配分詞算法在漢字語言處理中，如何準確地將漢字序列分離成一個個具有實際意義的詞是其最基礎、最重要的功能之一，這個功能稱為中文分詞。通常中文分詞算法可分為三大類：基于字符串匹配的分詞算法、基于理解的分詞算法和基于統(tǒng)計的分詞算法。在基于字符串匹配的分詞算法中，中文分詞需要借助詞典來實現(xiàn)，詞典的結構以及查找算法的設計往往對分詞算法的效率有很大影響?；谧址ヅ涞姆衷~通常采用最大匹配法算法，它能夠保證將詞典中存在的最長復合詞在句子中切分出來。最大匹配法算法又分為正向最大匹配算法和逆向最大匹配算法兩種。應用實例4.4.1最大匹配分詞算法（1）正向最大匹配算法正向最大匹配算法（MaximumMatchingMethod），簡稱MM算法。具體策略是在計算機中存放一個已知的詞典，假定詞典中的最長詞有k個漢字，則在對句子進行分詞時，首先取句子的前k個漢字作為匹配串，在詞典中查找。若詞典中存在一個長度為k個漢字的詞與之相等，則匹配成功，將匹配串作為一個詞從句子中切分出來，對句子剩余部分繼續(xù)按MM算法進行分詞處理；如果詞典中找不到這樣一個長度為k個漢字的詞，則匹配失敗，再取句子的前k-1個漢字作為匹配串，繼續(xù)在詞典中進行匹配處理，如此進行下去，直到匹配成功，或者匹配串的長度為1（注意我們可以默認單個漢字就是一個詞，即使在詞典中沒有也算一個詞）。將該詞從句子中切分出來，再對句子剩余部分繼續(xù)按MM算法進行分詞處理，直到句子剩余部分為空，完成句子的分詞。應用實例4.4.1最大匹配分詞算法（2）逆向最大匹配算法逆向最大匹配算法（Reverse

Maximum

Matching

Method），簡稱

RMM

算法。具體策略與

MM算法相同，兩者區(qū)別是RMM切詞時，掃描方向是從句子的右到左取匹配串進行匹配。以句子“華中科技大學今日開學”為例，。采用正向最大匹配算法分詞時，首先查以“華”字開頭的詞，這里假定字典中的詞最長為10，這時就要取出前10個漢字的匹配串“華中科技大學今日開學”在詞典中查找，查找失敗后再取前9個漢字的匹配串詞典中查找，……匹配串的長度不斷減1，到了6時，匹配成功得到第一個詞“華中科技大學”；然后將其從句子中去掉，剩下部分為“今日開學”，假定詞典中沒有這個詞，但有“今日”和“開學”，按算法思想，最終得到分詞結果為：華中科技大學/今日/開學。應用實例4.4.1最大匹配分詞算法顯然，這個算法有很大的盲目性，詞庫中詞的最大長度不好確定；另外，在取出匹配串后，可能要與相應漢字開頭的所有字符串進行比較，

效率大打折扣。為此，需要在詞典的存儲結構和算法流程上進行綜合考慮，以提高分詞的效率。首先考慮詞典的存儲結構。在詞典中，將第一個漢字相同的詞按長度遞減的方式進行存放。為了消除詞庫中詞的最大長度對匹配串提取的影響，以及避免不必要的字符串比較，每個詞的存放格式是詞的長度和詞的漢字序列，最后需要一個結束標記（比如0）代表某漢字開頭的詞到此結束，后續(xù)是其他漢字開頭的詞。同時建立一個索引表，每個表項包含一個漢字和該漢字開頭的詞在詞典中的起始位置。右圖就是按這樣方式組織的詞典存儲結構。應用實例4.4.1最大匹配分詞算法算法實現(xiàn)時，消除詞庫中詞的最大長度這個屬性值對算法的影響，根據實際情況來取出匹配串進行比較，可以避免盲目取匹配串進行比較操作。給定一個待分詞的句子S，依據詞庫LexTable進行分詞，詞庫的索引表為indexTable，算法流程如下。（1）當

S

非空時，用

S

的長度初始化分詞長度

LexLen，轉步驟（2），否則算法結束。（2）取S

的第一個漢字到word0，根據word0

通過indexTable查找得到以word0

中詞開頭的詞在詞庫中的起始位置

i。如果

i

不為-1，轉步驟（3），否則表示詞庫中沒有以

word0

中詞開頭的詞，此時可以單獨將

word0

中詞作為一個詞，顯示

word0，并從

S

中刪除

word0，轉步驟（1）。（3）根據S長度計算S最大可能取出的漢字序列長度LexLen，通過與LexTable[i]表示的詞長度LexTable[i][0]進行比較，跳過詞庫中所有以word0開頭且長度大于LexLen的詞，定位到第一個長度不大于LexLen的詞，避免不必要的比較。應用實例4.4.1最大匹配分詞算法（4）當i定位到第一個長度不大于LexLen的詞LexTable[i]后，根據該詞的長度在S中取一個長度為LexTable[i][0]的漢字