概述：
喬姆斯基（Noam Chomky）曾經(jīng)把語言定義為：按照一定規(guī)律構成的句子和字符串的有限或無限的集合。也有把語言看成一個數(shù)學系統(tǒng)....深奧椭豫，看不懂～～～
總之呢耻瑟，描述一種語言大致有如下三種途徑：
- 窮舉法
- 文法：每個句子都由嚴格定義的規(guī)則來構造，基于規(guī)則產(chǎn)生句子赏酥。我這里理解為我們語文中的語法規(guī)則喳整。什么主謂賓之類的～～～
- 自動機法：通過對輸入的句子進行合法性監(jiān)測區(qū)別哪些是語言中的句子，哪些不是今缚。
形式語言
也稱之為代數(shù)語言學算柳，用來精確的描述語言及其結構的手段。
形式語法的定義這里就不闡述了姓言，可以參考wiki瞬项。文法表示為：。
喬姆斯基將文法分發(fā)分為如下四種：
- 正則文法
- 上下文無關文法
- 上下文相關文法
- 無約束文法
自動機
理論太難懂了..... 簡單說就是由5組元素組成何荚，字符集囱淋，狀態(tài)集，狀態(tài)轉移餐塘，起始妥衣，末尾。5個要素。税手，
文法與自動機之間的關系
文法中的非終結符可以理解為自動機中的字符集蜂筹，終結符理解為狀態(tài)集，狀態(tài)轉移可以用規(guī)則轉換得到芦倒。
自動機的應用：編輯距離：從一個字符串轉變到另一個字符串最少步驟（插入艺挪，刪除，交換兵扬，修改）麻裳。場景應用：拼寫糾錯～。
拼寫糾錯
字母表A上的字母構成的所有合法單詞都是自動機中的一條路徑（有向圖）器钟。即一條路徑上從起始狀態(tài)到終止狀態(tài)連起來的字符串就是合法拼寫津坑。目標：尋找有向圖中編輯距小于給定閾值t的所有路徑。這些路徑就是滿足閾值t的相似拼寫集合傲霸。
當然疆瑰，當數(shù)據(jù)量大的話，為了提高搜索速度狞谱，則會采取剪枝操作乃摹。
其中
編輯距離
例如：ed（hanzhou，hangzhou） = 1伶跷，需要進行一次插入操作掰读。
主要思想：判斷當前是需要插入，交換叭莫，還是修改使得修改次數(shù)最小蹈集。
三種情況：
(1) ,當
。
(2),當
執(zhí)行交換操作
(3) ,其他情況
簡單解析：
min 操作就是判斷前一步驟是修改拢肆，還是刪除，還是插入靖诗。ed(X{[i]},Y{[i+1]}）是插入操作郭怪，ed(X{[i+1]},Y{[i]})刪除操作,ed（X{[i]},Y{[i]}）則是修改操作。
附頁
常見符號解釋
| 標記代碼 | 標記名稱 |
|---|---|
| ROOT | 要處理文本的語句 |
| IP | 簡單從句 |
| NP | 名詞短語 |
| VP | 動詞短語 |
| PU | 斷句符刊橘，通常是句號鄙才、問號、感嘆號等標點符號 |
| LCP | 方位詞短語 |
| PP | 介詞短語 |
| CP | 由‘的’構成的表示修飾性關系的短語 |
| DNP | 由‘的’構成的表示所屬關系的短語 |
| ADVP | 副詞短語 |
| ADJP | 形容詞短語 |
| DP | 限定詞短語 |
| QP | 量詞短語 |
| NN | 常用名詞 |
| NR | 固有名詞 |
| NT | 時間名詞 |
| PN | 代詞 |
| VV | 動詞 |
| VC | 是 |
| CC | 表示連詞 |
| VE | 有 |
| VA | 表語形容詞 |
| AS | 內(nèi)容標記（如：了） |
| VRD | 動補復合詞 |
| CD | 表示基數(shù)詞 |
來源原文：https://blog.csdn.net/lihaitao000/article/details/51812618
