「统计语言模型」是建立在词的基础上，因为词是表达语义的最小单位。对于西方语言来讲，词之间有明确的分隔符(识别手写体时分隔符不明显，也需要进行分词)，而对于一些亚洲语言，词之间没有明确分隔符。因此，要做自然语言处理，需要先对句子进行分词。

中文分词历史

最容易想到的分词方法，也是最简单的分词方法，就是查字典。这种方法最早由北京航天航空大学的梁南元教授提出。「查字典」方法其实就是把句子从左向右扫码一遍，遇到字典里有的词就标识出来；遇到复合词(如 “上海大学”)就找最长的词匹配；遇到不认识的字串就分割成单字词。

这种最简单的方法可以解决七八成以上的分词问题。但是，它毕竟太简单，遇到复杂一点的问题就无能为力了。20 世纪 80 年代，哈尔滨工业大学的王晓龙博士将查字典的方法理论化，发展成最少词数的分词理论，即一句话应该分成数量最少的词串。这种方法明显的不足是遇到有二义性的分割时就无能为力了。比如 “上海大学城书店” 的正确分词应该是 “上海 - 大学城 - 书店”，而不是 “上海大学 - 城 - 书店”。

基于语言统计模型分词

1990 年前后，清华大学郭进博士用统计语言模型成功解决了分词二义性的问题，将汉语分词的错误率降低一个数量级，上面举的二义性例子用统计语言模型都可以解决。

利用统计语言模型分词的方法，可以用数学公式进行概括。假定一个句子 S 有几种分词方法，为了简单起见，假定有一下三种： A1, A2,A3,...,Ak B1,B2,B3,...,Bm C1,C2,C3,...,Cn。其中，A1,A2,B1,B2,C1,C2 等都是汉语的词，上述各种分词结果可能产生不同数量的词串，所以用 k,m,n 三个下标表示分词结果词的数目。那么最好的一种分词方法应该保证分词后这个句子出现的概率最大。也就是说，如果 A1, A2,A3,...,Ak 是最好的分词方法，那么其概率满足：

P(A1, A2,A3,...,Ak) > P(B1,B2,B3,...,Bm)

并且

P(A1, A2,A3,...,Ak) > P(C1,C2,C3,...,Cn)

因此，只要利用上一章提到的统计语言模型计算出每种分词句子出现的概率，并找出其中最大的，就能找到最好的分词方法。

中文分词以统计语言模型为基础，经过几十年的发展和完善，今天基本上可以看做是一个已解决的问题。当然不同的人做的分词器有好有坏，这里的差别主要在于数据的使用和工程实现的精度。

前面一直强调，自然语言从产生开始，逐渐演变成一种上下文相关的信息表达和传递的方式，因此要让计算机处理自然语言，一个基本的问题就是为自然语言这种上下文相关的特性建立数学模型。这个模型就是在自然语言处理中常说的「统计语言模型」(Statistical Language Model)，它是今天所有自然语言处理的基础，广泛应用于机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询。

统计语言模型

用数学的方法描述语言规律

「统计语言模型」由贾里尼克及其同事提出，初衷是为了解决语音识别的问题。在语音识别中，计算机需要知道一个文字序列是否能构成一个大家理解并有意义的句子，然后显示或打印给使用者。例如：
美联储主席本・伯南克昨天告诉媒体 7000 亿美元的救助资金将借给上百家银行、保险公司和汽车公司。
这句话很通顺，意思也很明白。如果改变一些词的顺序或替换掉一些词，变成:
本・伯南克美联储主席昨天 7000 亿美元的救助资金告诉媒体将借给银行、保险公司和汽车公司百家。
虽然多少能猜到一点，但意思就含混了，但如果再换成：
联主美储席本・伯诉体南将借天的救告媒昨助资金 70 元亿 00 美给上百百百家银保行、汽车险公司公司和。
基本上读者就不知所云了。

如果问一个没学过自然语言处理的人为什么会这样？他可能会说，第一个句子合乎语法、词义清晰；第二个句子虽然不合乎语法但词义还算清晰；而第三个句子则连词义都不清晰了。70 年代以前，科学家也是这样想的，他们试图判断这个文字序列是否合乎文法、含义是否准确等，但这条路走不通。

贾里尼克用一个简单的统计模型漂亮的搞定了这个问题，他的出发点很简单：一个句子是否合理，就看它的可能性大小如何。可能性则用概率来衡量，如第一个句子的概率大约是 10⁻²⁰，第二个句子出现的概率是10⁻²⁵，第三个句子出现的概率是 10⁻⁷⁰。因此，第一个句子出现的概率最大。这种方法更普遍而严格的描述是：
假定 S 表示一个有意义的句子，由一串特定顺序排列的词 w₁,w₂,…,w𝑛 组成，n 代表句子的长度(词的个数)。

现在想知道 S 的概率 P(S)，那么 P(S) = P(w₁,w₂,…,wn)，利用条件概率的公式， S 这个序列出现的概率等于每一个词出现的条件概率相乘，于是可继续展开为：P(w₁,w₂,…,w𝑛) = P(w₁)·P(w₂|w₁)·P(w₃|w₂,w₁)·…·P(w𝑛|w₁,w₂,...,w𝑛₋₁)。 其中P(w₁)表示第一个词出现的概率；P(w₂|w₁)则是已知第一个词的前提下，第二个词出现的概率，依此类推。不难看出，词w𝑛出现的概率取决于它前面的所有词。

从计算上来说P(w₁)很容易算，P(w₂|w₁)也不太麻烦，但P(w𝑛|w₁,w₂,...w𝑛₋₁)可能性太大，无法估算，怎么办呢？数学上有种偷懒但颇为有效的方法叫「马可夫假设」：假设任意一个词w𝑛出现的概率只同她前面的词w𝑛₋₁有关，于是问题变得很简单，S 出现的概率就简单多了：P(S) = P(w₁)·P(w₂|w₁)·P(w₃|w₂)·…·P(w𝑛|w𝑛₋₁)

上面公式对应的统计语言模型是二元模型（Bigram Model)，当然，也可以假设一个词由前面 N-1 个词决定，对应的模型稍微复杂些，被称为「N 元模型」。接下来的问题是如何估算P(w𝑛|w𝑛₋₁)，根据它的定义：P(w𝑛|w𝑛₋₁) = P(w𝑛₋₁,w𝑛) ∕ P(w𝑛₋₁)，从而估计联合概率 P(w𝑛₋₁,w𝑛) 和边缘概率 P(w𝑛₋₁)。

因为有了大量的语料库，只要数一数 w𝑛₋₁,w𝑛 这对词在统计的文本中前后相邻出现了多少次 #(w𝑛₋₁,w𝑛)，以及 w𝑛₋₁ 在同样的文本中出现了多少次 #(w𝑛₋₁)，然后再用两个数分别除以语料库的大小 #，即可得到这些词或者二元组的相对频度：
𝒇(w𝑛₋₁,w𝑛) = #(w𝑛₋₁,w𝑛) ∕ #
𝒇(w𝑛₋₁) = #(w𝑛₋₁) ∕ #
根据大数定理，只要统计量足够，相对频度就等于概率，即:
P(w𝑛₋₁,w𝑛) ≈ #(w𝑛₋₁,w𝑛) ∕ #
P(w𝑛₋₁) ≈ #(w𝑛₋₁) ∕ #
而 P(w𝑛|w𝑛₋₁) 就是两个数的比值，再考虑到上面的两个概率有相同的分母，可以约掉，因此：P(w𝑛|w𝑛₋₁) ≈ #(w𝑛₋₁,w𝑛) ∕ #(w𝑛₋₁).

现在，你已开始感受数学的美妙了，它把一些复杂问题变得如此简单，用这么简单的数学模型解决复杂的语音识别、机器翻译等问题。

语言的出现是为了在人类之间通信。字母、文字和数字实际是信息编码的不同单位。任何一种语言都是一种编码方式，而语言的语法规则则是编码和解码算法。人类将头脑中的信息通过一句话表达出来，则是对信息进行编码，编码的结果则是一串文字。

从 1946 年现代电子计算机出现后，计算机在很多事情上都做的比人还好。那么，机器能不能懂的自然语言呢？这要从「图灵测试」开始。

图灵测试

最早提出机器智能的是计算机科学之父「阿兰・图灵」，他在「计算的机器和智能」这篇论文中提出了一种验证机器是否有智能的方法：让人和机器进行交流，如果人无法判断出自己交流的对象是人还是机器，就说明这个机器有智能了。这种方法被后人称为「图灵测试」。

自然语言处理

图灵其实是留下了一个问题，而非答案，但是一般认为自然语言机器处理的历史可以追溯到那个时候，至今已 60 多年了。这 60 多年的发展过程，可以分成两个阶段：从 20 世纪 50 年代到 70 年代，是走弯路的阶段；70 年代开始，一些自然语言处理的先驱重新认识这个问题，找到了基于数学模型和统计的方法，自然语言处理进入第二个阶段。

基于语法规则

20 世纪 60 年代，对于怎样理解自然语言，科学家的普遍认识是先要做好两件事：分析语句和获取语义。这种惯性思维受到传统语言学研究的影响：中世纪以来，语法一直是大学教授的主要课程之一，西方的语言学家们已经对各种自然语言进行看非常形式化的总结，形成了十分完备的体系。而这些语法规则又很容易用计算机算法描述，这就更加坚定了大家对基于规则的自然语言处理的信心。

20 世纪 80 年代以前，自然语言处理工作中的文法规则都是人工写的。科学家们原本以为随着对自然语言语法概括的越来越全面，同时计算机计算能力的提高，这种方法可以逐步解决自然语言理解的问题。这里面有两个越不过去的坎：首先，通过文法规则覆盖哪怕 20% 的真实语句，规则的数量也至少是几万条，而且，这些规则甚至会出现矛盾，为了解决矛盾，还要说明规则的特地使用环境。其次，即使能能列出所有规则，也很难用计算机来解析。在自然语言的演变过程中，产生了词义与上下文相关的特性，因此，它的文法是比较复杂的上下文有关文法。

从规则到统计

70 年代，基于规则的语法分析很快走到了尽头，而对于语义的处理则遇到了更大的麻烦，计算机无法处理自然语言中词语的多义性(The box is in the pen)。可以说，利用计算机处理自然语言的努力直到 20 世纪 70 年代初是相当失败的。

1970 年以后统计语言学的出现使得自然语言处理重获新生并取得今天的非凡成就。推动这个技术路线转变的关键人物是弗里德里克・贾里尼克(Frederick Jelinek)和他领导的 IBM 华生实验室。基于规则的自然语言处理和基于统计的自然语言处理的争执后来还持续了 15 年左右，直到 90 年代初期。这期间，两路人马各自组织和召开自己的会议，如果在共同的会议上，则在各自的分会场开小会。到 90 年代以后，坚持前一种的研究人员越来越少，后者参会人数则越来越多，这样，自然语言处理从规则到统计的过渡就完成了。

这场争议为什么持续了 15 年呢？其一，一种新的研究方法的成熟需要很多年，当时，基于统计的自然语言处理还有很多问题，在从 80 年代末至今的 25 年里，随着计算机能力的提高和数据量的不断增加，过去看似不可能通过统计模型完成的任务，渐渐都变得可能了。2005 年以后，随着 Google 基于统计方法的翻译系统全面超越基于规则的 SysTran 翻译系统，基于规则方法学派固守的最后一个堡垒被拔掉了。第二点就很有意思了，用基于统计的方法代替传统方法，需要等第一批语言学家退休。毕竟，不是所有人都乐意改变自己的观点。当然，等这批人退休之后，科学就会以更快的速度发展。

这系列文章是我在看《数学之美》这本书时的一些笔记，全部摘抄自书中对应章节。

我是个阅读能力很差的人，基本是过目就忘。为了更好的理解书中知识，决定做些记录，也便于以后回顾。

起源

早期智人并没有语言，他们通过声音来传递信息，但随着人类的进步和文明的进化，需要表达的信息越来越多，简单的几个声音已不能覆盖要传递的信息，语言就此产生。

随着语言要描述的要素越来越多，大脑已经记不住所有词汇了。于是，高效记录信息的需求就产生了，这便是文字的起源。目前可考显示：在尼罗河流域出现的象形文字(用图形表示事物)是最早的文字。

当人类第二个文明中心在两河流域的美索不达米亚建立的时候，楔形文字诞生了。腓尼基人不愿花大量时间雕刻这些楔形字母，而将他们简化成 22 个字母并在商业活动中传播给希腊人的祖先。这些拼音文字在古希腊得到充分发展，字母的拼写和读音紧密的结合起来，相对容易学习。在随后的几个世纪传遍欧亚非大陆及「罗马式语言」。

编码

从象形文字到拼音文字是一个飞跃，从物体的外表进化到了抽象的概念，同时不自觉的对信息进行编码。
语言从古语发展到现代语言，表意比以前更准确、丰富，这里没语法起了很大的作用。如果说从字母到词的「构词法」是词的编码规则，那么语法则可以认为是语言的编码与解码规则。

引语

作为一个 iOS 开发，你应该知道一个 app 是怎样从无到有，但对于游戏，却不一定。所以，本文可以你了解游戏开发方面的知识。

为什么是 SpriteKit？

首先，我们需要了解目前手机游戏开发的现状。目前，手机游戏引擎用的最多的应该是 Cocos2d-x 和 Unity，它们都是垮平台的引擎，但这两者对于初学者来说，需要额外学习的东西太多。
SpriteKit 是由 Apple 在 WWDC 2013 发布 2D 游戏引擎，目前可用于 iOS, macOS tvOS 和 watchOS。它有着良好的设计、简单易用、API 和 Cocos2D 非常像。
对于已经熟悉 iOS 开发的人来说，其用法和 UIKit 差不多，而且，他并非只能用来开发游戏。本文后面就会用 SpriteKit 实现类似 iTunes Music 的风格选择交互。

SpriteKit Framework 介绍

首先，我们来看 SpriteKit 主要类结构。

• SKView 用来管理和渲染 SKScene， 继承自 UIView。你甚至可以将 SKView 与 UIKit 里的其他 View 结合使用，比如在其之上加一个 UIButton。
• SKNode 是基础类，和 UIKit 类似，SpriteKit 有 node trees 的概念，实际中一般和其子类打交道。SKNode 定义了一些基础属性和方法，如 position, frame, alpha, physicBody, addChild(), runAction() 等。
• SKAction 用来实现位移、缩放等效果，调用 SKNode.runAction() 将 Action 添加到 Node，可以自由组合 Action 实现复杂效果。
• SKPhysicBody 定义了一个 Node 的物理属性，设置 node.physicBody 后 node 就可以进行物理计算、碰撞检测。SKPhysicBody 包含了质量、速度、弹性、摩擦力等属性。
• SKScene 是 root node，定义了 SKView 显示的具体内容， physicsWorld 属性可设置重力等全局属性，通过 SKPhysicsContactDelegate 获得碰撞通知。就游戏来说，其内容是动态变化的，所以 SKScene 有一个 rendering loop (见下图)

每一帧都会执行这个 loop，loop 执行完之后被改变的内容才会重新绘制。子类化 SKScene 时可以重写 update(_:) 和 didXXX 方法获得回调。

结合 Magnetic 进行代码讲解

上面介绍了 SpriteKit 的一些基本概念，下面我们通过一个示例来介绍如何在普通 app 中结合 SpriteKit 实现一些优雅的交互。此示例受 Github 上的 Magnetic 项目启发，用 SpriteKit 实现 iTunes Music 的「个人喜好定制」功能，源码见 https://github.com/iblacksun/Artists， 最后效果如下：

开始实现

第一步，使用 Xcode 新建一个 Game 类型的项目，Game Technology 选 SpriteKit。简单起见，修改 Deployment Info，使其只支持 iPhone 和 Portrait 方向。Build & Run 之后你会看到我们熟悉的 Hello World。

Hello World 项目中很多模板代码在我们项目中并不需要，删除 GameScene.sks, Actions.sks, GameScene.swift 几个文件；修改 Main.storyboard 将 SKView 的 backgroudColor 修改成白色；修改 GameViewController 替换成如下：

1
2
3
4
5
6
7
8
9
10
11

class GameViewController: UIViewController {
	override func viewDidLoad() {
		super.viewDidLoad()
		guard let skView = self.view as? SKView else{
			return
		}
		skView.ignoresSiblingOrder = true
		skView.showsFPS = true
		skView.showsNodeCount = true
	}
}

此时如果运行项目的话应该是一个灰色空白界面，底部显示了 nodes 数量和 fps。

构建 Node

现在该主角们登场了，新建 ArtistsScene.swift ArtistNode.swift，分别继承 SKScene 和 SKShapeNode。修改 GameViewController 的 viewDidLoad 方法，在末尾加入代码：
let scene = ArtistsScene(size: skView.bounds.size)
skView.presentScene(scene)
调用 presentScene(_:) 方法呈现 Scene，此时 ArtistsScene 就是 root node，因 SKScene 的默认背景色是黑色，所以现在运行项目的话会看到一个黑色空白界面。
接下来开始实现功能，重写 ArtistsScene 的 didMove(to:) 的方法，此方法在 Scene 被 present 时会被调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

override func didMove(to view: SKView) {
	super.didMove(to: view)
	//1.禁用重力
	physicsWorld.gravity = CGVector.zero
	backgroundColor = .white
	let viewWidth = view.frame.size.width
	let viewHeight = view.frame.size.height
	let radius = max(viewWidth, viewHeight)
	//2.添加一个具有向心力的特殊 SKFieldNode.
	let fieldNode = SKFieldNode.radialGravityField()
	fieldNode.region = SKRegion(radius: Float(radius))
	fieldNode.minimumRadius = Float(radius)
	fieldNode.strength = 50
	addChild(fieldNode)
	//3.修改坐标原点
	anchorPoint = CGPoint(x: 0.5, y: 0.5)
	//4. 添加所有 Artist nodes，初始随机分配在左右两侧，受向心力作用，会自动汇聚到中心点
	for (index, artistName) in artists.enumerated() {
		let x = (index % 2 == 0) ? -viewWidth/2 : viewWidth/2
		let y = CGFloat.random(-viewHeight/2, viewHeight/2)
		let node = ArtistNode(circleOfRadius: 40)
		node.fillColor = .red
		node.position = CGPoint(x: x, y: y)
		addChild(node)
	}
}

1. physicsWorld.gravity = CGVector.zero 禁用重力作用，否则所有设置过 physicBody 的 node 都会受重力影响自动坠落；
2. 添加一个具有向心力的特殊 SKFieldNode，在其 region 内的所有 node 都会受影响，自动向中心移动；
3. SpriteKit 的坐标原点在左下角，这点和 UIKit 不一样。设置 anchorPoint = (0.5, 0.5)，方便计算后面 ArtistNode 的 position；
4. 循环添加 ArtistNode，设置其 position，其中 x 平均分配到左右两侧，y 则取顶部和底部间的随机值。

此时如果运行的话会发现所有 ArtistNode 都停留在屏幕两侧并不会想中心靠拢，猜猜原因？
打开 ArtistNode，实现一个 convenience init 方法，传入 artistName

1
2
3
4
5
6
7
8
9
10
11
12

convenience init(artistName :String) {
	self.init()
	self.init(circleOfRadius: 40)
	fillColor = .red
	physicsBody = SKPhysicsBody(circleOfRadius: frame.size.width / 2)
	physicsBody?.allowsRotation = false
	physicsBody?.friction = 0
	physicsBody?.linearDamping = 3
	addMultilineTextNode(artistName, radius: 40)
}

在 init 中创建一个半径为 40 的圆形 node，填充色是红色；创建一个大小和自身相等的圆形 physicsBody。
接下来的问题是如何将 artistName 添加到 ArtistNode？SpriteKit 提供了 SKLabelNode，但它不支持文字换行。addMultilineTextNode(artistName, radius: 40) 里的代码是将文字转换成图片，然后往 ArtistNode 添加一个 SKSpriteNode。

1
2
3
4
5
6

if let image = UIGraphicsGetImageFromCurrentImageContext(){
	let texture = SKTexture(image: image)
	let spriteNode = SKSpriteNode(texture: texture)
	addChild(spriteNode)
}
UIGraphicsEndImageContext()

添加交互

完成上面代码并运行之后，所有 ArtistNode 会自动从左右两侧缓慢的向中心移动，但并不能拖拽和点击。
SKNode 继承自 UIResponder (NSResponder)，其事件处理和 UIView 一样：通过 touchesBegan touchesMoved touchesEnded touchesCancelled 几个方法处理。
因我们的 root node 是 ArtistsScene，所以我们可以重写 ArtistsScene 的这几个方法来处理拖拽和点击事件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

override func touchesMoved(_ touches: Set<UITouch>, with event: UIEvent?) {
	guard let touch = touches.first else {
		return
	}
	let previous = touch.previousLocation(in: self)
	let location = touch.location(in: self)
	if location.distance(from: previous) == 0{
		return
	}
	isMoving = true
	let x = location.x - previous.x
	let y = location.y - previous.y
	for node in children{
		let distance = node.position.distance(from: location)
		let acceleration: CGFloat = 3 * pow(distance, 1/2)
		let direction = CGVector(dx: x * acceleration, dy: y * acceleration)
		node.physicsBody?.applyForce(direction)
	}
}
override func touchesEnded(_ touches: Set<UITouch>, with event: UIEvent?) {
	guard let touch = touches.first, !isMoving else {
		isMoving = false
		return
	}
	isMoving = false
	let location = touch.location(in: self)
	guard let artistNode = artistNodeAt(location) else{
		return
	}
	artistNode.isSelected = !artistNode.isSelected
}
override func touchesCancelled(_ touches: Set<UITouch>, with event: UIEvent?) {
	isMoving = false
}

1. touchesMoved 方法中处理拖拽事件，如果发生拖拽，则向所有 node 施加一个作用力，使之随着手指位置一起移动；
2. touchesEnded 中处理点击事件。通过 isMoving 区分这个事件是拖拽还是点击，点击的话查找出被点击的 ArtistNode，设置其 isSelected 属性。

接下来看看 ArtistNode.isSelected 的实现：

1
2
3
4
5
6
7
8
9
10

var isSelected = false {
	didSet {
		guard oldValue != isSelected else {
			return
		}
		removeAction(forKey: "scale")
		let scaleAction = SKAction.scale(to: (isSelected ? 1.5 : 1.0), duration: 0.2)
		run(scaleAction, withKey: "scale")
	}
}

didSet 获得设值之后的回调，通过 run(_ action:)，选中缩放至 1.5，取消选择还原至 1.0。

如何深入

以上通过示例的方式介绍了 SpriteKit 的基础，以及如何将 SpriteKit 运用到普通 App 中。如果还想继续深入的话，可以参考以下资源：

• https://developer.apple.com/spritekit/
• SpriteKit Tutorial: Create an Interactive Children’s Book with SpriteKit and Swift 3
• 2D Apple Games by Tutorials

丁香园早在 2015 年就全面转向 Swift 了。虽然 Xcode 在写 Swift 时候各种崩溃，但相比 OC，写出来的代码更加简洁。
直到最近，我们发布的 app 经常收到用户的反馈：「打开 app 时经常闪退。」在后台查看收集的闪退日志并无异常，从 iTunes Connect 的「App 分析」查看确实闪退率飙升。

Crash Log

继续此话题前，最好需要对 Crash log 的收集机制有些了解，推荐 《漫谈 iOS Crash 收集框架》 —— 念茜。

dyld

如何解决

参考

• Mach Exception Handlers
• 漫谈 iOS Crash 收集框架 —— 念茜
• https://github.com/artsy/eigen/issues/1246

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.