CH1、导论

1.1语音与语言处理中的知识

·语音学与音系学，研究语言的语音：能够接收并分析人发出的声音信号；生成人能识别的生成信号

·形态学，研究词的有意义的组合：产生并识别单词的变体，如can't

·句法学，研究词与词之间的结构关系：组词成句

·语义学，研究意义：解决词的不同意思，了解语言实体的意义

·语用学，研究如何用语言来达成一定的目的：回答语的情感，如直接的，委婉的，客气的等

·话语学，研究大于话段的语言单位：使用代词？这里不太懂

1.2歧义

语言中存在歧义，会产生不同的意思。

英文中：单词的词性；一词多义；代词的指代；动词的用法，如及物不及物会引起歧义。同时，除了书面，语音中会引起同音的歧义。例如：I&eye

问：中文中有什么特别的歧义吗？

目前主要有两大解决方法：词汇排歧与句法排歧。其中词汇排歧分词类排歧（POS）和词义排歧（word sense disambiguation）；句法排歧例如根据概率剖析判断实体关系。

除了以上两种，还可以根据语言行为解释方法来解决，如判断一个句子是陈述句还是疑问句

1.3模型与算法

模型与理论中最重要的部分大多来源于状态机、形式规则系统、逻辑以及概率论和其他机器学习工具。其中最重要的算法是状态空间搜索算法和动态规划算法。

第一种要讨论的模型是状态机，状态机是形式模型

第二种要讨论的是陈述模型，最重要的是正则语法、正则关系、上下文无关语法、特征增益语句等

第三种要讨论的是逻辑模型。传统方法上，语义、语用很大程度上依赖依赖逻辑。

第四种概率论。以上三种模型都可以使用概率得到进一步提升。

概率论同时也是一种机器学习方法。

1.4语言、思维和理解

1.5学科现状与近期发展

1.6语音和语言处理简史

计算机科学（自然语言处理）、电子工程（语音识别）、语言学（计算语言学）与心理认知语言学（computational psycholiguistics）等不同领域都有研究。

领域研究最早可以追溯到第二次世界大战结束，计算机刚刚发明的时代。

1957年开始分为两个学派：符号派&随机派。符号派主要由语言学家与计算机科学家在两个方面进行研究：一方面研究形式语言理论和生成句法；另一方面研究人工智能。随机派主要由统计学家和电子学研究人员，应用贝叶斯解决最优字符识别问题。

1970年出现四个paradigm：随机范型、逻辑范型、自然语言理解范型、话语模型范型

1983年经验主义与有限状态模型复苏

1994年概率与数据驱动的方法几乎成为自然语言处理的标准方法。

ch2、政策表达式与自动机

2.1正则表达式

正则表达式的搜索要求有一个试图搜索的模式pattern和一个被搜索的文本语料库corpus

1.基本正则表达式模式：

正则表达式对大小写敏感；

[]内的字符是或者的关系；

正则表达式[1234567890]可以表达任何简单数字；

-可以表示某一范围内的字符，如A-Z表示一个大写字母；

^表示不出现某个单独字符，但是仅当^在第一个字符时才起效果；

？表示前一个字符可有可无；

*表示前面一个字符可以出现零次或连续出现多次；

+表示前面一个字符出现一次或者多次；

.是一个通配符，表示任何一个字符；

.*表示任何一个字符串；

\b表示词界

2.pipe symbol、组合以及优先级

|表示或者的关系；

（）将多个字符组合成让机器以为是一个字符；

（）也可以用来表示算符之间的优先关系；

3.高级算符

{n}前面一个字符匹配n次；

{n,m}前面一个字符出现n到m词；

{n,}前面一个字符至少出现n次；

在引用特殊符号前要加\，如*；

4.利用正则表达式进行替换

s/(原表达式)/(新表达式)就可以进行替换；

\1表示回过头去参照第一个模式

2.2有限状态机(finite-state automaton)

正则表达式时自然语言处理的计算工作的理论基础。

有限状态机可以由五个参数来定义：

1）N种状态的有限集合

2）有限的输入符号字母表

3）初始状态

4）终止状态的集合

5）状态之间的转移函数或者转移矩阵

1.确定性识别算法

D-RECOGNIZE，是一种没有选择的算法，对于任何的输入，算法总是知道怎样工作。

算法第一步：初始化index，使之成为传送带的爱头

算法第二步：初始化自动机的状态使之成为current-state

接下来算法进入一个loop不断检查是否已经到达输入的终点。若到达输入的重点则判断是接受输入还是拒绝输入；若未到达输入的终点则根据转移表判断下一步地状态，并更新index和current-state的值。若转移表中没有值则直接拒绝输入。

2.形式语言

形式语言是一种模型，这个模型能够而且仅能够生成或者识别满足形式语言的定义所要求的某一形式语言的字符串。他是字符串的集合，而每个字符串由字母表的有限地符号的集合组合而成。

形式语言和自然语言是不同的，但通常我们使用形式语言来模拟自然语言的某些部分。

3.非确定FSA

非确定PSA又叫NFSA，带有判断点的自动机称为NFSA，或者存在没符号的弧。

在非确定自动机模型中存在选择问题，对于非确定问题有三个解决方法：backup、look-ahead、parallelism；对于回退算法，我们需要记住两点：1.机器将进入的状态；2.输入带子上的相应位置。

NFSA的例子和算法语言没看懂

NFSA系统的探索自动机中所有可能的解的路径的算法称为状态空间搜索算法。这种算法定义一个空间，空间内包含所有可能的解。提高算法的关键在于空间的顺序。NFSA在处理状态顺序时用到的状态通常被称为深度优先搜索或者后进先出策略，通过栈来实现。第二种状态探索方法是广度优先搜索或者叫先进先出，通过队列来实现。深度优先算法可能陷入死循环，广度优先算法可能耗费相当大的存储量，所以适合小规模。对于大规模则更适合动态规划和A*

4.DFSA与FNFSA的关系

对于任何NFSA存在一个完全等价的DFSA

how？没看懂

2.3正则语言与FSA

由于由正则表达式所定义的语言类恰好也是有有限自动机所刻画的语言类，所以我们把这些语言统称为正则语言。正则语言定义如下：

正则语言定义

正则语言定义看不懂了

正则表达式与自动机等价的证明可以分为两个部分，第一：证明对于每一个正则语言都可以建立一个自动机；第二证明每一个自动机都可以建立一个正则语言。

但要特别注意的是正则表达式中的存储器\1是无法实现成自动机的。

CH3、词与转录机

首先了解一个概念：形态剖析。剖析是指取一个输入并且产生出关于这个输入的各类语言结构，可以是形态结构、句法结构、语义结构或话语结构，产生的形式也可以是多样的。形态剖析中一个重要算法就是有限状态转录机。在实际应用中，也可以使用词干还原、词目还原、词例还原、单词气氛、最小编辑距离等概念、算法或方法。

3.1 英语形态学概观

形态学研究如何从语素构成词，语素是语言中具有意义的最小的单位。语素可以被分为词干和词缀，词干是语素中的主要元素，词缀则提供附加意义。

利用语素构词通常有四种方法“屈折”、“派生”、“合成”、“附着”。

1）屈折形态学：英文名词中通常只有两种屈折变化，一种是加词缀表示负数，一种是加词缀表示领域。英文的动词相对复杂。动词有三类：主要动词、情态动词、基础动词

2）派生形态学：英文中的派生通常是将词干和一个语法语素结合形成通常是属于不同此类的新词，新词的意义也很难预测

3）附着：英文中通常有两种附着成分，一种是前附着成分；一种是后附着成分。

以上讨论的范畴都是毗连形态学，但此时又相互毗连的词素构成的；还有一种是非毗连形态学，单词中的中缀就是非毗连形态学的一个实例。

语言中存在着复数语素，时态语素，行的标记等。这是我们还需要要求他们必须保持一致。

3.2有限状态转录机

我们之前讨论的都是形态剖析，当实现形态剖析器的时候我们需要：词表、形态顺序规则、正词法规则（拼写规则）

而有限转态转录机就是一种实现此表的形态特征建模和形态剖析的一种工具。

我们使用FSA可以实现形态识别，也就是判断有字母构成的输入字符串是否是合法的。但FSA是能返回合法与非法。这是我们就需要有限状态转录机，他可以进行形态剖析他可以同时进行输入和输出。

FST有四个使用途径：识别器、生成器、翻译器、关联器。

FST有两个附加的必包特性：逆反和组合。逆反使得用于剖析的转录机可以转化为作为生成的转录机；组合可以使两个转录机转化为一个更为复杂的转录机。

转录机通常是非确定性的，有一些可以转化成确定性的状态转录机。定序转录机是转录机的一个次类，她的输入是确定的，但输出不一定是定序的。后继转录机是定序转录机的泛化。定序转录机与后记转录机都是确定性的，无法处理歧义，但它们都将输入的字符串准确的转录为一个可能的输出。p-后继转录机是后继转路机的一种泛化，他可以处理有限数目的歧义。

1）用于形态剖析的FST

根据有限状态学理论，我们可以吧FST看成是两个带子，上层带子表示词汇带子，下层带子表示表层带子。

2）用转录机实现正词法规则

此时需要引入拼写规则或者叫正词法规则，以此来处理语素边界发生的拼写变化问题。

3）把FST词表与规则相结合

4）与词表无关的FST：Porter词干处理器

不要求大规模的联机词表，所以通常用于网络搜索和信息检索。

3.3单词和句子的词例还原

把文本切成单词和句子就是词例还原。

英文切词中比较简单，可以应用空格来进行切分，但也存在一定的问题。

句子切分也是文本的关键步骤，一般依据标点符号进行。比如英文的.

中文自动切词

中文切词最简单的算法是最大匹配算法，是一种贪心的搜索算法，他要求匹配一个次词典。

3.4拼写错误的检查与更正

并写错误的更正的标准算法是一种概率算法，拼写错误检查与更正基本有三大类：非错词错误检查、孤立词错误更正、依赖于上下文的错误检查与更正。

对于非词错误检查通常可以使用词典。更正的话可以使用最小编辑距离算法。他是衡量两个字符串之间的距离，相似程度。