Natural Language Processing with Python

引言

人类的语言有五千多种,研究人类起源的专家认为,通过口语交流是人类区别于其他动物的最显著标志。

自然语言处理( Natural Language Processing,NLP)是指采用计算机技术处理自然语言,包括词性标注(Part-Of-Speech,POS)、文本分类(Text Classification)、句法分析(Syntactic Analysis)等任务。NLP是很多任务或者系统的基础,例如语音合成系统等,已成为人工智能的基础。

两大工具:

  • Python。Python已经广泛应用到很多领域,成为很多程序员的利器,也是很多项目的支撑。这里采用Python2.7:https://www.python.org/downloads/
  • NLTK(Natural Language Toolkit)。包含了相关的软件、数据以及文档。下载地址:http://www.nltk.org/

语言处理与Python

文本语料和词汇资源

处理原始文本

编写结构化程序

词的分类与标注

分类文本

文本信息抽取

句法结构分析

基于特征的句法

语义分析

语言数据的管理

TIMIT

获取数据

标注的层次大致可分为如下几种:

  • 词正则化
  • 句子切分
  • 段落切分
  • 词性标注
  • 语义结构
  • 浅层语义
  • 对话与交谈

标注的方式:

  • 内嵌标注(inline annotation):直接修改原始文档,插入相关的标注信息。
  • 外置标注(standoff annotation):不修改原始文档,通过在额外文档中的标注信息实现。

参考文献

  1. Bird S, Klein E, Loper E. Natural language processing with Python[M]. “ O’Reilly Media, Inc.”, 2009.

使用PIP管理Python模块(Use pip install package)

简介

Pip是管理Python模块的工具,目前Python3中已经包含,但是Python2中没有。
使用Pip可以很好管理Python模块,例如安装某一模块。

安装pip

安装PIP最简单的方式是利用PIP源码安装:获取pip
解压缩代码压缩包,进入路径,运行setup.py即可。具体如下所示。

1
python setup.py install

配置pip国内源

编辑或者新建配置文件
vim ~/.pip/pip.conf

1
2
[global]
index-url = https://pypi.tuna.tsinghua.edu.cn/simple

安装模块

PIP安装好之后,就可以很简单地利用其安装其他模块了。具体如下所示。

1
python -m pip install PackageName

深入理解计算机系统--存储器层次结构

引言

存储器系统是一个具有不同容量、成本以及访问时间的存储设备的层次结构。
局部性(locality)是计算机程序的一个基本属性。

局部性

局部性的两周形式:

  • 时间局部性(temporal locality):具有良好时间局部性的程序,被引用过一次的存储器位置很可能在不远的将来继续被多次引用。
  • 空间局部性(spatial locality):具有良好空间局部性的程序,如果一个存储器位置被引用了一次,那么不久的将来,附近的存储器位置很可能被引用。

程序员要理解局部性原理并应用到代码中,有良好局部性的程序比局部性差的程序运行得更快。

引用程序数据的局部性

一个连续向量中,每隔k个元素进行访问,被称为步长为k的引用模式。

取指令的局部性

由于程序指令是存放在存储器中的,CPU需要取出这些指令,所以一个程序也具有取指令的局部性。

局部性小结

  • 重复引用同一个变量的程序具有良好的时间局部性。
  • 对于取指令,循环具有较好的时间和空间局部性。循环体越小,循环迭代次数越多,局部性越好。

存储器的层次结构

存储器层次结构的中心思想是,k层的更快更小的存储设备作为k+1层的更大更慢的存储设备的缓存。也就是说,存储器层次结构的本质是每一层存储设备都是较低一层的缓存。

数据以块为传送单元在第k层和第k+1层之间来回拷贝。

高速缓存存储器

参考文献

  • (美)布莱恩特(Bryant, R. E.), (美)奥哈拉伦(O’Hallaron),等. 深入理解计算机系统[M]. 机械工业出版社, 2012.

深入理解计算机系统--链接

引言

链接是将各种代码和数据收集起来并组合成一个单一文件的过程,这个文件可被加载到存储器并执行。
现代系统中,链接是由链接器(linker)自动执行的。

符号解析

首先定义强符号与弱符号。

  • 强符号:函数和已初始化的全局变量。
  • 弱符号:未初始化的全局变量。

规则1

不允许有多个强符号。

规则2

如果有一个强符号和多个弱符号,那么选择强符号。
如果在一个模块里x未被初始化,那么链接器将安静地选择定义在另一个模块中的强符号。

规则3

如果有多个弱符号,那么从这些弱符号中任意选择一个。

一个有趣的错误

在foo5模块中,x被定义为int类型;在bar5模块,x被定义为double类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//foo5.c
#include <stdio.h>
void f(void);

int x = 15213;
int y = 15212;

int main()
{
f();
printf("x = 0x%x, y = 0x%x\n", x, y);
return 0;
}

//bar5.c
double x;

void f() {
x = -0.0;
}

使用gcc(版本为4.8.0)编译,会有警告信息。与参考文献中所说的没有警告信息有出入。

1
2
$gcc -o foobar5 foo5.c  bar5.c 
$/usr/bin/ld: Warning: alignment 4 of symbol `x' in /tmp/ccrGpxXb.o is smaller than 8 in /tmp/ccYL3Zqs.o

运行结果:

1
2
$./foobar5
$x = 0x0, y = 0x80000000

结果显示,y的值被修改,这是因为double类型是8个字节,int类型是4个字节,在bar5模块中对x赋值,双精度浮点数覆盖了存储器中x和y的位置。

重定位

链接器完成符号解析之后,就可以把代码中的每个符号引用和确定的一个符号定义联系起来。此时,链接器就知道它的输入目标模块中的代码节和数据节的确切大小,就可以开始重定位了。
重定位由两步组成:

  1. 重定位节和符号定义。链接器将所有相同类型的节合并,得到新的聚合节。
  2. 重定位节中的符号定义。链接器修改代码节和数据节中对每个符号的引用,使他们指向正确的地址。

动态链接共享库

静态库的缺点

  1. 需要定期维护和更新,如果程序员想使用最新版本,必须了解该库的更新情况,显式地将程序与更新的库重新链接。
  2. 库中被调用函数的代码会被复制到每个运行进程的代码段中,几乎每个程序都会包含标准I/O函数,这对存储资源是一种浪费。

共享库是致力于解决静态库缺陷的一个现代创新产物。共享库是一个目标模块,在运行时可以加载到任意的存储器地址,并和一个在存储器的程序链接起来。这个过程称为动态链接,由动态链接器的程序来执行。

共享库也称为共享目标(shared object)。在Unix、Linux系统中通常用后缀.so来表示。Window系统也大量利用了共享库,称为动态链接库,用后缀.dll来表示。

参考文献

  • (美)布莱恩特(Bryant, R. E.), (美)奥哈拉伦(O’Hallaron),等. 深入理解计算机系统[M]. 机械工业出版社, 2012.

基于深层神经网络的语音合成

简介

随着深度学习在各个领域取得了优异的性能,例如计算机视觉、自然语言处理领域。深度学习也被应用到语音合成中,并取得了不错的效果。本文就简单介绍基于深层神经网络的语音合成。

基于DBN的语音合成

深层置信网络(Deep Neural Network,DBN)是概率生成模型,其中包含了多个隐层。

基于DBN的语音合成系统框图

基于DNN的语音合成

深层神经网络(Deep Neural Network,DNN)是一种前馈神经网络,除了输入层和输出层,包含多个隐层。

基于DNN的语音合成系统框图

基于RNN的语音合成

循环神经网络(Recurrent Neural Network,RNN)包含循环连接,可以获取输入序列任意时刻的信息。

基于RNN的语音合成系统框图

总结

  • 在客观指标方面,基于深层神经网络的语音合成显著优于传统的语音合成(例如基于HMM的语音合成)。
  • 在主观听感方面,基于深层神经网络的语音合成整体高于基于HMM的语音合成,但是某些地方会出现较差的情况。
  • 基于深层神经网络的语音合成需要更多的计算量。

参考文献

  • S.-Y. Kang, X.-J. Qian, and H. Meng, “Multi-distribution deep belief network for speech synthesis,” in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Pro- cessing (ICASSP), 2013, pp. 8012–8016.
  • H. Zen, A. Senior, and M. Schuster, “Statistical parametric speech synthesis using deep neural networks,” in Proc. IEEE Int. Conf. Acoustics, Speech and Sig- nal Processing (ICASSP), 2013, pp. 7962–7966.
  • Y. C. Fan, Y. Qian, F. L. Xie, F. K. Soong. TTS synthesis with bidirectional LSTM based recurrent neural networks.[C]. Interspeech. 2014, pp. 1964–1968.

LeetCode Word Search 2

Description

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return [“eat”,”oath”].

The original problem is here.

The original code is here.

Read More