學習總結
在ER中，有一類算法依靠參考結構化數據庫的模型實現，以便提高ER的速度。但是這類算法常常在運行中產生了大量重復計算，降低了效率。由此，通過介紹以下方法，來解決這個問題：
塊分割
給定的字符串：
X=x1,...xn;其中既有單詞又有標點
子序列：
s1,...,sp;對X進行分割后，生成的包含一個或多個單詞的字符串
sp=(tp,up,y);tp起始位置，up為結束位置，y為特征
特征集合：
Y=y1,..,yj；先后有序令y表示X中子序列的特征
例子：
x1x2x3表示一個人名；x5x6x7x8表示一個題目；
人名，題目用yj表示；
子序列s1=x1x2x3。
其中s1的起始位置用t1表示（這里t1=2），結束位置用u1=3表示。
并且
最大不超過X的長度，最小不低于1.
第二個子串的起始位置在第一個子串結束位置之后的第一個單詞，也就是相鄰子串之間沒有空隙，是連續的。
最后一個子串up結束的位置為X序列結束位置，第一個子串s1起始位置為X序列第一個單詞。
注意up的下標p，對應子序列sp中的p，下標的計數p跟子串個數S相關，把X分成10個子串，那么P=10，且起始位置tp與結束位置up的下標是一致的，例s1（t1，u1），s2（t2，u2）
特征提取函數：
y'表示前一個特征，y表示當前特征，X表示字符串，tj，uj同上描述。
特征提取函數集g1,...gv，每個一個特征函數（就是一種分割方法）都會有一個與其對應的權重wk。
通過使用維特比算法從這些特征函數中找到使得權重和最大的特征提取函數序列，換句話說，權重和最大表示了該特征提取函數序列對X進行了最優化分割。
這一過程是在訓練中完成。接下來將介紹最優化分割。
最優化分割：
s*表示在所有s1,...,sp中，得分最高的一個si。
由于每個特征提取函數g都會生成一個序列s1,...,sp，所以需要維特比算法找到一條路徑，使得改路徑上的每一個s都達到最大值。
該算法將形成一條路徑，該路徑上每一個si：y都是整個Si：y集合中的最大值,用
y'表示前一個特征，其作用是概率傳遞，意思是，在計算完第一個特征值后，其值將影響下一個特征值的計算，以此類推，形成一條路徑。若沒有y'，則退化成簡單最大值計算問題。
y1 y2 y3 . . . ym s1 s1max . . . . s1 s2max s2 . s2 s3 s3 . s3 . . . . . . . . . . . . . . . . . si si . . . . . . . . . si i行m個列，每次計算從m個列中選取一個，計算到下一個列的距離(從第i行的m個節點中挑一個計算到i+1行m個節點的距離)，m*m，一共計算i行， 其復雜度為O(IM2)
σ(1,y)表示在序列s2中，y1特征得到了最大值。依據公式（1），在對y2計算時，將選取s2作為起點，將其值傳入下一步計算。也就是說y2的最大值受y1影響。
從m個分詞中挑選一個分詞，計算該分詞到下一個分詞的值（以前一個分詞為起點，把下一個所有特征的分詞都計算一遍）。
維特比算法
維特比算法是一個特殊但應用最廣的動態規劃算法，利用動態規劃，可以解決任何一個圖中的最短路徑問題。其優點是利用動態規劃降低復雜度。而維特比算法是針對一個特殊的圖——籬笆網絡的有向圖（Lattice )的最短路徑問題而提出的。 它之所以重要，是因為凡是使用隱含馬爾可夫模型描述的問題都可以用它來解碼。
假設整個籬笆有向圖中每一列節點最多有m個（也就是圖的寬度為D），并且圖一共有N列，那么，每次計算至多計算m*m次（從i列的m個節點中挑一個計算到i+1列m個節點的距離）。至多計算N次。那么復雜度驟減為O（Nm2）m的平方，遠遠小于窮舉O（mN)m的n次方。
馬爾科夫鏈是對多參數條件概率計算的化簡，假設某一點的條件概率只和其之前某點相關，與其他點無關。這樣就形成了概率傳遞鏈。
為了比較算法的優劣，我們設計了一個時間下線，即在最好的情況下的時間消耗。用空間換時間是優化算法的一個常用的方法。存儲大量中間生成組件，并重復利用，避免了重新生成部件的過程，減少了時間，但存儲空間變大了。
)
)
