hanlp中的N最短路径分词
N-最短路徑?是中科院分詞工具NLPIR進(jìn)行分詞用到的一個(gè)重要算法，張華平、劉群老師在論文《基于N-最短路徑方法的中文詞語粗分模型》中做了比較詳細(xì)的介紹。該算法算法基本思想很簡(jiǎn)單，就是給定一待處理字串，根據(jù)詞典，找出詞典中所有可能的詞，構(gòu)造出字串的一個(gè)有向無環(huán)圖，算出從開始到結(jié)束所有路徑中最短的前N條路徑。因?yàn)樵试S相等長度的路徑并列，故最終的結(jié)果集合會(huì)大于或等于N。
根據(jù)算法思想，當(dāng)我們拿到一個(gè)字串后，首先構(gòu)造圖，接著針對(duì)圖計(jì)算最短路徑。下面以一個(gè)例子“他說的確實(shí)在理”進(jìn)行說明，開始為了能夠簡(jiǎn)單說明，首先假設(shè)圖上的邊權(quán)值均為1。?
先給出對(duì)這句話的3-最短路(即路徑最短的前3名, 因?yàn)橛胁⒘谐煞? 所以可能候選路徑大于3)徑求解過程圖：?
從節(jié)點(diǎn)4開始, 因?yàn)?是第一個(gè)出現(xiàn)多個(gè)前驅(qū)節(jié)點(diǎn)的
?
首先看圖中上方，它是根據(jù)一個(gè)已有詞典構(gòu)造出的有向無環(huán)圖。它將字串分為單個(gè)的字，每個(gè)字用圖中相鄰的兩個(gè)結(jié)點(diǎn)表示，故對(duì)于長度為n的字串，需要n+1個(gè)結(jié)點(diǎn)。兩節(jié)點(diǎn)間若有邊，則表示兩節(jié)點(diǎn)間所包含的所有結(jié)點(diǎn)構(gòu)成的詞，如圖中結(jié)點(diǎn)2、3、4構(gòu)成詞“的確”。
圖構(gòu)造出來后，接下來就要計(jì)算最短路徑，N-最短路徑是基于Dijkstra算法的一種簡(jiǎn)單擴(kuò)展，它在每個(gè)結(jié)點(diǎn)處記錄了N個(gè)最短路徑值與該結(jié)點(diǎn)的前驅(qū)，具體過程如上圖中下方列表。Table(4)表示位于結(jié)點(diǎn)4時(shí)的最短路徑情況，表示從結(jié)點(diǎn)0到4有兩條路徑，長度為3的路徑前驅(qū)為2；長度為4的路徑前驅(qū)為3。前驅(qū)括號(hào)里面第二個(gè)數(shù)表示對(duì)相同前驅(qū)結(jié)點(diǎn)的區(qū)分，如（4,1）、（4,2）。由列表可知，該字串的3-最短路徑結(jié)果集合為｛5,5,6,6,7｝。
當(dāng)然，在實(shí)際情況中，權(quán)值不可能都設(shè)為1的，否則隨著字串長度n和最短路徑N的增大，長度相同的路徑數(shù)將會(huì)急劇增加。為了解決這樣的問題，我們需要通過某種策略為有向圖的邊賦權(quán)重，很自然的想法就是邊的權(quán)重就是該詞出現(xiàn)的可能性。
NShortPath的基本思想是Dijkstra算法的變種，拿1-最短路來說吧，先Dijkstra求一次最短路，然后沿著最短路的路徑走下去，只不過在走到某個(gè)節(jié)點(diǎn)的時(shí)候，檢查到該節(jié)點(diǎn)在路徑上的下一個(gè)節(jié)點(diǎn)是否還有別的路到它（從PreNode查），如果有，就走這些別的路中的沒走過第一條（它們都是最短路上的途徑節(jié)點(diǎn)）。然后推廣到N-最短路，N-最短路中PreNode有N個(gè)，分別對(duì)應(yīng)n-最短路時(shí)候的PreNode，就這么簡(jiǎn)單。
圖解
再談PreNode的準(zhǔn)備
需要為每個(gè)頂點(diǎn)維護(hù)一個(gè)最小堆，最小堆里儲(chǔ)存的是邊的花費(fèi)，每條邊的終點(diǎn)是這個(gè)頂點(diǎn)。還需要維護(hù)到每個(gè)頂點(diǎn)的前N個(gè)最小路徑的花費(fèi)：
回憶一下Dijkstra求最短路的時(shí)候，我們只需記錄一個(gè)最短路的累計(jì)花費(fèi)就行了
這與此處的N-最短路徑顯著不同。
在遍歷圖的時(shí)候，與Dijkstra最短路徑不同，N-最短路徑從第二個(gè)節(jié)點(diǎn)開始，需要將當(dāng)前節(jié)點(diǎn)可能到達(dá)的邊根據(jù)累積第i短長度+該邊的長度之和排序記錄到PreNode隊(duì)列數(shù)組中，排序由CQueue完成的。
然后從CQueue出隊(duì)，這樣路徑長度就是升序了，按順序更新?weightArray當(dāng)前節(jié)點(diǎn)就行了。
另外CQueue是一個(gè)不同于普通隊(duì)列的隊(duì)列，它維護(hù)了一個(gè)當(dāng)前指針（下圖的藍(lán)色部分），這個(gè)藍(lán)色指針在求解第i短路徑的時(shí)候會(huì)用到。
假定看到這里，算法已經(jīng)計(jì)算出了正確的PreNode隊(duì)列，下面討論如何從PreNode中找出N最短路徑的確切途經(jīng)節(jié)點(diǎn)集合。
1-最短路徑的求解
整個(gè)計(jì)算過程維護(hù)了一個(gè)路徑棧，對(duì)于上圖來說，
1）首先將最后一個(gè)元素壓入棧（本例中是6號(hào)結(jié)點(diǎn)），什么時(shí)候這個(gè)元素彈出棧，什么時(shí)候整個(gè)任務(wù)結(jié)束。
2）對(duì)于每個(gè)結(jié)點(diǎn)的PreNode隊(duì)列，維護(hù)了一個(gè)當(dāng)前指針，初始狀態(tài)都指向PreNode隊(duì)列中第一個(gè)元素。這個(gè)指針是由CQueue維護(hù)的，嚴(yán)格來講不屬于算法關(guān)心的問題。
3）從右向左依次取出PreNode隊(duì)列中的當(dāng)前元素（當(dāng)前元素出隊(duì)）并壓入棧，并將隊(duì)列指針重新指向隊(duì)列中第一個(gè)元素。如上圖：6號(hào)元素PreNode是3，3號(hào)元素PreNode是1，1號(hào)元素PreNode是0。
4）當(dāng)?shù)谝粋€(gè)元素壓入棧后，輸出棧內(nèi)容即為一條隊(duì)列。本例中0, 1, 3, 6便是一條最短路徑。
5）將棧中的內(nèi)容依次彈出，每彈出一個(gè)元素，就將當(dāng)時(shí)壓棧時(shí)該元素對(duì)應(yīng)的PreNode隊(duì)列指針下移一格。如果到了末尾無法下移，則繼續(xù)執(zhí)行第5步（也就是繼續(xù)出棧），如果仍然可以移動(dòng)，則執(zhí)行第3步。
對(duì)于本例，先將“0”彈出棧，在路徑上0的下一個(gè)是1，得出該元素對(duì)應(yīng)的是1號(hào)“A”結(jié)點(diǎn)的PreNode隊(duì)列，該隊(duì)列的當(dāng)前指針已經(jīng)無法下移，因此繼續(xù)彈出棧中的“1” ；同理該元素對(duì)應(yīng)3號(hào)“C”結(jié)點(diǎn)，因此將3號(hào)“C”結(jié)點(diǎn)對(duì)應(yīng)的PreNode隊(duì)列指針下移。由于可以移動(dòng)，因此將隊(duì)列中的2壓入隊(duì)列，2號(hào)“B”結(jié)點(diǎn)的PreNode是1，因此再壓入1，依次類推，直到0被壓入，此時(shí)又得到了一條最短路徑，那就是0，1，2，3，6。如下圖：
再往下，0、1、2都被彈出棧，3被彈出棧后，由于它對(duì)應(yīng)的6號(hào)元素PreNode隊(duì)列記錄指針仍然可以下移，因此將5壓入堆棧并依次將其PreNode入棧，直到0被入棧。此時(shí)輸出第3條最短路徑：0, 1, 2, 4, 5, 6。如下圖：
輸出完成后，緊接著又是出棧，此時(shí)已經(jīng)沒有任何棧元素對(duì)應(yīng)的PreNode隊(duì)列指針可以下移，于是堆棧中的最后一個(gè)元素6也被彈出棧，此時(shí)輸出工作完全結(jié)束。我們得到了3條最短路徑，分別是：
0, 1, 3, 6,
0, 1, 2, 3, 6,
0, 1, 2, 4, 5, 6,
推廣到N-最短路
N-最短路中PreNode有N個(gè)，分別對(duì)應(yīng)n-最短路時(shí)候的PreNode，也就是當(dāng)前路徑是第n短的時(shí)候，當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的PreNode隊(duì)列。
在該圖中，觀察黃顏色的路徑長度表格，到達(dá)1號(hào)、2號(hào)、3號(hào)結(jié)點(diǎn)的路徑雖然有多條，但長度只有一種長度，但到達(dá)4號(hào)“D”結(jié)點(diǎn)的路徑長度有兩種，即長度可能是3也可能是4，此時(shí)在“最短路”處（index＝0）記錄長度為3時(shí)的PreNode，在“次短路”處（index＝1）處記錄長度為4時(shí)的PreNode，依此類推。
值得注意的是，此時(shí)用來記錄PreNode的坐標(biāo)已經(jīng)由前文求“1-最短路徑”時(shí)的一個(gè)數(shù)（ParentNode值)變?yōu)?個(gè)數(shù)（ParentNode值以及index值）。
如上圖所示，到達(dá)6號(hào)“末”結(jié)點(diǎn)的次短路徑有兩個(gè)ParentNode，一個(gè)是index=0中的4號(hào)結(jié)點(diǎn)，一個(gè)是index=1的5號(hào)結(jié)點(diǎn)，它們都使得總路徑長度為6。
當(dāng)N=2時(shí)，我們求得了2-最短路徑，路徑長度有兩種，分別長度為5和6，而路徑總共有6條，如下：
最短路徑：
0, 1, 3, 6,
0, 1, 2, 3, 6,
0, 1, 2, 4, 5, 6,
========================
次短路徑
0, 1, 2, 4, 6,
0, 1, 3, 4, 5, 6,
0, 1, 2, 3, 4, 5, 6,
文章來源于random-walk的博客
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的hanlp中的N最短路径分词的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： NodeJS：将指定文件夹内所有文件重命
- 下一篇： hadoop学习笔记2