U1C2 文本预处理

admin管理员组

文章数量:1584233

U1C2 Text pre-processing

• 一、正则表达式 - Regular Expressions
• • 1、基本正则表达式模式 Basic Regular Expression Patterns
  • 2、析取、分组与优先级 Disjunction, Grouping, and Precedence
  • 3、一个简单的例子 A Simple Example
  • 4、更多操作符 more operatiors
  • 5、一个更加复杂的例子 A More Complex Example
  • 6. 替换、捕捉组和ELIZA Substitution, Capture Groups, and ELIZA
  • 7、先行断言 Lookahead Assertions
• 二、单词 - words
• 三、语料库 - Corpora
• 四、文本归一化 - Text Normalization
• • 1、用于原始标记和归一化的Unix工具 - Unix Tools for Crude Tokenization and Normalization
  • 2、单词标记 - Word Tokenization
  • 3、用于标记化的字节对编码 - Byte-Pair Encoding for Tokenization
  • 4、词语的归一化、词根化和词干化 - Word Normalization, Lemmatization and Stemming
  • • 波特词干提取器 The Porter Stemmer
  • 5、句子分割 - Sentence Segmentation
• 五、最小编辑距离 - Minimum Edit Distance
• • 1、最小编辑距离算法 - The Minimum Edit Distance Algorithm
• 总结 Summary
• 参考
• 修改时间

这一节将学习文本数据挖掘(text data mining) 的第一步：文本预处理 - text pre-processing

上面的对话来自ELIZA (伊丽莎)，这是一种早期的自然语言处理系统(natural language processing system)，它可以通过模仿罗杰斯式心理治疗师(Rogerian psychotherapist)的反应来与用户进行有限的对话 （Weizenbaum, 1966）。ELIZA是一个非常简单的程序，它使用模式匹配来识别短语，比如“I need X”，并将它们翻译成合适的输出，比如“What would it mean to you if you got X?”。这个简单的技巧在这个领域很成功，因为ELIZA实际上不需要知道任何东西就能模仿(mimic)罗杰斯式的心理治疗师。正如Weizenbaum所指出的，这是为数不多的对话类型之一，听众可以表现得好像对世界一无所知。ELIZA对人类对话的模仿非常成功：许多与ELIZA互动的人开始相信它真的理解了他们和他们的问题，许多人甚至在向他们解释了该程序的操作之后仍然相信ELIZA的能力（Weizenbaum，1976），甚至在今天，比如聊天机器人(chatbots)——也是一种有趣的消遣方式。

当然，现代会话代理远不止是一种消遣；他们可以回答问题、预订航班或查找餐厅，这些功能依赖于对用户意图的更复杂理解，我们将在第24章中看到。尽管如此，支持ELIZA和其他聊天机器人的简单的基于模式的方法在自然语言处理中发挥着关键作用。

我们将从描述文本模式的最重要的工具开始:正则表达式(regular expression)。正则表达式可以用来指定我们可能想从文档中提取的字符串，从上面ELIZA中的转换“I need X”，到定义字符串，如$199或$24.99，用于从文档中提取价格表。

然后，我们将讨论一组统称为 文本规范化(text normalization) 的任务，在这些任务中正则表达式的规范化扮演着重要的角色。规范化(normalizing)文本意味着将其转换为更方便的标准形式(standard form)。例如，我们将要对语言做的大部分工作都依赖于首先从运行标记化文本中分离或标记化(tokenizing)单词，即标记化任务(the task of tokenization)。英文单词之间通常用空格隔开，但空格并不总是足够的。“New York”和“rock ’n’ roll”有时被视为大词(large words)，尽管它们包含空格，但有时我们需要将“I’m”分为“I”和“am”。为了处理推文(tweets)或文本，我们需要标记(tokenize)表情符号(emoticons)，如：）或标签(hashtags)，如#nlproc。有些语言，比如日语(Japanese)，单词之间没有空格，所以单词的标记化变得更加困难。

文本规范化(text normalization)的另一部分是词根化(lemmatization)，即确定两个单词是否有相同的词根(root)，尽管它们的表面不同。例如，单词sang、sung和sings是动词sing的形式。单词sing是这些单词的常见词根(lemma)，一个词根还原工具(lemmatizer)将所有这些词映射为sing。词根化对于处理形态复杂的语言(如阿拉伯语(Arabic))是必不可少的。词干法(Stemming)指的是一种简单的词根法，我们主要是从词尾去掉后缀。文本规范化还包括句子分割(sentence segmentation)：使用句号(periods)或感叹号(exclamation points)等提示(cues)将文本拆分为单独的句子。

最后，我们需要比较单词和其他字符串。我们将引入一个称为编辑距离(edit distance) 的度量(metric)，它根据将一个字符串更改为另一个字符串所需的编辑(插入、删除、替换(insertions, deletions, substitutions))次数来度量两个字符串的相似程度。编辑距离是一种算法，应用于整个语言处理过程，从拼写校正(spelling correction)到语音识别(speech recognition)，再到共指消解(coreference resolution)。

一、正则表达式 - Regular Expressions

re正则表达式必备基础知识

在计算机科学标准化(standardization)方面，正则表达式(RE)是一个默默无闻的成功例子，它是一种用于指定文本搜索字符串的语言(text search strings)。这种实用的语言被用于每一种计算机语言(computer language)、字处理器(word processor)和文本处理工具(text processing tools)，如Unix工具grep或Emacs。在形式上，正则表达式是一种用于描述一组字符串的代数表示法(algebraic notation)。当我们有要搜索的模式和要搜索的文本语料库(corpus of texts)时，它们对于在文本中搜索特别有用。正则表达式搜索函数将搜索整个语料库，返回匹配模式的所有文本。语料库可以是单个文档，也可以是一个集合。例如，Unix命令行工具grep接受一个正则表达式，并返回与该表达式匹配的输入文档中的每一行。

搜索可以设计为返回一行中的每个匹配项，如果有多个匹配项，或者只返回第一个匹配项。在下面的例子中，我们通常强调匹配正则表达式的模式的确切部分，并只显示第一个匹配项。我们将展示用斜杠分隔(delimited by slashes)的正则表达式，但请注意，斜杠不是正则表达式的一部分。

正则表达式有很多变体(variants)。我们会描述扩展正则表达式(extended regular expressions);不同的正则表达式解析器可能只识别这些表达式的子集，或者对某些表达式的处理略有不同。使用在线正则表达式解析器(regular expression parsers)是测试表达式和探索这些变化的一种简便方法。

1、基本正则表达式模式 Basic Regular Expression Patterns

正斜杠的正则表达式意义

最简单的正则表达式是一个简单字符序列。要搜索woodchuck，我们输入/woodchuck/。

正则表达式是大小写敏感的(case sensitive)，模式 /woodchucks/ 是不能够匹配到字符串 Woodchucks的

方括号(braces) 内的字符字符串指定要匹配的字符的析取(disjunction)。

使用 /[1234567890]/ 或 /[ABCDEFGHIJKLMNOPQRSTUVWXYZ]/ 去指定任何数字或者字母显然很不方便，那么对于有顺序关联的字符集合，可以使用破折号(-) 来指定范围内的任意一个字符。

脱字符号的来由 ^

方括号还可以通过使用插入脱字符号 ^ 来指定单个字符不能是什么。例如，模式/[^a]/匹配除a之外的任何单个字符(包括特殊字符)。这只在方括号内的第一个符号时才成立。如果它出现在其他地方，它通常就单纯的表示插入符号。

我们如何谈论可选元素(optional elements)，比如 woodchuck 和 woodchucks 中的可选 s ? 我们不能用方括号，因为它们允许我们匹配 " s或S"，他们不允许我们去匹配" s或nothing"。为此，我们使用问号 /？/，表示“?的前一个字符有或没有”。

还有一些其他的表示方式，如重复匹配：

/a*/表示“任何0或更多的字符串”，这个会匹配 a 或者 aaaaaa等等, 但是这个也会同时匹配 “Off
Minor” 因为这个字符串有0个a。更复杂的模式同样也可以重复，例如 /[ab]*/ 表示“0或多个a 或 b”(注意不包含方括号”)。这将匹配像aaaa或ababab或bbbb这样的字符串。

/[0-9]+/ 表示"任何1或者更多的字符串"，这个会匹配1 或者 1342等等。

一个非常重要的特殊字符是句点(/./)，这是一个通配符表达式，可以匹配任何单个字符(除了回车(换行符))

锚(Anchors)是将正则表达式锚定到字符串中特定位置的特殊字符，最常见的锚点是插入符号^和美元符号$。

所以，^有三种用途:匹配一行的开始(模式pattern字符串开头)，指示方括号内的否定(模式pattern中的方括号开头)，以及仅仅表示一个插入符号(除前两者)。

还有另外两个锚:\b匹配单词边界，\b匹配非边界。因此，/\bthe\b/匹配单词the，但不匹配单词other。

更严格地说，正则表达式中的“单词(word)”定义为数字、下划线或字母(digits, underscores, or letters)的任意序列;这是基于编程语言中“单词”的定义。例如，/ b99\b/将匹配字符串99，在句子 There are 99 bottles of beer on the wall 中(因为 99 前后有空格)，但是在 There are 299 bottles of beer on the wall 中匹配不到 99(因为99前有个2，不是空格边界)，但是它会匹配到 99 在 $99 这个句子中，因为$不属于前面定义的单词。

2、析取、分组与优先级 Disjunction, Grouping, and Precedence

假设我们需要去在文本中搜索宠物(pets)，我们可能对猫(cats)和狗(dogs)很感兴趣。一般情况下，我们可能想要搜索 cat 或者 dog，但是我们不能使用方括号 /[catdog]/，因为方括号内都是以单个字符而不是整个单词表示的，所以我们需要一个新操作符(operator) - 析取操作符(disjunction operator)，同时也叫做管道符号(pipe symbol) |。举个例子，模式 /cat|dog/ 既能匹配字符串 cat 也能匹配 dog。

有时候，我们需要在一个更大的序列中使用这个析取操作。例如，假设我想要搜索关于我叔叔宠物鱼的信息，我该如何指定 guppy 和 guppies？我们不能简单地表示为 /guppy | ies/，因为这样可能只能匹配字符串 guppy 和 ies。这是因为像 guppy 这样的序列

为了使析取操作符只适用于特定的模式，我们需要使用括号操作符(parenthesis operators)( )，将模式括在括号内使其作为一个单独的字符，所以模式/gupp(y|ies)/会指定我们指的是只适用于后缀y和ies的析取。

假设我们想要匹配字符串的重复实例。也许我们有一行具有表单的列标签
Column 1 Column 2 Column 3，表达式/Column[0-9]+ */将不匹配任何数量的列;相反，它将匹配后面跟着任意数量空格的单个列，这里的星号只适用于它前面的空格符，而不是整个序列。使用括号，我们可以编写表达式/(Column[0-9]+ *)*/来匹配单词Column，后面跟着一个数字和可选空格，整个pattern重复零次或多次。

一种操作符可能优先于另一种操作符，这需要我们有时使用括号来指定我们的意思，这种思想由正则表达式的操作符优先层次结构来形式化。下表给出了RE操作符优先级的顺序，从最高优先级到最低优先级。

因此，由于Counters的优先级高于Sequences，/the*/匹配theeeee但不匹配thethe。因为序列的优先级高于析取，/ |any/匹配或any，但不匹配或theny。

模式可能以另一种方式变得模糊(ambiguous)。考虑表达式/[a-z]/在匹配之前的文本时。因为/[a-z]/匹配0个或多个字母，所以这个表达式不能匹配任何字符，或者只匹配第一个字母o、on、once或once。在这些情况下，正则表达式总是匹配最大的字符串;我们说模式是贪婪的(greedy)，扩展到尽可能多地覆盖字符串。

但是，有一些方法可以强制 非贪心(non-greedy) 匹配，使用?限定符。操作符* ?重复任意次，但尽可能减少重复。操作符+ ?重复1次或更多，但尽可能减少重复。

3、一个简单的例子 A Simple Example

假设我们要编写一个RE来查找英语文章中的字母 the。一个简单的(但不正确)模式可能是:
/the/
一个问题就是这个模式会错过那些以它开头大写的单词，例如:The。那么我们会这样写：
/[Tt]he/
但是我们依然会错误的返回那些嵌套其他单词的文本，例如：other or theolog。所以我们需要去指明单词两边的边界，比如：
/b[Tt]he\b/

有时，我们想去实现这个而不使用 /\b/，因为/\b/不会将下划线和数字视为单词边界，但是我们可能希望某些情况下能附带上下划线或数字，比如匹配 the_or 或者 the25。那么我们就只需要指明，the的两边没有字母就行：
/[^a-zA-Z][tT]he[^a-zA-Z]/
但是，这个模式还是有一个问题，当 the 为一句的开头时，这个模式会找不到 the，因为[^a-zA-Z]会匹配一个非字母字符在the之前。我们可以避免这个问题，通过在 the 之前指定析取操作符，尾部也一样：
/(^|[^[a-zA-Z]])[tT]he([^a-zA-Z]|$)/

我们刚刚经历的过程是基于两种错误的修订：
false positive，字符串被错误的匹配，类似于 other 或者 there
false negative，字符串错误的错过了，比如 The

在实现语音和语言处理系统时，解决这两类错误的问题一再出现。因此，降低应用程序的总体错误率涉及两个对立的结果：

• 增加精确率precision(最小化 false positives)
• 增加召回率recall(最小化false negative)

我们会回到精确率与召回率更精细的定义在Chapter4

4、更多操作符 more operatiors

上图显示了一些常用范围的别名(aliases)，主要用来节省输入(save typing)。我们也可以使用显式数字作为Counters，方法是将它们括在花括号中。正则表达式/{3}/表示 “前一个字符或表达式正好出现3次”。所以/ \.{24}z/将匹配a后接24个点后接z(但不匹配a后接23或25个点后接z)。

除此之外，还可以指定一个数字范围。因此/{n,m}/指定前一个字符或表达式出现n到m次，而/{n，}/表示前一个表达式至少出现n次。总结如下：

最后，某些特殊字符(special characters)由基于换行反斜杠()的特殊符号表示。其中最常见的是换行符(newline character) \n 和 制表符(tab character) \t。

其次还有自身就是特殊字符的，如. 和 * 和 [ 和 \ 等，在它们前面加上反斜杠，即，/\./， /\*/， /\[/，和/\\/

5、一个更加复杂的例子 A More Complex Example

我们用一个更加重要的例子去展示正则表达式的强大。

加入我们要去构建一个应用去帮助一个用户在网上购买电脑。这个用户可能想要：任何至少有6GHz和500GB硬盘空间的机器，且价格低于$1000。为了要进行这种检索(retrieval)，首先需要能够寻找一些表达，像 6GH 或者 500 GB 或者 Mac 或者 $999.99。对于其余的部分，我们将使用一些简单的正则表达式去完成这个任务。

首先，让我们完成对于价格的正则表达式。这里有一个美元符号的正则表达式，后面跟着数字字符串：
/$[0-9]+/

注意这里的 $ 字符串与我们之前讨论的行尾结束符(end-of-line)函数不一样。很多正则表达式解析器非常智能，以至于能辨识到这里的 $ 不是表示行尾结束符。

现在我们仅仅需要去处理美元的小数部分(fractions)。我们将加上一个小数点(decimal point)还有后面加上两个数字：
/$[0-9]+.[0-9][0-9]/

这个模式仅仅允许 $199.99 但不允许 $199。我们需要去使美分部分变得可选并且确定一个词边界：
/(^|\W)$[0-9]+(.[0-9][0-9])?\b/

最后一下，这个模式允许价格像 $199999.99 这个价格会非常昂贵，我们需要去限制美元大小：
/(^|\W)$[0-9]{0,3}(.[0-9][0-9])?\b/

那么关于磁盘空间又该如何做呢？我们又要用到可选分数部分(5.5GB)；注意 ? 和 * 的使用，数字和GB之间可能有不确定长度的空格，于是：
/\b[0-9]+(.[0-9]+)? *(GB|[Gg]igabytes?)\b/

更改这个正则表达式，以至于能匹配超过500GB，留给读者作为练习。

6. 替换、捕捉组和ELIZA Substitution, Capture Groups, and ELIZA

正则表达式的一个重要用途是替换(Substitution)。例如，在Python和Unix命令(如vim或sed)中使用的替换操作符s/regexp1/pattern/允许一个由正则表达式描述的字符串被另一个字符串替换:
s/colour/color/

能够引用匹配第一个模式的字符串的特定子部分通常很有用。例如，假设我们想在文本中的所有整数周围加上尖括号(angle brackets)，例如，将 35 boxes 更改为 <35> boxes。我们想要一种方法来引用我们找到的整数，这样我们可以很容易地添加括号。
为此，我们在第一个模式周围放置括号( )，并在第二个模式中使用数字操作符(number operator)\1引用。它看起来是这样的:
s/([0-9]+)/<\1>/

括号(parenthesis)和数字操作符(number operators)还可以指定某个字符串或表达式必须在文本中出现两次。例如，假设我们正在寻找模式“the Xer they were, the Xer they will be”，我们想将这两个X限制为相同的字符串。我们用括号操作符包围第一个X，用数字操作符\1替换第二个X，如下所示:

/the (.*)er they were, the \1er they will be/

这里\1将被括号中匹配第一项的任何字符串替换。所以会匹配：
the bigger they were, the bigger they will be.
而不是
the bigger they were, the faster they will be.

使用括号在内存中存储模式的这种用法称为捕获组(capture group)。每次使用捕获组(即，用括号包围一个模式)时，得到的匹配将存储在一个编号寄存器(numbered register)中。如果您匹配两个不同的圆括号集合，\2表示匹配第二个捕获组的内容。因此：
/the (.*)er they (.*), the \1er we \2/
将会匹配 the faster they ran, the faster we ran 而不是 the faster they ran, the faster
we ate。类似地，第三个捕获组存储在\3中，第四个捕获组存储在\4中，以此类推。

因此，括号在正则表达式中有一个双函数(double function);它们用于对术语进行分组，以指定操作符应用的顺序，并用于捕获寄存器中的某些内容。

有时，我们可能希望使用括号进行分组，但不希望捕获寄存器中的结果模式。这种情况下，我们使用一个非捕获组(non-capturing group)，它是通过在开括号后输入命令 ?: 来指定的，格式为(?: pattern)。
/(?:some|a few)(people|cats) like some \1/

这将会匹配 some cats like some cats
而不会匹配到 some cats like some a few.

替换组和捕获组在实现ELIZA这样的简单聊天机器人时非常有用（Weizenbaum, 1966）.回想一下，ELIZA模仿罗杰斯心理学家，像这样进行对话:

ELIZA的工作方式是使用一系列或级联的正则表达式替换，每个替换都匹配和更改输入行的某些部分。

输入行首先大写。第一次替换将MY的所有实例改为YOUR, I 'M改为YOU ARE，以此类推。下一组替换将匹配并替换输入中的其他模式。下面是一些例子:

由于多重替换(multiple substitutions)可以应用于一个给定的输入，替换被分配一个等级(rank)并按顺序应用。创建模式是练习2.3的主题，我们将在第24章回到ELIZA架构的细节。

7、先行断言 Lookahead Assertions

最后，有时我们需要预测未来：在文本中提前查看是否有匹配的模式，但不要提前匹配光标(cursor)，以便在模式出现时处理该模式。

这些先行断言使用了我们在前一节中为非捕获组看到的（？语法。如果出现模式，则运算符（？=pattern）为真，但为零宽度(zero-width)，即匹配指针不前进。运算符（？！pattern）仅在模式不匹配时返回true，但同样是零宽度且不推进光标。当我们分析一些复杂的模式，但想排除特殊情况时，通常使用负先行(negative lookahead)。例如，假设我们想在一行的开头匹配任何一个不以“Vocano”开头的单词。我们可以使用负前瞻来实现这一点：
/^(?!Volcano[A-Za-z])/

二、单词 - words

在讨论处理单词(words)之前，我们需要确定什么才算一个单词。让我们先看一个特定的语料库（复数语料库(plural corpora)），一个计算机可读的(computer-readable)文本或语音集合。

例如，布朗语料库(Brown corpus)是一个百万字的语料库，它收集了来自不同体裁(报纸、小说、非小说、学术等)的500个书面英语文本样本，于1963年和1964年在布朗大学(Ku cera和Francis, 1967年)收集而成。在下面的布朗句子中有多少个单词：
He stepped out into the hall, was delighted to encounter a water brother.

这个句子有13个单词，不算标点符号(punctuation marks)的话，算标点的话是15个。我们是否将句号(“.”)、逗号(“，”)等视为单词取决于任务。标点符号对于发现事物的界限(boundaries)至关重要(逗号commas、句号periods、冒号colons)以及用于识别含义的某些方面(问号question marks、感叹号exclamation marks、引号quotation marks)。对于某些任务，比如词性标注(part-of-speech tagging)、语法解析(parsing)或语音合成(speech synthesis)，我们有时将标点符号视为单独的单词。

Switchboard语料库收集了20世纪90年代初陌生人之间的美式英语电话交谈;它包含2430个对话，平均每个对话6分钟，总计240小时的演讲和大约300万个单词（Godfrey et al., 1992）。

这样的口语语料库没有标点符号，但在定义单词时确实引入了其他的复杂性。让我们看看Switchboard的一句话;话语是一个句子的口语相关物:
I do uh main- mainly business data processing

这句话有两种不流利的(disfluencies)地方。断开的(borken-off)单词main-称为一个片段(fragment)。像uh和um这样的词被称为填充词(filler)或填充停顿词(filler pauses)。我们应该把这些看作是文字吗?同样，这取决于应用程序。如果我们正在构建一个语音转录系统，我们可能希望最终去掉(strip out)不流畅的部分(disfluencies)。

但我们有时也会保留不流畅。像uh或um这样的不流畅实际上有助于语音识别(speech recognition)预测即将到来的单词，因为它们可能表明说话者正在重新启动子句或想法，因此对于语音识别来说，它们被视为常规单词。因为人们使用不同的不流利性，它们也可以作为说话者身份的暗示。事实上，Clark and FoxTree(2002) 表明 uh和um有不同的含义。你是怎么思考这两个词的？

大写的token像They和非大写的token像they是同一个单词吗?在某些任务(语音识别)中，它们被集中在一起(lumped together)，而对于词干(part-of-speech)或命名实体标签(named-entity tagging)，大写是一个有用的特性，并被保留下来(retained)。

那么像 cats 和 cat 这样的变形形式呢?这两个词有相同的词根(lemma)，但词形(wordform)不同。词根是一组词干(stem)相同、词性(part-of-speech)相同、词义(word sense)相同的词汇形式(lexical forms)。词形(wordform)是单词的完整屈折(full inflected)或派生形式(derived form)。对于阿拉伯语(Arabic)等形态复杂的(morphologically complex)语言，我们通常需要进行词根化。然而，对于英语中的许多任务，词形就足够了。

英语有多少个单词?要回答这个问题，我们需要区分谈论单词的两种方式。类型(types) 是语料库中不同单词的数量;如果词汇表中的单词集合是V，那么类型的数量就是词汇表大小 |V|。标记(tokens)是运行词(running words)的总数N。如果我们忽略标点符号，下面的Brown句子有16个标记和14种类型（有三个the为同一类型）：
They picnicked by the pool, then lay back on the grass and looked at the stars.
当我们谈论语言(language)中的单词数量(number of words)时，我们通常指的是单词类型(word types)。

上图显示了从一些流行的英语语料库(popular English corpora)计算出的类型和标记的大致数量。我们观察的语料库越大，我们发现的单词类型就越多，事实上，类型数| V |和标记数N之间的这种关系被称为Herdan’s Law（Herdan，1960）或Heaps’ Law（Heaps，1978），分别在语言学(linguistics)和信息检索领域(information retrieval discoverers)。如公式如下所示，其中 k k k和 β \beta β为正常数， 0 < β < 1 0<\beta<1 0<β<1。
∣ V ∣ = k N β |V|=kN^\beta ∣V∣=kNβ
β \beta β的取值取决于语料库的大小(size)和体裁(genre)，但至少对于上图中的大型语料库来说， β \beta β的取值范围在.67到.75之间。粗略地说，一篇文章的词汇量增加的速度要比单词长度的平方根快得多。

语言中单词数量的另一种度量方法是词根(lemma)的数量，而不是单词类型(type)的数量。词典可以帮助统计词根(lemma);字典条目(dictionary entries)或黑体字形式(boldface forms)是引理数目的一个非常粗略的上限(因为有些词根有多个黑体字形式)。1989年版
《牛津英语词典》(Oxford English Dictionary)共有61.5万个词条。

三、语料库 - Corpora

语言不会凭空出现。我们研究的任何文本都是由一个或多个特定的讲述者或作家，在特定的时间，特定的地点，为了特定的功能，用特定的语言的特定方言(dialect)创作出来的。

也许变体(variation)最重要的方面是语言。NLP算法在应用于多种语言时最有用。根据在线民族志目录(online Ethnologue catalog)（Simons and Fennig，2018），在撰写本文时，世界上有7097种语言。在不止一种语言上测试算法很重要，尤其是在具有不同属性的语言上；相比之下，目前有一种不幸的趋势，即NLP算法只在英语上开发或测试（Bender，2019）。即使算法是在英语之外开发的，它们也倾向于为大型工业化国家(large industrialized nations)的官方语言(official languages)（汉语、西班牙语、日语、德语等）开发，但我们不想将工具仅限于这几种语言。此外，大多数语言也有多种变体(varieties)，通常在不同的地区或不同的社会群体中使用。因此，例如，如果我们重新处理使用非裔美国人英语(African American English)（AAE）或非裔美国人方言英语(African American Vernacular English)（AAVE）特征的文本，以及非裔美国人社区数百万人使用的英语变体（King 2020），我们必须使用具有这些变体特征的NLP工具。Twitter帖子可能会使用非裔美国英语使用者经常使用的功能，例如iont（我在主流美国英语（MAE）中没有）或对应于MAE谈论的talmbout，这两个例子都会影响分词（Blodgett et al.2016，Jones 2015）。

说话者或作家在单一的交际行为中使用多种语言也很常见，这种现象称为语码转换(code switching)。语码转换在世界范围内非常普遍;以下是显示西班牙语(Spanish )和(音译transliterated)印地语(Hindi)代码与英语转换的例子(Solorio et al. 2014, Jurgens et al. 2017)

变体的另一个维度是体裁(genre)。我们的算法必须处理的文本可能来自新闻专线(newswire)、小说(fiction)或非小说书籍(non-fiction books)、科学文章(scientific articles)、维基百科(Wikipedia)或宗教文本(religious texts)。它可能来自语音类型(spoken genres)，如电话交谈(telephone conversations)、商务会议(business meetings)、警用摄像机(police body-worn cameras)、医疗采访(medical interviews)或电视节目(transcripts of television)或电影(movies)的文本。它可能来自工作场合(work situations)，如医生的笔记(doctors’ notes)、法律文本(legal text)或议会(parliamentary)或国会程序(congressional proceedings)。

文本也反映了作者(writer)(或说话者(speaker))的人口统计学特征(demographic characteristics):他们的年龄(age)、性别(gender)、种族(race)、社会经济阶层(socioeconomic class)都能影响我们正在处理的文本的语言属性(linguistic properties)。

最后，时间(time)也很重要。语言随着时间的推移而变化，对于一些语言，我们有来自不同历史时期的很好的语料库。

由于语言处于这样的环境中，在从语料库开发语言处理的计算模型时，重要的是要考虑谁在什么环境下产生了语言，出于什么目的。数据集的用户如何知道所有这些细节?最好的方法是，语料库创建者为每个语料库建立一个数据表(datasheet)（Gebru et al.,
2020）或数据声明(data statement)（Bender and Friedman, 2018）。数据表指定数据集的属性，如：

动机(Motivation): 为什么收集文集，由谁收集，谁资助它?
情景(Situation): 这篇文本是在什么时候和什么情况下写成/说的? 例如:有任务吗?这种语言最初是口语对话、编辑文本、社交媒体交流、独白还是对话?
语言多样性(Language variety): 语料库是什么语言(包括方言/地区)?
演讲者人口统计数据(Speaker demographics): 文本作者的年龄或性别是什么?
收集过程(Collection process): 数据有多大?如果是子样本，它是如何采样的?收集的数据是否得到了同意?如何对数据进行预处理，有哪些元数据可用?
注释过程(Annotation process): 注释是什么，注释者的人口统计特征是什么，他们是如何训练的，数据是如何注释的?
发布(Distribution): 是否存在版权或其他知识产权限制。

四、文本归一化 - Text Normalization

在对文本进行几乎任何自然语言处理之前，文本都必须被归一化。
在任何归一化过程中，至少有三个任务是常用的:

1. 标记(分段)单词 - Tokenizing (segmenting) words
2. 归一化单词的格式 - Normalizing word formats
3. 分段的句子 - Segmenting sentences

在下一节中，我们将详细介绍这些任务。

1、用于原始标记和归一化的Unix工具 - Unix Tools for Crude Tokenization and Normalization

让我们从一个简单的(虽然有点幼稚)的单词标记化和规范化(以及频率计算)版本开始，这个版本受Church(1994)的启发，仅在一个UNIX命令行中就可以完成英语。我们将使用一些Unix命令:tr，用于系统地改变输入中的特定字符;排序，按字母顺序对输入行进行排序;还有uniq，它折叠并计算相邻相同的线。

例如，让我们从莎士比亚的“完整单词”开始，在一个文件中，sh.txt。我们可以使用tr来通过将每个非字母字符序列更改为换行符来标记单词(’ a- za -z '表示字母，-c选项补充非字母，-s选项将所有序列压缩为一个字符):

现在每行有一个单词，我们可以对这些行进行排序，并将它们传递给uniq -c，它将折叠并对它们进行计数：

或者，我们可以将所有大写字母折叠为小写字母:

现在我们可以再次排序，找到频繁出现的单词。排序的-n选项表示按数字而不是字母排序，而-r选项表示按倒序排序(从最高到最低):

结果表明，和其他语料库一样，莎士比亚作品中出现频率最高的词是短虚词，如冠词、代词、介词:

这类Unix工具可以非常方便地为任何语料库构建快速的单词计数统计信息。

2、单词标记 - Word Tokenization

上面的简单UNIX工具对于获取粗略的单词统计数据很好，但是对于标记化(将文本分割成单词的任务)通常需要更复杂的算法。

虽然Unix命令序列只是删除了所有的数字和标点符号，但对于大多数NLP应用程序，我们需要在我们的标记化中保留这些符号。我们经常想把标点符号拆成一个单独的符号;逗号对解析器来说是一个有用的信息，句号有助于指出句子的边界。但是我们常常希望保留出现在单词内部的标点符号，例如m.p.h.， Ph.D.， AT&T 和 cap’n。特殊字符和数字需要保留在价格($45.55)和日期(01/02/06)中;我们不希望将价格分割成45和55的标记。还有URLs(http://www.stanford.edu)、Twitter标签(#nlproc)或电子邮件地址(someone@cs.colorado.edu)。

数字表示(number experssion)也带来了其他的并发问题(complications);逗号通常出现在单词边界处，而在英语中，逗号则用在数字内部，每三位数使用一次:555,500.50。语言和标记化需求在这一点上有所不同;相比之下，许多欧洲大陆语言，如西班牙语、法语和德语，使用逗号来表示小数点，在英语中使用空格(有时是句号)来表示逗号，例如，555 500,50。

标记器还可以用于扩展由撇号(apostrophes)标记的撇格缩略词(clitic contractions)，例如，将what’re转换为what are和we’re转换为we are。撇(clitic)是一个单词的一部分，它不能独立存在，只有当它与另一个单词相连时才会出现。一些这样的缩写出现在其他字母语言中，包括法语中的冠词和代词(j’ai, l’homme)。

根据应用程序的不同，标记化算法(tokenization algorithms)也可以将像New York或rock ‘n’ roll这样的多单词表达式标记为单个标记，这需要某种类型的多单词表达式字典(multiword experssion dictionary)。因此，标记化与命名实体识别(named entity recognition) 密切相关，即检测名称、日期和组织的任务(第8章)。

一种常用的标记化标准被称为Penn Treebank标记化标准，用于语言数据联盟(LDC)发布的解析语料库(Treebank)，它是许多有用数据集的来源。这一标准将撇号分隔开(doesn’t变成does + n’t)，将用连字符连接的单词放在一起，并将所有标点符号分隔开(为了节省空间，我们在标记之间显示可见的空格，尽管换行符是更常见的输出)

实际上，由于标记化需要在任何其他语言处理之前运行，所以它需要非常快。因此，标记化的标准方法是使用基于正则表达式的确定性算法(deterministic algorithms)，正则表达式编译成非常高效的有限状态自动机(finite state automata)。例如，下图显示了一个基本正则表达式的示例，它可以用于标记化，基于python的自然语言工具包(NLTK)的nltk.regexp_tokenize（Bird et al. 2009;http://www.nltk）。

精心设计的确定性算法(deterministic algorithms)可以处理由此产生的歧义(ambiguities)，比如撇号(apostrophe)作为属格标记(genitive marker)(如在书的封面上)时需要不同的标记，引号(quotative)作为"The other class", she said，或者在 “they’re”时使用撇号。

在书写的汉语、日语和泰国语等语言中，单词的标记更加复杂，因为这些语言不使用空格来标记潜在的单词边界(word-boundaries)。例如，在汉语中，单词是由汉字组成的(在汉语中称为汉字hanzi)。每个汉字通常代表一个单独的意义单位(称为语素morpheme)，并可作为一个音节(syllable)发音。单词的平均长度约为2.4个字符。但在中文中，确定什么才是一个单词是复杂的。例如，考虑下面的句子：

正如Chen et al.(2017)所指出的，这可以被视为3个单词(‘Chinese Treebank’分段)：

或5个词((‘Peking University’ 分段):

最后，在汉语中，可以完全忽略单词，而使用字符作为基本元素，将句子视为7个字符组成的系列:

事实上，对于大多数中文NLP任务来说，将字符作为输入比将单词作为输入效果更好，因为对于大多数应用程序来说，字符的语义水平(semantic level)是合理的，而且相比之下，大多数单词标准会产生大量词汇，其中包含大量非常罕见的单词(Li et al., 2019)。

然而，对于日语和泰国语来说，字符的单位太小，因此需要分词算法(word segmentation)。这对汉语来说也很有用，在一些罕见的情况下，需要单词而不是字符的边界。这些语言的标准分割算法使用在手工分割训练集(hand-segmented training sets)上通过监督机器学习训练的神经序列模型(neural sequence models);我们将在第8章和第9章介绍序列模型(sequence models)。

3、用于标记化的字节对编码 - Byte-Pair Encoding for Tokenization

还有第三个选项可以标记文本。我们可以使用数据自动告诉我们标记应该是什么，而不是将标记定义为单词（无论是用空格还是更复杂的算法分隔）或字符（如中文）。这在处理未知词时尤其有用，这是语言处理中的一个重要问题。我们将在下一章中看到，NLP算法通常从一个语料库（训练语料库a training corpus）中学习一些关于语言的事实，然后使用这些事实来决定一个单独的测试语料库(test corpus)及其语言。因此，如果我们的训练语料库包含单词low、new、newer，但不是lower，那么如果单词lower出现在我们的测试语料库中，我们的系统将不知道如何处理它。

为了解决这个未知单词的问题，现代标记化者(modern tokenizers)通常会自动归纳出一组标记，其中包括比单词小的标记，称为子单词(subwords)。子词可以是任意的子串(arbitrary substrings)，也可以是语素(morphemes)-est或-er等承载意义的单位(meaning-bearing units)。（语素(morphemes)是语言中最小的语义单位；例如，“unlikeliest”一词的语素有un-、likely和-est。）在现代标记化方案中，大多数标记是单词，但一些标记是频繁出现的语素(morphemes)或其他子单词(subwords)，如-er。因此，每一个看不见的(unseen)单词，比如lower，都可以用一些已知的子单词单位序列来表示，比如low和er，或者在必要的情况下，甚至可以用一系列单独的字母来表示。

大多数标记化方案(tokenization schemes)有两个部分：标记学习器(token learner) 和标记切分器(token segmenter)。标记学习器 获取一个原始的训练语料库(raw training corpus)（有时粗略地预先划分(preseparated)成单词，例如通过空格），并归纳出一个词汇，一组标记。标记切分器 获取一个原始测试句子，并将其切分为词汇表中的标记。有三种算法被广泛使用：字节对编码(byte-pair encoding)（Sennrich et al.，2016）、一元语言模型(unigram language modeling)（Kudo, 2018）和 词块(WordPiece)（Schuster and Nakajima, 2012）；还有一个句块库(SentencePiece library)，其中包括三个句子中前两个的实现（Kudo and Richardson，2018）。

在本节中，我们将介绍三种算法中最简单的一种，字节对编码 或 BPE算法（Sennrich et al，2016）；见下图。BPE 标记学习器从一个词汇开始，这个词汇只是所有单个字符的集合。然后，它检查训练语料库(training corpus)，选择最常见的两个相邻符号（比如“A”、“B”），在词汇表中添加一个新的合并符号(merged symbol) “AB”，并用新的“AB”替换语料库中每个相邻的“A”、“B”。它继续计数和合并，创建越来越长的新字符串，直到k个合并完成，创建k个新的标记；因此，k是算法的一个参数。生成的词汇表由原始字符集和k个新符号组成。

该算法通常在单词内部(inside words)运行（而不是跨单词边界合并），因此输入语料库首先被分隔成一组空格(white-space-separated)，给出一组字符串，每个字符串对应于单词的字符，加上一个特殊的词尾符号(end-of-word symbol __)及其计数。让我们看看它在以下由18个单词组成的小型输入语料库上的操作，每个单词都有计数（单词low出现5次，单词newer出现6次，以此类推），它的起始词汇表为11个字母。

BPE算法首先对所有相邻符号对(pairs of adjacent symbols) 进行计数：最频繁的是符号对 e 和 r，因为它以 newer（频率6）和 wider（频率3）出现，总共出现9次。然后我们合并这些符号，将er视为一个符号，然后再次计数：

现在最常见的一对是er 和 __，我们将其合并；我们的系统已经了解到，单词的词尾(word-final)应该有一个标记 er，表示为er__:

下一个n 和 e(总数为8)被合并为 ne:

如果我们继续，下一个合并就是：

一旦我们学习了词汇表，就可以使用**标记解析器(token parser)**来标记测试句子。标记解析器只是在测试数据上运行我们从训练数据中学习到的合并，贪婪地(greedily)按照我们学习它们的顺序运行。（因此，测试数据中的频率不起作用，只是训练数据中的频率）。首先，我们把每个测试句子的单词分割成几个字符。然后我们应用第一条规则：用er替换测试语料库中e和r的每个实例，然后第二条规则：用er__替换测试语料库中er的每个实例，依此类推。最后，如果测试语料库包含单词 newer__，它将被标记为一个完整的单词。但是像 l o w e r __这样的新（未知）单词会合并到 low 和 er 这两个标记中。

当然，在真正的算法中，BPE是在一个非常大的输入语料库上运行成千上万的合并。结果是，大多数单词将被表示为完整的符号，只有非常罕见的单词(和未知的单词)必须由它们的部分表示。

4、词语的归一化、词根化和词干化 - Word Normalization, Lemmatization and Stemming

单词归一化(normalization 规范化) 的任务是将单词(words)/标记(tokens)置于标准格式(standard format)，为具有多种形式的(multiple forms)单词（如 USA 和 US 或 uh-huh 和uhhuh）选择一种单一的标准形式(single normal form)。这种标准化(standardization)可能很有价值，尽管在标准化(normalization)过程中丢失了拼写信息(spelling information)。对于有关US的信息检索(retrieval)或信息提取(extraction)，我们可能希望看到来自文件的信息，无论它们提到 US 还是 USA。

案例折叠(case folding) 是另一种规范化(normalization)。将所有内容映射(mapping)到小写表示 Woodchuck 和 woodchuck 是相同的，这对于信息检索(information retrieval)或语音识别(speech recognition)等许多任务中的泛化(generalization)非常有帮助。相比之下，对于情感分析(sentiment analysis)和其他文本分类任务(other text classification tasks)、信息提取(information extraction)和机器翻译(machine translation)，案例(case)可能非常有用，而案例折叠通常不做。这是为了保持差异，举个例子：“US” 是一个国家 和“us” 是代词之间的差异，可能会在泛化上(generalization)超过(outweigh)大小写折叠为其他单词提供的优势。

对于许多自然语言处理情况，我们也希望一个词的两种形态不同的形式表现相似。例如，在网络搜索(web search)中，有人可能会键入字符串“woodchucks”，但一个有用的系统可能还希望返回提到woodchuck但没有s的页面。这在俄语等形态复杂的语言中尤其常见，例如，“Moscow”一词在短语“Moscow”、“of Moscow”、“to Moscow”等中有不同的结尾。

词根化(lemmatization) 的任务是确定两个词有相同的词根root，尽管它们的表面不同。单词am，are，is有共同的词根 be；单词“dinner”和“dinners”都有词根“dinner”。将这些形式的每一个词根化为同一个词根，可以让我们在俄语中找到所有提到的单词，比如 Moscow。因此，像 He is reading detective stories 这样的句子的词根化形式就是 He be read detective story。

词根化(lemmatization)是怎么做的？最复杂的词根化方法是对单词进行完整的形态分析(morphological parsing)。词法(morphology) 是研究单词是如何由更小的词素(morphemes) 构成的。词素可分为两大类(two broad classes)：**词干(stems)**是词的中心词素(central morpheme)，提供主义(main meaning)，词缀(affixes) 增加各种附加意义。例如，单词 fox 由一个语素（语素fox）组成，单词 cats 由两个语素组成：语素cat和语素-s。词法分析器(morphological parser) 将一个类似 cats 的单词解析为两个语素 cat 和 s，或者将一个类似 amaren 的西班牙语单词（‘if in the future they would love’）解析为语素amar ‘to love’，第三方语言(3PL)和未来虚拟语气(future subjunctive)的形态特征(morphological features)。

波特词干提取器 The Porter Stemmer

词根化算法(lemmatization algorithm)可能很复杂。出于这个原因，我们有时会使用一种更简单(simpler)但更粗糙(cruder)的方法，主要包括切掉(chopping off)单词的词尾词缀(word-final affixes)。这种简单的(native)形态学分析(morphological analysis)称为词干分析(stemming)。使用最广泛的词干提取算法(stemming algorithms)之一是Porter（1980）。波特词提取器适用于以下段落：

产生下列输出：

该算法是基于一系列的重写规则串联运行(series of rewrite rules run in series)，作为一个级联(cascade)，其中每个传递的输出作为输入到下一个传递;下面是一些规则的例子

Porter stemmer 的详细规则列表和代码(Java、Python等)可以在Martin Porter的主页上找到。参见原始论文(Porter, 1980)。

在需要跨同一词根的不同变体折叠(collapse)的情况下，简单的词干分析器非常有用。尽管如此，他们确实倾向于犯下过度概括(over-)和欠概括(under-generalizing)的错误，如下表所示(Krovetz, 1993)：

5、句子分割 - Sentence Segmentation

句子切分(Sentence Segmentation) 是文本处理的另一个重要步骤。将文本分割成句子最有用的提示(cue)是标点符号，如句号(peroids)、问号(question marks)和感叹号(exclamation)。问号和感叹号是相对明确的(unambiguous)句子边界标记(sentence boundaries)。另一方面，句号则更加模糊(ambiguous)，比如句子边界标记和缩写标记（如Mr.或 Inc.）之间存在歧义。你刚才读到的前一个句子显示了这种歧义的更复杂情况，其中Inc的最后一个句号同时标记了缩写和句子边界标记。因此，句子标记化(sentence tokenization)和单词标记化(word tokenization)可以联合处理(addressed jointly)。

一般来说，句子标记化方法首先（基于规则rules或机器学习ML）确定句点是单词的一部分还是句子边界标记。缩略语词典(abbreviation dictionary)可以帮助确定句点是否是常用缩略语的一部分；这些词典可以是手工制作的(hand-built)，也可以是机器学习的（Kiss and Strunk, 2006），最后的分句器(sentence splitter)也是如此。例如，在斯坦福大学CoreNLP toolkit（Manning et al.，2014）中，句子分割是基于规则的(rule-based)，这是标记化的一种确定性结果(deterministic consequence)；当一个句子结束标点符号（，！，或？）尚未与其他字符组合到标记中（例如缩写或数字），一个句子就结束了，可选择性的添加反引号或括号。

五、最小编辑距离 - Minimum Edit Distance

许多自然语言处理都与测量两个字符串的相似程度有关。例如，在拼写更正(spelling correction)中，用户输入了一些错误的(erroneous)字符串，比如graffe，我们想知道用户的意思。用户可能想要一个类似于graffe的单词。在候选的相似单词中，giraffe这个词与giraffe只有一个字母不同，从直觉上看，giraffe似乎比grail或graf更相似，grail或graf有更多的字母不同。

另一个例子来自coreference，它的任务是确定两个字符串（例如下面的字符串）是否引用同一个实体(entity)：

同样，这两个字符串非常相似（只有一个单词不同）这一事实似乎是决定它们可能是相互关联的(coreferent)有用证据。

编辑距离(edit distance) 为我们提供了一种量化(quantify)这两种关于字符串相似性的直觉的方法。更正式地说，两个字符串之间的最小编辑距离(minimum edit distance) 定义为将一个字符串转换为另一个字符串所需的最小编辑操作数(minimum number of editing operations)（插入(insertion)、删除(deletion)、替换(substitition)等操作）。

例如，INTENTION(意图)和EXECUTION(执行)之间的差距是5（删除i，用e代替n，用x代替t，插入c，用u代替n）。通过查看最重要的字符串距离可视化(visualization for string distances)，即两个字符串之间的对齐(alignment)，可以更容易地看到这一点，如下图所示。给定两个序列，对齐是两个序列的子串之间的对应。因此，我们说I与空字符串对齐，N与E对齐，依此类推。在对齐的字符串下面是另一种表示；表示将顶部字符串转换为底部字符串的操作列表的一系列符号：d表示删除，s表示替换，i表示插入。

我们还可以为每项操作分配特定的成本(cost)或权重(weight)。两个序列之间的莱文斯坦距离(Levenshtein dsitance) 是最简单的加权因子(weighting factor)，其中三个操作中的每一个都有1的成本（Levenshtein，1966）。我们假设用一个字母代替它本身，例如用t代替t，成本为零。意图和执行之间的Levenshtein距离为5。Levenshtein还提出了他的度量标准的另一个版本，其中每次插入或删除的成本为1，不允许替换。（这相当于允许替换，但每个替换的成本为2，因为任何替换都可以用一次插入和一次删除来表示）。使用这个版本，意图和执行之间的Levenshtein距离是8。

1、最小编辑距离算法 - The Minimum Edit Distance Algorithm

我们如何找到最小的编辑距离?我们可以把它想象成一个搜索任务，在这个任务中，我们在搜索从一个字符串到另一个字符串的一系列编辑的最短路径。

所有可能编辑的空间都是巨大的(enormous)，所以我们不能天真地(naively)搜索。然而，许多不同的编辑路径最终将处于相同的状态（字符串），因此，我们不需要重新计算所有这些路径，而是可以在每次看到最短路径时记住它。我们可以通过使用动态规划(dynamic programming) 来实现这一点。动态规划是Bellman（1957）首次提出的一类算法的名称，该算法通过组合子问题的解决方案来应用表驱动方法(table-driven method)来解决问题。自然语言处理中一些最常用的算法使用了动态规划，例如 维特比算法(Viterbi algorithm) （第8章）和 CKY算法（第13章）用于解析。

动态规划问题的直觉是，一个大问题可以通过适当地组合各种子问题(sub-problems)的解来解决。考虑表示在下图中所示的字符串intention和execution之间的最小编辑距离的转换词的最短路径(shortest path)。

想象一下某个字符串（可能是exention）处于这个最佳路径(optimal path)（不管它是什么）。动态规划的直觉是，如果exention在最优操作列表中，那么最优序列还必须包括从intention到exention的最优路径。为什么？如果从intention到exention的路径较短，那么我们可以使用它，从而导致整体路径更短，而最佳顺序不会是最优的，从而导致矛盾。

让我们首先定义两个字符串之间的最小编辑距离。给定两个字符串，长度为n的源字符(source string)串X和长度为m的目标字符串(target string)Y，我们将D[i, j]定义为X[1 … i]和Y[1 … j]之间的编辑距离，即X的前i个字符和Y的前j个字符。因此，X和Y之间的编辑距离为D[n, m]。

我们将使用动态规划自下而上计算D[n, m]，结合子问题(subproblems)的解决方案。在基本情况下，如果源子字符串(source substring)的长度为i，但目标字符串为空，则从i个字符到0需要i个删除。目标子字符串长度为j，但空源从0个字符到j个字符需要插入j。通过小i, j去计算D[i, j]，然后，我们根据之前计算的较小值计算较大的D[i, j]。D[i, j]的值是通过矩阵到达的三条可能路径中的最小值来计算的：

如果我们假设Levenshtein距离的版本，其中插入和删除的成本分别为1（ i n s − c o s t ( . ) = d e l − c o s t ( . ) = 1 ins-cost(.)=del-cost(.)=1 ins−cost(.)=del−cost(.)=1），替换的成本为2（除了替换相同字母的成本为零），则D[i, j]的计算为：

算法总结如下图所示，下下图显示了在版本中应用Levenshtein算法对intention与exention距离进行处理的结果。

Alignment(对齐)：知道最小编辑距离对于查找潜在拼写错误更正(potential spelling error corrections)等算法很有用。但编辑距离算法在另一方面很重要；只需稍作改动，它还可以在两个字符串之间提供最低成本的对齐(minimum cost alignment)。在整个语音和语言处理过程中，对齐两个字符串非常有用。在语音识别(speech recognition)中，最小编辑距离对齐用于计算单词错误率(word error rate)（第26章）。对齐在机器翻译中起着重要作用，在机器翻译中，平行语料库(parallel corpus)（包含两种语言文本的语料库）中的句子需要相互匹配。

下图还显示了如何计算该路线的直观性。计算分两步进行。在第一步中，我们增加了最小编辑距离算法，以在每个单元格中存储反向指针(backpointer)。单元格的后向指针指向我们在进入当前单元格时来自的前一个（或多个）单元格。我们在下图中展示了这些反向指针的示意图。有些单元格有多个反向指针，因为最小扩展可能来自多个以前的单元格。在第二步中，我们执行回溯(backtrace)。在回溯中，我们从最后一个单元格（在最后一行和最后一列）开始，沿着指针返回动态规划矩阵。最终单元和初始单元之间的每条完整路径都是最小距离对齐。

当我们使用简单的Levenshtein距离来处理我们的例子时，前面的算法图中的算法允许操作任意权重。例如，对于拼写纠正，键盘上相邻的字母之间更容易发生替换。维特比(Viterbi)算法是最小编辑距离的概率扩展。Viterbi不是计算两个字符串之间的最小编辑距离，而是计算一个字符串与另一个字符串对齐的最大概率。我们将在第8章中进一步讨论这个问题。

总结 Summary

本章介绍了语言处理中的一个基本工具正则表达式(regular expression)，并展示了如何执行基本的文本归一化(text normalization) 任务，包括分词(word segmentation)和归一化(normalization)、句子分割(sentence segmentation) 和词干提取(stemming)。我们还介绍了用于比较字符串的重要最小编辑距离算法(minimum edit distance)。下面是我们对这些想法的主要观点的总结：

• 正则表达式(regular expression) 语言是模式匹配的强大工具
• 正则表达式中的基本操作包括符号的连接(concatenation)、符号的析取(disjunction)([]、|和。)、计数器(counters)(*，+和{n,m})、锚(anchors)(^， $)和优先操作符(precedence operators)((，))。
• 词的标记化和归一化(word tokenization and normalization) 通常是通过简单正则表达式替换或有限自动机级联来完成的。
• 波特算法(Porter algorithm) 是一种简单而有效的方法来做词干词干，去掉词缀。它的精度不高，但可能对某些任务有用。
• 两个字符串之间的最小编辑距离 (minimum edit distance) 是将一个字符串编辑成另一个字符串所需的最小操作数。最小编辑距离可以通过动态规划(dynamic programming) 计算，这也会导致两个字符串对齐(alignment)。

参考

Eric Atwell - Data Mining and Text Analytics

Jurafsky, D. and Martin, J. 2022 Speech and Language Processing 3rd ed.,Pearson

修改时间

2022/2/5

本文标签： 文本