无向图 Undirected graphs

图的介绍 Introduction to graph

图：一对对顶点 vertices 用边 edge 连接

路径 path：用边连接在一起的顶点序列

环 cycle：首尾相同的路

如果两个顶点间有路，则这两个顶点相连 connected

图 API Graph API

顶点表示：00 到 V−1V-1 的整数（用符号表将名称与整数转换）

public class Graph {
    Graph(int V)

    Graph(In in)

    void addEdge(int v,int w)

    Iterable<Integer>adj(int v)

    int V()

    int E()

    String toString()
}

一些关于度数的处理：

public static int degree(Graph G, int v) {
    int degree = 0;
    for (int w : G.adj(v))
        degree++;
    return degree;
}

public static int maxDegree(Graph G) {
    int max = 0;
    for (int v = 0; v < G.V(); v++)
        if (degree(G, v) > max)
            max = degree(G, v);
    return max;
}

public static double averageDegree(Graph G) {
    return 2.0 * G.E() / G.V();
}

public static int numberOfSelfLoops(Graph G) {
    int count = 0;
    for (int v = 0; v < G.V(); v++)
        for (int w : G.adj(v))
            if (v == w)
                count++;
    return count;
}

边的表示：

  1. 用一个列表维护边
  2. 邻接矩阵：对于每个边 v-w 有 adj[v][w] = adj[w][v] = true
  3. 维护以顶点为索引的列表
/* 使用方法3表示边 */
public class Graph {
    private final int V;
    private Bag<Integer>[] adj;

    Graph(int V) {
        this.V = V;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<Integer>();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

使用邻接表的原因：

  • 算法往往基于迭代 vv 的邻边
  • 真实世界的图往往是稀疏的
表示方法 空间 添加边 vv 和 ww 之间的边 迭代 vv 相邻的顶点
边列表 EE 11 EE EE
邻接矩阵 V2V^2 11 11 VV
邻接表 E+VE + V 11 degree(v) degree(v)

来源：迷宫探索该算法最早可追溯到古希腊神话中的米诺陶洛斯迷宫的走法

设计模式：dfs 处理+询问

方法：当访问顶点 vv 时

  • 标记顶点 vv 为已访问
  • 递归访问所有与 vv 相邻的未标记过的顶点
public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private int s;

    public DepthFirstPaths(Graph G, int s) {
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) {
                dfs(G, w);
                edgeTo[w] = v;
            }
    }
}

时间复杂度为度数之和（因为每个与 ss 相连的顶点都只被访问一次）

正确性证明：

  • 若 ww 被标记了，则 ww与 ss 相连
  • 若 ww 与 ss 相连，则 ww 被标记了
public boolean hasPathTo(int v) {
    return marked[v];
}

public Iterable<Integer> pathTo(int v) {
    if (!hasPathTo(v))
        return null;
    Stack<Integer> path = new Stack<>();
    for (int x = v; x != s; x = edgeTo[x])
        path.push(x);
    path.push(s);
    return path;
}

edgeTo[]是父亲表示法表示的以 ss 为根结点的树

应用：连通块 flood fill

方法：重复此过程直到队列为空

  • 从队列中移除顶点 vv
  • 向队列中添加所有与 vv 相邻的未标记过的顶点并标记它们

区别：dfs 用栈，bfs 用队列

bfs 计算以 ss 为源点的最短路时间复杂度  E+V~E+V（因为每个与 ss 相连的顶点都只被访问一次）

正确性证明：队列总是由零个或多个离 ss 距离为 kk 的结点，后面跟着零个或多个离 ss 距离为 k+1k+1 的结点组成

import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;

    private void bfs(Graph G, int s) {
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        marked[s] = true;
        while (!q.isEmpty()) {
            int v = q.remove();
            for (int w : G.adj(v))
                if (!marked[w]) {
                    q.add(w);
                    marked[w] = true;
                    edgeTo[w] = v;
                }
        }
    }
}

连通性查询 Connectivity queries

在常数时间回答 vv 是否与 ww 相连

思想：对于每个未标记的顶点 vv，使用 dfs 访问到的所有顶点在一个连通分量中

public class CC {
    private boolean marked[];
    private int[] id;
    private int count;

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) {
                dfs(G, v);
                count++;
            }
    }

    public int count() {
        return count;
    }

    public int id(int v) {
        return id[v];
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w]) {
                dfs(G, w);
            }
    }
}

连通分量的应用：粒子追踪

图处理的挑战 Graph-processing challenge

二分图、寻找回路、欧拉回路都能使用搜索做到

汉密尔顿圈(旅行售货员)问题：NP 问题，很困难

相似图问题：没人知道怎么做

相交问题：Tarjan 实现了线性算法

有向图 Directed Graph

介绍有向图 Introduction to Digraphs

边有方向

有向图 API Digraph API

同无向图，多了个reverse()

维护方法也一样，只是边不需要添加两边

同无向图，dfs、bfs 本质上是有向图算法

可够到性应用：程序控制分析、垃圾收集

多源最短路径：使用 bfs，但是初始时将所有源点入队

bfs 应用：网站爬虫dfs 会误入歧途

拓扑排序 topological sort

有向无环图 Directed acyclic graph（DAG）

拓扑排序：以所有边指向上的方式重绘 DAG

方法：

  • 运行 dfs
  • 以后根的逆序返回结点
import java.util.Stack;

public class DepthFirstPaths {
    private boolean[] marked;
    private Stack<Integer> reversePost;

    public DepthFirstPaths(Graph G, int s) {
        reversePost = new Stack<>();
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            if(!marked[v])dfs(G, v);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
        reversePost.push(v);
    }
}

正确性证明：对于任意边 v→w，当 dfs(v) 被调用时：

  1. dfs(w) 被调用并返回了：w 在 v 之前完成
  2. dfs(w) 还没有被调用：dfs(w) 会被直接或非直接地被 dfs(v) 调用并在 dfs(v) 之前完成，所以 w 在 v 之前完成
  3. dfs(w) 被调用但没有返回：不存在，形成了一个环

如果没有有向环，有向图存在拓扑顺序

应用：优先权安排

强连通分量 Strong component

如果 vv 和 ww 之间有一条有向路径且 ww 和 vv 之间也有一条有向路径，则称 vv 和 ww 强连通 strongly connected

Kosaraju-Sharir（两次访问的线性算法）方法：

  • 在 G 的反图中计算拓扑顺序
  • 在 G 中使用 dfs，以拓扑顺序访问未标记过的顶点
public class KosarajuSharirSCC {
    private boolean[] marked;
    private int[] id;
    private int count;

    public KosarajuSharirSCC(Digraph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());
        for (int v : dfs.reversePost())
            if (!marked[v]) {
                dfs(G, v);
                count++;
            }
    }

    private void dfs(Digraph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
    }

    public boolean stronglyConnected(int v, int w) {
        return id[v] == id[w];
    }
}

时间复杂度：E+VE+V

最小生成树 Minimum spanning tree

介绍 MSTs introduction to MSTs

生成树是子图，同时是个树并包括所有顶点

贪心算法 Greedy algorithm

cut 是把顶点分成两个非空集合

crossing edge 连接两个不同集合的顶点

给任何 cut，最小的连接边是 MST

证明：假设最小的连接边 ee 不在 MST 中

  • 加入 ee 形成一个环
  • 某条边 ff 是连接边
  • 去掉 ff 加入 ee 也是一个生成树
  • 因为 ee 比 ff 小，所以不是 MST
  • 所以矛盾

贪心 MST 演示：

  • 以所有边都灰色开始
  • 找到没有黑色连接边的 cut，将它最小边涂黑
  • 重复直到 V−1V - 1 个边涂黑

正确性证明：

  • 所有黑色边在 MST 中
  • 若少于 V−1V - 1 条黑边，则有无黑边的 cut

边有权重的图的 API edge-weighted graph API

public class Edge implements Comparable<Edge> {
    private final int v, w;
    private final double weight;

    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public int either() {
        return v;
    }

    public int other(int vertex) {
        if (vertex == v)
            return w;
        else
            return v;
    }

    @Override
    public int compareTo(Edge that) {
        return Double.compare(this.weight, that.weight);
    }
}

处理边时：int v = e.either(), w = e.other(v)

图：同无权图，其中Bag保存的由顶点改为边

Kruskal 算法 Kruskal's algorithm

思想：重复添加权重递增的边除非形成一个环

正确性证明：Kruskal 算法是贪心 MST 算法的一个特殊情况

  • 假设算法中 v→wv→w 的边为黑色
  • cut 相当于在树中与 vv 相连的顶点
  • 没有连接边是黑色的
  • 没有连接边有更小的权重

使用并查集查询是否会形成一个环

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class KruskalMST {
    private Queue<Edge> mst = new LinkedList<>();

    public KruskalMST(EdgeWeightedGraph G) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (Edge e : G.edges())
            pq.add(e);
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.remove();
            int v = e.either(), w = e.other(v);
            if (!uf.connected(v, w)) {
                uf.union(v, w);
                mst.add(e);
            }
        }
    }
}

最坏情况的时间复杂度为 Elog⁡EE\log E

Prim 算法 Prim's algorithm

  • 从 00 开始贪心构造树 TT
  • 向 TT 中添加只有一端在 TT 中的最小边
  • 重复直到 V−1V - 1 条边

正确性证明：Prim 算法是贪心 MST 算法的一个特殊情况

  • 假设 ee 是连接在树上和不在树上的顶点的最小边
  • cut 是连接在树上的点集
  • 没有连接边是黑色的
  • 没有连接边有更小的权重

懒惰实现： 查找只有一端在 $T $中的最小边：维护一个只有一端在 TT 中的边的优先队列

  • 键为边，优先级为边权
  • 如果边的两端都在 TT 中，不予考虑
  • 加入所有与 ww 相连的顶点
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class LazyPrimMST {
    private boolean[] marked;
    private Queue<Edge> mst;
    private PriorityQueue<Edge> pq;

    public LazyPrimMST(WeightedGraph G) {
        pq = new PriorityQueue<>();
        mst = new LinkedList<>();
        marked = new boolean[G.V()];
        visit(G, 0);
        while (!pq.isEmpty()) {
            Edge e = pq.remove();
            int v = e.either(), w = e.other(v);
            if (marked[v] && marked[w])
                continue;
            mst.add(e);
            if (!marked[v])
                visit(G, v);
            if (!marked[w])
                visit(G, w);
        }
    }

    private void visit(WeightedGraph G, int v) {
        marked[v] = true;
        for (Edge e : G.adj(v))
            if (!marked[e.other(v)])
                pq.add(e);
    }

    public Iterable<Edge> mst() {
        return mst;
    }
}

最坏情况时间复杂度  Elog⁡E~E\log E，空间复杂度  E~E

优化实现：维护与 TT 相连的顶点的优先队列，优先级为最小边

  • 如果有更短的边，减少优先级

需要使用能通过索引改变键的优先队列

  • 维护并行数组pq[]、qp[]、key[]：
    • pq[i]是在堆的i位置的键的索引
    • qp[i]是索引为i的堆的位置
    • key[i]是i的优先级
  • 使用swim(pq[k])实现decreaseKey(k, key)

MST 语境 MST context

k 团簇：把一堆东西分成 k 个组

单链 single link：两个团簇间的距离等于最近的两个物体的距离

单链团簇：找到两个最近团簇的距离最大的 k 团簇

方法：

  1. Kruskal 算法，但是在有了 k 个连通分量之后停下
  2. Prim 算法，删除前 k 大的边

最短路径 Shortest path

最短路径 API shortest path APIs

最短路径性质 shortest path properties

松弛 relax：

  • distTo[v] 是已知的从 s 到 v 的最短路径
  • distTo[w] 是已知的从 s 到 w 的最短路径
  • edgeTo[w] 是从 s 到 w 的最短路径已知最后一条边
  • 如果 v→w 创造了更小的边，同时更新 distTo[w]、edgeTo[w]

最短路径最优性情况：edgeTo[]是最短路径的距离，当且仅当

  • edgeTo[s] = 0
  • 对每个顶点 v，edgeTo[v] 是从 s 到 v 的某条路径的长度
  • 对每一条边 v→w，有edgeTo[v] <= distTo[v] + e.weight()

Dijkstra 算法 Dijkstra's algorithm

思想：

  • 按照离 ss 的距离的升序考虑顶点
  • 把顶点加到树中并松弛所有相连的边

Dijkstar 算法处理无负边的问题

正确性证明：

  • 每条边 v→w 松弛一次，使得edgeTo[v] <= distTo[v] + e.weight()
  • 不等式直到算法结束始终成立，因为
    • distTo[w] 不增加
    • distTo[v] 不变
public class DijkstraSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double> pq;

    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        pq = new IndexMinPQ<Double>(G.V());

        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        pq.insert(s, 0.0);
        while (!pq.isEmpty()) {
            int v = pq.delMin();
            for (DirectedEdge e : G.adj(v))
                relax(e);
        }
    }

    private void relax(DirectedEdge e) {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (pq.contains(w))
                pq.decreaseKey(w, distTo[w]);
            else
                pq.insert(w, distTo[w]);
        }
    }
}

Dijkstra 算法和 Prim 算法相似，因为他们（包括 dfs，bfs）都是计算图的生成树的算法

  • Prim：选择最靠近树的顶点
  • Dijkstra：选择离源点最近的顶点

有边权的 DAG edge-weighted DAGs

无环最短路思想：

  • 按照拓扑顺序考虑顶点
  • 从该顶点松弛所有边

时间复杂度：E+VE+V

证明：同 Dijkstra 算法

public class AcyclicSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;

    public AcyclicSP(EdgeWeightedDigraph G, int s) {
        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];

        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        Topological topological = new Topological(G);
        for (int v : topological.order())
            for (DirectedEdge e : G.adj(v))
                relax(e);
    }

    private void relax(DirectedEdge e) {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
        }
    }
}

相似的，该算法也可以计算 DAG 的最长路

负边 negative weight

负环：边权之和为负数的有向环

当且仅当无负环时，最短路径存在。

Bellman-Ford 算法：重复 VV 次，松弛所有边

for (int i = 0; i< G.V(); i++)
    for (int v = 0; v< G.V(); v++)
        for (DirectedEdge e : G.adj(v))
            relax(e);

时间复杂度为：EVEV

证明：在第 ii 次后，找到包含最多 ii 条边的最短路径

优化方法：如果 distTo[v] 在第 ii 次时没有改变，第 i+1i + 1 次不需要松弛与 vv 相连的边

队列实现：维护 distTo[] 改变的顶点的队列

算法 局限 一般情况 最坏情况 额外空间
拓扑排序 无有向环 E+VE+V E+VE+V VV
Dijkstra 算法（二叉堆） 无负边 Elog⁡VE\log V Elog⁡VE\log V VV
Bellman-Ford（队列优化） 无负环 E+VE+V EVEV VV

Bellman-Ford 算法找负环：如果在第 VV 次时有顶点被更新，就存在一个负环，实践中可以更加频繁地检查负环

负环应用：倒狗

最大流和最小割 Maximum flow and minimum cut

介绍最大流 Introduction to maxflow

st-cut是将 ss 分到集合 AA 中，tt 分到集合 BB 中，容量是从 AA 到 BB 的边的容量之和

st-flow是将分配给边的值，满足：

  • 容量限制：00 ≤ 流量 ≤ 边的容量
  • 本地平衡：除了 ss 和 tt 以外，每个顶点的入流 = 出流

流的值是 tt 的入流

Ford–Fulkerson 算法 Ford–Fulkerson Algorithm

增广路：从 ss 到 tt 的满足以下条件的路：

  • 前向边可增加流（非满）
  • 后向边可减少流（非空）

终止条件：无增广路

最大流最小割定理 Maxflow–Mincut Theorem

跨越一个 cut (A,B)(A, B) 的网络流是从 AA 到 BB 的边的和 - 从 BB 到 AA 的边的和

流值引理：任意 cut (A,B)(A, B) 的网络流 = 任意流 ff 的值

证明：归纳法：

  • 基础情况：B=tB={t}
  • 递推步骤：因为本地平衡，从 AA 向 BB 中移动任何顶点后，依旧成立

推论：ss 的出流 = tt 的入流 = 流的值

弱对偶性：任意流 ff 的值 ≤ 任意 cut (A,B)(A, B) 的容量

证明：任意流 ff 的值 = 任意 cut (A,B)(A, B) 的网络流 ≤ cut (A,B)(A, B) 的容量

增广路定理：当且仅当无增广路时，流 ff 是最大流

最大流最小割定理：最大流的值 = 最小割的容量

证明：对任意流 ff，三种情况等价：

  1. 存在容量等于 ff 的值的割
  2. ff 是最大流
  3. 无增广路

1 → 2：因为任意流 ff 的值 ≤ 任意 cut (A,B)(A, B) 的容量
2 → 3：逆否命题：假如有增广路，ff 可以沿增广路增加
3 → 1：(A,B)(A, B) 满足 AA 为所有与 ss 通过没有满的前向或空的后向路相连的点的集合，因为没有增广路，tt 在另一个集合 BB 中，该割的容量 = 割之间的网络流 = ff 的值

游戏时间分析 Running Time Analysis

整数容量情况：

不变量：在 Ford–Fulkerson 算法中，流始终为整数

增广路的数量 ≤ 最大流的值

证明：每条增广路至少使值增加 11

完满定理：存在整数值的最大流（因为 Ford–Fulkerson 算法能终止且找到的最大流是整数）

Ford–Fulkerson 算法的效率依赖于增广路的选择：

增广路 路的数量 实现
最短路 ≤12EV≤ \frac 12 EV bfs
最胖路 ≤Eln⁡(EU)≤ E\ln(EU) 优先队列
随机路/dfs 路 ≤EU≤ EU 随机队列/dfs

Java 实现 Java Implementation

剩余容量：

  • 前向路：c−fc-f
  • 后向路：ff

增广路：

  • 前向路：增加
  • 后向路：减小

原图中的增广路等价于剩余网络中的有向路

public class FlowEdge {
    private final int v, w;
    private final double capacity;
    private double flow;

    public FlowEdge(int v, int w, double capacity) {
        this.v = v;
        this.w = w;
        this.capacity = capacity;
    }

    public int from() {
        return v;
    }

    public int to() {
        return w;
    }

    public double capacity() {
        return capacity;
    }

    public double flow() {
        return flow;
    }

    public int other(int vertex) {
        if (vertex == v)
            return w;
        else
            return v;
    }

    public double residualCapacityTo(int vertex) {
        if (vertex == v)
            return flow;
        else
            return capacity - flow;
    }

    public void addResidualFlowTo(int vertex, double delta) {
        if (vertex == v)
            flow -= delta;
        else
            flow += delta;
    }
}

import java.util.ArrayList;

public class FlowNetwork {
    private final int V;
    private ArrayList<FlowEdge>[] adj;

    public FlowNetwork(int V) {
        this.V = V;
        adj = (ArrayList<FlowEdge>[]) new ArrayList[V];
        for (int v = 0; v < V; v++)
            adj[v] = new ArrayList<>();
    }

    public void addEdge(FlowEdge e) {
        int v = e.from();
        int w = e.to();
        adj[v].add(e);
        adj[w].add(e);
    }

    public Iterable<FlowEdge> adj(int v) {
        return adj[v];
    }

    public int V() {
        return V;
    }
}

import java.util.LinkedList;
import java.util.Queue;

public class FordFulkerson {
    private boolean[] marked;
    private FlowEdge[] edgeTo;
    private double value;

    public FordFulkerson(FlowNetwork G, int s, int t) {
        value = 0.0;
        while (hasAugmentingPath(G, s, t)) {
            double bottle = Double.POSITIVE_INFINITY;
            for (int v = t; v != s; v = edgeTo[v].other(v))
                bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
            for (int v = t; v != s; v = edgeTo[v].other(v))
                edgeTo[v].addResidualFlowTo(v, bottle);
            value += bottle;
        }
    }

    private boolean hasAugmentingPath(FlowNetwork G, int s, int t) {
        edgeTo = new FlowEdge[G.V()];
        marked = new boolean[G.V()];
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        marked[s] = true;
        while (!q.isEmpty()) {
            int v = q.remove();
            for (FlowEdge e : G.adj(v)) {
                int w = e.other(v);
                if (e.residualCapacityTo(w) > 0 && !marked[w]) {
                    edgeTo[w] = e;
                    marked[w] = true;
                    q.add(w);
                }
            }
        }
        return marked[t];
    }

    public double value() {
        return value;
    }

    public boolean inCut(int v) {
        return marked[v];
    }
}

最大流应用 Maxflow Applications

二分图匹配

不知道有没有线性算法

基数排序 radix sort

Java 中的字符串 strings in Java

字符串：字符序列

public final class String implements Comparable<String>{
    private char[] value;
    private int offset;
    private int length;
    private int hash;

    public int length() {
        return length;
    }

    public char charAt(int i) {
        return value[i + offset];
    }

    private String(int offset,int length,char[] value) {
        this.offset = offset;
        this.length = length;
        this.value = value;
    }

    public String substring (int from,int to) {
        return new String(offset + from, to - from, value); // 切片飞快的原因
    }
}
操作 String 效率/额外空间 StringBuilder 效率/额外空间
length() 11 11
charAt() 11 11
substring() 11 NN
concat() NN 11 
public static int lcp(String s, String t) {
    int N = Math.min(s.length, t.length);
    for (int i = 0; i < N; i++)
        if (s.charAt(i) != t.charAt(i))
            return i;
    return N;
}

基数：字母表中数字个数 RR

键索引计数 Key-Indexed Counting

排序必须  Nlg⁡N~N\lg N 比较，但若不作比较，可以超越下界

思想：

  • 使用键做索引计数
  • 计算累加频率决定位置
  • 用键做索引移动项
  • 复制回原数组
int N = a.length;
int[] count = new int[R + 1];
for (int i = 0; i < N; i++)
    count[a[i] + 1]++;
for (int r = 0; r < R; r++)
    count[r + 1] += count[r];
for (int i = 0; i < N; i++)
    aux[count[a[i]]++] = a[i];
for (int i = 0; i < N; i++)
    a[i] = aux[i];

时间复杂度： 11N+4R~11N+4R 访问数组，额外空间 N+RN+R，稳定

LSD 基数排序 LSD radix sort

Least-significant-digit-first string sort：

  • 从右向左考虑
  • 使用第 dd 个字符作键稳定排序

证明（归纳法）：

  • 如果两个字符串在待排序字符不同，排序将它们放在合适的顺序上
  • 如果它们相同，稳定性将它们放在合适的顺序上
public class LSD {
    public static void sort(String[] a, int W) {
        int R = 256;
        int N = a.length;
        String[] aux = new String[N];
        for (int d = W - 1; d >= 0; d--) {
            int[] count = new int[R + 1];
            for (int i = 0; i < N; i++)
                count[a[i].charAt(d) + 1]++;
            for (int r = 0; r < R; r++)
                count[r + 1] += count[r];
            for (int i = 0; i < N; i++)
                aux[count[a[i].charAt(d)]++] = a[i];
            for (int i = 0; i < N; i++)
                a[i] = aux[i];
        }
    }
}

MSD 基数排序 MSD Radix Sort

Most-significant-digit-first string sort：（一种特殊的快速排序）

  • 根据第一个字符分成 RR 个部分
  • 递归排序所有开头相同的字符串
public class MSD {
    private static int R = 256;
    private static String[] aux;

    public static void sort(String[] a) {
        aux = new String[a.length];
        sort(a, aux, 0, a.length - 1, 0);
    }

    private static void sort(String[] a, String[] aux, int lo, int hi, int d) {
        if (hi <= lo)
            return;
        int[] count = new int[R + 2];
        for (int i = lo; i <= hi; i++)
            count[charAt(a[i], d) + 2]++;
        for (int r = 0; r < R; r++)
            count[r + 1] += count[r];
        for (int i = lo; i <= hi; i++)
            aux[count[charAt(a[i], d) + 1]++] = a[i];
        for (int i = lo; i <= hi; i++)
            a[i] = aux[i - lo];
        for (int r = 0; r < R; r++)
            sort(a, aux, lo + count[r], lo + count[r + 1] - 1, d + 1);
    }

    private static int charAt(String s, int d) {
        if (d < s.length())
            return s.charAt(d);
        else
            return -1;
    }
}

对于小数组太慢了，并且因为递归，小数组的数量太多了，所以可以用插入排序代替

public static void sort(String[] a, int lo, int hi, int d) {
    for (int i = lo; i <= hi; i++)
        for (int j = i; j > lo && less(a[j], a[j - 1], d); j--)
            exch(a, j, j - 1);
}

private static boolean less(String v, String w, int d) {
    return v.substring(d).compareTo(w.substring(d)) < 0;
}

MSD 基数排序的缺点：

  • 访问内存随机
  • 内部循环太多语句了
  • 额外空间多

直接快速排序的缺点：对于有很长前缀相同的字符串，必须重新扫描很多字符

三路基数快速排序 3-way Radix Quicksort

和三路快速排序一样，但是每次比较字符

public class wayRadixQuick {
    public static void sort(String[] a) {
        sort(a, 0, a.length - 1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d) {
        if (hi <= lo)
            return;
        int lt = lo, gt = hi;
        int v = charAt(a[lo], d);
        int i = lo + 1;
        while (i <= gt) {
            int cmp = charAt(a[i], d).compareTo(v);
            if (cmp < 0)
                exch(a, lt++, i++);
            else if (cmp > 0)
                exch(a, i, gt--);
            else
                i++;
        }
        sort(a, lo, lt - 1, d);
        if (v >= 0)
            sort(a, lo, gt, d + 1);
        sort(a, gt + 1, hi, d);
    }
}
算法 保证 随机 额外空间 稳定 对键的操作
LSD 2NW2NW 2NW2NW N+RN+R ✓✓ charAt()
MSD 2NW2NW Nlog⁡RNN\log_R N N+DRN+DR ✓✓ charAt()
三路基数快速排序 1.39WNlg⁡N1.39WN \lg N 1.39Nlg⁡N1.39N \lg N log⁡N+W\log N +W ×× charAt()

后缀数组 suffix array

上下文搜索关键词：

  • 预处理排序后缀
  • 询问：二分查找

最长重复子串：Manber-Myers MSD 算法：在第 ii 阶段，对于前 2i−12^{i-1} 个字符排序的后缀数组，创造对前 2i2^{i} 个字符排序的后缀数组

最坏情况：Nlg⁡NN\lg N

  • 在 lg⁡N\lg N 个阶段后完成
  • 每个阶段只要线性时间

Tries

R 路 Trie R-way Tries

本质是对于 string 类型的符号表，可以通过字符串的一些性质优化

思想：trie 得名于 retrieval

  • 在结点中存字符（而不是键中）
  • 每个结点有 R 个子结点，每个对应可能的字符
  • 在最后一个字符的键中存值

搜索：

  • 找到：搜索结束的结点有非空值
  • 未找到：搜索到了空的链接或搜索结束的结点没有值

插入：

  • 碰到空链：创建一个新结点
  • 碰到键的最后一个字符：在结点中添加值

删除：

  • 找到和键相关的结点并将值设为 null
  • 如果结点所有链都是空的，移除该结点（递归）
public class TrieST<Value> {
    private static final int R = 256;
    private Node root = new Node();

    private static class Node {
        private Object val;
        private Node[] next = new Node[R];
    }

    public void put(String key, Value val) {
        root = put(root, key, val, 0);
    }

    private Node put(Node x, String key, Value val, int d) {
        if (x == null)
            x = new Node();
        if (d == key.length()) {
            x.val = val;
            return x;
        }
        char c = key.charAt(d);
        x.next[c] = put(x.next[c], key, val, d + 1);
        return x;
    }

    public boolean contains(String key) {
        return get(key) != null;
    }

    public Value get(String key) {
        Node x = get(root, key, 0);
        if(x == null) return null;
        return (Value) x.val;
    }

    private Node get(Node x , String key, int d) {
        if (x == null) return null;
        if (d == key.length()) return x;
        char c = key.charAt(d);
        return get(x.next[c],key,d+1);
    }
}

R-way trie：

  • 对于小的 R 有用
  • 对于大的 R，使用空间太多
  • 插入快，查找一般更快

三叉搜索树 Ternary Search Tries

本质就是一个利用了前缀了二叉搜索树：

  • 在结点中存值和字符
  • 每个结点有 3 个子结点：左边小，中间相等，右边大

搜索：将每个字符与键比较：

  • 如果小于，走左边；大于，走右边
  • 如果相等，走中间并移动到下一个字符

和普通 trie 相比优势在于每个结点只有 3 个链，大量节省空间

public class TST<Value> {
    private class Node {
        private Value val;
        private char c;
        private Node left, mid, right;
    }

    private Node root;

    public void put(String key, Value val) {
        root = put(root, key, val, 0);
    }

    private Node put(Node x, String key, Value val, int d) {
        char c = key.charAt(d);
        if (x == null) {
            x = new Node();
            x.c = c;
        }
        if (c < x.c)
            x.left = put(x.left, key, val, d);
        else if (c > x.c)
            x.right = put(x.right, key, val, d);
        else if (d < key.length() - 1)
            x.mid = put(x.mid, key, val, d + 1);
        else
            x.val = val;
        return x;
    }

    public boolean contains(String key) {
        return get(key) != null;
    }

    public Value get(String key) {
        Node x = get(root, key, 0);
        if (x == null)
            return null;
        return x.val;
    }

    private Node get(Node x, String key, int d) {
        if (x == null)
            return null;
        char c = key.charAt(d);
        if (c < x.c)
            return get(x.left, key, d);
        else if (c > x.c)
            return get(x.right, key, d);
        else if (d < key.length() - 1)
            return get(x.mid, key, d + 1);
        else
            return x;
    }
}

类似于 BST，可以通过旋转建立平衡 TST 实现最坏情况的保证

R-way trie 和 TST 和混合：

  • 在根结点建立 R2R^2 路分支
  • 每个 R2R^2 根结点指向一个 TST
实现 查找到 未查找到 插入 空间 中等数据使用时间 大数据
红黑树 L+clg⁡2NL+c\lg ^2 N clg⁡2Nc\lg ^2 N clg⁡2Nc\lg ^2 N 4N4N 1.401.40 97.497.4
哈希（线性探查） LL LL LL 4N 16N4N~16N 0.760.76 40.640.6
R 路 trie LL log⁡RN\log _R N LL (R+1)N(R+1)N 1.121.12 超内存
TST L+ln⁡NL+\ln N ln⁡N\ln N L+ln⁡NL+\ln N 4N4N 0.720.72 38.738.7
R 路 TST L+ln⁡NL+\ln N ln⁡N\ln N L+ln⁡NL+\ln N 4N+R24N+R^2 0.510.51 32.732.7

哈希：

  • 需要检查每个键
  • 查找到和未找到花费相同
  • 效率依赖于哈希函数
  • 不支持有序符号表操作

TST：

  • 只对字符串或数字键有效
  • 只检查足够的键字符
  • 搜索失败只需要一些字符
  • 支持有序符号表操作

总的来说，TST：

  • 比哈希快（尤其是搜索失败）
  • 比红黑树更灵活

以字符为基础的操作 Character-Based Operations

有序迭代：

  • 对 trie 作中序遍历：把遇到的键添加到队列中
  • 维护从根到结点的字符串序列
public Iterable<String> keys() {
    Queue<String> queue = new LinkedList<>();
    collect(root, "", queue);
    return queue;
}

public void collect(Node x, String prefix, Queue<String> q) {
    if (x == null)
        return;
    if (x.val != null)
        q.add(prefix);
    for (int c = 0; c < R; c++)
        collect(x.next[c], prefix + c, q);
}

前缀匹配

public Iterable<String> keysWithPrefix(String prefix) {
    Queue<String> queue = new LinkedList<>();
    Node x = get(root, prefix, 0);
    collect(x, prefix, queue);
    return queue;
}

最长前缀：

  • 查找字符串
  • 跟踪遇到的最长键
public String longestPrefixOf(String query) {
    int length = search(root, query, 0, 0);
    return query.substring(0, length);
}

private int search(Node x, String query, int d, int length) {
    if (x == null)
        return length;
    if (x.val != null)
        length = d;
    if (d == query.length())
        return length;
    char c = query.charAt(d);
    return search(x.next[c], query, d + 1, length);
}

Patricia trie(Practical Algorithm to Retrieve Information Coded in Alphanumeric)

  • 移除单路分支
  • 每个结点代表字符序列

后缀树：

  • 字符串后缀的 Patricia trie
  • 线性时间构建，可用于线性时间的最长重复子串

子串查找 substring search

对每个位置查找匹配

public static int search(String pat, String txt) {
    int M = pat.length();
    int N = txt.length();
    for (int i = 0; i <= M - N; i++) {
        int j;
        for (j = 0; j < M; j++)
            if (txt.charAt(i + j) != pat.charAt(j))
                break;
        if (j == M)
            return i;
    }
    return N;
}

避免备份（因为输入是流）的暴力方法

public static int search(String pat, String txt) {
    int i, N = txt.length();
    int j, M = pat.length();
    for (i = 0, j = 0; i < N && j < M; i++) {
        if (txt.charAt(i) == pat.charAt(j))
            j++;
        else {
            i -= j;
            j = 0; // 备份
        }
    }
    if (j == M)
        return i - M;
    else
        return N;
}

理论挑战：线性时间保证

实践挑战：避免备份

KMP 算法 Knuth–Morris–Pratt

思想：

  • 如果我们匹配了 5 个字符，第六个字符匹配失败
  • 我们已知了前 6 个字符
  • 不需要备份下一个指针

DFA（deterministic finite state automaton）：

  • 有限阶段（包括开始和停止）
  • 对于字母表中的每一个字符都有一个特定的转移
  • 接受转移导向停止阶段的序列

在 KMP 中，阶段 = 已经匹配的字符数（pat[]的最长前缀，txt[0...i]的一个后缀）

和暴力方法的关键不同：

  • 需要提前计算 dfa[][]
  • 指针 i 从不减小（最多访问 N 个字符）
  • 可以使用输入流
public static int search(String txt) {
    int i, j, N = txt.length();
    for (i = 0, j = 0; i < N && j < M; i++)
        j = dfa[txt.charAt(i)][j];
    if (j == M)
        return i - M;
    else
        return N;
}

匹配转移：如果在阶段 j，且下一个字符c == pat.charAt(j)，到 j+1 阶段

失配转移：如果在阶段 j，且下一个字符c != pat.charAt(j)，输入流的最后 j-1 个字符是pat[1...j-1]，后面跟着 c

计算dfa[c][j]：在 DFA 上模拟pat[1...j-1]，用 c 转移（如果维护阶段 X 的话，只需要常数时间）

失配转移：对于每个阶段 j，且下一个字符c != pat.charAt(j)，设置dfa[c][j] = dfa[c][X]，然后更新X = dfa[pat.charAt(j)][X]

public void KMP(String pat) {
    this.pat = pat;
    M = pat.length();
    dfa[pat.charAt(0)][0] = 1;
    for (int X = 0, j = 1; j < M; j++) {
        for (int c = 0; c < R; c++)
            dfa[c][j] = dfa[c][X];
        dfa[pat.charAt(j)][j] = j + 1;
        X = dfa[pat.charAt(j)][X];
    }
}

KMP 算法搜索时访问不超过 M+NM + N 个字符

证明：

  • 在构造 DFA 时，每个模式字符被访问了一次
  • 在模拟 DFA 时，每个文本字符在最坏情况在访问了一次

KMP 构造dfa[][]的时间和空间复杂度为 RMRM

大字母表：KMP 的优化版本构造nfa[][]的时间和空间复杂度为 MM

KMP 算法是三个人独立发明的

Boyer–Moore 算法

思想：启发式搜索

  • 从右到左在模式中扫描字符
  • 当找到一个不在模式中的字符时，可以跳过 M 个文本字符

提前计算在模式串中最右出现的字符 c 的索引

right = new int[R];
for (int c = 0; c < R; c++)
    right[c] = -1;
for (int j = 0; j < M; j++)
    right[pat.charAt(j)] = j;
public int search(String txt) {
    int N = txt.length();
    int M = pat.length();
    int skip;
    for (int i = 0; i <= N - M; i += skip) {
        skip = 0;
        for (int j = M - 1; j >= 0; j--)
            if (pat.charAt(j) != txt.charAt(i + j)) {
                skip = Math.max(1, j - right[txt.charAt(i + j)]);
                break;
            }
        if (skip == 0)
            return i;
    }
    return N;
}

花费一般为  N/M~N/M，但最坏情况为 MNMN

Rabin–Karp 算法

思想：模块化哈希

  • 计算模式串的哈希
  • 对每个 ii，计算 ii 到 M+i−1M + i - 1 文本串的哈希
  • 如果两者相等，检查匹配

模块化的哈希函数：对于多项式

xi=tiRM−1+ti+1RM−2+⋯+ti+M−1R0(modQ)x_i = t_i R^{M-1} + t_{i+1}R^{M-2} + ⋯ + t_{i+M-1}R^{0} (mod Q)

有线性方法计算多项式哈希函数（Horner's method）：

private long hash(String key, int M) {
    long h = 0;
    for (int j = 0; j < M; j++)
        h = (R * h + key.charAt(j)) % Q;
    return h;
}

相似的，对于给定的 xix_i，可以计算 xi+1x_{i+1}：

xi+1=(xi−tiRM−1)R+ti+Mx_{i+1} = (x_i - t_i R^{M-1})R + t_{i+M}

当然，也可以对各项取模，RM−1R^{M-1} 可以提前计算

public class RabinKarp {
    private long patHash;
    private int M;
    private long Q;
    private int R;
    private long RM;

    private long hash(String key, int M) {
        long h = 0;
        for (int j = 0; j < M; j++)
            h = (R * h + key.charAt(j)) % Q;
        return h;
    }

    public RabinKarp(String pat) {
        M = pat.length();
        R = 256;
        Q = longRandomPrime();
        RM = 1;
        for (int i = 1; i < M; i++)
            RM = (RM * R) % Q;
        patHash = hash(pat, M);
    }

    public int search(String txt) {
        int N = txt.length();
        long txtHash = hash(txt, M);
        if (patHash == txtHash)
            return 0;
        for (int i = M; i < N; i++) {
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            if (patHash == txtHash)
                return i - M + 1; // Las Vegas版本，进一步检查是否正确
        }
        return N;
    }
}

理论：如果 QQ 是一个足够大的质数，错误冲突的概率为 1/N1/N

实际：选择大质数 QQ，在合理的假设下，冲突的概率为 1/Q1/Q

Monte Carlo 版：

  • 总是以线性时间运行
  • 一般返回的是正确答案

Las Vegas 版：

  • 总是返回正确的答案
  • 一般以线性时间运行
算法 版本 保证 一般 需要输入备份 正确 额外空间
暴力 MNMN 1.1N1.1N 是 是 11
Knuth–Morris–Pratt 完全 DFA 2N2N 1.1N1.1N 否 是 MRMR
Knuth–Morris–Pratt 只错配转移 3N3N 1.1N1.1N 否 是 MM
Boyer-Moore 完全算法 3N3N N/MN/M 是 是 RR
Boyer-Moore 只启发式错配字符 MNMN N/MN/M 是 是 RR
Rabin-Karp Monte Carlo 7N7N 7N7N 否 一般是 11
Rabin-Karp Las Vegas 一般7N7N 7N7N 是 是 11

正则表达式 Regular Expression

正则表达式 Regular Expression

子字符串搜索：在文本中寻找一个字符串

模式匹配：在文本中寻找特定集合的字符串

为了简单起见，这里的正则表达式只包括基础的|、*、()和字符匹配

  • 写正则表达式就像在写程序，需要理解程序模型
  • 写起来容易，读起来难
  • debug 难

正则表达式和 NFA REs and NFAs

正则表达式：描述字符串集合的方法

DFA：识别所给字符串是否在给定集合中的机器

Kleene's 定理：

  • 对于任意 DFA，存在描述相同集合的字符串的 RE
  • 对于任意 RE，存在识别相同集合的字符串 DFA

底层抽象：NFA（Nondeterministic finite automaton）

基本计划：（类似于 KMP）【使用 Kleene's 定理】

  • 从 RE 建造 NFA
  • 用 NFA 模拟文本输入

正则表达式匹配 NFA：

  • RE 被封闭在括号内
  • 每个 RE 字符一个状态
  • 红色的 ϵ 转移（改变状态，但不扫描文本）
  • 黑色的匹配转移（改变状态并扫描文本的下一个字符）
  • 如果有序列转移到接受状态，接受

非确定性：

  • 机器可以猜测合适的状态转移序列

  • 序列是机器接受文本的证明

  • 匹配成功：有某个转移序列到达接受状态

  • 匹配失败：没有转移序列能够到达接受状态

模拟要点：保证考虑了所有可能的转移序列

NFA 模拟 NFA Simulation

ϵ 转移：存在有向图中

维护所有 NFA 在读了第 i 个文本字符后所有可能状态的集合

读下一个输入字符：

  • 找到通过匹配转移能到达的状态
  • 找到通过 ϵ 转移能到达的状态

当没有输入字符时：

  • 如果能到达接受状态，接受
  • 否则拒绝

可以使用 dfs 找到所有可到达的状态

public class NFA {
    private char[] re;
    private Digraph G;
    private int M;

    public NFA(String regexp) {
        M = regexp.length();
        re = regexp.toCharArray();
        G = buildEpsilonTransitionDigraph();
    }

    public boolean recognizes(String txt) {
        Bag<Integer> pc = new Bag<Integer>();
        DirectedDFS dfs = new DirectedDFS(G, 0);
        for (int v = 0; v < G.V(); v++)
            if (dfs.marked(v))
                pc.add(v);
        for (int i = 0; i < txt.length(); i++) {
            Bag<Integer> match = new Bag<Integer>();
            for (int v : pc) {
                if (v == M)
                    continue;
                if ((re[v] == txt.charAt(i)) || re[v] == '.')
                    match.add(v + 1);
            }
            dfs = new DirectedDFS(G, match);
            pc = new Bag<Integer>();
            for (int v = 0; v < G.V(); v++)
                if (dfs.marked(v))
                    pc.add(v);
        }
        for (int v : pc)
            if (v == M)
                return true;
        return false;
    }
}

最坏情况下时间复杂度为MNMN

NFA 构造 NFA Construction

串联：从字母表的字符向下一个状态添加模式转移边

终止：对每个*操作符，添加三条 ϵ 转移边

或：对每个|操作符，添加 2 条 ϵ 转移边

为了实现“终止”和“或”，需要记住左括号的位置：用栈维护

左括号：

  • 向下一个状态添加 ϵ 转移边
  • 向栈中加入(的索引

字母表符号：

  • 向下一个状态添加模式转移边
  • 向后看一个字符：如果下一个字符是*，添加 ϵ 转移边

右括号：

  • 向下一个状态添加 ϵ 转移边
  • 弹出相关的(和可能的|，对“或”添加 ϵ 转移边
  • 向后看一个字符：如果下一个字符是*，添加 ϵ 转移边
private Digraph buildEpsilonTransitionDigraph() {
    Digraph G = new Digraph(M + 1);
    Stack<Integer> ops = new Stack<>();
    for (int i = 0; i < M; i++) {
        int lp = i;
        if (re[i] == '(' || re[i] == '|')
            ops.add(i);
        else if (re[i] == ')') {
            int or = ops.pop();
            if (re[or] == '|') {
                G.addEdge(lp, or + 1);
                G.addEdge(or, i);
            } else
                lp = or;
        }
        if (i < M - 1 && re[i + 1] == '*') {
            G.addEdge(lp, i + 1);
            G.addEdge(i + 1, lp);
        }
        if (re[i] == '(' || re[i] == '*' || re[i] == ')')
            G.addEdge(i, i + 1);
    }
    return G;
}

构造 NFA 的时间和空间正比于 MM，因为每次添加最多 3 条 ϵ 转移边，执行最多 2 次栈操作

正则表达式应用 Regular Expression Applications

命令行的grep操作

收获信息

检查

数据压缩 Data Compression

介绍数据压缩 Introduction to Data Compression

优点：

  • 节省存储空间
  • 节省传输时间

压缩 compress：对于 B，生成压缩表达 C(B) 解压缩 expand：重新构造原始的 B

没有算法能够压缩每一个比特字符串

运行长度编码 Run-Length Coding

8bit 计数 0 和 1 交替出现的次数

public class RunLength {
    private final static int R = 256;
    private final static int lgR = 8;

    public static void expand() {
        boolean bit = false;
        while (!BinaryStdIn.isEmpty()) {
            int run = BinaryStdIn.readInt(lgR);
            for (int i = 0; i < run; i++)
                BinaryStdOut.write(bit);
            bit = !bit;
        }
        BinaryStdOut.close();
    }
}

Huffman 压缩 Huffman Compression

使用不同数量的比特编码不同的字符

避免歧义：

  1. 固定长度编码
  2. 向每个编码字符添加特殊的停止字符
  3. 构造前缀不冲突的编码

构造前缀不冲突的编码：

  • 二叉 trie
  • 字符在叶结点上
  • 编码为从根到叶结点的路径、

压缩：

  1. 从叶结点开始，沿路径向根结点，反向输出比特
  2. 创造键值对的 ST

解压：

  • 从根结点开始
  • 如果是 0，向左；如果是 1，向右
  • 如果是叶结点，输出字符并返回根

Shannon-Fano 算法：

  • 把 SS 分成几乎相等的两部分 S0S_0 和 S1S_1
  • 在 S0S_0 中的编码开头为 0；在 S1S_1 中的编码开头为 1
  • 在 S0S_0 和 S1S_1 递归

Huffman 算法：

  • 在输入中计算每个字符的出现频率
  • 选择两个最小重量的 trie
  • 把两个 trie 合并
public class Huffman {
    private static class Node implements Comparable<Node> {
        private char ch;
        private int freq;
        private final Node left, right;

        public Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        @Override
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }

    public void expand() {
        Node root = readTrie();
        int N = BinaryStdIn.readInt();
        for (int i = 0; i < N; i++) {
            Node x = root;
            while (!x.isLeaf()) {
                if (!BinaryStdIn.readBoolean())
                    x = x.left;
                else
                    x = x.right;
            }
            BinaryStdOut.write(x.ch, 8);
        }
        BinaryStdOut.close();
    }

    private static Node buildTrie(int[] freq) {
        MinPQ<Node> pq = new MinPQ<>();
        for (char i = 0; i < R; i++)
            if (freq[i] > 0)
                pq.insert(new Node(i, freq[i], null, null));
        while (pq.size() > 1) {
            Node x = pq.delMin();
            Node y = pq.delMin();
            Node parent = new Node('\0', x.freq + y.freq, x, y);
            pq.insert(parent);
        }
        return pq.delMin();
    }

    private static void writeTrie(Node x) {
        if (x.isLeaf()) {
            BinaryStdOut.write(true);
            BinaryStdOut.write(x.ch, 8);
            return;
        }
        BinaryStdOut.write(false);
        writeTrie(x.left);
        writeTrie(x.right);
    }

    private static Node readTrie() {
        if (BinaryStdIn.readBoolean()) {
            char c = BinaryStdIn.readChar(8);
            return new Node(c, 0, null, null);
        }
        Node x = readTrie();
        Node y = readTrie();
        return new Node('\0', 0, x, y);
    }
}

Huffman 算法生成最优化的无前缀编码

实现：

  • 列表字符频率并建立 trie
  • 通过遍历 trie 或查表编码文件

时间 N+Rlog⁡RN + R\log R

LZW 压缩 LZW Compression

静态模型（ASCII，摩斯密码）：对于所有的文本模型相同

  • 快
  • 非最优化：不同文本有不同的静态性质

动态模型（Huffman）：基于文本生成模型

  • 需要初次 pass 生成模型
  • 必须传递模型

适应性模型（LZW）：在读文本的过程中学习并更新模型

  • 更多精确的模型产生更好的压缩
  • 必须从开始解码

LZW 压缩：

  • 用字符串键创建关联 W 比特编码的 ST
  • 对单个字符键初始化 ST
  • 在 ST 中找到最长的字符串 s，s 为输入未扫描部分的前缀
  • 写出关联 s 的 W 比特编码
  • 把 s+c 添加到 ST 中，c 是输入的下一个字符

LZW 解压：

  • 用字符串键创建关联 W 比特编码的 ST
  • 对单个字符键初始化 ST
  • 读一个 W 比特的键
  • 在 ST 中找到相关的字符串值并输入
  • 更新 ST

使用数组

无损压缩：

  • 用可变长度编码代替定长符号（Huffman）
  • 用定长编码代替可变长度符号（Huffman）

压缩的理论限制：香农熵

归约 reductions

介绍归约 Introduction to Reductions

需求：根据计算需求给问题分类

如果可以使用一个能解决 YY 的算法来解决 XX，则称问题 XX 归约于 YY

解决 XX 的花费 = 解决 YY 的总花费 + 归约的花费

设计算法 Designing Algorithms

Graham 扫描算法：把凸包归约于排序

把无向图最短路径归约到有向图最短路径（用两个有向边代替无向边），时间复杂度 Elog⁡VE\log V(有向图最短路径花费) + EE(归约花费)

建立下界 Establishing Lower Bounds

问题 XX 线性时间归约到问题 YY，如果 XX 能被解决：

  • 线性数量的标准计算步
  • 常数数量调用 YY

凸包问题的下界：

排序线性时间归约到凸包：

  • 待排序 x1,x2,...,xNx_1,x_2,...,x_N
  • 凸包实例 (x1,x12),(x2,x22),...,(xN,xN2)(x_1,x_1^2),(x_2,x_2^2),...,(x_N,x_N^2)
  • 所有点都在凸包上
  • 从最左端 xx 开始，逆时针遍历凸包

给问题分类 Classifying Problems

证明两个问题 XX 和 YY 有相同的复杂度

  • 证明 XX 线性时间归约到 YY
  • 证明 YY 线性时间归约到 XX

凸包和排序有相同的复杂度

线性代数归约：

  • 整数乘法
  • 矩阵乘法

线性规划 Linear programming

酿酒人问题 Brewer's Problem

最优分配稀有资源的问题，有相互竞争的行为

例如，已知：

5A+15B≤4805A + 15B ≤ 480

4A+4B≤1604A + 4B ≤ 160

35A+20B≤119035A + 20B ≤ 1190

A,B≥0A,B ≥ 0

求最大化：13A+23B13A+23B

标准形式：

  • 向关联的对象函数添加 ZZ 和等式
  • 添加松弛变量来把不等关系变为相等关系
  • 变成了六维问题

最大化 ZZ

13A+23B−Z=013A + 23B - Z = 0

5A+15B+SC=4805A + 15B + S_C = 480

4A+4B+SH=1604A + 4B + S_H = 160

35A+20B+SM=119035A + 20B + S_M = 1190

A,B≥0A,B ≥ 0

几何直观：

不等式定义半平面，有效区域是一个凸多边形，最优决策出现在极限点

当任何两个集合中的点的中点在集合中，则称该集合为凸的

极限点是集合中一个不能被写成两个点中点的点

极限点的性质：

  • 如果存在 PP 的最优解，则存在一个极限点
  • 极限点的数量是有限的，但可能是指数级的

单纯形算法 Simplex Algorithm

泛型算法：

  • 从某个极限点开始
  • 从一个极限点转动到相邻的（不下降函数）
  • 重复直到最优化

基是 nn 个变量的包含 mm 个元素的子集

基本的可行措施 BFS：

  • 把 n−mn - m 非基变量设为 0，解决剩下的 mm 个变量
  • 解关于 mm 个未知数的 mm 个方程
  • 如果唯一且可行，则是 BFS
  • BFS 对应于极限点

初始 BFS：

  • 从松弛变量 SC,SH,SM{S_C,S_H,S_M} 开始
  • 把非基变量 AA 和 BB 设为 00
  • SC=480,SH=160,SM=1190S_C = 480,S_H = 160, S_M = 1190

选择支点：目标函数系数为正

停止条件：没有目标函数系数为正

单纯形实现 Simplex Implementations

public class Simplex {
    private double[][] a;
    private int m, n;

    public Simplex(double[][] A, double[] b, double[] c) {
        m = b.length;
        n = c.length;
        a = new double[m + 1][m + n + 1];
        for (int i = 0; i < m; i++) // 矩阵A
            for (int j = 0; j < n; j++)
                a[i][j] = A[i][j];
        for (int j = n; j < n + m; j++) // 矩阵I
            a[j - n][j] = 1.0;
        for (int j = 0; j < n; j++) // 系数矩阵C
            a[m][j] = c[j];
        for (int i = 0; i < m; i++) // 矩阵b
            a[i][m + n] = b[i];
    }

    private int bland() {
        for (int q = 0; q < m + n; q++)
            if (a[m][q] > 0)
                return q; // 找到第一个正系数q
        return -1;
    }

    private int minRatioRule(int q) {
        int p = -1;
        for (int i = 0; i < m; i++) {
            if (a[i][q] <= 0)
                continue;
            else if (p == -1)
                p = i;
            else if (a[i][m + n] / a[i][q] < a[p][m + n] / a[p][q])
                p = i;
        }
        return p;
    }

    public void pivot(int p, int q) { // 高斯消元
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= m + n; j++)
                if (i != p && j != q)
                    a[i][j] -= a[p][j] * a[i][q] / a[p][q];
        for (int i = 0; i <= m; i++)
            if (i != p)
                a[i][q] = 0.0;
        for (int j = 0; j < m + n; j++)
            if (j != q)
                a[p][j] /= a[p][q];
        a[p][q] = 1.0;
    }

    public void solve() {
        while (true) {
            int q = bland();
            if (q == -1)
                break;
            int p = minRatioRule(q);
            if (p == -1)
                break;
            pivot(p, q);
        }
    }
}

在一般的实际应用中，单纯形算法在最多 2(m+n)2(m+n) 个主元后终止

主元规则：平衡了找到进入变量的花费和需要的主元数量

线性规划归约 Linear Programming Reductions

最小化问题：将求 13A+15B13A + 15B 的最小值转化为求 −13A−15B-13A - 15B 的最大值

≥≥ 约束：将 4A+4B≥1604A + 4B ≥ 160 替换为 4A+4B−Sn=160,Sn≥04A + 4B - S_n = 160, S_n ≥ 0

无约束变量：将 BB 替换为 B=B0−B1,B0≥0,B1≥0B = B_0 - B_1, B_0 ≥ 0, B_1 ≥ 0

线性规划 → 归约到线性规划

  • 对一个问题处理为 LP 模型
  • LP 的解就是问题的解

例如：最大流问题

难以解决的 Intractability

介绍难以解决的问题 Introduction to Intractability

简单计算模型：DFA

通用计算模型：图灵机（相比 DFA 增加了写的功能）

不存在比图灵机更强大的计算模型，因为可以通过模拟证明模型的等价

实践中可以解决的问题是有多项式时间的算法

如果一个问题不能在多项式时间内被解决，则该问题是难以解决的 Intractable

搜索问题 Search Problems

LSOLVE：给定一个线性方程组，找到一个解

LP：给定一个线性不等式组，找到一个解

ILP：给定一个线性不等式组，找到一个 0−10-1 的解

SAT：给定一个 bool 等式组，找到一个二进制解

是否有多项式时间算法：

  • LSOLVE 有，高斯消元
  • LP 有，Ellipsoid 算法
  • ILP 和 SAT 至今未知是否存在

搜索问题：给定一个问题的一个实例 I，找到一个解 S

需求：必须能有效地验证 S 是一个解

P 和 NP P vs. NP

NP 是所有搜索问题的类

P 是所有可以在多项式时间内解决的搜索问题的类

不确定性机器可以猜测想要的解

扩展 Church-Turing 论点：P = 所有可以在多项式时间内解决的自然界的搜索问题

很多人认为 P≠NPP≠NP，这似乎相当直观，但如果成功证明了 P=NPP=NP，那一定是一场颠覆性的革命

我想到了一个绝妙的证明方法，可惜我的博客写不下

给问题分类 Classifying Problems

NP 中的很多问题都可以多项式时间归约到 SAT 问题中

NP 完全 NP-Completeness

如果 NP 中的所有问题都可以归约到某个问题，则该问题是NP 完全问题 NP-complete

SAT 就是一个 NP 完全问题

证明：

  • 把不确定性图灵机记号改为 SAT 记号
  • 如果可以解决 SAT，就可以解决 NP 中的所有问题

现在有很多 NP 完全问题

处理难以解决的问题 Coping with Intractability

现代密码学：RSA（大因数分解）