新書推薦：
《
打好你手里的牌（斯多葛主义+现代认知疗法，提升当代人的心理韧性！）
》
售價：NT$
301.0
《
新时代硬道理 广东寻路高质量发展
》
售價：NT$
352.0
《
6S精益管理实战（精装版）
》
售價：NT$
458.0
《
异域回声——晚近海外汉学之文史互动研究
》
售價：NT$
500.0
《
世界文明中的作物迁徙：聚焦亚洲、中东和南美洲被忽视的本土农业文明
》
售價：NT$
454.0
《
无端欢喜
》
售價：NT$
347.0
《
股票大作手操盘术
》
售價：NT$
245.0
《
何以中国·何谓唐代：东欧亚帝国的兴亡与转型
》
售價：NT$
398.0
|
| 編輯推薦： |
|
全书以零基础的读者自学完成一个中文分词系统作为目标。从Java基础语法开始，然后到文本处理相关的数据结构和算法，*后实现文本切分和词性标注。本书是少有的介绍业界热门的Java开发中文分词的书籍。本书选取相关领域的经典内容深入理解和挖掘，也综合了实践性强的创新想法。适用于对软件开发感兴趣的青少年或者大学生。
|
| 內容簡介： |
本书以让零基础的读者通过自学完成一个中文分词系统为目标，从Java基础语法开始讲解，然后介绍文本处理相关的数据结构和算法，*后介绍如何实现文本切分和词性标注。
本书是介绍业界热门的以Java开发中文分词技术的*书籍。本书选取相关领域的经典内容，深入理解和挖掘，也综合了实践性强的创新想法，适合对软件开发感兴趣的青少年或者大学生阅读和学习。
|
| 關於作者： |
|
罗刚，计算机软件硕士，毕业于吉林工业大学。2005年创立北京盈智星科技发展有限公司，2008年联合创立上海数聚软件公司。猎兔搜索创始人，当前猎兔搜索在北京和上海以及石家庄均设有研发部。带领猎兔搜索技术开发团队先后开发出猎兔中文分词系统、猎兔文本挖掘系统，智能垂直搜索系统以及网络信息监测系统等,实现互联网信息的采集、过滤、搜索和实时监测，其开发的搜索软件日用户访问量达万次以上。
|
| 目錄：
|
目 录
第1章 Java软件开发1
1.1 背景3
1.1.1 好身体是一切成功的保证3
1.1.2 路线图4
1.1.3 Java4
1.2 软件工具7
1.2.1 搜索引擎7
1.2.2 Windows命令行8
1.2.3 机器翻译9
1.2.4 Linux10
1.2.5 源代码比较工具11
1.3 Java基础11
1.3.1 准备开发环境11
1.3.2 Eclipse13
1.4 本章小结17
第2章 结构化程序设计19
2.1 基本数据类型19
2.2 变量20
2.2.1 表达式执行顺序22
2.2.2 简化的运算符23
2.2.3 常量24
2.3 控制结构25
2.3.1 语句25
2.3.2 判断条件25
2.3.3 三元运算符27
2.3.4 条件判断27
2.3.5 循环31
2.4 方法36
2.4.1 main方法41
2.4.2 递归调用41
2.4.3 方法调用栈42
2.5 数组42
2.5.1 数组求和45
2.5.2 计算平均值举例45
2.5.3 前趋节点数组46
2.5.4 快速复制47
2.5.5 循环不变式49
2.6 字符串50
2.6.1 字符编码52
2.6.2 格式化53
2.6.3 增强switch语句54
2.7 数值类型54
2.7.1 类型转换58
2.7.2 整数运算59
2.7.3 数值运算60
2.7.4 位运算61
2.8 安装Java69
2.8.1 服务器端安装69
2.8.2 自动安装Java70
2.9 提高代码质量72
2.9.1 代码整洁72
2.9.2 单元测试72
2.9.3 调试73
2.9.4 重构73
2.10 本章小结74
第3章 面向对象编程77
3.1 类和对象77
3.1.1 类78
3.1.2 类方法78
3.1.3 类变量79
3.1.4 实例变量79
3.1.5 构造方法82
3.1.6 对象84
3.1.7 实例方法87
3.1.8 调用方法89
3.1.9 内部类89
3.1.10 克隆90
3.1.11 结束91
3.2 继承92
3.2.1 重写92
3.2.2 继承构造方法94
3.2.3 接口95
3.2.4 匿名类98
3.2.5 类的兼容性98
3.3 封装98
3.4 重载99
3.5 静态100
3.5.1 静态变量100
3.5.2 静态类100
3.5.3 修饰类的关键词101
3.6 枚举类型101
3.7 集合类105
3.7.1 动态数组105
3.7.2 散列表106
3.7.3 泛型109
3.7.4 Google Guava集合112
3.7.5 类型擦除112
3.7.6 遍历114
3.7.7 排序117
3.7.8 lambda表达式119
3.8 比较119
3.8.1 Comparable接口119
3.8.2 比较器120
3.9 SOLID原则122
3.10 异常123
3.10.1 断言123
3.10.2 Java中的异常124
3.10.3 从方法中抛出异常126
3.10.4 处理异常128
3.10.5 正确使用异常130
3.11 字符串对象132
3.11.1 字符对象135
3.11.2 查找字符串135
3.11.3 修改字符串136
3.11.4 格式化136
3.11.5 常量池137
3.11.6 关于对象不可改变139
3.12 日期140
3.13 大数对象141
3.14 给方法传参数142
3.14.1 基本类型和对象143
3.14.2 重载145
3.15 文件操作146
3.15.1 文本文件146
3.15.2 二进制文件149
3.15.3 文件位置152
3.15.4 读写Unicode编码的文件153
3.15.5 文件描述符155
3.15.6 对象序列化156
3.15.7 使用IOUtils160
3.16 Java类库161
3.16.1 使用Java类库162
3.16.2 构建JAR包163
3.16.3 使用Ant167
3.16.4 生成JavaDoc167
3.16.5 ClassLoader168
3.16.6 反射172
3.17 编程风格173
3.17.1 命名规范173
3.17.2 流畅接口174
3.17.3 日志175
3.18 IDEA181
3.19 实例181
3.20 本章小结183
第4章 处理文本185
4.1 字符串操作185
4.2 有限状态机188
4.2.1 从NFA到DFA190
4.2.2 DFA194
4.2.3 DFA交集197
4.2.4 DFA并集203
4.2.5 有限状态转换204
4.3 本章小结207
第5章 数据结构209
5.1 链表209
5.2 树算法210
5.2.1 标准Trie树211
5.2.2 链表Trie树221
5.2.3 二叉搜索树223
5.2.4 数组形式的二叉树227
5.2.5 三叉Trie树233
5.2.6 三叉Trie树交集244
5.2.7 Trie树词典245
5.2.8 平衡Trie树249
5.2.9 B树250
5.3 双数组Trie251
5.4 队列257
5.4.1 链表实现的队列257
5.4.2 优先队列258
5.4.3 找出前k个最大的元素261
5.5 堆栈262
5.6 双端队列264
5.7 散列表268
5.7.1 快速查找的散列表269
5.7.2 HashMap272
5.7.3 应用散列表276
5.7.4 开放式寻址279
5.7.5 布隆过滤器282
5.7.6 SimHash284
5.8 图286
5.8.1 表示图287
5.8.2 遍历图295
5.9 大数据297
5.10 本章小结297
第6章 算法299
6.1 贪婪法299
6.2 分治法301
6.3 动态规划302
6.4 在中文分词中使用动态规划算法303
6.5 本章小结310
第7章 最长匹配分词311
7.1 正向最大长度匹配法312
7.2 逆向最大长度匹配法316
7.3 处理未登录串320
7.4 开发分词324
7.5 本章小结326
第8章 概率语言模型的分词方法327
8.1 一元模型328
8.2 整合基于规则的方法334
8.3 表示切分词图336
8.4 形成切分词图342
8.5 数据基础344
8.5.1 文本形式的词表344
8.5.2 数据库词表348
8.6 改进一元模型349
8.7 二元词典352
8.8 完全二叉数组357
8.9 三元词典360
8.10 N元模型361
8.11 N元分词362
8.12 生成语言模型368
8.13 评估语言模型369
8.14 概率分词的流程与结构370
8.15 本章小结371
第9章 词性标注373
9.1 数据基础376
9.2 隐马尔科夫模型377
9.3 存储数据385
9.4 统计数据390
9.5 整合切分与词性标注392
9.6 知识型词性序列标注396
9.7 本章小结396
参考资源397
后记398
|
| 內容試閱：
|
前言
前门到了，请在后门下车。把前门标注成地名就容易理解这句话了。从种地到买菜、买房、养生保健以及投资理财等，都可以用到中文分词等文本信息挖掘技术。各行业都在构建越来越复杂的软件系统，很多系统都会用到文本处理技术。但是即使在计算机专业，也有很多人对文本信息处理相关技术不太了解。其实，学习相关技术的门槛并不高。而本书就是为了普及相关开发而做的一次新的尝试，其中也结合了作者自己的研究成果，希望为推动相关应用的发展做出贡献。本书借助计算机语言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位虚拟机时，返回64String x = System.getProperty"sun.arch.data.model";System.out.printlnx; 在32位虚拟机中输出32System.out.printlnx.indexOf"64"; 输出-1如果找到了，则返回的值不小于0。所以可以这样写：if x.indexOf"64" ecMap = new HashMap;ecMap.put"I", "我"; 放入一个键值对ecMap.put"love", "爱";ecMap.put"you", "你";
String english = "I love you";
StringTokenizer tokenizer = new StringTokenizerenglish; 用空格分割英文句子whiletokenizer.hasMoreElements { 有更多的词没遍历完System.out.printecMap.gettokenizer.nextToken; 输出：我爱你}StringTokenizer有几个构造方法，其中最复杂的构造方法是：StringTokenizerString str, String delim, boolean returnDelims如果最后这个参数returnDelims标记是false，则分隔字符只作为分隔词使用，一个返回的词是不包括分隔符号的最长序列。如果最后一个参数标记是true，则返回的词可以是分隔字符。默认是false，也就是不返回分隔字符。如果需要把字符串存入二进制文件。可能会用到字符串和字节数组间的互相转换。首先看一下如何从字符串得到字节数组：String word = "的";byte[] validBytes = word.getBytes"utf-8"; 字符串转换成字节数组System.out.printlnvalidBytes.length; 输出长度是3可以直接调用Charset.encode实现字符串转字节数组：Charset charset = Charset.forName"utf-8"; 得到字符集CharBuffer data = CharBuffer.wrap"数据".toCharArray;ByteBuffer bb = charset.encodedata;System.out.printlnbb.limit; 输出数据的实际长度6Charset.decode把字节数组转回字符串：byte[] validBytes = "程序设计".getBytes"utf-8"; 字节数组对字节数组赋值Charset charset = Charset.forName"utf-8"; 得到字符集字节数组转换成字符CharBuffer buffer = charset.decodeByteBuffer.wrapvalidBytes;System.out.printlnbuffer; 输出结果除了使用Charset.decode方法，还可以使用new StringvalidBytes, 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.setLength0;StringBuilder类没有提供现成的方法去掉StringBuilder首尾的空格，下面是一个实现：public static String trimSubstringStringBuilder sb {int first, last;for first=0; firstfirst; last--if !Character.isWhitespacesb.charAtlast-1break;return sb.substringfirst, 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 状态转移表状态输入012Start
中文英文中文End
英文End
End
可以用一个二维数组来记录状态转换表。第一个维度是所有可能的状态，第二个维度是所有可能的事件，二维数组中的值就是目标状态。有限状态机定义如下：public class FSM { 有限状态机static State[][] transTable = new State[State.values.length][10] 状态转换表static { 初始化状态转换表transTable[State.start.ordinal][1] = State.chinese; 普通话请按1transTable[State.start.ordinal][2] = State.english; press two for englishtransTable[State.chinese.ordinal][0] = State.end;transTable[State.english.ordinal][0] = State.end;}State current = State.start; 开始状态State stepState s, char c { 转换函数return transTable[s.ordinal][c -''0''];}}这里使用二维数组来表示状态转换表，也可以用散列表来存储状态转换表。测试这个有限状态机：FSM fsm = new FSM;System.out.printlnfsm.stepfsm.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 状态转移表状态输入01{q0}{q0, q1}{q0}{q1}{q2}*{q2}{q0, q1}{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 从初始状态生成的状态转移表状态输入01{q0}{q0, q1}{q0}{q0, q1}{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 状态转移表状态输入ab{q0}{q2, q3}{q1, q4}{q1}{q2}{q1}*{q2}{q3}{q3}{q4}*{q4}使用即时构建新的状态的方法创建等价的确定状态转移表，如表4-5所示。表4-5 确定状态转移表状态输入ab{q0}{q2, q3}{q1, q4}*{q2, q3}{q3}{q4}*{q1, q4}{q2}{q1}{q3}{q3}{q4}{q1}{q2}{q1}*{q4}*{q2}表4-5中的确定状态转移表中的q2和q4都是结束状态，而且都没有输出状态，所以，可以把q2和q4合并成一个状态，如表4-6所示。构造一个等价的确定有限状态机，使得状态数量最少，这叫作最小化确定有限状态机。表4-6 最小化后的确定状态转移表状态输入ab{q0}{q2, q3}{q1, q2}*{q2, q3}{q3}{q2}*{q1, q2}{q2}{q1}{q3}{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; 把正则表达式转换成DFASystem.out.printlna.toString; 输出有限状态机String s = "ab";System.out.println"Match： " a.runs; 输出true正则表达式a*b|b*a对应的有限状态机是：initial state： 2state 0 [accept]： b - 1 a - 4state 1 [accept]：state 2 [reject]： b - 5 a - 0state 3 [reject]： b - 3 a - 1state 4 [reject]： b - 1 a - 4state 5 [accept]： b - 3 a - 1一共有6个状态，编号从0到5。初始状态是2。表4-7给出了dk.brics.automaton中的状态转移表。表4-7 dk.brics.automaton中的状态转移表状态输入ab0411205313441513如果把{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后到状态01 2----状态1接收输入a后到状态1，状态1接收输入b后到状态21 3----状态2接收输入a后到状态1，状态2接收输入b后到状态31 0----状态3接收输入a后到状态1，状态3接收输入b后到状态03 ----这一行代表接收状态，若有多个接收状态用空格隔开aaabb ----接下来的每行代表一个待识别的字符串abbababbaaabbabbb# ----#号代表待识别的字符串到此结束0 0 ----两个0代表所有输入的结束，或者定义新的DFA开始，格式同上一个DFA图4-8 给定的确定有限状态机处理DFA.in的实现代码如下：static boolean isFinalint x, BitSet acceptStates { 判断x是否为结束状态return acceptStates.getx;}
看状态机能否接收wordstatic boolean recognizeStringint[][] next, BitSet acceptStates, String word {int currentState = 0; 初始状态for int i=0; i transitions = new HashMap; 记录状态之间的转换HashSet finalStates = new HashSet; 记录所有的结束状态public State nextState src, char input { 源状态接收一个字符后到目标状态HashMap stateTransition = transitions.getsrc;if stateTransition == nullreturn null;State dest = stateTransition.getinput;return dest;}判断一个状态是否为结束状态private boolean isFinalState s {return finalStates.containss; 看结束状态集合中是否包含这个状态}public boolean acceptString word { 判断是否可以接收一个单词State currentState = startState; 当前状态从开始状态开始int i = 0;从字符串的开始进入有限状态机for ; i transitions = new HashMap;HashSet finalStates = new HashSet;public DFAState s {startState = s;}public void addFinalStateState newState {finalStates.addnewState;}public void addTransitionState src, char input, State dest {HashMap transition = transitions.getsrc;if transition == null {transition = new HashMap;transitions.putsrc, transition;}transition.putinput, dest;}}根据图4-10生成DFA1的代码：State q0 = new State0;DFA dfa1 = new DFAq0; 接收以0开始的字符串State q1 = new State1;dfa1.addTransitionq0, ''0'', q1;
State q2 = new State2;dfa1.addTransitionq0, ''1'', q2;
dfa1.addTransitionq1, ''0'', q1;dfa1.addTransitionq1, ''1'', q1;
dfa1.addFinalStateq1;
dfa1.addTransitionq2, ''0'', q2;dfa1.addTransitionq2, ''1'', q2;
String word = "101001"; "01001";System.out.printlndfa1.acceptword; 输出false根据图4-11生成DFA2的代码：State r0 = new State0;DFA dfa2 = new DFAr0; 接收以0结束的字符串State r1 = new State1;dfa2.addTransitionr0, ''0'', r1;dfa2.addTransitionr0, ''1'', r0;dfa2.addTransitionr1, ''0'', r1;dfa2.addTransitionr1, ''1'', r0;
dfa2.addFinalStater1;
String word = "1010010"; "01001";System.out.printlndfa2.acceptword; 输出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 intersectionSet setA, Set setB {if setA == nullreturn null;Set tmp = new HashSet;for T x ： setA 遍历集合A中的元素if setB.containsx 如果x也在集合B中tmp.addx; 把同时在集合A和B中的元素加入到交集return tmp;}两个DFA求交集的代码：public static DFAStatePair intersectDFA dfa1, DFA dfa2 {Stack stack = new Stack; 待遍历的状态对StatePair start = new StatePairdfa1.startState, dfa2.startState; 开始状态对DFAStatePair newDFA = new DFAStatePairstart;stack.addstart; 首先加入初始状态HashSet visited = new HashSet; 记住访问历史，避免环路while !stack.isEmpty {StatePair stackValue = stack.pop;Set inputs = intersection dfa1.edgesstackValue.s1, dfa2.edgesstackValue.s2;for char edge ： inputs {同步向前遍历State state1 = dfa1.nextstackValue.s1, edge;State state2 = dfa2.nextstackValue.s2, edge;if state1==null || state2==null {continue;}如果状态对已经存在，则不创建StatePair nextStackPair = newDFA.getOrCreateStatestate1, state2;newDFA.addTransitionstackValue, edge, nextStackPair;ifvisited.containsnextStackPair {continue;}visited.addstackValue;if!stackValue.equalsnextStackPair 避免重复加到待访问的状态stack.addnextStackPair;if dfa1.isFinalstate1 && dfa2.isFinalstate2 {newDFA.addFinalStatenextStackPair; 标志可结束状态}}}return newDFA; 返回两个DFA求交集后的DFA}带默认转换的两个DFA求交集的代码：public static DFAInt intersectDFAInt dfa1, DFAInt dfa2 {if dfa2 == nullreturn dfa1;Stack stack = new Stack;StatePair start = new StatePairdfa1.startState, dfa2.startState; 开始状态对DFAStatePair newDFA = new DFAStatePairstart;stack.addstart;while !stack.isEmpty {StatePair stackValue = stack.pop;Set ret = intersect dfa1.edgesstackValue.s1, dfa2.edgesstackValue.s2;for String edge ： ret {同步向前遍历Integer state1 = dfa1.nextstackValue.s1, edge;Integer state2 = dfa2.nextstackValue.s2, edge;if state1==null && state2==null {continue;}if state1 == nullstate1 = 0;if state2 == nullstate2 = 0;StatePair nextStackPair = new StatePairstate1, state2;newDFA.addTransitionstackValue, edge, nextStackPair;stack.addnextStackPair;if dfa1.isFinalstate1 && dfa2.isFinalstate2 {newDFA.addFinalStatenextStackPair; 标志可结束状态}}默认转换Integer dest1 = dfa1.defaults.getstackValue.s1;Integer dest2 = dfa2.defaults.getstackValue.s2;if dest1==nulldest1 = 0;if dest2==nulldest2 = 0;if dest1!=0 && dest2!=0 {newDFA.defaults.putstackValue, new StatePairdest1, dest2;}}DFAInt finaDFA = new DFAIntnewDFA; 把状态对表示的DFA转换成整数表示的DFAreturn 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 unionSet setA, Set setB {Set tmp = new HashSet;if setA != null {for T x ： setA {tmp.addx;}}if setB != null {for T x ： setB {tmp.addx;}}return tmp;}对两个DFA求并集public static DFAInt unionDFAInt dfa1, DFAInt dfa2 {if dfa2 == nullreturn dfa1;Stack stack = new Stack;StatePair start = new StatePairdfa1.startState, dfa2.startState; 开始状态对DFAStatePair newDFA = new DFAStatePairstart;stack.addstart;while !stack.isEmpty {StatePair stackValue = stack.pop;Set ret = union dfa1.edgesstackValue.s1, dfa2.edgesstackValue.s2;for Character edge ： ret {同步向前遍历Integer state1 = dfa1.nextstackValue.s1, edge;Integer state2 = dfa2.nextstackValue.s2, edge;if state1==null && state2==null {continue;}if state1 == nullstate1 = 0;if state2 == nullstate2 = 0;StatePair nextStackPair = new StatePairstate1, state2;newDFA.addTransitionstackValue, edge, nextStackPair;stack.addnextStackPair;if dfa1.isFinalstate1 || dfa2.isFinalstate2 {newDFA.addFinalStatenextStackPair; 标志可结束状态}}默认转换Integer dest1 = dfa1.defaults.getstackValue.s1;Integer dest2 = dfa2.defaults.getstackValue.s2;if dest1 == nulldest1 = 0;if dest2 == nulldest2 = 0;if dest1!=0 || dest2!=0 {newDFA.defaults.putstackValue, new StatePairdest1, dest2;}}DFAInt finaDFA = new DFAIntnewDFA; 把状态对表示的DFA转换成整数表示的DFAreturn finaDFA;}}4.2.5 有限状态转换面粉经过面条机，就变成了面条。有限状态转换器就是利用有限状态机把输入串映射成输出串的。术语：Finite State Transducer有限状态转换机 是一个有限状态机，映射一个单词字节序列到一个任意的输出。例如判断二进制串的奇偶性。用两个状态s1和s2表示。s1：偶数；s2：奇数。状态转换图如图4-16所示。
图4-16 状态转换图字符串中1的数量是奇数还是偶数。例如：1 0 1 1 0 0 1 s10 0 0 1 0 0 0 s2表4-8给出了状态转换表。表4-8 状态转换表状 态转 换s10s1, 1s2s20s2, 1s1实现这个有限状态转换机的代码如下：int parityString s {int state = 1;forint i=0; i transitions = new HashMap;HashSet finalStates = new HashSet; 结束状态集合public FSTChemistryType... types {int stateId = 1;startState = stateId;int currentState = startState;forChemistryType t ： types {int nextState = currentState 1;HashMap value = new HashMap;value.putt, nextState;transitions.putcurrentState, value;currentState = nextState;}finalStates.addcurrentState;}public String transString sentence, int offset {int atomCount = sentence.length;int i = offset;Integer currentState = startState;StringBuilder wordBuffer = new StringBuilder;while i char c = sentence.charAti;i;ChemistryType input = getTypec;ifinput == nullbreak;currentState = nextcurrentState, input;if currentState == nullbreak;wordBuffer.appendc;}ifisFinalcurrentStatereturn wordBuffer.toString;return null;}}例如二氧化锰的成词规则是汉文数字 化学元素名 化学介词 化学元素名。用一个有限状态转换对象识别这类名词：FST fst = new FSTChemistryType.number, ChemistryType.element,ChemistryType.prep, ChemistryType.element;
String sentence = "二氧化锰溶液";int offset = 0;String n = fst.transsentence, offset; 得到二氧化锰这个化学名词可以使用FST存储键值对。FST的操作包括：合并、级联和组合等。术语：Union合并。Concatenation级联。Composition组合。Closure闭包。可以把标准Trie树看成是有限状态转换机，接收字符，转换出来的也是字符，如图4-18所示。
图4-18 标准Trie树中的有限状态转换机4.3 本 章 小 结幂集构造的方法把NFA转换成DFA，然后再用Hopcroft算法最小化DFA。最小化除了Hopcroft算法，还有Brzozowski算法以及Huffman算法。从字符串到接收器叫作FSA。从字符串到转换器叫作FST。
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
