自然语言处理

前文实现了 Patricia Trie，但用的是字符比较，而原论文则采用的是二进制位比较。 然后，我们心里可能会有疑问：二进制位比较是如何推广到字符比较的呢？二进制位比较相比于字符比较，又有哪些优点或缺点呢？ 相关代码：https://github.com/patricklaux/perfect-code 1. 基数 让我们先从基数说起吧。 1.1. 基数(radix) 基数(radix)，在定位数系(positional numeral system) 中表示不重复编码(digit) 的数量。 譬如在10进制中，有 {0, 1, 2, … ,8, 9} 共 10 个编码，那么基数就是 10； 譬如在16进制中，有 {0, 1, 2, … ,e, f} 共 16 个编码，那么基数就是 16； ………… 如果我们用 EASCII 字符编码来作为集合，那么其基数就是 256； 如果我们用 UTF-16 字符编码来作为集合，那么其基数就是 65536； ………… 如果我们用小写英文字母 {a, b, c, … , y, z} 来作为集合，那么其基数就是26。 也就是说，我们可以根据需要定义一套编码集，而基数就是这套编码集的元素数量。 注：基数(radix) 也可以看作是集合论中的基数(cardinal)，而编码集是有限良序集。 1.2. 基数树(radix tree) 基数概念推广到树中，那么这个基数就是 R 的大小。 我们在前两篇文章的节点定义就有一个 R，用来指定数组容量。类似于如下定义： class RadixNode{ // 值 V val; // 子节点数组 RadixNode<V>[] table; // R为数组容量 public RadixNode(int R) { this.table = new RadixNode[R]; } } 这棵树会有 R 个分支，又因为编码集是有限良序集，所以可将数组索引映射为唯一编码。 ...

这篇文章我将介绍 StandardTrie 的简单变体： PatriciaTrie1。 PatriciaTrie 或 PatriciaTree， 在一些论文中又被称为 CompactTrie（紧凑 trie）或 CompressedTrie（压缩 trie）。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 PatriciaTrie 的显著优化是合并单路分支：如果一个非根无值节点有且仅有一个子节点，则将其子节点与该节点合并。 文字描述稍有点抽象，还是看图： 节点合并 图1：节点合并 节点分裂 如果需要添加键 “da”，该如何来处理哪？我们需要将 “dad” 分裂成两个节点，效果见下图： 图2：节点分裂 相信，这两张图已足以说明一切😀 同时，我们也可以看到合并后节点数变少，因此减少了可能的内存消耗。 2. 代码实现 依照惯例，还是写代码来实现它。 2.1. 节点定义 package com.igeeksky.perfect.nlp.trie; private static class PatriciaNode<V> { // key 的子串 String subKey; // 值（支持泛型，可以是非字符串） V val; // 子节点 PatriciaNode<V>[] table; public PatriciaNode(int R) { this.table = new PatriciaNode[R]; } public PatriciaNode(int R, String subKey) { this.subKey = subKey; this.table = new PatriciaNode[R]; } public PatriciaNode(String subKey, V value) { this.subKey = subKey; this.val = value; } public PatriciaNode(int R, String subKey, V value) { this.subKey = subKey; this.val = value; this.table = new PatriciaNode[R]; } } 对比前文的 StandardNode，多了一个 String 类型的 subKey 字段，该字段用于存储节点合并之后的字符串，其它无变化。 ...

这篇文章将介绍最简单的 Trie 结构，即 StandardTrie，常被称为 标准 Trie，或朴素 Trie。 相关代码：https://github.com/patricklaux/perfect-code 1. 导引 假设有一个关键词集，其中有 6 个单词：bad, bade, bed, ca, cad, dad。 当输入 “b” 时，输出以 “b” 为前缀的所有单词； 输入一段文本，输出文本中存在这六个单词的哪几个，以及单词出现的起止位置…… 我们可以建立如下图所示的树形结构。 图1：字典树示例 每个字符一个节点，节点之间用边相连； 有特殊标记（有值）则代表一个完整的关键词。 2. 基本性质与操作 通过观察 ”图1：字典树示例“，我们可以发现一些性质和规律。 基本性质 根节点无字符； 兄弟节点的字符互异； 非根节点有且仅有一个字符； 非根节点有且仅有一个父节点； 根节点到其它节点的每条路径代表一个唯一的字符串。 根据以上性质，我们又可以得到一个有意思的推论：6. 兄弟节点都具有同一前缀； 键查找 从根节点沿着序列路径递归查找子节点，最后一个字符对应节点如果有特殊标记，则命中。 譬如要查找 bad，root → b → a → d，命中，返回 bad；譬如查找 cup，root → c → NULL，未命中，返回空。 前缀匹配 先找到前缀节点，然后遍历其子节点。 譬如查找以 b 为前缀的关键词：1. 先找到 b 对应的节点，root → b，找到 b 节点；2. 遍历 b 节点的所有子节点。 ...

Trie1 通常被称为字典树（或前缀树、单词搜索树），是一种用于存储和检索字符串的树型数据结构。 Trie 是英文单词 retrieval 的一部分，名称最早由 E. Fredkin2 提出，发音同 “try”。 图1：关键词推荐列表 典型的应用场景是搜索引擎的输入框：譬如当输入 “trie” 时，会列出以 “trie” 为前缀的关键词推荐列表。 此外，还有诸如拼写检查、词典分词、词频统计、数据压缩、倒排索引、字符串排序、关键词过滤……等等众多应用场景。 技术演化 由于字典树相关算法的应用广泛，所以演化出大量的数据结构和优化技术，其进化史就是一个脑洞大开的过程。 我之前画过一张复杂的演进图，现在看来并无必要，事实上只要了解关键脉络即可。删繁就简，最终留下了这张比较简单的图。 图2：技术演化 文章目录 字典树之旅01：开篇（本文） 字典树之旅02：Trie 的标准实现 字典树之旅03：Patricia Trie(一) 字典树之旅04：Patricia Trie(二) 未完待续…… 参考资料 https://en.wikipedia.org/wiki/Trie ↩︎ Fredkin, E. . “Trie memory.” Communications of the Acm 3(1960). ↩︎

1. 前言 随着自然语言处理和智能语音识别技术的发展，智能会话机器人开始部分替代人工客服。 网上关于 NLP 算法的文章有很多，但关于 Chatbot 架构的却很少，关于 Chatbot SaaS 平台架构的则更少。我是一名对机器学习感兴趣的程序员，更关注如何设计实现一个架构良好的 Chatbot SaaS 平台，因此写下了这篇文章。 2. Chatbot架构 2.1. 智能会话机器人的分类 智能会话机器人按照对话轮次来划分，可以分为单轮对话机器人和多轮对话机器人；按照知识领域来划分，可以分为限定域机器人和开放域机器人；按照任务类型来划分，可以分为任务型机器人、问答型机器人、闲聊型机器人和融合型机器人。 任务型：根据用户给出的信息完成指定的任务。一般限定于某个垂直领域，常采用多轮对话的形式。如订餐、订票等服务。 问答型：为用户提出的事实型、布尔型、计算型、推理型等类型的问题自动给出答案，进一步还可以再划分为常见问题解答（FAQ）和知识图谱问答（KBQA），一般限定于某个特定知识领域。 闲聊型：与用户进行开放式聊天，满足用户的情感陪护需求。一般不限定话题范围，但有可能偏向于某个领域。 融合型：一般以任务型或问答型为主，融合闲聊功能。如对于电商客服机器人来说，能完成商品推荐购买任务，能回答保修政策问题，还能陪客户闲聊天，融合型是应用场景越来越复杂的产物。 从应用的发展趋势来看：单轮对话——>多轮对话，以获得更多更完整的信息；单领域——>多领域，以满足用户更多层面的需求。 2.2. 任务型机器人交互模型 企业应用中最常见的需求是任务型机器人，上图是任务型机器人经典的交互模型。其中红色框为文字语音转换部分，这里暂不作讨论。 2.2.1. 自然语言理解（NLU） 领域识别（Domain Identification） 检测用户输入内容所涉及的领域概念。 意图识别（Intent Detection） 检测用户在特定领域下表述内容所代表的意图。 词槽填充（Slots Filling） 收集用户在对话过程中任务所必需的关键信息。 2.2.2. 对话管理（DM） 对话状态追踪（Dialogue State Tracking，DST） 记录和判断当前会话处于任务的何种状态。 对话策略（Dialogue Policy，DP） 根据对话状态决定下一步的系统行为。 2.2.3. 自然语言生成（NLG） 自然语言生成主要有两种方法：基于模板生成和基于模型生成。 基于模板生成：调用设计人员预先设计的回复模板，根据前置阶段获取到的状态和关键信息生成自然语言回复给用户。优点是响应速度较快，缺点是语言表达不够丰富，需要人工定义模板规则。因此比较适合在响应动作较少时使用，或是在系统冷启动时使用。 基于模型生成：通常使用seq2seq模型学习大量交互语料数据，根据用户输入直接生成相关自然语言回复给用户。优点是不需要人工定义模板规则，语言表达较为丰富；缺点是回复结果不太可控，响应速度较慢，需要学习大量的交互语料数据。因此比较适合系统资源充足且有大量交互数据时采用。 2.3. 组件集成（pipeline） 任务型机器人的系统设计中，通常采用pipeline方式来集成各个组件。 pipeline的组件构成根据采用的方法不同而不同。有可能整个pipeline由三个组件构成，NLU、DM、NLG分别为一个模型；也可能整个pipeline由两个组件构成，NLU + DM 为一个模型，NLG 是一个模型；也有可能整体仅有一个组件，NLU + DM + NLG 是一个整体的模型（end2end）。 某些情况下，为了提高响应速度，还可能是一个并行流（如下图所示）。 ...