正则表达式

当我们需要搜索特定形式的文本的时候，就可以使用正则表达式进行处理。

规则

[]：匹配方括号中的任意一个字符

image.png
[A-Za-z]：匹配任意一个字母
image.png

[^]：否定方括号里的字符

image.png

|：或

image.png

? * + .

  • ?：问号前一个字符可以省略
  • *：星号前一个字符可重复 0 次或者多次
  • +：加号前一个字符可重复 1 次或者多次
  • .：句号代表所有字符

image.png

^ $：行开头和行结尾

  • ^[A-Z]：以大写字母开头
  • [A-Z]$：以大写字母结尾

image.png

工具

https://www.regexpal.com/

句子切分与决策树（sentence segmentation and Decision Tree）

句子切分

可以通过标点符号来切分：

  • ! / ?：相对清晰
  • “.”：十分含糊，它可以表示
    • 句子分界
    • 缩写，例如：Inc.
    • 数字，例如：4.3

因此，我们可以构造一个二元分类器，以检查一个标点符号是否表示句子的分界。这个分类器可以通过以下方式实现：

  • 手写规则
  • 正则表达式
  • 机器学习
  • 决策树

决策树

image.png
E-O-S：End Of Sentence

更复杂的决策树特征：

  • 带有“.”的单词的大小写：大小写、首字母是否大写、数字
  • “.”后的单词的大小写：大小写、首字母是否大写、数字
  • 数字特征
    • 带有“.”的单词的长度（区分是否缩写）
    • 概率
      • 带有“.”的单词出现在句子末尾的概率
      • “.”后的单词出现在句子开头的概率

实现

一颗决策树就是一系列的 if-then-else 语句，重点在于特征（条件）的选择。

手动构造决策树通常很难，它只适用于一些非常简单的特征。因此，通常使用机器学习，从训练语料库构造决策树。

Word Tokenization

每一个 NLP 任务都需要进行文本归一化（text normalization）：

  • 切分单词（segmenting/tokenizing words）
  • 归一化单词格式（normalizing word formats）
  • 切分句子（segmenting sentences）

这里先讲单词切分。

单词个数

即对于给定的一个句子，如何确定其中的单词个数？

一个句子中可能会有以下问题：

  • 单词碎片（fragments）
  • 停顿（pauses）
  • 词元（lemma）：具有相同的词干、词性（part of speech）、
    • 例如，cat 和 cats 具有相同的词元
  • 词形（wordform）：表面形式
    • 例如，cat 和 cats 词形就不一样

计算单词个数的方式

  • 根据 Type（根据词汇表），不计重复的单词
    • 用 V 表示词汇表
      • |V| 表示词汇表大小（词汇量）
  • 根据 Token 计数，计算重复的单词
    • 用 N 表示 token 数

例如，对于句子：they lay back on the San Francisco grass and looked at the stars and their。
如果根据 Token 计数：

  • 将“San Francisco”当成一个词，上面句子单词个数为 14；
  • 将“San Francisco”当成两个词，上面句子单词个数为 15；

如果根据 Type 计数：

  • “the”和“and”多个重复，计为一个：
    • 将“San Francisco”当成一个词，则单词个数为 12
      • 将“they”和“their”当成一个词，则单词个数为 11
    • 将“San Francisco”当成两个词，则单词个数为 13
      • 将“they”和“their”当成一个词，则单词个数为 12

image.png

单词切分时可能遇到的问题

  • 引号
    • Finland’s capital 要切分成 Findland、Findlands 还是 Finland’s？
    • what’re、I’m、isn’t 可以切分成 what are、I am、is not
  • dash（-）
    • Hewlett-Packard 要切分成 Hewlett Packard 吗？
    • state-of-the-art 要切分成 state of the art 吗？
  • 是要当成一个 token 还是多个？
    • 例如 San Francisco
  • “.”
    • m.p.h.、PhD. 要如何处理？
  • 语言自身的问题
    • 中文：单词之间并没有空格。

中文中的单词切分

又称为 word segmentation。
标准做法是最大匹配法（Maximum Matching），又称为贪心算法。

最大匹配单词段算法（Maximum Matching Word Segmentation Algorithm）

给定一个中文词汇列表和一个中文句子：

  1. 初始化指针指向句子开头
  2. 在词汇表中查找匹配的最大单词，设置一个分割
  3. 指针跳到分割后，继续执行步骤 2，直至句子处理完毕

伪代码如下：

  1. def maximum_matching_word_segmentation(wordlist, string):
  2.     ptr, N = 0, len(string)
  3.     words = []
  4.     while ptr < N:
  5.         end = find_longest_word_in_wordlist(wordlist, string[ptr:])
  6.         words.append(string[ptr:end+1])
  7.         ptr = end+1
  8.     return words

注：该算法对于英文不总是适用

工具

命令：tr

用来对输入的字符进行替换、压缩和删除

  1. # -s 表示把连续重复的字符以单独一个字符表示
  2. # -c 表示取代所有不属于第一个字符集的字符
  3. # 将输入流中所有不属于大小写字母的字符转换为“\n”，并且把连续重复字符以单独一个字符表示
  4. $ tr -sc 'A-Za-z' '\n' < txt

参考：tr 命令

命令：sort

排序，并按排序结果标准输出

  1. $ sort txt
  2. # -n 按照数值大小排序
  3. # -r 以相反顺序排序
  4. # -d 排序时，只处理英文字母、数字和空格字符，忽略其他字符
  5. $ sort -n -r txt

命令：uniq

用于报告或忽略文件中的重复行

  1. # -c 在每列旁边显示该行重复出现的次数
  2. $ uniq -c txt

单词归一化和词干（Word Normalization and Stemming）

我们需要对单词进行归一化，例如，在信息检索（IR）中，索引和查询都需要单词具有相同的形式。
因此，我们通常会隐式定义单词的等价形式，例如，删除单词中的句号。
或者，对单词进行不对称展开（asymmetric expansion）。例如：

  1. 输入：window        查询：window, windows
  2. 输入：windows    查询：Windows, windows, window
  3. 输入：Windows    查询：Windows

但是，这种展开的效率比较低，因此，还是尽可能使用对称展开（symmetric expansio）。下面介绍对称展开的几种方式。

小写化（case folding）

即，将所有的字母转换成小写。

对于信息检索（IR）类的应用

由于大多数用户都倾向于使用小写，因此小写化是很有用的。
但是，对于句子中的大写字母，大小写形式的含义有可能完全不同，例如：

  • General Motors
  • Fed 与 fed
  • SAIL 与 sail

此时，应该保留大小写形式

对于情感分析、MT、信息提取

大小写形式是很有用的。例如，US 与 us 的区别很有用。

单词变形（lemmatization）

即，将单词变体转换为原形。其任务就是为给定的单词形式找到一个正确的字典词目形式。

例如：

  1. am, are, is --> be
  2. car, cars, car's, cars' --> car
  3. the boy's cars are different colors --> the boy car be different color

词法（morphology）

词法就是研究词素的。

词素

词素（**morpheme**）指的是构成单词的最小单元。

  • 词干（stems）：确定一个词的词汇意义
  • 词缀（affixes）：附加到词干上
    • 通常具有语法意义

例如，对于单词 stems，词干是 stem，词缀是 s。

词干（stemming）

即删除单词词缀，只留下词干。
例如，将 automate(s) / automatic / automation 都转换成 automat。

波特算法（Porter’s algorithm）：最常见的英语词干分析器

即，根据一系列规则，进行简单转换
image.png

参考