Ch03 词 与 转录机
正词法规则（orthographic rules）
形态规则（morphological rules）
形态剖析（morphological parsing）：把单词剖析为多个词素
剖析产生的结果可以是形态结构、句法结构、语义结构或者话语结构
剖析产生的形式可以是符号串、树或者网络
词干还原（stemming）、词目还原（lemmatization）、词例还原（tokenization）或者单词切分（word segmentation）
计算两个单词在正记法上的相似度：
形态剖析计算相似度；最小编辑距离计算相似度。
英语形态学概观
形态学：是研究语素（小的意义单位）构成词的方法。
语素（morpheme）：是语言中负荷意义最小的单位。分为词干（stem）和词缀（affix）。
词缀包括：
前缀（prefix）：位于词干之前
后缀（suffix）：紧接词干之后
中缀（infix）：插入到词干中间
位缀（circumfix）：同时处于词干的前面和后面
语素构成单词的四种方法：
屈折（inflection）：把词干和一个表示语法的语素结合起来，所形成的单词一般与原来的词干属于同一个词类，还会产生一些如“一致关系”类的语法功能。
派生（derivation）：把词干和一个表示语法的语素结合起来，所形成的单词一般属于不同的词类，产生的新意义经常难于精确地预测
合成（compounding）：把多个词干结合在一起
附着（cliticization）：把一个单词与一个附着成分（clitic）结合起来。附着成分也是一个语素，它的句法作用像一个形式简化了的单词，按照音系学的规则或者正词法的规则附着在其他单词上。
屈折形态学（inflectional morphology）
英语的屈折系统相对简单：只有名词、动词和部分形容词有屈折变化，可能的屈折词缀的数目也相对较少。屈折的能产性（productive）比较高。
英语名词的屈折变化：
复数（plural）
领属（possessive）
英语动词分类：
主要动词（main verbs）：eat, sleep, impeach
情态动词（modal verbs）：can, will, should
基础动词（primary verbs）：be, have, do
英语动词的屈折变化：
规则的屈折动词：
不规则的屈折动词：
派生形态学（derivational morphology）
英语的派生系统相对复杂：通过对动词和形容词的变化产生名词，即名词化（nominalization）。派生的能产性比较低。
附着（cliticization）
附着成分是处于词缀和单词之间的语言单位。位于单词前面的附着成分称为前附着成分（proclitics），跟在单词后面的附着成分称为后附着成分（enclitics）。
附着成分的音系学功能相当于词缀，一般比较短，也没有重读。
附着成分的句法功能更像一个单词，作用经常相当于代词、冠词、连接词或者动词。
非毗连形态学
毗连形态学（concatenative morphology）：单词是由彼此毗连的语素构成的符号串。
非毗连形态学（non-concatenative morphology），也称为模板形态学（template morphology）或者词根与模式形态学（root-and-pattern morphology）。
一致关系（agreement）
数的一致，性的一致。
有限状态形态剖析
形态剖析器：
词表（lexicon）：词干和词缀表以及它们的基本信息
形态顺序规则（morphotactics）：关于形态顺序的模型，用于解释在一个词内，语素与语素之间的联系规则。
正词法规则（orthographic rules）：即拼写规则（spelling rules）。当两个语素结合时，拼写变化的规则。
有限状态词表的建造
计算机词表的构造：
列出语言中的每个词干和词缀
表示出形态顺序规则，即词干和词缀的结合规则
- 基于有限状态自动机为形态顺序规则建模
形态识别（morphological recognition）问题：使用 FSA 判断由字母构成的输入符号串是否合法。
有限状态转录机（FST）
有限状态转录机（Finite-State
Transducer，FST）：用来进行两个层之间的映射的自动机，即可以进行两个符号集合之间的映射的有限自动机。
FST 的用途：
作为识别器（recognizer）：取一对符号串 S1 和 S2 作为输入和输出，如果 S1 作为输入得到输出是 S2，或者 S2 作为输入得到输出是 S1，则识别成功；否则识别失败。
作为生成器（generator）：如果 FST 能够输出一对符号串 S1 和 S2，则输出成功并同时输出这对符号串，否则输出失败。
作为翻译器（translator）：FST 输入符号串 S1，输出符号串 S2
作为关联器（relater）：计算机符号串的两个集合之间的关系
FST 需要 7 个参数定义：
状态的有限集合 N
对应于输入字母表中的符号的有限集合
对应于输出字母表中的符号的有限集合
初始符号
终极状态的集合
转换函数或者状态之间的转换矩阵
输出函数。对应于每一个状态和输入，给出可能的输出符号串的集合。
FSA 与正则语言同构（isomorphic），FST 与正则关系（regular relation）同构。
正则关系是符号串偶对的集合，作为符号串集合的正则语言的自然扩充。
定序转录机和确定性
定序转录机（sequential transducer）：是转录机的一个次类，输入是确定的。
后继转录机（subsequential transducer）是定序转录机的泛化。
p- 后继转录机（p-subsequential transducer）：是后继转录机的泛化。
用于形态剖析的有限状态转录机
有限状态形态学（finite-state morphology）的范式（paradigm），把一个单词表示为词汇层（lexical level）和表层（surface level）之间的对应。
词汇层：表示组成该词的语素之间的毗连关系
表层：表示该词实际拼写的字母之间的毗连关系。
转录机和正词法规则
使用正词法规则来处理英语中在语素边界发生拼写变化的问题。
正词法规则可以在转录机上实现。
结合有限状态转录机的词表与规则
把转录机的词表和规则结合起来进行剖析和生成。
双层形态学结构，即能用于剖析，也能用于生成。
词表转录机把表示词干和形态特征的词汇层面映射于表示语素简单毗连的中间层面。
若干个正词法转录机并行地运行各种不同的拼写规则。
有限状态转录机从词汇带子生成表层带子时，或者从表层带子剖析词汇带子时，都可以使用带有同样状态序列的同样的层叠式转录机。
剖析比生成要复杂一些，因为在剖析中存在歧义的问题，而排歧需要某些外部的证据。
运行层叠式转录机时，可以通过组合（composing）和交合（intersecting）转录机的方式使之更加有效。
Porter 词干处理器（不使用词表）
形态剖析的标准算法：使用词表加规则的方法来建立转录机。缺点是需要大规模的联机词表。
Porter 词干处理器是相对简单的算法，可以应用于信息检索中。（Ref：Ch23）
单词和句子的词例还原
词例还原（tokenization）：把文本切分成单词和句子。
单词切分（word segmentation）
句子切分（sentence segmentation）
中文的自动切词
中文切分算法：最大匹配算法（maximum
matching，maxmatch），是一种贪心搜索算法，作为基准算法，需要配备一部语言的词典（词表）。缺陷在处理未知词或者未知组合时。
拼写错误的检查与更正
拼写错误更正的标准算法是概率算法。
拼写错误的检查和更正分解为三大问题：
非词错误检查（non-word error detection）：检查会导致非词的拼写错误。
孤立词错误更正（isolated-word error correction）：更正会导致非词的拼写错误。
依赖于上下文的错误检查和更正（context-dependent error detection and correction）：如果错误的拼写恰好是一个英语中真实存在的单词，就需要使用上下文来检查和更正这样的拼写错误。
有限状态形态剖析器提供了实现大规模词典的技术手段。对于每个单词都可以给出形态剖析，因此 FST 剖析器在本质上就是单词的识别器。如果使用投影操作把 FST 下侧的语言图抽取出来，那么 FST 形态剖析器就可以转化为有效的 FSA 单词识别器。FST 词典就会表示那些能产性的形态变化。
最小编辑距离算法用于计算来源和表层错误之间的距离。
最小编辑距离（minimum edit distance）
字符串距离（string
distance）：两个符号串之间的距离是这两个符号串彼此相似程度的度量。
最小编辑距离是符号串距离算法的基础，说明了两个符号串之间对齐的情况。
Levenshtein 距离是加权的最小编辑距离。
最小编辑距离使用动态规划进行计算。
最小编辑距离算法可以用来做两个符号串之间的最小代价对齐（alignment）。
人的形态处理方式
完全枚举法（full
listing）：假定人的心理词表中，不管单词内部形态结构如何，只会把语言中的全部单词都一一枚举出来。形态结构只是一种没有因果关系的现象。
最小羡余法（minimum
redundancy）：假定人的心理词表中，只表示那些有组合能力的语素，因此当处理单词中必须把与单词相关的所有语素组成起来。
3.13 小结
形态剖析是发现在词中所包含的连续的语素的过程
英语主要使用前缀和后缀来表示屈折形态和派生形态
英语的屈折形态比较简单，包括：人称和数的一致关系以及时态标志
英语的派生形态比较复杂，包括：前缀和后缀
英语的形态顺序规则（可容许的语素的顺序）可以用有限自动机来表示
有限状态转录机是能生成输出符号的有限自动机的扩充。FST 的重要运算包括：组合、投影和交运算
有限状态形态学和双层形态学是有限状态转录机在形态表示和剖析中的应用
转录机的自动编译程序是存在的，并且对于任何简单的重写规则都能够选出一个转录机。词表和拼写规则可以通过组合和交合不同的转录机的方式结合起来
Porter 算法是词干还原的简单方法，可以帮助词干剥离词缀。没有包含了词表的转录机那么精确，但是可以应用在不需要做精确形态剖析的工作中，例如：信息检索
单词的词例还原可以使用简单的正则表达式替换或者使用转录机来实现
拼写错误检查通常可以通过发现那些没有在词典中出现的单词的办法来实现；为此可以使用 FST 的词典
两个符号串之间的最小编辑距离是把一个符号串编辑为另一个符号串时所需要的最少的操作次数。最小编辑距离可以使用动态规划的方法来计算结果，也可以用来作两个符号串的对齐。