演算法字典樹

Ⅰ 怎麼做字典樹

Tries樹是典型的用空間換時間的演算法。
如果要查找字元串，就算是hash，最快也要比較一次該單詞(遍歷一次該單詞)，而通常沖突是不可避免的。
Tries樹通過一顆二十六叉樹來存儲字典。
結點是這樣的:
struct node{
type data;

node* next[26];
int flag;

};
比如字元串acfg
那麼首先用root節點(這里置空)，判斷node->['a'-『a'](node初始為root)是否為空，如果不為空，則
node = node->['a'-'a']....依次到最後一個字母g，如果標記flag為1(表示是個單詞，避免只是另一個單詞的字串，比如acfgd;

Ⅱ 數據結構與演算法中，樹一般會應用在哪些方面為什麼

基礎類：二叉搜索（排序）樹，線索二叉樹，哈夫曼樹（最優二叉樹），二叉堆
平衡樹類：AVL，紅黑樹，2-3樹，2-3-4樹，B樹，B+樹，B-樹，treap，SBT。
優先隊列類：左高樹（左偏樹，可並堆，斜堆），雙端堆，斐波那契堆
集合類：並查集
區間樹類：線段樹，劃分樹，歸並樹，樹狀數組
字母樹類：字典樹，後綴樹。AC自動機演算法
動態樹類：伸展樹
計算幾何類：KD-tree （塊狀樹），4叉樹
RMQ轉LCA：笛卡爾樹
圖論相關：最小生成樹，無根樹
其它：敗者樹，博弈樹

Ⅲ 字典樹和二叉樹區別

字典樹和二叉樹區別有。
1、字典樹，是一種空間換時間的數據結構，又稱Trie樹、前綴樹，是一種樹形結構(字典樹是一種數據結構)，典型用於統計、排序、和保存大量字元串。
2、二叉樹是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，是樹也能簡單地轉換為二叉樹，而二叉樹的存儲結構及其演算法都較為簡單，二叉樹顯得很重要。二叉樹特點是每個結點最多隻能有兩棵子樹。

Ⅳ 怎樣做字典樹

What's on the tree?
There is an dictionary on the book

Ⅳ 演算法導論：後綴樹

參考資料：
在線構造後綴樹
Ukkonen's Algorithm構造後綴樹實錄
後綴樹系列
在閱讀本文之前，需要了解字典樹，請看 字典樹

下面將對後綴樹的構建以及優化做出詳細的介紹。

以字元串S=MISSISSIPPI$為例
S的所有後綴如下：
S[0…11]= MISSISSIPPI$           字元串本身，起始位置0
S[1…11]=   ISSISSIPPI$            起始位置1
S[2…11]=  SSISSIPPI$            起始位置2
S[3…11]=    SISSIPPI$            起始位置3
   .
   .
S[10…11]=         I$           起始位置10
S[11…11]=        $            終結符
字元串最後的$是人為添加的，這樣保證後綴的唯一性，不會出現橫跨多個字元串的後綴。

（1）將上述字元串的所有後綴加入到字典樹中，得到如下結構：

（2）將字典樹中沒有分支的路徑壓縮：

這種方法的含義就是給定一個字元串，直接構造後綴樹，不需要先構造字典樹。
在講這個方法之前，需要先了解一些概念：

在這里後綴樹中的結點分為兩大類，顯示結點，隱士結點。顯示節點就是那些分支處或者葉子節點，隱式節點是被壓縮的那些節點。還有用來輔助構造後綴樹的尾部鏈表，構造時，會沿著尾部鏈表進行更新。

首先第一個字元a開始，構建如圖所示，尾部鏈表從a的葉子節點指向根節點。現在我們插入下一個字元b，插入字元時說沿著鏈表進行更新的，這里先更新葉子節點，再更新根節點這個內部節點。

現在插入字元b

是在方法二的基礎上進行的優化，下面將喲用具體的例子進行講解，給出的字元串為abcabxabcd$。

首先構建字元a

我們在按規則插入之後，要在字元a後做一個標記，就像之前講的隱式結點，表示出有由a開始的後綴，a之後的字元就可以在這里操作。
為了記錄這些信息，我們需要引入一些概念：
1、活動點（active point)
是一個三元組(活動結點,活動邊, 活動長度)
2、剩餘後綴數（remainder）
還沒有在後綴樹中體現的後綴
  那對於上圖，活動點是多少呢？答案是（0，a，1）0表示額就是根節點，在這個結點上進行活動。a表示的是會在由根節點周圍a開始的那條邊上進行相關操作，1表示的是在一位字元後操作，也就是a後，如果是2呢那就是在b後操作。
  此時還沒有體現在後追樹上的後綴數是1.也就是後綴a，因為我們並不能找到a這個後綴，我們只是在a後做了標記，表示接下來會有由a開始的標記。

此時活動點變為了（0（根節點），none(無活動邊)，0(無長度)）,剩餘的後綴是x。
我們會發現圖中多了一條=由4指向6的索引。這個就是另一條規則。

在根據規則處理完所有的字元後，得到如圖所示的後綴樹，因為在整個過程中，只遍歷了一遍字元串，且沒有進行多餘的結點操作，只是記錄了一些信息，所以這個方法的時間復雜度是O(n)，可以在線性時間內完成。

Ⅵ 圖解：數據結構與演算法之字典樹

字典樹（Trie樹）這一數據結構是不太常見但是十分好用<typo id="typo-32" data-origin="而" ignoretag="true">而</typo>一種數據結構，博主也就是最近一段時間做了幾道位元組的題目才了解到字典樹這一數據結構。並將自己的學習內容跟大家分享。

首先，何為字典樹（Trie樹）？顧名思義，就是在查詢目標時，像字典一樣按照一定排列順序標准和步驟訪問樹的節點，舉一個簡單例子，英文字典查單詞"He"，那麼第一步你肯定要按照a-z的順序先找到h這個首字母，然後再按照相同順序找到e。博主所要介紹的字典樹就是類似字典這樣的結構。

上述查找單詞的過程就是不斷查找與所查單詞相同前綴的字元串，直至查找到所查單詞的最後一個字母。因此，字典樹又稱為前綴樹(prefix Tree)。

以hell、hi、new、nop為例建立一個字典樹，構造如下

根據上文所述可以得到字典樹的結構性質

根據以上三點來構造字典樹。

字典樹的構造其實較為簡單，和一般樹的構造沒有太大區別。接下來將對字典樹的插入、刪除、查詢操作進行分析與講解。

在沒有字典樹的時候，我們需要先構建出字典樹。

以插入hell為例：

再插入單詞hit，過程如下，檢查＝>存在則訪問/不存在則建立新節點再訪問＝>直到要插入的單詞到達最後一個字元。

字典樹的插入操作比較簡單，不需要考慮太多排序問題。

正如上文所說，按照一定的標准進行查詢目標字元串，每個節點都儲存一個字元，根節點到達子節點路徑組成的字元串即為該節點所對應的字元串，那麼查詢目標字元串時按照從根節點一步一步訪問相應字元所在的節點，其實也就是匹配字元串前綴的過程。

如下圖，在字典樹中，查詢"hell"，

[圖片上傳失敗...(image-f028c4-1611057619223)]

如果在該字典中查詢no

刪除操作相對於插入與查詢復雜一點，但是也很簡單，刪除的前提是單詞已經存在於字典樹。

刪除字典樹節點的操作需要考慮目標字元串最後一個字元是否是樹中的葉子節點。

因為一個單詞可能是另一個單詞的前綴部分，如果不是葉子節點，我們只需要把該單詞的單詞標志位清空即可，無需刪除整個「樹枝」。

比如，想要刪除"no"這個單詞

比如，想要刪除"hell"這個單詞，與第一種刪除相同，只不過是從最後一個節點，'l'節點是葉子節點，開始往上進行節點刪除操作。

比如，想要刪除"hi",那麼與前兩種其實一致，訪問到葉子節點'i',刪除葉子節點，並向上訪問，訪問到'h'，由於刪除'i'以後，'h'依然不是葉子節點，因此不再繼續刪除節點。

比如，想要刪除"nop",與前幾種類似，先訪問到葉子節點'p'刪除，然後上移發現'o'是葉子節點，然而'o'有單詞標記位，所以，這里不再繼續刪除。

有上面幾種刪除操作，我們得到了刪除的標准：

了解了這么多字典樹的各種操作，相信你對字典樹的用途有個大概了解了，字典樹最大作用是用於==字元串的各種匹配==，前綴匹配（模糊搜索），字元串查找（字典）等等。

博主只打出了「涓涓清泉」四個關鍵字，其搜索列表返回了諸多以涓涓清泉為首的選項

顧名思義，就是一個單純的字典而已，不多舉例。

字典樹的構建，通過利用空間換時間的思想以及字元串的公共前綴減少無效的字元串比較操作從而使得插入和查找字元串變得高效．其插入或者查找的時間復雜度為O(n)，n為字元串長度。

當然，字典樹有著它的弊端，當所插入的單詞沒有很多公共前綴時，字典樹的構建變得十分復雜和低效。

字典樹的難度不是很大，但卻是一種十分有用的數據結構，掌握之後，對於解決一些有關字元串匹配、公共前綴的問題十分有幫助。

當然我們也說了，字典樹有著自己的弊端，由於用空間換時間，如果遇到了一堆公共前綴很少的單詞進行字典樹構造時，空間需求就顯得十分大了。

Ⅶ 演算法筆記之前綴樹——字典序的第K小數字

前綴樹（字典樹）的一種應用場景，和傳統的前綴樹使用不太一樣，但是使用了其中的思想。

LeetCode 440. 字典序的第K小數字

定整數 n 和 k，找到 1 到 n 中字典序第 k 小的數字。

題目描述比較簡單，據說這是位元組跳動面試喜歡出的一道題。

首先簡單解釋下，字典序就是1、10、11、12這樣按照類似字典一樣的字元順序排序數字。

既然要用前綴樹的思想，那麼我們先把前綴樹畫出來。

我們可以看到相同前綴的數字可以放到一個子樹里，子樹的每個層級依次有1、10、100...個節點。

我們可以先判斷數字k屬於哪個子樹，然後在當前子樹往下一層級移動。然後重復找子樹和往下層移動的過程，直到找到節點（也就是數字）。

Ⅷ 數據結構與演算法中，樹一般會應用在哪些方面為什麼

數據結構就不多說了，樹以遞歸性質這一對計算機而言最普遍的描述結構簡直貫穿始終。查找樹字典樹四叉樹哪個都是樹的實際應用。除了低維結構不用樹描述（其實一維結構也可以看成是退化後的樹）。

演算法層面，樹基本上到處都是（當然有些時候是隱性的）。計算機執行指令是線性的，程序代碼也是順序的，是個一維結構，一旦需要解決高維問題，利用棧、隊列等一維基礎結構所能做到的只有樹，而樹則可以用來描述高維邏輯，起到了個橋梁作用。

演算法舉例如下。
狀態空間遍歷類：DFS、BFS

決策類：各種自動機（特例還有退化為一位情況的KMP）、貪心、分治、動態規劃（同屬狀態空間遍歷）、匹配
圖與流：尋路（最短路）、生成樹

應用舉例就更多了，例如XML、DOM樹、編譯器中的模式識別和語法樹、JSON數據傳遞、磁碟路徑結構……

樹的普遍取決於它的結構與通常解決問題的演算法的一致性和結構簡單嚴謹：遞歸定義、拓撲有序（無環）、實現簡單。當面臨高維狀態時，其它結構的處理方式幾乎一定不如轉化為樹來的簡單，所以就成為了組織一維實現與高維邏輯中的橋梁。

Ⅸ 自然語言處理（NLP）的基礎難點：分詞演算法

自然語言處理（NLP，Natural Language Processing）是人工智慧領域中的一個重要方向，主要研究人與計算機之間用自然語言進行有效通信的各種理論和方法。自然語言處理的底層任務由易到難大致可以分為詞法分析、句法分析和語義分析。分詞是詞法分析（還包括詞性標注和命名實體識別）中最基本的任務，也是眾多NLP演算法中必不可少的第一步，其切分准確與否往往與整體結果息息相關。

金融領域分詞的難點

分詞既簡單又復雜。簡單是因為分詞的演算法研究已經很成熟了，大部分的演算法（如HMM分詞、CRF分詞）准確率都可以達到95%以上；復雜則是因為剩下的5%很難有突破，主要可以歸結於三點：

▲粒度，即切分時的最小單位，不同應用對粒度的要求不一樣，比如「融資融券」可以是一個詞也可以是兩個詞

▲歧義，比如「恆生」一詞，既可指恆生公司，又可指恆生指數

▲未登錄詞，即未出現在演算法使用的詞典中的詞，比如不常見的專業金融術語，以及各種上市公司的名稱

在金融領域中，分詞也具有上述三個難點，並且在未登錄詞方面的難點更為突出，這是因為金融類詞彙本來就多，再加上一些專有名詞不僅有全稱還有簡稱，這就進一步增大了難度。

在實際應用中，以上難點時常會造成分詞效果欠佳，進而影響之後的任務。尤其是在一些金融業務中，有許多需要與用戶交互的場景，某些用戶會用口語化的詞彙描述業務，如果分詞錯誤會影響用戶意圖的解析，這對分詞的准確性提出了更高的要求。因此在進行NLP上層應用開發時，需要對分詞演算法有一定的了解，從而在效果優化時有能力對分詞器進行調整。接下來，我們介紹幾種常用的分詞演算法及其應用在金融中的優劣。

幾種常見的分詞演算法

分詞演算法根據其核心思想主要分為兩種：

第一種是基於字典的分詞，先把句子按照字典切分成詞，再尋找詞的最佳組合方式，包括最大匹配分詞演算法、最短路徑分詞演算法、基於N-Gram model的分詞演算法等；

第二種是基於字的分詞，即由字構詞，先把句子分成一個個字，再將字組合成詞，尋找最優的切分策略，同時也可以轉化成序列標注問題，包括生成式模型分詞演算法、判別式模型分詞演算法、神經網路分詞演算法等。

最大匹配分詞尋找最優組合的方式是將匹配到的最長片語合在一起，主要的思路是先將詞典構造成一棵Trie樹（也稱為字典樹），Trie樹由詞的公共前綴構成節點，降低了存儲空間的同時可以提升查找效率。

最大匹配分詞將句子與Trie樹進行匹配，在匹配到根結點時由下一個字重新開始進行查找。比如正向（從左至右）匹配「他說的確實在理」，得出的結果為「他／說／的確／實在／理」。如果進行反向最大匹配，則為「他／說／的／確實／在理」。

這種方式雖然可以在O(n)時間對句子進行分詞，但是只單向匹配太過絕對，尤其是金融這種詞彙較豐富的場景，會出現例如「交易費/用」、「報價單/位」等情況，所以除非某些詞的優先順序很高，否則要盡量避免使用此演算法。

最短路徑分詞演算法首先將一句話中的所有詞匹配出來，構成詞圖（有向無環圖DAG），之後尋找從起始點到終點的最短路徑作為最佳組合方式，例：

我們認為圖中每個詞的權重都是相等的，因此每條邊的權重都為1。

在求解DAG圖的最短路徑問題時，總是要利用到一種性質：即兩點之間的最短路徑也包含了路徑上其他頂點間的最短路徑。比如S->A->B->E為S到E到最短路徑，那S->A->B一定是S到B到最短路徑，否則會存在一點C使得d(S->C->B)<d(S->A->B)，那S到E的最短路徑也會變為S->C->B->E，這就與假設矛盾了。利用上述的最優子結構性質，可以利用貪心演算法或動態規劃兩種求解演算法：

（1）基於Dijkstra演算法求解最短路徑，該演算法適用於所有帶權有向圖，求解源節點到其他所有節點的最短路徑，並可以求得全局最優解；

（2）N-最短路徑分詞演算法，該方法是對Dijkstra演算法的擴展，在每一步保存最短的N條路徑，並記錄這些路徑上當前節點的前驅，在最後求得最優解時回溯得到最短路徑。這種方法的准確率優於Dijkstra演算法，但在時間和空間復雜度上都更大。

相較於最大匹配分詞演算法，最短路徑分詞演算法更加靈活，可以更好地把詞典中的片語合起來，能更好地解決有歧義的場景。比如上述「他說的確實在理」這句話，用最短路徑演算法的計算結果為「他／說／的／確實／在理」，避免了正向最大匹配的錯誤。但是對於詞典中未存在的詞基本沒有識別能力，無法解決金融領域分詞中的「未登錄詞」難點。

N-Gram（又稱N元語法模型）是基於一個假設：第n個詞出現與前n-1個詞相關，而與其他任何詞不相關。在此種假設下，可以簡化詞的條件概率，進而求解整個句子出現的概率。

現實中，常用詞的出現頻率或者概率肯定比罕見詞要大。因此，可以將求解詞圖最短路徑的問題轉化為求解最大概率路徑的問題，即分詞結果為「最有可能的詞的組合「。

計算詞出現的概率，僅有詞典是不夠的，還需要充足的語料，所以分詞任務已經從單純的「演算法」上升到了「建模」，即利用統計學方法結合大數據挖掘，對「語言」（句子出現的概率）進行建模。

我們將基於N-gram模型所統計出的概率分布應用到詞圖中，可以得到詞的概率圖。對該詞圖用最短路徑分詞演算法求解最大概率的路徑，即可得到分詞結果。

相較於前兩種分詞演算法，基於N-Gram model的分詞演算法對詞頻進行了統計建模，在切分有歧義的時候力求得到全局最優值，比如在切分方案「證券/自營/業務」和「證券/自/營業/務」中，統計出「證券/自營/業務」出現的概率更大，因此結果有更高的准確率。但也依然無法解決金融場景中未登錄詞的問題。

生成式模型主要有隱馬爾可夫模型（HMM，Hidden Markov Model）、樸素貝葉斯分類等。HMM是常用的分詞模型，基於Python的jieba分詞器和基於Java的HanLP分詞器都使用了HMM。

HMM模型認為在解決序列標注問題時存在兩種序列，一種是觀測序列，即人們顯性觀察到的句子，另一種是隱狀態序列，即觀測序列的標簽。假設觀測序列為X，隱狀態序列是Y，則因果關系為Y->X。因此要得到標注結果Y，必須對X的概率、Y的概率、P(X|Y)進行計算，即建立P(X,Y)的概率分布模型。

HMM演算法可以在一定程度上解決未登錄詞的問題，但生成式模型的准確率往往沒有接下來要談到的判別式模型高。

判別式模型主要有感知機、支持向量機（SVM，Support Vector Machine）、條件隨機場（CRF，Conditional Random Field）、最大熵模型等，其中感知機模型和CRF模型是常用的分詞模型。

（1）平均感知機分詞演算法

感知機是一種簡單的二分類線性模型，通過構造超平面，將特徵空間（輸入空間）中的樣本分為正負兩類。通過組合，感知機也可以處理多分類問題。但由於每次迭代都會更新模型的所有權重，被誤分類的樣本會造成很大影響，因此採用平均的方法，在處理完一部分樣本後對更新的權重進行平均。

（2）CRF分詞演算法

CRF可以看作一個無向圖模型，假設給定的標注序列為Y，觀測序列為X，CRF對條件概率P(Y|X)進行定義，而不是對聯合概率建模。

平均感知機演算法雖然速度快，但仍不夠准確。適合一些對速度要求高、對准確性要求相對不那麼高的場景。CRF分詞演算法可以說是目前最常用的分詞、詞性標注和實體識別演算法，它對未登陸詞也有很好的識別能力，是目前在速度、准確率以及未登錄詞識別上綜合表現最突出的演算法，也是我們目前所採用的解決方案，但速度會比感知機慢一些。

在NLP中，最常用的神經網路為循環神經網路（RNN，Recurrent Neural Network），它在處理變長輸入和序列輸入問題中有著巨大的優勢。LSTM（Long Short-Term Memory，長短期記憶網路）為RNN變種的一種，在一定程度上解決了RNN在訓練過程中梯度消失和梯度爆炸的問題。

目前對於序列標注任務，業內公認效果最好的模型是BiLSTM+CRF。相比於上述其它模型，雙向循環神經網路BiLSTM，可以更好地編碼當前字等上下文信息，並在最終增加CRF層，核心是用Viterbi演算法進行解碼，以得到全局最優解，避免B,S,E這種不可能的標記結果的出現，提高准確率。

神經網路分詞雖然能在准確率、未登錄詞識別上有更好的表現，但RNN無法並行計算，在速度上沒有優勢，所以該演算法通常在演算法研究、句子精確解析等對速度要求不高的場景下使用。

分詞作為NLP底層任務之一，既簡單又重要，很多時候上層演算法的錯誤都是由分詞結果導致的。因此，對於底層實現的演算法工程師，不僅需要深入理解分詞演算法，更需要懂得如何高效地實現和調試。

而對於上層應用的演算法工程師，在實際分詞時，需要根據業務場景有選擇地應用上述演算法，比如在搜索引擎對大規模網頁進行內容解析時，對分詞對速度要求大於精度，而在智能問答中由於句子較短，對分詞的精度要求大於速度。