《计算之魂》 - 4 分类与组合思维

4.1 选择与分类

计算机在实际问题中的大部分操作并非纯粹计算，而是分类和组合，这正是人工智能和模式识别最底层的逻辑。

分类和组合构建了连接现实世界与计算机世界的两座关键桥梁：

1. 分类组织为信息问题：将现实生活中的分类、组织、查找和重组抽象为信息处理问题
2. 抽象计算：将信息处理问题进一步抽象为计算问题

这种逻辑也是数据库和数据分析的底层基础——大多数业务逻辑和数据分析本质上都是分类和重组问题。

下棋的例子：象棋和围棋都可视为N选1问题。若抽象为树结构，则形成博弈树。博弈双方交替选择，奇数层由一方选择，偶数层由另一方选择，具体选择策略则属于算法范畴。

OCR技术：其核心是将图片分类到特定字符类别。手写体因边界模糊，比印刷体更难识别。

思考题参考：《计算之魂》思考题4.1——分类损失

4.2 组织信息：集合与判定

集合的基本性质由ZFC公理化体系定义，可见集合论：

• 正则公理：集合归属判定是二值的，不允许中间状态
• 外延公理：集合相同的判定标准是所有元素完全相同
• 无序唯一性：集合元素不可重复且无次序关系
• 无性质限制：任何事物都可成为集合元素

计算机实现集合运算的方法

• 二叉决策树

  • 优势特性：
    • 操作简单（仅左右分支）
    • 信息表示高效（N层可表示$2^N$信息）
    • 自相似结构适合递归处理
  • 与N叉树的等价性：可互相转换表示

• 哈希表

  • 通过索引清晰划定集合边界
  • 实际应用案例：黄色网站过滤方案
    • 直接哈希存储
    • 布隆过滤器实现
    • 混合方案（简单的规则分类+然后用哈希处理）

对以上两个思维的总结：

• 二叉决策树需要概念抽象，更符合人类思维；
• 哈希表直接划定边界，更契合计算机思维。

在语音识别(SR)中，可抽象为在N叉树中搜索词汇，根据上下文构建最可能语句的问题。

4.3 B树家族与数据库索引 P148

键(Key) 作为信息的唯一标签，是分类的核心概念。B树家族是数据库索引的核心组织结构：

B树

受限制的N叉树，扩展自二叉树。为避免N叉树退化为线性复杂度，设置三大限制：

1. 根节点含2~2d个数据
2. 节点索引化：按内部值划分为多个子树区间
3. 动态平衡：通过合并/拆分维持结构

B+树改进

• 核心改进：
  • 非叶节点仅存键，数据全存叶子
  • 叶子节点链表串联
• 优势：
  • 结构简洁
  • 预排序适合大数据处理
• 复杂度等效性：与二叉树同为$lo{g}_{2}V$

字典存储实例： B+树平衡了存储效率与灵活性，解决二叉树不平衡和N叉树空间浪费问题。

B*树进阶

• 横向兄弟节点指针
• 优化分裂机制减少空间浪费

数据库索引本质是多维哈希表，提升信息访问效率。

思考题解析：《计算之魂》思考题4.3——词典

4.4 卡特兰数与二叉树

满二叉树（所有节点度为0或2）的结构计数问题引出卡特兰数：

递归求解

对每个中间节点，左右子树情况数相乘：

$$S(N)=\sum _{k=1}^{N-1}S(k)\cdot S(N-k)$$

解析解：

$$S(N)=\left(\begin{array}{c}2N-2\\ N-1\end{array}\right)/N$$

节点的状态转移方程，可以表示为：

等价问题

1. 凸N边形划分：连接顶点划分N-2个三角形的方案数

2. N字符串合并：相邻合并的序列方案数（如abcd有5种合并方式）

在句法分析中，卡特兰数表征了语法树结构变化的上限，呈指数增长导致分析困难。

思考题4.4

街区行走问题是否属于卡特兰数？ 《计算之魂》思考题4.4分析
疑问：可能是杨辉三角问题而非卡特兰数？

附录

• 集合论中的 ZFC 公理化体系详解