描述

开本: 16开纸张: 胶版纸包装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302469360

产品特色

编辑推荐

全书以零基础的读者自学完成一个中文分词系统作为目标。从Java基础语法开始，然后到文本处理相关的数据结构和算法，*后实现文本切分和词性标注。本书是少有的介绍业界热门的Java开发中文分词的书籍。本书选取相关领域的经典内容深入理解和挖掘，也综合了实践性强的创新想法。适用于对软件开发感兴趣的青少年或者大学生。

内容简介

本书以让零基础的读者通过自学完成一个中文分词系统为目标，从Java基础语法开始讲解，然后介绍文本处理相关的数据结构和算法，*后介绍如何实现文本切分和词性标注。

本书是介绍业界热门的以Java开发中文分词技术的*书籍。本书选取相关领域的经典内容，深入理解和挖掘，也综合了实践性强的创新想法，适合对软件开发感兴趣的青少年或者大学生阅读和学习。

作者简介

罗刚，计算机软件硕士，毕业于吉林工业大学。2005年创立北京盈智星科技发展有限公司，2008年联合创立上海数聚软件公司。猎兔搜索创始人，当前猎兔搜索在北京和上海以及石家庄均设有研发部。带领猎兔搜索技术开发团队先后开发出猎兔中文分词系统、猎兔文本挖掘系统，智能垂直搜索系统以及网络信息监测系统等,实现互联网信息的采集、过滤、搜索和实时监测，其开发的搜索软件日用户访问量达万次以上。

目　　录

　　各行业都在构建越来越复杂的软件系统，很多系统都会用到文本处理技术。但是即使在计算机专业，也有很多人对文本信息处理相关技术不太了解。其实，学习相关技术的门槛并不高。而本书就是为了普及相关开发而做的一次新的尝试，其中也结合了作者自己的研究成果，希望为推动相关应用的发展做出贡献。

　　本书借助计算机语言Java实现中文文本信息处理，试图通过恰当的数据结构和算法来应对一些常见的文本处理任务。相关代码可以从清华大学出版社的网站下载。

　　本书的第1章到第3章介绍了相关的Java开发基础。第4章介绍处理文本所用到的有限状态机基本概念和具体实现。第5章介绍相关的基础数据结构。第6章到第9章介绍中文分词原理与实现。

　　书中的很多内容来源于作者的开发和教学实践。作者的实践经验还体现在相关的其他书中，如《自己动手写搜索引擎》、《自然语言处理原理与技术实现》、《自己动手写网络爬虫》、《使用C#开发搜索引擎》、《解密搜索引擎技术实战》等。相对于作者编写的其他书籍，本书更加注意零基础入门。

　　学习是个循序渐进的过程。可以在读者群中共同学习。群体往往比单个人有更多的智慧产出。为了构建出更好的技术群体，请加读者QQ群(453406621)交流。希望快速入门的读者也可以参加相关培训。这本书开始是为一位从苏州专门来北京现场学习的学员入门中文分词而编写。感谢他为编写本书提供的帮助。

　　也希望通过本书能结识更多的同行。有您真诚的建议，我们会发展得更好。例如，通过与同行的交流，让我们的数量、日期等量化信息的提取工具更加成熟。当前，语义分析等文本处理技术仍然需要更深入的发展，来更好地支持各行业的智能软件开发。

　　本书由罗刚、张子宪、崔智杰编著，参与本书编写的还有石天盈、张继红、童晓军，在此一并表示感谢。感谢开源软件和我们的家人、关心我们的老师和朋友、创业伙伴，以及选择猎兔自然语言处理软件的客户多年来的支持。

　　编者

在线试读

第4章处理文本

　　网上聊天时，可能会遇到过找错对象的尴尬事情。程序应该可以帮助判断聊天对象是否正确。

　　XML和JSON这样的文本格式很流行，因为不仅程序可以读，人也是可以读懂的。这样的文本格式也需要解析。

4.1 字符串操作

　　经常需要分割字符串。例如IP地址127.0.0.1按.分割。可以先用String类中的indexOf方法来查找子串“.”，然后再截取子串。例如：

String inputIP = “127.0.0.1”; //本机IP地址

int p = inputIP.indexOf(‘.’); //返回位置3

　　这里的‘.’在字符串“127.0.0.1”中出现了多次。因为是从头开始找起，所以返回次出现的位置3。

　　如果没有找到子串，则indexOf返回-1。例如要判断虚拟机是否为64位的：

//当在32位虚拟机时，将返回32；而在64位虚拟机时，返回64

String x =
System.getProperty(“sun.arch.data.model”);

System.out.println(x); //在32位虚拟机中输出32

System.out.println(x.indexOf(“64”));
//输出-1

　　如果找到了，则返回的值不小于0。所以可以这样写：

if (x.indexOf(“64”) < 0) {

　　System.out.println(“32位虚拟机”);

}

　　indexOf(String str, int fromIndex)从指定位置开始查找。例如：

String inputIP = “127.0.0.1”;

System.out.println(inputIP.indexOf(‘.’,
4)); //输出5，也就是第二个.所在的位置

　　从字符串inputIP里寻找点“.”的位置，但寻找的时候，要从inputIP的索引为4的位置开始，这就是第二个参数4的作用，由于索引是从0开始的，这样，实际寻找的时候是从字符0开始的，所以输出5，也就是第二个点“.”所在的位置。

　　String.subString取得原字符串其中的一段，也就是子串。传入两个参数：开始位置和结束位置。例如：

String inputIP = “127.0.0.1”;

int p = inputIP.indexOf(‘.’);

int q = inputIP.indexOf(‘.’, p 1);

String IPsection1 = inputIP.substring(0,
p); //得到”127″

String IPsection2 = inputIP.substring(p 1,
q); //得到”0″

　　StringTokenizer类专门用来按指定字符分割字符串。StringTokenizer的nextToken()方法取得下一段字符串。

　　hasMoreElements()方法判断是否还有字符串可以读出。可以在StringTokenizer的构造方法中指定用来分隔字符串的字符。

　　例如分割IP地址：

String inputIP = “127.0.0.1”;

StringTokenizer token =

new
StringTokenizer(inputIP, “.”); //用.分割IP地址串

while(token.hasMoreElements()) { //有更多的子串

　　System.out.print(token.nextToken() ” “); //输出下一个子串

}

　　StringTokenizer默认按空格分割字符串。例如翻译英文句子：

HashMap ecMap = new
HashMap();

ecMap.put(“I”, “我”); //放入一个键/值对

ecMap.put(“love”, “爱”);

ecMap.put(“you”, “你”);

String english = “I love you”;

StringTokenizer tokenizer =

new
StringTokenizer(english); //用空格分割英文句子

while(tokenizer.hasMoreElements()) { //有更多的词没遍历完

　　System.out.print(ecMap.get(tokenizer.nextToken())); //输出：我爱你

}

　　StringTokenizer有几个构造方法，其中复杂的构造方法是：

StringTokenizer(String str, String delim,
boolean returnDelims)

　　如果后这个参数returnDelims标记是false，则分隔字符只作为分隔词使用，一个返回的词是不包括分隔符号的长序列。如果后一个参数标记是true，则返回的词可以是分隔字符。默认是false，也就是不返回分隔字符。

　　如果需要把字符串存入二进制文件。可能会用到字符串和字节数组间的互相转换。首先看一下如何从字符串得到字节数组：

String word = “的”;

byte[] validBytes =
word.getBytes(“utf-8”); //字符串转换成字节数组

System.out.println(validBytes.length); //输出长度是3

　　可以直接调用Charset.encode实现字符串转字节数组：

Charset charset =
Charset.forName(“utf-8”); //得到字符集

CharBuffer data = CharBuffer.wrap(“数据”.toCharArray());

ByteBuffer bb = charset.encode(data);

System.out.println(bb.limit()); //输出数据的实际长度6

　　Charset.decode把字节数组转回字符串：

byte[] validBytes = “程序设计”.getBytes(“utf-8”);
//字节数组

//对字节数组赋值

Charset charset =
Charset.forName(“utf-8”); //得到字符集

//字节数组转换成字符

CharBuffer buffer =
charset.decode(ByteBuffer.wrap(validBytes));

System.out.println(buffer); //输出结果

　　除了使用Charset.decode方法，还可以使用new String(validBytes, “UTF-8”)方法把字节数组转换成字符串。

　　合并多个字符串，可以直接用“ ”。一般只有对基本的数据类型才能使用“ ”这样的运算符。String是一个很常用的类，所以能使用运算符计算。String是不可变的对象。因此在每次对String类型进行改变的时候，其实都等同于生成了一个新的String对象。例如：

String name = “Mike”;

name = ” Jack”;

　　这个过程中用到了三个String对象。分别是“Mike”、“ Jack”和“Mike Jack”。考虑把个和第三个对象共用一个，对应一个更长的字符数组。这个对象的类型就是StringBuilder：

StringBuilder name = new
StringBuilder(“Mike”);

name.append(” Jack”);

　　这里用到了两个String对象和一个StringBuilder对象。如果要往字符串后面串接很多字符串，则StringBuilder速度就快了，因为可以一直用它增加很多字符到后面。

　　StringBuilder开始的时候分配一块比较大的内存，可以用来存储比较长的字符串，只有当字符串的长度增加到超过已经有的内存容量时，才会再次分配内存。如图4-1所示。

图4-1 StringBuilder

　　清空StringBuilder时，使用delete方法太麻烦。可以调用setLength方法：

StringBuilder bracketContent = …

bracketContent.setLength(0);

　　StringBuilder类没有提供现成的方法去掉StringBuilder首尾的空格，下面是一个实现：

public static String
trimSubstring(StringBuilder sb) {

　　int first, last;

　　for (first=0; first

　　　　if (!Character.isWhitespace(sb.charAt(first)))

　　　　　　break;

　　for (last=sb.length(); last>first; last–)

　　　　if (!Character.isWhitespace(sb.charAt(last-1)))

　　　　　　break;

　　return sb.substring(first, last);

}

4.2 有限状态机

　　回顾一下拨打电话银行的提示音：普通话请按1，press two for english。查询余额或者缴费结束后，语音提示：结束请按0。按0后通话结束。

　　把所有可能的情况抽象成4个状态：开始状态(start state)、中文状态、英文状态和结束状态(accepting state)。开始状态接收输入事件1到中文状态；开始状态接收输入事件2到英文状态。在中间状态接收输入事件0达到结束状态。

　　可以用图形象地表示这个有限状态机，每个状态用一个圆圈表示。状态之间的转换用一条边表示，边上的说明文字是输入事件。形成的图如图5-1所示。其中双圈节点表示可以作为结束节点。箭头指向的节点是开始节点。开始节点只能有一个，而结束节点可以有多个。这样的图叫作状态转换图。如图4-2所示。

图4-2 电话银行中的有限状态机

　　转换函数，一般记作δ。转换函数的参数是一个状态和输入符号，返回一个状态。一个转换函数可以写成δ(q, a) = p，这里q和p是状态，而a是一个输入符号。转换函数的含义是：如果有限状态机在状态q，而接收到输入a，则有限状态机进入状态p。这里的q可以等于p。

　　例如图4-2中的有限状态机用转换函数表示是：δ(Start, 1) = 中文；δ(Start, 2) = 英文；δ(中文, 0) = End；δ(英文, 0) = End。

　　可以把状态定义成枚举类型：

public enum State {

　　start, //开始状态

　　chinese, //中文

　　english, //英文

　　end //结束状态

}

　　用表4-1所示的状态转换表来记录转换函数。状态转换表中的每行表示一个状态，每列表示一个输入字符。

表4-1 状态转移表

状态/输入

Start

中文

英文

中文

End

英文

End

　　可以用一个二维数组来记录状态转换表。个维度是所有可能的状态，第二个维度是所有可能的事件，二维数组中的值就是目标状态。有限状态机定义如下：

public class FSM { //有限状态机

　　static State[][] transTable =

　　 new
State[State.values.length][10] //状态转换表

　　static { //初始化状态转换表

　　　　transTable[State.start.ordinal()][1] =

　　　　 State.chinese; //普通话请按1

　　　　transTable[State.start.ordinal()][2] =

　　　　 State.english; //press two
for english

　　　　transTable[State.chinese.ordinal()][0] = State.end;

　　　　transTable[State.english.ordinal()][0] = State.end;

　　}

　　State current = State.start;
//开始状态

　　State step(State s, char c) { //转换函数

　　　　return transTable[s.ordinal()][c -‘0’];

　　}

　　这里使用二维数组来表示状态转换表，也可以用散列表来存储状态转换表。

　　测试这个有限状态机：

FSM fsm = new FSM();

System.out.println(fsm.step(fsm.current,
‘1’)); //输出chinese

　　如果从同一个状态接收同样的输入后可以任意到达多个不同的状态，这样的有限状态机叫作非确定有限状态机。从一个状态接收一个输入后只能到达某一个状态，这样的有限状态机叫作确定有限状态机。

术语：NFA(非确定有限状态机) Nondeterministic
Finite-state Automata的简称。DFA则为确定有限状态机，即Deterministic Finite-state Automata的简称。

　　以乘车为例，假设一个站是一个状态，一张票是一个输入。例如，买一张北京的地铁单程票，2块钱可以到任何地方。输入一张地铁单程票，到任何站出来都是有效的。这是非确定有限状态机。输入北京到天津的火车票，则只能从天津站出来，这是确定有限状态机。从上海虹桥火车站检票口输入D318车票可以到达北京，输入G7128车票可以到达南京。

　　火车票中的确定有限状态机如图4-3所示。

图4-3 火车票中的确定有限状态机

4.2.1
从NFA到DFA

　　任何非确定有限状态机都可以转换成确定有限状态机。转换的方法叫作幂集构造(powerset construction)。幂集就是原集合中所有的子集(包括全集和空集)构成的集族。所以幂集构造又叫作子集构造。例如，图4-4中的有限状态机中存在q0、q1、q2三个状态。这些状态的幂集是{ Ø, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2},{q1, q2}, {q0, q1, q2} }。

图4-4 非确定有限状态机

　　图4-4所示的非确定有限状态机使用状态转移表可以表示成表4-2所示的形式。

表4-2 状态转移表

状态/输入

→{q0}

{q0, q1}

{q0}

{q1}

{q2}

*{q2}

{q0, q1}

{q0, q2}

*{q0, q2}

{q0, q1}

{q0}

*{q1, q2}

{q2}

*{q0, q1, q2}

{q0, q1}

{q0, q2}

　　新的转移函数从集合中的任何状态出发，把所有可能的输入都走一遍。带*的状态表示可以结束的状态，类似Trie树中的可结束节点。

　　许多状态可能不能从开始状态达到。从NFA构造等价的DFA的一个好方法，是从开始状态开始，当我们达到它们时，即时构建新的状态。q0输入0，有可能是q0，也可能是q1，所以就把q0和q1捏在一起。也就是产生了组合状态{q0, q1}。q0输入1，只可能是q0。

　　这样构建的表4-3比表4-2小。

表4-3 从初始状态生成的状态转移表

状态/输入

→{q0}

{q0, q1}

{q0}

{q0, q1}

{q0, q2}

*{q0, q2}

{q0, q1}

{q0}

　　图4-4对应的确定有限状态机如图4-5所示。

图4-5 确定有限状态机

　　正则表达式可以写成对应的有限状态机。正则表达式a*b|b*a对应的非确定有限状态机如图4-6所示。

图4-6 非确定有限状态机

　　比如看到输出串个字符是a，这时候还不知道是a*b能匹配上，还是b*a能匹配上，因为两条路都有可能走通。假设整个字符串是aab，这个时候才知道是a*b能匹配上，而b*a不能匹配上。刚开始不知道什么能够匹配上，因为这时在用不确定的有限状态机来匹配。比如说不管白猫黑猫抓住老鼠就是好猫，因为开始时不知道哪个猫更好。图4-6所示的非确定有限状态机对应的状态转移表如表4-4所示。

表4-4 状态转移表

状态/输入

→{q0}

{q2, q3}

{q1, q4}

{q1}

{q2}

{q1}

*{q2}

{q3}

{q4}

*{q4}

　　使用即时构建新的状态的方法创建等价的确定状态转移表，如表4-5所示。

表4-5 确定状态转移表

状态/输入

→{q0}

{q2, q3}

{q1, q4}

*{q2, q3}

{q3}

{q4}

*{q1, q4}

{q2}

{q1}

{q3}

{q4}

{q1}

{q2}

{q1}

*{q4}

*{q2}

　　表4-5中的确定状态转移表中的q2和q4都是结束状态，而且都没有输出状态，所以，可以把q2和q4合并成一个状态，如表4-6所示。构造一个等价的确定有限状态机，使得状态数量少，这叫作小化确定有限状态机。

表4-6 小化后的确定状态转移表

状态/输入

→{q0}

{q2, q3}

{q1, q2}

*{q2, q3}

{q3}

{q2}

*{q1, q2}

{q2}

{q1}

{q3}

{q2}

{q1}

{q2}

{q1}

*{q2}

　　可以简化一些状态而不影响DFA接收的字符串：

* 从初始状态不可达到的状态。

* 一旦进去就不能结束的陷阱状态。

* 对任何输入字符串都不可区分的一些状态。

　　小化的过程，就是自顶向下划分等价状态。如果对于所有的输入都到等价的状态，就把一些状态叫作等价的。这是个循环定义。发现等价状态后，然后删除从初始状态不可到达的无用的状态。

　　发现等价状态往往用分割的方法。首先把所有状态分成可以结束的和不可以结束的两类状态。然后看这两类之间是否有关联，把有关联的类细分开。

　　例如，表4-5中的状态先分成两类：非结束状态{q0},{q1},{q3}和结束状态{q1, q4},{q2, q3},{q2},{q4}。输入符号a和b把非结束状态分成三类{q0},{q1},{q3}。输入符号a和b把结束状态分成三类，{q1,
q4}是类，{q2, q3}是第二类，{q2}和{q4}是第三类。这样，总共得到6个等价类。该方法叫作Hopcroft算法。后得到的确定有限状态机如图4-7所示。

图4-7 确定有限状态机

　　dk.brics.automaton是一个有限状态自动机的实现。它把正则表达式编译成确定有限状态机后，再匹配输入字符串。使用它测试正则表达式：

RegExp r = new RegExp(“a*b|b*a”);
//正则表达式

Automaton a = r.toAutomaton(); //把正则表达式转换成DFA

System.out.println(a.toString()); //输出有限状态机

String s = “ab”;

System.out.println(“Match: ”
a.run(s)); //输出true

　　正则表达式“a*b|b*a”对应的有限状态机是：

initial state: 2

state 0 [accept]:

b
-> 1

a
-> 4

state 1 [accept]:

state 2 [reject]:

b
-> 5

a
-> 0

state 3 [reject]:

b
-> 3

a
-> 1

state 4 [reject]:

b
-> 1

a
-> 4

state 5 [accept]:

b
-> 3

a
-> 1

　　一共有6个状态，编号从0到5。初始状态是2。

　　表4-7给出了dk.brics.automaton中的状态转移表。

表4-7 dk.brics.automaton中的状态转移表

状态/输入

→2

　　如果把{q0}用2代替，{q2, q3}用0代替，{q1, q2}用5代替，{q3}用4代替，{q2}用1代替，{q1}用3代替，则表4-6和表4-7是等价的。

4.2.2
DFA

　　确定有限状态机需要定义初始状态、状态转移函数、结束状态。这里先定义一个确定有限状态机，然后执行它。为了效率，状态定义成从0开始的一个整数编号。默认状态0是DFA的初始状态。

　　首先是一个状态迁移函数，next[][]定义了在一个状态下接收哪些输入后可以转到哪些状态。二维数组next的每一行代表一个状态，每一列代表一个输入符号，第0列代表‘a’，第1列代表‘b’，……，依此类推。

　　例如：定义下面的一个状态迁移二维数组：

int[][] next = {{1,0}, {1,2}}; //其中的数字都是状态编号

　　表示此DFA在状态0时，当输入为‘a’时，迁移到状态1，当输入为‘b’时迁移到状态0；而DFA在状态1时，当输入为‘a’时，迁移到状态1，当输入为‘b’时迁移到状态2。

　　接受状态的集合可以用一个位数组来表示，每个状态用一位表示，所以位数组的长度是状态个数。结束状态的对应位置为1。如果状态2和状态3是接受状态，则acceptStates的第2位和第3位置为1。

　　文本文件DFA.in定义了确定有限状态机的输入和要处理的字符串。例如，对于图4-8所示的确定有限状态机表示如下：

4 2
—-DFA有4个状态，2个输入符号，接下来的4行2列代表状态迁移函数

1 0
—-表示状态0接收输入a后到状态1，状态0接收输入b后到状态0

1 2
—-状态1接收输入a后到状态1，状态1接收输入b后到状态2

1 3
—-状态2接收输入a后到状态1，状态2接收输入b后到状态3

1 0
—-状态3接收输入a后到状态1，状态3接收输入b后到状态0

3
—-这一行代表接收状态，若有多个接收状态用空格隔开

aaabb
—-接下来的每行代表一个待识别的字符串

abbab

abbaaabb

abbb

#
—-‘#’号代表待识别的字符串到此结束

0 0
—-两个0代表所有输入的结束，或者定义新的DFA开始，格式同上一个DFA

图4-8 给定的确定有限状态机

　　处理DFA.in的实现代码如下：

static boolean isFinal(int x, BitSet
acceptStates) { //判断x是否为结束状态

　　return acceptStates.get(x);

}

//看状态机能否接收word

static boolean recognizeString(int[][]
next, BitSet acceptStates,

String word) {

　　int currentState = 0; //初始状态

　　for (int i=0; i

　　　　//进入下一个状态

　　　　currentState = next[currentState][word.charAt(i) – ‘a’];

　　}

　　if (isFinal(currentState, acceptStates))

　　　　return true; //接收

　　else

　　　　return false; //拒绝

}

public static void main(String args[])
throws IOException {

　　//读入要执行的文件

　　BufferedReader in = new BufferedReader(new
FileReader(“DFA.in”));

　　StringTokenizer st = new StringTokenizer(in.readLine());

　　int n = Integer.parseInt(st.nextToken()); //状态数量

　　int m = Integer.parseInt(st.nextToken()); //字符种类

　　while (n != 0) {

　　　　int[][] next = new int[n][m]; //状态转移矩阵

　　　　for (int i=0; i

　　　　　　st = new StringTokenizer(in.readLine());

　　　　　　for (int j=0; j

　　　　　　　　next[i][j] = Integer.parseInt(st.nextToken());

　　　　}

　　　　String line = in.readLine();

　　　　StringTokenizer finalTokens = new StringTokenizer(line);

　　　　BitSet acceptStates = new BitSet(n); //结束状态

　　　　while(finalTokens.hasMoreTokens())

　　　　　　acceptStates.set(Integer.parseInt(finalTokens.nextToken()));

　　　　String word = in.readLine(); //判断能够接收的字符串

　　　　while (word.compareTo(“#”) != 0) {

　　　　　　if (recognizeString(next, acceptStates, word))

　　　　　　　　System.out.println(“YES:” word); //可以接收

　　　　　　else

　　　　　　　　System.out.println(“NO:” word); //不能接收

　　　　　　word = in.readLine();

　　　　}

　　　　st = new StringTokenizer(in.readLine());

　　　　n = Integer.parseInt(st.nextToken());

　　　　m = Integer.parseInt(st.nextToken());

　　}

　　输出的结果是：

YES:aaabb

NO:abbab

YES:abbaaabb

NO:abbb

YES:cacba

　　也可以使用HashMap保存状态转换。用一个专门的State类表示状态。因为要把State对象作为HashMap的键对象，所以重写State类的hashCode和equals方法。

　　DFA的实现代码如下：

public class DFA {

　　public static class State { //有限状态机中的状态

　　　　int state; //用整数表示一个状态

　　　　public State(int s) {

　　　　　　state = s;

　　　　}

　　　　@Override

　　　　public boolean equals(Object obj) {

　　　　　　if (obj==null || !(obj instanceof State)) {

　　　　　　　　return false;

　　　　　　}

　　　　　　State other = (State)obj;

　　　　　　return (state==other.state);

　　　　}

　　　　@Override

　　　　public int hashCode() {

　　　　　　return state;

　　　　}

　　private State startState; //开始状态

　　HashMap> transitions =

　　 new HashMap>(); //记录状态之间的转换

　　HashSet finalStates = new HashSet(); //记录所有的结束状态

　　public State next(State src, char input) { //源状态接收一个字符后到目标状态

　　　　HashMap stateTransition =
transitions.get(src);

　　　　if (stateTransition == null)

　　　　　　return null;

　　　　State dest = stateTransition.get(input);

　　　　return dest;

　　}

　　//判断一个状态是否为结束状态

　　private boolean isFinal(State s) {

　　　　return finalStates.contains(s); //看结束状态集合中是否包含这个状态

　　}

　　public boolean accept(String word) { //判断是否可以接收一个单词

　　　　State currentState = startState;
//当前状态从开始状态开始

　　　　int i = 0; //从字符串的开始进入有限状态机

　　　　for (; i

　　　　　　char c = word.charAt(i);

　　　　　　//当前状态接收一个字符后，到达下一个状态

　　　　　　currentState = next(currentState, c);

　　　　　　if (currentState == null)

　　　　　　　　break;

　　　　}

　　　　//如果已经到达后一个字符，而且当前状态是结束状态，就可以接收这个单词

　　　　if (i==word.length() && isFinal(currentState))

　　　　　　return true;

　　　　return false;

　　}

　　如果直接使用整数作为状态State，则把这个类叫作DFAInt。

4.2.3
DFA交集

　　有两个DFA，每个DFA可以接收一些词表。两个DFA都可以接收的单词组成的新的DFA叫作DFA交集。如DFA1接受单词{“foo”, “foods”, “food”}，DFA2接受单词{“seed”, “food”}。DFA1和DFA2的交集就是接受单词{“food”}的DFA。

　　求交集的方法是：把其中一个DFA中的状态映射到另外一个DFA中的状态。例如，图4-9左边的DFA状态i接收输入0以后转换到状态j，状态i接收输入1以后转换到状态k。状态j和状态k被映射到右边的DFA，因为右边的DFA也存在从开始状态接收输入0以后转换到一个新状态，从开始状态接收输入1以后转换到另外一个新状态。

图4-9 DFA取交集

　　例如，图4-10中的DFA1接收以0开始的字符串，例如“0111”。图4-11中的DFA2接收以0结束的字符串，例如“1110”。这两个DFA求交集的结果是一个新的DFA，它接收以0开始并且以0结束的字符串，例如“00111000”。

图4-10 接收以0开始的字符串的DFA1

图4-11 接收以0结束的字符串的DFA2

　　生成DFA的代码如下：

public class DFA {

　　private State startState; //开始状态

　　HashMap> transitions =

　　 new HashMap>();

　　HashSet finalStates = new HashSet();

　　public DFA(State s) {

　　　　startState = s;

　　}

　　public void addFinalState(State newState) {

　　　　finalStates.add(newState);

　　}

　　public void addTransition(State src, char input, State dest) {

　　　　HashMap transition = transitions.get(src);

　　　　if (transition == null) {

　　　　　　transition = new HashMap();

　　　　　　transitions.put(src, transition);

　　　　}

　　　　transition.put(input, dest);

　　}

　　根据图4-10生成DFA1的代码：

State q0 = new State(0);

DFA dfa1 = new DFA(q0); //接收以0开始的字符串

State q1 = new State(1);

dfa1.addTransition(q0, ‘0’, q1);

State q2 = new State(2);

dfa1.addTransition(q0, ‘1’, q2);

dfa1.addTransition(q1, ‘0’, q1);

dfa1.addTransition(q1, ‘1’, q1);

dfa1.addFinalState(q1);

dfa1.addTransition(q2, ‘0’, q2);

dfa1.addTransition(q2, ‘1’, q2);

String word = “101001”;
//”01001″;

System.out.println(dfa1.accept(word)); //输出false

　　根据图4-11生成DFA2的代码：

State r0 = new State(0);

DFA dfa2 = new DFA(r0); //接收以0结束的字符串

State r1 = new State(1);

dfa2.addTransition(r0, ‘0’, r1);

dfa2.addTransition(r0, ‘1’, r0);

dfa2.addTransition(r1, ‘0’, r1);

dfa2.addTransition(r1, ‘1’, r0);

dfa2.addFinalState(r1);

String word = “1010010”;
//”01001″;

System.out.println(dfa2.accept(word)); //输出true

　　做一个新的DFA，其中的状态就是原来两个DFA所在的状态对(qi, rj)。

　　开始的时候，它们都在开始状态，如图4-12所示。

图4-12 交集DFA中的初始状态对

然后从那里开始，追踪状态对(qi, rj)。DFA1和DFA2步调一致地前进。例如q0接收0之后到达q1，r0接收0之后到达r1，所以(q1, r1)是状态对。q0接收1之后到达q2，r0接收1之后到达r0，所以(q2, r0)是状态对。这样就得到了如图4-13所示的交集状态对。

图4-13 交集DFA中的状态对

　　终，状态对重复，接近结束生成新的DFA，如图4-14所示。

图4-14 交集DFA中接近结束的状态对

　　两个DFA都可以作为结束状态，新的状态才能算作可结束的状态。例如状态对(q1, r1)中的两个原来的状态都是可以结束的，所以新状态(q1, r1)也是可以结束的。如图4-15所示。

图4-15 交集DFA中的可结束状态

　　把DFA1中的当前状态叫作s1，DFA2中的当前状态叫作s2。s1和s2组成一个当前状态对。当前状态对还要记录已经接收过的字符序列。

　　当前状态对StatePair类的部分代码如下：

public static class StatePair { //当前状态对

　　State s1; //DFA1中的当前状态

　　State s2; //DFA2中的当前状态

}

　　在每个当前状态对中，都对状态s1和s2的所有可能接收的输入求交集。对两个输入集合求交集的代码如下：

public static Set
intersection(Set setA, Set setB) {

　　if (setA == null)

　　　　return null;

　　Set tmp = new HashSet();

　　for (T x : setA) //遍历集合A中的元素

　　　　if (setB.contains(x)) //如果x也在集合B中

　　　　　　tmp.add(x); //把同时在集合A和B中的元素加入到交集

　　return tmp;

}

　　两个DFA求交集的代码：

public static DFAStatePair intersect(DFA
dfa1, DFA dfa2) {

　　Stack stack = new Stack(); //待遍历的状态对

　　StatePair start =

　　 new
StatePair(dfa1.startState, dfa2.startState); //开始状态对

　　DFAStatePair newDFA = new DFAStatePair(start);

　　stack.add(start); //首先加入初始状态

　　HashSet visited =

　　 new
HashSet(); //记住访问历史，避免环路

　　while (!stack.isEmpty()) {

　　　　StatePair stackValue = stack.pop();

　　　　Set inputs = intersection(

　　　　 dfa1.edges(stackValue.s1),
dfa2.edges(stackValue.s2));

　　　　for (char edge : inputs) {

　　　　　　//同步向前遍历

　　　　　　State state1 = dfa1.next(stackValue.s1, edge);

　　　　　　State state2 = dfa2.next(stackValue.s2, edge);

　　　　　　if (state1==null || state2==null) {

　　　　　　　　continue;

　　　　　　}

　　　　　　//如果状态对已经存在，则不创建

　　　　　　StatePair nextStackPair =

　　　　　　
newDFA.getOrCreateState(state1, state2);

　　　　　　newDFA.addTransition(stackValue, edge, nextStackPair);

　　　　　　if(visited.contains(nextStackPair)) {

　　　　　　　　continue;

　　　　　　}

　　　　　　visited.add(stackValue);

　　　　　　if(!stackValue.equals(nextStackPair)) //避免重复加到待访问的状态

　　　　　　　　stack.add(nextStackPair);

　　　　　　if (dfa1.isFinal(state1) && dfa2.isFinal(state2)) {

　　　　　　　　newDFA.addFinalState(nextStackPair);
//标志可结束状态

　　　　　　}

　　return newDFA; //返回两个DFA求交集后的DFA

}

　　带默认转换的两个DFA求交集的代码：

public static DFAInt intersect(DFAInt dfa1,
DFAInt dfa2) {

　　if (dfa2 == null)

　　　　return dfa1;

　　Stack stack = new Stack();

　　StatePair start =

　　 new
StatePair(dfa1.startState, dfa2.startState);
//开始状态对

　　DFAStatePair newDFA = new DFAStatePair(start);

　　stack.add(start);

　　while (!stack.isEmpty()) {

　　　　StatePair stackValue = stack.pop();

　　　　Set ret = intersect(

　　　　 dfa1.edges(stackValue.s1),
dfa2.edges(stackValue.s2));

　　　　for (String edge : ret) {

　　　　　　//同步向前遍历

　　　　　　Integer state1 = dfa1.next(stackValue.s1, edge);

　　　　　　Integer state2 = dfa2.next(stackValue.s2, edge);

　　　　　　if (state1==null && state2==null) {

　　　　　　　　continue;

　　　　　　}

　　　　　　if (state1 == null)

　　　　　　　　state1 = 0;

　　　　　　if (state2 == null)

　　　　　　　　state2 = 0;

　　　　　　StatePair nextStackPair = new StatePair(state1, state2);

　　　　　　newDFA.addTransition(stackValue, edge, nextStackPair);

　　　　　　stack.add(nextStackPair);

　　　　　　if (dfa1.isFinal(state1) && dfa2.isFinal(state2)) {

　　　　　　　　newDFA.addFinalState(nextStackPair);
//标志可结束状态

　　　　　　}

　　　　//默认转换

　　　　Integer dest1 = dfa1.defaults.get(stackValue.s1);

　　　　Integer dest2 = dfa2.defaults.get(stackValue.s2);

　　　　if (dest1==null)

　　　　　　dest1 = 0;

　　　　if (dest2==null)

　　　　　　dest2 = 0;

　　　　if (dest1!=0 && dest2!=0) {

　　　　　　newDFA.defaults.put(stackValue, new StatePair(dest1, dest2));

　　　　}

　　DFAInt finaDFA = new DFAInt(newDFA); //把状态对表示的DFA转换成整数表示的DFA

　　return finaDFA;

}

4.2.4
DFA并集

　　对两个DFA求并集得到的DFA有这样的特征：它可以接收两个DFA中任何一个可以接收的单词。这样的运算叫作DFA求并集，也就是Union操作。

　　例如，当前位于状态Ab，得到输入0以后，个DFA到达状态B，第二个DFA到达状态b，并集DFA接收这个输入后的下一个状态是Bb。这里的Ab和Bb都是个DFA和第二个DFA的状态组合。在输入0后，如果有一个DFA状态不变呢？如果以前的状态是A，那新状态就还是那个A，例如，从Ab到Ad。

　　DFA求并集的代码如下：

public class DFAUnion {

　　// 对两个输入集合求并集

　　public static Set union(Set setA,
Set setB) {

　　　　Set tmp = new HashSet();

　　　　if (setA != null) {

　　　　　　for (T x : setA) {

　　　　　　　　tmp.add(x);

　　　　　　}

　　　　if (setB != null) {

　　　　　　for (T x : setB) {

　　　　　　　　tmp.add(x);

　　　　　　}

　　　　return tmp;

　　}

　　//对两个DFA求并集

　　public static DFAInt union(DFAInt dfa1, DFAInt dfa2) {

　　　　if (dfa2 == null)

　　　　　　return dfa1;

　　　　Stack stack = new Stack();

　　　　StatePair start =

　　　　 new
StatePair(dfa1.startState, dfa2.startState);
//开始状态对

　　　　DFAStatePair newDFA = new DFAStatePair(start);

　　　　stack.add(start);

　　　　while (!stack.isEmpty()) {

　　　　　　StatePair stackValue = stack.pop();

　　　　　　Set ret = union(

　　　　　　 dfa1.edges(stackValue.s1),
dfa2.edges(stackValue.s2));

　　　　　　for (Character edge : ret) {

　　　　　　　　//同步向前遍历

　　　　　　　　Integer state1 = dfa1.next(stackValue.s1, edge);

　　　　　　　　Integer state2 = dfa2.next(stackValue.s2, edge);

　　　　　　　　if (state1==null && state2==null) {

　　　　　　　　　　continue;

　　　　　　　　}

　　　　　　　　if (state1 == null)

　　　　　　　　　　state1 = 0;

　　　　　　　　if (state2 == null)

　　　　　　　　　　state2 = 0;

　　　　　　　　StatePair nextStackPair = new StatePair(state1, state2);

　　　　　　　　newDFA.addTransition(stackValue, edge, nextStackPair);

　　　　　　　　stack.add(nextStackPair);

　　　　　　　　if (dfa1.isFinal(state1) || dfa2.isFinal(state2)) {

　　　　　　　　　　newDFA.addFinalState(nextStackPair);
//标志可结束状态

　　　　　　　　}

　　　　　　//默认转换

　　　　　　Integer dest1 = dfa1.defaults.get(stackValue.s1);

　　　　　　Integer dest2 = dfa2.defaults.get(stackValue.s2);

　　　　　　if (dest1 == null)

　　　　　　　　dest1 = 0;

　　　　　　if (dest2 == null)

　　　　　　　　dest2 = 0;

　　　　　　if (dest1!=0 || dest2!=0) {

　　　　　　　　newDFA.defaults.put(stackValue, new StatePair(dest1, dest2));

　　　　　　}

　　　　DFAInt finaDFA =

　　　　 new DFAInt(newDFA); //把状态对表示的DFA转换成整数表示的DFA

　　　　return finaDFA;

　　}

4.2.5
有限状态转换

　　面粉经过面条机，就变成了面条。有限状态转换器就是利用有限状态机把输入串映射成输出串的。

术语：Finite State Transducer(有限状态转换机) 是一个有限状态机，映射一个单词(字节序列)到一个任意的输出。

　　例如判断二进制串的奇偶性。用两个状态s1和s2表示。s1：偶数；s2：奇数。

　　状态转换图如图4-16所示。

图4-16 状态转换图

　　字符串中1的数量是奇数还是偶数。例如：

　　1 0 1 1 0 0 1 → s1

　　0 0 0 1 0 0 0 → s2

　　表4-8给出了状态转换表。

表4-8 状态转换表

状态

转换

0→s1, 1→s2

0→s2, 1→s1

　　实现这个有限状态转换机的代码如下：

int parity(String s) {

　　int state = 1;

　　for(int i=0; i

　　　　char ch = s.charAt(i);

　　　　switch (state) {

　　　　　　case 1:

　　　　　　　　if(ch==’1′)

　　　　　　　　　　state = 2;

　　　　　　　　break;

　　　　　　case 2:

　　　　　　　　if(ch==’1′)

　　　　　　　　　　state = 1;

　　　　　　　　break;

　　　　}

　　}

　　return state;

}

　　测试这个方法：

System.out.print(parity(“01010”));
//输出1

　　有限状态转换机如图4-17所示。

图4-17 有限状态转换机

　　为了构建小完美散列，需要把排好序的单词{clear, clever, ear, ever, fat, father}映射到序号(0, 1,
2, …)。当遍历的时候，把经过的值加起来，例如father在f命中4并且在h命中1，因此它的输出是5。

　　根据构词规则识别“二氧化锰”这样的化学专有名词。化学物质的成词语素如下。

* 化学元素名：溴、氧、氯、碳、硫、磷……；锑、银、铜、锡、铁、锰……

* 化学功能名：酸、胺、脂、酮、酰、烷、酚、酊、羟……

* 化学介词：化、合、代、聚、缩、并、杂、联……

* 特定词头：亚、过、偏、原、次、高、焦、连……

* 各类符号：阿拉伯数字、罗马数字、汉文数字、天干、希腊字母、英文字母、标点符号。

　　把成词语素定义成枚举类型：

public enum ChemistryType {

　　element, //化学元素，例如：溴、氧、氯、碳、硫、磷

　　function, //化学功能，例如：酸、胺、脂、酮、酰

　　prep, //化学介词，例如：化、合、代、聚、缩、并、杂、联

　　prefix, //前缀，例如：亚、过、偏、原、次、高、焦、连

　　number; //数字

}

　　有限状态转换：

public class FST {

　　int startState; //开始状态编号

　　HashMap>
transitions =

　　 new HashMap>();

　　HashSet finalStates = new HashSet();
//结束状态集合

　　public FST(ChemistryType… types) {

　　　　int stateId = 1;

　　　　startState = stateId;

　　　　int currentState = startState;

　　　　for(ChemistryType t : types) {

　　　　　　int nextState = currentState 1;

　　　　　　HashMap value =

　　　　　　 new
HashMap();

　　　　　　value.put(t, nextState);

　　　　　　transitions.put(currentState, value);

　　　　　　currentState = nextState;

　　　　}

　　　　finalStates.add(currentState);

　　}

　　public String trans(String sentence, int offset) {

　　　　int atomCount = sentence.length();

　　　　int i = offset;

　　　　Integer currentState = startState;

　　　　StringBuilder wordBuffer = new StringBuilder();

　　　　while (i

　　　　　　char c = sentence.charAt(i);

　　　　　　i ;

　　　　　　ChemistryType input = getType(c);

　　　　　　if(input == null)

　　　　　　　　break;

　　　　　　currentState = next(currentState, input);

　　　　　　if (currentState == null)

　　　　　　　　break;

　　　　　　wordBuffer.append(c);

　　　　}

　　　　if(isFinal(currentState))

　　　　　　return wordBuffer.toString();

　　　　return null;

　　}

}

　　例如“二氧化锰”的成词规则是“汉文数字化学元素名化学介词化学元素名”。用一个有限状态转换对象识别这类名词：

FST fst =

new
FST(ChemistryType.number, ChemistryType.element,

ChemistryType.prep, ChemistryType.element);

String sentence = “二氧化锰溶液”;

int offset = 0;

String n = fst.trans(sentence, offset); //得到“二氧化锰”这个化学名词

　　可以使用FST存储键/值对。

　　FST的操作包括：合并、级联和组合等。

术语：Union(合并)。Concatenation(级联)。Composition(组合)。Closure(闭包)。

　　可以把标准Trie树看成是有限状态转换机，接收字符，转换出来的也是字符，如图4-18所示。

图4-18 标准Trie树中的有限状态转换机

4.3 本章小结

　　幂集构造的方法把NFA转换成DFA，然后再用Hopcroft算法小化DFA。小化除了Hopcroft算法，还有Brzozowski算法以及Huffman算法。

　　从字符串到接收器叫作FSA。从字符串到转换器叫作FST。

书摘插画

Java中文文本信息处理—从海量到精准

猎兔搜索工程师数十年技术积淀与升华，算法基本原理与具体搜索技术的完美结合，重新设计面向未来的人工智能代码实现，带领读者快速入门中文分词软件系统

作者:罗刚张子宪崔智杰出版社:清华大学出版社出版时间:2017年05月

ISBN: 9787302469360

年中特卖用“SALE15”折扣卷全场书籍85折！可与三本88折，六本78折的优惠叠加计算！全球包邮!

描述

目录

抢先评论了 “Java中文文本信息处理—从海量到精准” 取消回复

评论

Java中文文本信息处理—从海量到精准

猎兔搜索工程师数十年技术积淀与升华，算法基本原理与具体搜索技术的完美结合，重新设计面向未来的人工智能代码实现，带领读者快速入门中文分词软件系统

作者:罗刚 张子宪 崔智杰 出版社:清华大学出版社 出版时间:2017年05月

ISBN: 9787302469360

年中特卖用“SALE15”折扣卷全场书籍85折！可与三本88折，六本78折的优惠叠加计算！全球包邮!

描述

目 录

抢先评论了 “Java中文文本信息处理—从海量到精准” 取消回复

评论

相关产品

学习使用C指针（影印版）

Unity 3D脚本编程——使用C#语言开发跨平台游戏

深度学习入门 基于Python的理论与实现

Python基础教程（第3版）

作者:罗刚张子宪崔智杰出版社:清华大学出版社出版时间:2017年05月

目录

深度学习入门基于Python的理论与实现