① 自然語言處理（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底層任務之一，既簡單又重要，很多時候上層演算法的錯誤都是由分詞結果導致的。因此，對於底層實現的演算法工程師，不僅需要深入理解分詞演算法，更需要懂得如何高效地實現和調試。
而對於上層應用的演算法工程師，在實際分詞時，需要根據業務場景有選擇地應用上述演算法，比如在搜索引擎對大規模網頁進行內容解析時，對分詞對速度要求大於精度，而在智能問答中由於句子較短，對分詞的精度要求大於速度。
② 字元串匹配演算法的使用（未完待整理）
字元串的匹配在Java中都知道使用indexOf函數來實現，那麼其匹配演算法是怎麼樣的呢？
單模式和多模式的區別就是一次遍歷主串能否將多個模式的字元串都查找出來。
英文全稱為Brute Force，暴力匹配演算法，匹配字元串的方法比較暴力，也比較簡單易懂。其大概的思路就是：
我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那麼總共需要尋找(n-m+1)次，且每次都需要比對m次，那麼時間復雜度將是 (n-m+1)*m ，即 O(n*m) ；但實際上並不會這么低效，因為我們的使用場景中主串和模式串都不會太長，而且在每個子串和模式串進行比對時，只要中途有一個不匹配，那麼當前比對就會提前結束，因此大部分情況下，時間復雜度都會比 O(n*m) 要好。
我們在BF演算法的基礎上引入哈希演算法，我們不需要將每個子串與模式串逐個字元地進行比較，而是計算得出每個子串的hash值，然後和模式串的hash值進行比較，如果有相等的，那就說明有子串和模式串匹配上了。
雖然我們只需要比對模式串和子串的hash值就能得到匹配結果，次數為(n-m+1)，但是對每個子串進行hash計算的時候，是要遍歷每個字元的，因此次數也是m，那麼總的時間復雜度還是 O(n*m) ，並沒有明顯地提升。
那麼我們該如何想出一個辦法，使得每個子串hash值的計算時間得到提升呢？這就是RK演算法的精髓，假設子串包含的字元集中元素個數為k，那麼就用k進制數來代表這個子串，然後hash的過程就是將這個k進制的數轉換為十進制的數，這個十進制的數就是該子串的hash值。
相鄰子串的hash值計算是有規律的，我們只需要遍歷一次主串就能得到所有子串的hash值，演算法復雜度為O(n)，而不是像原先一樣，每個子串都需要O(m)的時間復雜度。
然後將模式串的hash值和所有子串的hash值進行比較，每次比較的時間復雜度是 O(1) ，總共比較(n-m+1)次，所以RK演算法的總的時間開銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時間復雜度比BF演算法更加高效。
當然，有hash的地方就有可能會存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內容就是不一樣，此時怎麼辦呢？其實很簡單，對於hash值一樣的子串，我們增加雙保險，再比較一下這m個字元是否都一樣即可，總的時間開銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。
如果極端情況下出現了很多hash沖突呢？我們對於每個和模式串相同hash值的子串都需要逐一再進行比較，那麼總的時間開銷就會為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過這種概率太小了，大部分情況下都不會這樣。
在真正的文本編輯器中查找和替換某個字元串時，使用的演算法既不是上述的BF演算法，也不是RK演算法；BF演算法只適合不是很長的主串，RK演算法則要設計一個沖突概率很低的hash演算法，這個比較困難，所以實際使用的是BM演算法，它是工程中非常常用的一種字元串匹配演算法，效率也是最高的。
演算法的思想和過程有些復雜，待以後整理。
KMP演算法在本質上是和BM演算法一樣的。演算法的思想和過程有些復雜，待以後整理。
瀏覽器輸入框中的智能輸入匹配是怎麼實現的，它是怎麼做動態字元串匹配查找的呢？這就用到了Trie樹。
又名字典樹，是一種專門用來快速查找字元串前綴匹配結果的樹形結構，其本質就是將所有字元串的重復的前綴合並在一起，構造一個多叉樹。
其中，根節點不包含任何信息，每個節點表示一個字元，從根節點到紅色節點的一條路徑表示存儲的一個字元串。當我們在如上Trie樹中查找"he"時，發現"he"並非是一個字元串，而是"hello"和"her"的公共前綴，那麼就會找到這兩個字元串返回。
Trie樹在內存中是如何存儲的呢？因為每一個節點都可能是包含所有字元的，所以每一個節點都是一個數組（或者散列表），用來存儲每個字元及其後綴節點的指針。
使用Trie樹，最開始構建的時候，時間復雜度為 O(n) ，其中n為所有字元串長度之和，但是一旦構建完成，頻繁地查詢某個字元串是非常高效的，時間復雜度為 O(k) ，其中k為查找字元串的長度。
Trie樹雖然查詢效率很高，但是比較浪費內存，每一個節點都必須維護一個數組存放所有可能的字元數據及其指向下一個節點的指針，因此在所有字元串公共前綴並不多的時候，內存空間浪費地就更多了。這種問題其實也有對應的解決辦法，我們可以不使用數組，而是使用有序數組、散列表、紅黑樹來存放，可以相應地降低性能來節省內存空間。
Trie樹除了可以實現瀏覽器動態輸入內容查找候選項的功能外，還可以實現多模式地敏感詞匹配功能。假設我們需要對用戶輸入的內容進行敏感詞檢查，將所有的敏感內容用***代替，那麼該如何實現呢？
首先我們可以維護一個敏感詞字典，使用上述四種單模式匹配演算法也可以實現，但是需要遍歷N次用戶輸入的內容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們如果將敏感詞字典維護為一個Trie樹，然後將用戶輸入的內容從位置0開始在Trie樹中進行查詢，如果匹配到紅色節點，那麼說明有敏感詞；如果沒有匹配到紅色節點，就從用戶輸入內容的下一個位置開始繼續在Trie樹中查詢，直至將用戶輸入內容遍歷完，因此我們只是遍歷了一遍主串。
然而更高效的多模式字元串匹配使用地更多的是如下的AC自動機。
如果把Trie樹比作BF演算法，KMP演算法是BF演算法的改進，那麼AC自動機就是利用同樣的思想改進了Trie樹。
演算法的思想和過程有些復雜，待以後整理。