
## Concepts

The computer system's fault always be caused by instruments' and components' aging and inefficient. We trait their lifespan and present statistics information, conclude that every component in system have three stages: starting stage, normal working stage and aging stage.

At first starting stage, the component's working status may not stable, and has higher failure rate. At second stage it works normally and enters into stable, also has lower failure rate. But if it enters the third stage, system reliability will decrease due to aging factors. Its failure rate will re-increase again. This is also known as the _bathtub curve_. So the component should be kept in the second stage as much as possible.

The definition of reliability in computer systems refers to the probability of it operating normally from its initiation at time $t = 0$ to a specified time $t$. This probability can be represented by $R(t)$. The failure rate of a computer system refers to the proportion of components failing per unit time compared to the total number of components. It is denoted by $\lambda$. When $\lambda$ is constant, the relationship between reliability and failure rate can be expressed as

$$
R(t) = e^{-\lambda t}
$$

In computer systems, the time during which the system operates normally between two failure occurrences is termed the system's uptime. The average of all such uptime durations is referred to as the Mean Time Between Failures (MTBF). Its relationship with the failure rate is expressed as:

$$
MTBF = \frac{1}{\lambda}
$$

To express the maintainability of a computer, we commonly use the Mean Time to Repair (MTTR), which represents the efficiency of maintenance. It is the average duration from the occurrence of a failure to the restoration of operation. In computer systems, we also use "availability" to denote the system's operational efficiency, which refers to the probability of the computer system functioning normally at any given time. It can be expressed as:

$$
A = \frac{MTBF}{MTBF + MTTR}
$$

The reliability measurement of a computer typically relies on the aforementioned concepts.

## Reliability of series components

In a series system composed of $N$ components connected sequentially end-to-end, the entire system operates normally only when all components function properly. If the reliability of these components is $R_{1}, R_{2}, R_{3}, ..., R_{N}$, and their failure rates are $\lambda_{1}, \lambda_{2}, \lambda_{3}, ..., \lambda_{N}$, then:

The overall reliability of the system is:

$$
R = R_{1} \times R_{2} \times ... \times R_{N}
$$

The overall failure rate of the system is:

$$
\lambda = \lambda_{1} + \lambda_{2} + \lambda_{3} + ... + \lambda_{N}
$$

## Reliability of parallel components

In a parallel system composed of $N$ components connected in parallel, the entire system operates normally as long as at least one component functions properly. In a parallel system, only one component is essential, while the remaining $N-1$ components are redundant. The more redundant components there are, the higher the system reliability. Assuming the reliability of these components is $R_{1}, R_{2}, R_{3}, ..., R_{N}$:

The overall reliability of the system is calculated as:

$$
R = 1 - (1-R_{1})(1-R_{2})...(1-R_{N})
$$

Assuming the failure rate of all components in the system is $\lambda$, the overall failure rate of the system is:

$$
\mu = \frac{1}{\frac{1}{\lambda}\sum_{j=1}^{N}\frac{1}{j}}
$$

## N-modular redundancy system

An N-modular redundancy system consists of N (where $N = 2n + 1$) identical subsystems and one voting unit. When the system is operational, all subsystems simultaneously compute results, and the voting unit outputs the result that is in the majority, thus serving as the final outcome. This setup helps to mitigate failures caused by random factors, ensuring the reliability of the system. If at least $n+1$ components function properly, then the entire system operates normally.

When a module in the system fails, the remaining modules continue to provide service, ensuring the system's availability. The level of redundancy in an N-modular redundancy system is determined by the value of N, with a higher N value indicating greater redundancy and reliability.

Assuming the voter is entirely reliable and each subsystem has a reliability of $R_{0}$ , the reliability of an N-modular redundancy system is calculated as:

$$
R = \sum_{i=n+1}^{N}\binom{i}{N}R_{0}^{i}(1-R_{0})^{N-i}
$$

In the United States' lunar exploration satellites, N-modular redundancy systems are utilized to construct the computer systems onboard the satellite to mitigate failures in the space environment.


Outlines computer system reliability, including series, parallel components, and N-modular redundancy.

System Reliability Model


For the integration of piecewise continuous functions, the results of "rectangular approximation" and "trapezoidal approximation" are the same, with the difference lying only in the speed of approximation. The essence of this problem lies in "error estimation".

We only need to analyze the "error reduction process" associated with the "approximation process".

To better understand the error, I will specifically calculate and analyze the integrations using rectangular and trapezoidal approximations for continuous functions on closed intervals.

Given $f \in \mathcal{C}[a, b]$, let's start with the expression for rectangular approximation integration:

$$
\lim_{n\to\infty}\sum_{k=1}^n f\left(\frac{(n-k)a+kb}{n}\right)\cdot\frac{(a-b)}{n} = \\
\lim_{n\to\infty}\sum_{k=1}^{n-1} f\left(\frac{(n-k)a+kb}{n}\right)\cdot\frac{(a-b)}{n}+f(b)\cdot\frac{(a-b)}{n} \quad {(1)}
$$

Now, let's look at the expression for trapezoidal approximation:

$$
\lim_{n\to\infty}\sum_{k=1}^n\frac{f\left(\frac{(n-k+1)a+(k-1)b}{n}\right)+f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n}\dots \quad {(2)}
$$

Let's rewrite the above expression, **pay attention to the change in the upper limit of summation**, observe:

$$
\begin{align*}
&\lim_{n\to\infty}\sum_{k=1}^n\frac{f\left(\frac{(n-k+1)a+(k-1)b}{n}\right)+f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n} \\
&=\lim_{n\to\infty}\sum_{k=1}^n\frac{f\left(\frac{(n-k+1)a+(k-1)b}{n}\right)}{2}\cdot\frac{(a-b)}{n} \\
&\qquad\quad +\lim_{n\to\infty}\sum_{k=1}^n\frac{f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n} \\
&=\lim_{n\to\infty}\sum_{k=0}^{n-1}\frac{f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n} \\
&\qquad\quad +\lim_{n\to\infty}\sum_{k=1}^n\frac{f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n} \\
&=\lim_{n\to\infty}\left[\left(\frac{f(a)}{2}\cdot\frac{(a-b)}{n}+\sum_{k=1}^{n-1}\frac{f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n}\right) \right. \\
&\qquad\quad \left. +\left(\sum_{k=1}^{n-1}\frac{f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n}+\frac{f(b)}{2}\cdot\frac{(a-b)}{n}\right)\right] \\
&=\lim_{n\to\infty}(\frac{f(a)}{2}\cdot\frac{(a-b)}{n}+\frac{f(b)}{2}\cdot\frac{(a-b)}{n})+ \\
& \lim_{n\to\infty}(2\cdot\sum_{k=1}^{n-1}\frac{f\left(\frac{(n-k)a+kb}{n}\right)}{2}\cdot\frac{(a-b)}{n}) \\
&=\lim_{n\to\infty}(\frac{f(a)+f(b)}{2}\cdot\frac{(a-b)}{n}+\sum_{k=1}^{n-1}f(\frac{(n-k)a+kb}{n})\cdot\frac{(a-b)}{n}) \\
&=\lim_{n\to\infty}\sum_{k=1}^{n-1}f\left(\frac{(n-k)a+kb}{n}\right)\cdot\frac{(a-b)}{n}+\frac{f(a)+f(b)}{2}\cdot\frac{(a-b)}{n} \dots \quad {(3)}
\end{align*}
$$

Comparing equation ${3}$ with equation ${1}$, did you notice? When integrating using two different approximation methods, the difference lies in:

$$
\frac{f(a)+f(b)}{2}\cdot\frac{(a-b)}{n}-f(b)\cdot\frac{(a-b)}{n} \\
=\frac{f(a)-f(b)}{2}\cdot\frac{(a-b)}{n}
$$

We denote this expression as $\Delta(n)$. Notice, it only involves one variable $n$. And it's easy to see:

- $I.$ If $f(a)=f(b)$, then $\Delta(n)\equiv0$.

- $II.$ If $f(a)\neq f(b)$, then $\Delta(n)=O(\frac{1}{n})$.

The first case might give you a feeling of reading an O. Henry novel. Surprisingly, only if $f(a)=f(b)$, no matter how the graph of $f$ fluctuates within the interval, rectangular and trapezoidal approximations are completely consistent, resulting in equal errors. As expected, when you write out the two expressions and observe each term of the summation, you'll find that the terms in both expressions are roughly the same.

The second case leads to a deeper conclusion. Let's denote the error of equation $(1)$ as $\delta_1(n)$ and the error of equation $(3)$ as $\delta_2(n)$, we have:

$$
\delta_1(n)-\delta_2(n)=\Delta(n)=O(\frac{1}{n})
$$

What does this mean? It means that $\delta_1(n)$ and $\delta_2(n)$ are at most one of them has an error term smaller than $o(\frac{1}{n})$! From your intuition, you might have guessed that the error of the trapezoidal approximation is smaller. Correct, the conclusion was proved.


Discusses the equivalence and error estimation in integrating piecewise continuous functions using rectangular and trapezoidal approximations.

Equivalence of Rectangular and Trapezoidal Approximations


<div class="mt-10">
  <div class="flex justify-center my-5">
    <div>
      <span>Do not stand by my grave, and weep.</span><br/>
      <span>I am not there, I do not sleep—</span><br/><br/>
      <span>I am the thousand winds that blow </span><br/>
      <span>I am the diamond glints in snow </span><br/>
      <span>I am the sunlight on ripened grain, </span><br/>
      <span>I am the gentle, autumn rain. </span><br/>
      <span>As you awake with morning's hush, </span><br/>
      <span>I am the swift, up-flinging rush </span><br/>
      <span>Of quiet birds in circling flight, </span><br/>
      <span>I am the day transcending night. </span><br/><br/>
      <span>Do not stand by my grave, and cry— </span><br/>
      <span>I am not there, I did not die.</span><br/>
    </div>
  </div>
  <div class="text-right">
  — Clare Harner, The Gypsy,<br/>
  December 1934
  </div>
</div>

---

<div class="mb-10">
  <div class="flex justify-center my-5">
    <div>
      <span>不要在我的墓前哭泣，</span><br/>
      <span>我不在那里，我没有离去。</span><br/><br/>
      <span>我是扬起的万里清风，</span><br/>
      <span>我是白雪晶莹的光芒，</span><br/>
      <span>我是阳光下成熟的麦穗，</span><br/>
      <span>我是温柔的秋雨纷纷扬扬，</span><br/>
      <span>我是夜幕中闪烁的星光，</span><br/>
      <span>当你在晨曦中醒来时，</span><br/>
      <span>我是盘旋的鸟飞舞直上。</span><br/><br/>
      <span>不要在我的墓前哭泣，</span><br/>
      <span>我不在那里，我没有离去。</span><br/>
    </div>
  </div>
  <div class="text-right">
  — 程虹教授 译
  </div>
</div>


Do Not Stand at My Grave and Weep

我没有离去


Node.js adopts an event-driven and non-blocking I/O model, allowing it to efficiently handle a large number of I/O requests and concurrent connections, which is crucial for a streaming media server. Meanwhile, FFmpeg, as a powerful video processing tool, provides rich video processing capabilities.

Combining Node.js's powerful extension capabilities, we can easily integrate FFmpeg to create a feature-complete video streaming media server, meeting various streaming media application requirements.

Now let's start from scratch and implement a simple video server: implementing the functionality to upload and play videos. In the process of learning, we will gradually understand how the video server works.

Before we begin, you need to:

- Understand the basic API of Node.js, such as the fs module, process module, etc.
- Understand the usage and common APIs of Express.js.
- Install and understand the basic usage of FFMPEG.

Now we want to implement a streaming media server. There are many streaming media protocols and formats on the market (RTP/RTCP/RTSP/RTMP/MMS/HLS, etc.), each with different applications. However, the vast majority of websites currently use HLS/M3U8 format streaming media, which is also supported by modern browsers.

Therefore, this article does not elaborate on these streaming media protocols but implements a simple HLS/M3U8 format streaming media server.

**The streaming media server implemented in this article is not technically difficult.**

## MP4 Video Slicing

Open some mainstream video websites, switch to the "Network" tab in Chrome Devtools, and then play the video. You can see that the browser is constantly downloading small files from a URL. These small files are video segments.

In general, web videos do not directly download the entire video file because a video file is usually several gigabytes, and downloading the entire file would be too large. Instead, the videos are split into many small segments, which are then continuously transferred to the browser. The browser then sequentially plays these segments.

For HLS/M3U8 type streaming media, the video playback address is the address for downloading the m3u8 file. The m3u8 file is a text-based list that stores the names, addresses, and order of video segments. Therefore, when playing this type of streaming media in the browser:

We can directly use ffmpeg to slice the video. Run the command in the terminal.

```bash
ffmpeg -i input_video.mp4 \
-c:v libx264 \
-c:a aac \
-hls_time 10 \
-hls_segment_type mpegts \
-hls_list_size 0 \
-f hls \
-max_muxing_queue_size 1024 \
output.m3u8
```

In this command:

- `-i input_video.mp4` specifies the input video file.
- `-c:v libx264 -c:a aac` specifies the video and audio codecs.
- `-hls_time 10` specifies the duration of each M3U8 segment, in seconds. Here, the duration of each segment is set to 10 seconds.
- `-hls_segment_type mpegts` specifies the type of M3U8 segment as MPEG-TS.
- `-hls_list_size 0` sets the maximum number of segments included in the M3U8 file. Here, it is set to 0, indicating no limit.
- `-f hls` specifies the output format as HLS.
- `-max_muxing_queue_size 1024` sets the maximum multiplexing queue size to ensure that the output does not exceed the specified size.
- The final output file is `output.m3u8`.

Of course, there are more advanced uses of the ffmpeg slicing command, such as limiting the size of all segments to not exceed `500kb`, etc.

![As shown in the image, executing the above command, we generated some video segments and an m3u8 video list.](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/20240323234019.webp)

We open the m3u8 list file, which shows the order and duration of each segment as follows.

```plaintext
#EXTM3U
#EXT-X-VERSION:3
#EXT-X-TARGETDURATION:11
#EXT-X-MEDIA-SEQUENCE:0
#EXTINF:11.386378,
output0.ts
#EXTINF:11.011000,
output1.ts
#EXTINF:9.050711,
output2.ts
#EXTINF:8.591911,
output3.ts
#EXTINF:6.506933,
output4.ts
#EXT-X-ENDLIST
```

## Frontend Playback

After the browser gets the m3u8 file, it sequentially traverses this list and then loads the segments listed in the list in order, i.e., output0.ts → output1.ts ... → output4.ts. Since it loads and plays the video while downloading, it immediately starts playing the first segment after loading the first segment and then simultaneously loads the second segment, and so on.

Next, let's create a new HTML file in the same directory and use `video.js` to play the m3u8 list we just generated.

```html
<html>
  <head>
    <title>Play the video</title>
    <link href="https://vjs.zencdn.net/8.10.0/video-js.css" rel="stylesheet" />
  </head>
  <body>
    <video class="video-js" controls preload="auto" width="640" height="264">
      <source src="./output.m3u8" type="application/x-mpegURL" />
    </video>
    <script src="https://vjs.zencdn.net/8.10.0/video.min.js"></script>
  </body>
</html>
```

![](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/20240323235457.webp)

As you can see, the browser successfully loads and plays the segments listed in the list.

So far, the process of slicing and playing streaming media is roughly understood. Therefore, it is not difficult for us to implement the basic functionality of a streaming media server.

## Design API

Before we start, we need to design the upload and play APIs.

- Video upload: `/upload`, POST request, accepts a file in the `multipart/form-data` form.
- Video playback: `/play/{videoId}/video.m3u8`, GET request, returns a text data of type m3u8. Where `videoId` is the unique identifier for each video.

## Implement Upload Functionality

Now we will implement the video upload functionality for the server. Video uploading involves three stages: receiving the uploaded file → video slicing → video persistent storage. After uploading, return a video playback address to the client for video playback.

Front-end video uploading is generally done through form files. After the server receives the file, it slices the file and stores it in the public area, then returns the generated m3u8 file address.

First, initialize the node project and install the following packages: `express` is the server framework for Node.js, `multer` is a form file processing middleware developed for Express, `nanoid` generates a unique identifier for the uploaded resource, `fluent-ffmpeg` is one of the ffmpeg extensions set for Node.js, `serve` allows you to set up a

server access environment in the local directory.

```bash
npm i multer express nanoid fluent-ffmpeg cors
npm i serve --save-dev
```

Add the following fields to `package.json`:

```json
{
  "main": "main.js",
  "type": "module"
}
```

Then create the `main.js` file and write the following code to create a server:

```js
import express from "express";
import fs from "fs";
import multer from "multer";
import { nanoid } from "nanoid";
import ffmpeg from "fluent-ffmpeg";
import path from "path";
import cors from "cors";

const server = express();
server.listen(3300);
console.log("Server started.");
server.use(cors()); // For easy debugging, allow cross-origin
```

According to the designed API, add a POST route to upload videos:

```js
const copeUpload = multer({
  dest: "uploads-temp/",
  filename: function (req, file, cb) {
    const uniqueSuffix = nanoid();
    cb(null, file.fieldname + "-" + uniqueSuffix);
  },
}).single("video");

server.post("/upload", copeUpload, function (req, res, next) {
  const tempFilePath = path.resolve(req.file.path);
  const videoId = nanoid();
  const storageDirectory = path.resolve("storage", videoId);
  fs.mkdirSync(storageDirectory);

  ffmpeg(tempFilePath)
    .videoCodec("libx264")
    .audioCodec("aac")
    .addOption("-hls_time", 10)
    .addOption("-hls_segment_type", "mpegts")
    .addOption("-hls_list_size", 0)
    .format("hls")
    .addOption("-max_muxing_queue_size", 1024)
    .output(`${storageDirectory}/video.m3u8`)
    .on("start", function () {
      console.log("Starting video slice process.");
    })
    .on("end", function () {
      fs.rmSync(tempFilePath); // Delete the uploaded temporary file
      console.log("OK");
    })
    .on("error", function (err) {
      fs.rmSync(tempFilePath); // Delete the uploaded temporary file
      console.error("Error:", err);
    })
    .run();

  res.json(`http://localhost:3300/play/${videoId}/video.m3u8`); // Return the playback address
});
```

## Implement Playback Functionality

Next is to set up the playback API for the server.

After uploading the video, the server will return a playback address to the client, which is the download address of the m3u8 file. So this part is very simple.

When the player requests the video address `play/abcde/video.m3u8` with the ID `abcde`, since the m3u8 specifies that the slice file and the m3u8 file are in the same directory, the address for requesting the slice is also

```
play/abcde/output01.ts
play/abcde/output02.ts
play/abcde/output03.ts
......
```

So what the server actually needs to do is to retrieve the files requested by `/play/${videoId}/*` from the `storage` directory and return them to the client.

```js
server.get("/play/:videoId/:filename", (req, res) => {
  const videoId = req.params["videoId"];
  const storageDirectory = path.resolve("storage", videoId);
  if (!existsSync(storageDirectory)) {
    res.status(404).send();
  }
  const filename = req.params["filename"];
  const filepath = path.join(storageDirectory, filename);
  if (!existsSync(filepath)) {
    res.status(404).send();
  }
  const data = fs.readFileSync(filepath);
  res.send(data);
});
```

## Functional Testing

In the above process, our video server is completed in less than 100 lines of code. Next, we will write code for the client to test the upload and playback functions of the server.

Requirements: After uploading the video, return the video playback address and play the specified video address.

Create an `index.html` in the same directory:

```html
<html>
  <head>
    <title>Video Server</title>
    <link href="https://vjs.zencdn.net/8.10.0/video-js.css" rel="stylesheet" />
  </head>
  <body>
    <div>
      <h2>Upload Video Files</h2>
      <form id="uploadForm" method="POST" enctype="multipart/form-data">
        <input type="file" name="video" accept="video/*" />
        <button type="submit">Upload</button>
      </form>
      <div id="response"></div>
      <script>
        const form = document.getElementById("uploadForm");
        form.addEventListener("submit", function (event) {
          event.preventDefault();
          const formData = new FormData(form);
          fetch("http://localhost:3300/upload", {
            method: "POST",
            body: formData,
          })
            .then((response) => response.text())
            .then((data) => {
              document.getElementById("response").innerText = "Upload successful, video address is: " + data;
            })
            .catch((error) => {
              console.error("Request error:", error);
            });
        });
      </script>
    </div>

    <hr />

    <div>
      <h2>Play Video</h2>
      <label for="m3u8-url">Enter the m3u8 address of the video:</label>
      <input type="text" id="m3u8-url" name="m3u8-url" placeholder="For example: https://example.com/video.m3u8" />
      <button onclick="playVideo()">Play</button>

      <video id="my-video" class="video-js" controls preload="auto" width="640" height="360" data-setup="{}">
        <source src="" type="application/x-mpegURL" />
      </video>
      <script src="https://vjs.zencdn.net/8.10.0/video.min.js"></script>
      <script>
        function playVideo() {
          var m3u8Url = document.getElementById("m3u8-url").value;
          var videoPlayer = videojs("my-video");
          videoPlayer.src({
            src: m3u8Url,
            type: "application/x-mpegURL",
          });
          videoPlayer.play();
        }
      </script>
    </div>
  </body>
</html>
```

Then start the server:

```bash
node main.js
```

The server is running at `http://localhost:3300`.

Then start the user interface:

```bash
npx serve
```

You can access it in the browser at `http://localhost:3000`.

Test results are as follows:

![Test result](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/vdsafvdag.gif)

## Conclusion

In this article, we implemented a simple streaming media server and successfully implemented two core functions: video upload and video playback.

Of course, this project is just a demo. It is far from enough for

a video server used in a production environment to have only these two functions. It also requires other more powerful functions such as video resource management, resource health monitoring, network fluctuation monitoring, encryption, and security, etc. I won't go into details about these. If you are interested, you can implement them yourself.

## Download Source Code

The source code repository for this project is [here on GitHub](https://github.com/PrinOrange/simple-node-media-server). It's released under the CC 1.0 open-source license.


Node.js utilizes an event-driven and non-blocking I/O model, which enables it to efficiently handle a large number of I/O requests and concurrent connections. This is crucial for a streaming media server. Meanwhile, ffmpeg provides powerful functionality for video processing. We can leverage Node.js's powerful extension capabilities to integrate ffmpeg and create a video streaming media server.

Let's Implement a Video Server with node.js and Ffmpeg


对于欧洲等基于字母文字的地区来讲，字体优化是一件很简单的事情，字体大小一般不超过 1MB。**但是对于亚洲尤其是东亚中国港澳台及日韩来讲，字体尺寸是一件非常令人头疼的问题。在前端项目中，字体文件可能动辄上几个单位的兆字节甚至更多。**

举个例子，以西班牙语的 `Cantina Fresca` 字体来讲，TTF 格式的字体大小仅为 300KB，并且打包成 WOFF2 格式后可以优化到 200KB 的大小，对于一个前端页面来讲，甚至还没有一张位图的体积大，加载字体的速度和时间均在可接受的范围内，并不是问题。

但是，对汉字不尽如此。汉字的基本单位 —— 偏旁部首不像字母文字一样可以随意拼接组合，而是必须以字为单位具体设计。根据中国的汉字分类法，一类汉字和二类汉字数量中常用的汉字数量大约在 4000 左右。再加上汉字的字体矢量图形也比字母文字复杂得多，所以一个包括常用汉字的字体文件大小至少在 2MB 以上，是字母字体的五到六倍。

如果字体文件太大，对于前端来讲则是很大的负担。过大的字体文件不仅会严重拖延加载速度，而且字体可能会导致页面排版布局的改变而触发浏览器重排（reflow）机制，降低渲染性能。

## 做成图片

在早期的网页，若想使用艺术字体，那么其中一种方法，就是用专业的设计软件如 PhotoShop 把字体用在图片素材上，或者生成背景透明的文字图片再用到网页上。这种办法一般只用于展示页、落地页。

![比如故宫博物院网站首页，把艺术字体用在落地页图片上](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/20240323103632.webp)

需要用什么字体，提前设计做成图片上，虽然有效，但如今看来这是一种笨办法。因为落地页是需求变化频率非常高的场合，如果需求变更，要求修改文字内容，亦或者是调整大小、颜色，那么还需要重头开始制作字体图片，从 UI 组到前端就必须重新干活，效率低下。

如果可以，我们换一种改进方法：制作字库。提前把所有的字符都抽出来做成矢量图片，需要的时候可以从字库中选取指定的图片即可。现在这种方法还常见于某些网站的落地页、展示页。

## 子集化

做成图片的方式效率太低，那么有没有办法改进办法呢？其中一个方法就是字体子集化（Subsetize）。字体文件是按照编码来给每个文字分别储存字形的。

根据中国大陆的文字分类工作方案，字表共收字 8105 个，其中一级字表（常用字集）3500 个，二级字表 3000 个。而一类字和二类字中有 4000 左右的常用汉字，就可以覆盖 90% 以上的文献资料。对于商业网站来讲，这些字量完全够用了。

而大多数字体也通常会给生僻字编码。像[康熙字典体](https://www.kangxizidian.com/index.php)具有很高的美学价值，完整版收录了 10 万左右的汉字，体积大小也达到了惊人的 70 MB，而其中 99% 以上都是生僻字。这些生僻字我们不需要，把它裁剪去就行了。在 Github 上有很多相关的工具，如 [FontSmaller](https://fontsmaller.github.io/)，这是一个在线子集化工具，还有[Fontmin](https://github.com/ecomfe/fontmin) 等。[我自己也收集总结了一些常用的汉字、符号等](https://gist.github.com/PrinOrange/20b6cf068e750b84b1236a52449f43f9)，可以用于字体子集化时挑选出指定的目标字体，用于参考。

被裁减后的康熙字典体体积可以缩减成 5MB。

对于静态生成式网页也可以更激进一点：由于生成的文字内容是相对固定的，那么每次生成网页时，可以先读取出网页上都有哪些字符，然后再从字体中挑选对应字符的字体，然后生成字体的子集。

例如 PHP 的 [php-font-lib](https://github.com/dompdf/php-font-lib) 库、Webpack 构建系统的插件[Fontmin-Webpack](https://github.com/patrickhulce/fontmin-webpack)。但是这样的方案适合静态生成式网页，对于动态网页则灵活性非常差，也不能很好处理用户输入的问题。

## Web Open Font Format

子集化的方案虽然能裁剪去很多不必要的字符，但是优化空间仍然有限。而对于 TTF，OTF 这类字体格式，那么能否寻找一种方式，能大限度地压缩字体文件大小？

后来，Mozilla 与 Type Supply、LettError 及其他组织于 2009 年协同开发了一种新的网页字体格式 WOFF（Web Open Font Format，Web 开放字体格式）。它使用了与 TrueType、OpenType、Open Font 所采用的 sfnt 结构类似的压缩算法。

WOFF 本质上是包含了基于 sfnt 的字体（如 TrueType、OpenType 或开放字体格式），且这些字体均经过 WOFF 的编码工具压缩，以便嵌入网页中。这个字体格式使用 zlib 压缩，文件大小一般比 TTF 小 40%。

后来对 WOFF 格式上再做一些改进，又开发了 WOFF2 格式。WOFF 2 标准在 WOFF1 的基础上，进一步优化了体积压缩，带宽需求更少，同时可以在移动设备上快速解压。

与 WOFF 1.0 中使用的 Flate 压缩相比，WOFF 2.0 是使用 Brotli 方法进行的压缩，压缩率更高，所以文件体积更小。

[在 Github 上也提供了字体转换为 WOFF 的相关工具](https://github.com/odemiral/WOFF2sfnt-sfnt2WOFF)。而且很多的专业字体转换网站如[Convert.io](https://cloudconvert.com/ttf-to-WOFF2)都提供字体转换功能

借助这种优化方案，我们就可以把子集化的字体在此基础上，继续优化到原大小的 40% 左右。例如我这个博客，正文使用的是思源屏显臻宋，由原来的 13.8MB 的 TTF 文件优化到现在的 2.5MB 左右。

但尽管如此，浏览器在加载超过 1MB 的字体时，性能非常差用 lighthouse 测评得分也很难超过 60。

## Font Spilt

根据统计，打开一个网站时，**用户能接受的加载时间为 7 秒左右。** 超过这个时间，用户就会丧失兴趣。以现代的网络条件下，不包括浏览器渲染过程，以带宽速度 0.5MBPS 下，想要在 7 秒内加载完一个网页，就意味着加载网站数据，包括静态资源、网页内容等大小一般在 2-3MB 左右。

但是中文字体再怎么优化也很难优化成 1MB 以下，中文字体大小在加载数据中仍然是个大头。这显然在用户体验上也不符合要求。

那么还有没有别的方案呢？或许，我们可以让字体按需加载。思路是：把一个完整的字体按照字符范围，拆分成十几个甚至几十上百个小字体。加载网页时，在网页上找出有哪些字符，然后再加载对应收录范围的小字体文件。

![如图，使用的是思源宋体，字体分包后分成了 60 左右的小字体，但是加载时只按需用了其中的 11 个。](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/20240323122837.webp)

这也是 [Google Fonts](https://fonts.google.com/) 的优化方案。

由此一来，就有望把字体加载大小降到 1MB 以下。这项方案需要 CSS 的支持。在 CSS 中有一个非常重要的规则：[unicode-range](https://developer.mozilla.org/en-US/docs/Web/CSS/@font-face/unicode-range)。

> The unicode-range CSS descriptor sets the specific range of characters to be used from a font defined using the @font-face at-rule and made available for use on the current page. If the page doesn't use any character in this range, the font is not downloaded; if it uses at least one, the whole font is downloaded.

简单来说，就是在使用 `@font-face` 定义字体时，它允许你指定 `unicode-range` 来标注应用字体的文字 Unicode 编码范围。

```css
@font-face {
  font-family: "source-serif";
  src: url("./source-serif.woff2") format("woff2");
  unicode-range: U+e240-e34f;
}
```

例如以上代码，这一行指定了应使用此字体的 Unicode 范围。在这个例子中，它只会对从 U+E240 到 U+E34F 的范围这一区间内的文字应用字体。假如文字不在 U+e240-e34f 这个编码范围内，那么就不会加载 source-serif 这个字体。

Google Font 就遵循了这个思路，通常针对中文字体把文字编码拆分成 100kb 左右的大量小字体文件，然后再生成对应的 CSS 规则代码，实现字体按需加载。

有了这个 CSS 特征，那么我们就可以很好地进一步优化了。首先第一步就是 Font-spilt，为字符范围编码，生成大量的、体积小的子字体，第二步是为编码范围和字体碎片生成指定的 CSS 规则文件。

这样就可以把每次加载字体的数据控制到 1MB，甚至 500KB 以下。就大大节省了加载数据量。

![优化前](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/20240323123739.webp)

![优化后](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/20240323123824.webp)

[在 Github 上已有对这类方案的成熟实现](https://github.com/Konghayao/cn-font-split)，并且提供了[在线的 Font-Spilt 工具](https://chinese-font.netlify.app/online-split/)，进行字体分包。

在此之前，开源界对中文字体的优化方案很少，感谢 [@江夏尧](https://github.com/KonghaYao) 的 [中文网字计划](https://chinese-font.netlify.app/)，提供了这个优秀的项目。

![](https://raw.githubusercontent.com/PrinOrange/pic-host/master/myblog/20240323124509.webp)

不尽如此，中文网字计划还托管了很好看的中文字体，可以开箱使用。[也欢迎各位为这个项目提供更好看的中文字体。](https://github.com/KonghaYao/chinese-free-web-font-storage)


对于欧洲等基于字母文字的地区，字体优化简单，大小通常不超过 1MB。但对于东亚国家，字体尺寸是一个头疼的问题，可能会达到数兆字节甚至更多。

汉字的前端字体体积优化方案


## Coding Methods

There are four ways to represent binary data in computers: sign-magnitude, one's complement, two's complement, and excess-n notation. These methods are used to represent and process signed numbers in computers, each solving the problems encountered when using binary to represent signed numbers.

1. **Sign-Magnitude**:

   Sign-magnitude was the earliest method used for representation. The highest bit represents the sign, while the remaining bits represent the magnitude. However, sign-magnitude has a problem: there are two representations for zero, positive zero and negative zero. Moreover, special processing is required to compare the results of addition and subtraction, which adds complexity to operations and comparisons.

   The main advantage of sign-magnitude is its simplicity, but the problem of representing zero makes it inconvenient for practical applications.

1. **One's Complement**:

   To address the issue of the sign bit in sign-magnitude representation, one's complement was introduced. In one's complement, the representation of negative numbers is obtained by taking the complement of each bit of the corresponding positive number. Therefore, addition and subtraction operations for two one's complement numbers can be unified as addition operations, with the sign bit participating in the operation, and the sign bit of the result being determined by the operation.

   One's complement solves the problem of the sign bit in sign-magnitude representation. However, when performing addition and subtraction operations, the issue of positive zero and negative zero still needs to be considered.

1. **Two's Complement**:

   To address the issue of positive and negative zero in one's complement representation, two's complement was introduced. In two's complement, all bits are complemented based on one's complement representation, and then $1$ is added.

   Since there is only one representation for zero in two's complement, the problem of positive and negative zero is avoided during operations.

1. **Excess-N Notation (Bias)**:
   Excess-N notation is commonly used to represent the exponent part of floating-point numbers. Excess-N notation is introduced to enable direct comparison of floating-point numbers with integers without the need for additional operations.

   Excess-N notation sets a bias value to represent unsigned integers as signed integers, enabling direct comparison with integers and simplifying the comparison process.

These different representation methods exist to more effectively represent and process signed numbers within a limited number of bits, while keeping operations and comparisons simple and efficient. The choice of representation method depends on specific application requirements and hardware design considerations.

Below, we will introduce their specific representation methods and calculation methods, assuming the binary number is $X_{(2)}$, and the machine's word length is $n$.

### Sign-Magnitude Representation

- If $X$ is a pure integer
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X_{(2)}$.
- If $X$ is a pure fraction
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X_{(2)}$.
- If $X$ is $0$, there are two representations: $+0$ and $-0$.
- Addition rule: First, determine the sign bit. If the signs are the same, add the absolute values, and the sign of the result remains unchanged; if the signs are different, perform subtraction, and the sign of the result is the same as the sign of the absolute value of the larger number.
- Subtraction rule: Subtracting two numbers represented by sign-magnitude, first negate the sign of the subtrahend, then perform sign-magnitude addition on the minuend and the negated subtrahend. (Subtract numbers with the same sign; add numbers with different signs)

### One's Complement Representation

- If $X$ is a pure integer
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, take the complement of each bit of $X_{(2)}$.
- If $X$ is a pure fraction
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, take the complement of each bit of $X_{(2)}$.
- If $X$ is $0$, there are two representations: $+0$ and $-0$.
- Addition and subtraction: $[X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]$. The sign bit is considered as part of the number, and any carry generated by the sign bit is discarded.

### Two's Complement Representation

- If $X$ is a pure integer
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X + 1_{(2)}$.
- If $X$ is a pure fraction
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X + 1_{(2)}$.
- If $X$ is $0$, there is only one representation, for example, when $n=8$, it is $00000000$.
- Addition and subtraction: $[X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]$. The sign bit is considered as part of the number, and any carry generated by the sign bit is discarded.

### Excess-N Notation (Bias)

A bias value of $(2^{n-1})_{(2)}$ is set.

- If $X$ is a pure integer, it is $X_{(2)} + (2^{n-1})_{(2)}$.
- If $X$ is a pure fraction, it is $X_{(2)} + 1_{(2)}$.
- If $X$ is $0$, there is only one representation, for example, when $n=8$, it is $10000000$.
- In fact, when the bias value is $(2^{n-1})_{(2)}$, **only the complement of the highest bit of the two's complement needs to be taken, to obtain the corresponding excess-n notation representation**. In other words, the highest bits of the two's complement and excess-n notation are each other's complements.
- Addition and subtraction operations are the same as two's complement.

### Fixed-Point Numbers

For fixed-point numbers, the decimal point is after the lowest bit. For fixed-point fractions, if there is a

sign bit, the decimal point is after the sign bit; if there is no sign bit, the decimal point is before the highest bit.

Among the above representation methods, for fixed-point integers,

- The representation range of sign-magnitude and two's complement is $[-(2^{n-1}-1),2^{n-1}-1]$.
- The representation range of two's complement and excess-n notation is $[-2^{n-1},2^{n-1}-1]$.
- They can both represent $2^{n}$ numbers.

For fixed-point fractions,

- The representation range of sign-magnitude and two's complement is $[-(1-2^{-(n-1)}),1-2^{-(n-1)}]$.
- The representation range of two's complement and excess-n notation is $[-(1-2^{-(n-1)}),1-2^{-(n-1)}]$.
- They can both represent $2^{n-1}$ numbers.

### Floating-Point Numbers

Floating-point numbers are represented by exponent $E$ and mantissa $F$, where the exponent is represented by $R$ bits of excess-n notation, and the mantissa is represented by $M$ bits of two's complement. The binary number $2^{E} * F$ can be expressed.

The range that can be expressed is $[-2^{(2^R-1)},(1-2^{-M+1})*(2^{(2^R-1)})]$.

## Error Checking Codes

### Parity Check

Parity check refers to adding $1$ to the check bit so that the number of $1$s in the binary number is odd. The same applies to even parity. However, odd parity can only detect coding errors in odd-numbered bits, and cannot detect coding errors in even-numbered bits. Even parity is the same.

### Hamming Code

Hamming codes insert $k$ check bits into $n$ bits of binary data. And satisfy $2^{k}-1≥ n+k$.

Taking the checked data $1100$ as an example, first determine the position of the check bits, and use the above formula to determine that $k=3$. Calculate the positions of the check bits using $2^{i},i =0,1,2,3$. These are the subscripts of the Hamming code check bits. Write down the binary representations of these subscripts.

| 1     | 2     | 4     |
| ----- | ----- | ----- |
| $001$ | $010$ | $100$ |

Then use $*$ to replace $0$ in the above table to use as a wildcard.

| 1     | 2     | 4     |
| ----- | ----- | ----- |
| $**1$ | $*1*$ | $1**$ |

Write down the binary sequence from $1$ to $n+k$, which is from $1$ to $4+3=7$.

| Decimal | Binary |
| ------- | ------ |
| $1$     | $001$  |
| $2$     | $010$  |
| $3$     | $011$  |
| $4$     | $100$  |
| $5$     | $101$  |
| $6$     | $110$  |
| $7$     | $111$  |

Then use the wildcard table to match the numbers.

| 1        | 2        | 4        |
| -------- | -------- | -------- |
| $**1$    | $*1*$    | $1**$    |
| $001(1)$ | $010(2)$ | $100(4)$ |
| $011(3)$ | $011(3)$ | $101(5)$ |
| $101(5)$ | $110(6)$ | $110(6)$ |
| $111(7)$ | $111(7)$ | $111(7)$ |

Then, the Hamming code table to be determined is obtained.

| $H_{7}$ | $H_{6}$ | $H_{5}$ | $H_{4}$ | $H_{3}$ | $H_{2}$ | $H_{1}$ |
| ------- | ------- | ------- | ------- | ------- | ------- | ------- |
| $1$     | $1$     | $0$     |         | $0$     |         |         |

Therefore, we can determine that

- $H_{1}$ is responsible for the parity check of bits $1,3,5,7$.
- $H_{2}$ is responsible for the parity check of bits $2,3,6,7$.
- $H_{4}$ is responsible for the parity check of bits $4,5,6,7$.

Now, let's determine the values of $H_{1},H_{2},H_{4}$. If it is even parity:

- $H_{3},H_{5},H_{7}$, the number of $1$s is odd, so $H_{1}=1$.
- $H_{3},H_{6},H_{7}$, the number of $1$s is even, so $H_{2}=0$.
- $H_{5},H_{6},H_{7}$, the number of $1$s is even, so $H_{4}=0$.

If it is odd parity, simply take the complement of the above check bits.

Finally, the complete Hamming code is obtained.

| $H_{7}$ | $H_{6}$ | $H_{5}$ | $H_{4}$ | $H_{3}$ | $H_{2}$ | $H_{1}$ |
| ------- | ------- | ------- | ------- | ------- | ------- | ------- |
| $1$     | $1$     | $0$     | $0$     | $0$     | $0$     | $1$     |

To check for errors, simply perform XOR operations on the check bits and the bits to be checked:

$$
G_{1}=H_{1} \oplus (H_{1} \oplus H_{3} \oplus H_{5} \oplus H_{7}) \\
G_{2}=H_{2} \oplus (H_{2} \oplus H_{3} \oplus H_{6} \oplus H_{7}) \\
G_{3}=H_{4} \oplus (H_{4} \oplus H_{5} \oplus H_{6} \oplus H_{7})
$$

If even parity is used, $G_{3}G_{2}G_{1}$ should be $000$, and for odd parity, it should be $111$. If it is not all $0$ or $1$, an error has occurred, and the data bit corresponding to the error should be flipped.


Concepts of Sign-Magnitude, One's Complement, Two's Complement, and Excess-n Notation, along with Parity Check and Hamming Code Error Detection Methods for Binary Data

Coding and Error Checking of Binary Data


## Functional Dependencies

In relational databases, functional dependencies describe the dependency relationships between attributes in a relational schema. If, given a relation $R$, the values of attribute set $X$ uniquely determine (through conditions or function arguments, for example) a value in attribute set $Y$, then we say that $Y$ is functionally dependent on $X$, typically denoted by the symbol $X \rightarrow Y$.

Specifically, if for every record in relation $R$, whenever two records have the same values for attribute set $X$, they must also have the same values for attribute set $Y$, then we say that $Y$ is functionally dependent on $X$.

For example, suppose we have a relation $R$ containing attribute set $\{ A,B,C \}$, where the values of attribute $A$ uniquely determine the values of attribute $B$, i.e., $A \rightarrow B$. Then, we say that attribute $B$ is functionally dependent on attribute $A$.

Functional dependency is an important concept in relational database design. It helps in understanding the relationships between data, normalizing database designs to reduce redundant data, while ensuring the consistency and integrity of data.

Functional dependencies can be classified into trivial functional dependencies and non-trivial functional dependencies.

If $X \rightarrow Y$ and $Y \subseteq X$, then $X \rightarrow Y$ is called a trivial functional dependency. Otherwise, it is a non-trivial functional dependency.

For functional dependencies, the dependency relationship between $X$ and $Y$ can also be further classified into partial functional dependency, full functional dependency, and transitive functional dependency.

- Partial Functional Dependency: Let $X,Y$ be two attribute sets of relation $R$. If $X→Y$ and $X' \subsetneq X$, where there exists $X'$ such that $X'→Y$, then $Y$ is said to be partially functionally dependent on $X$, denoted as $X \overset{P}{\rightarrow} Y$. In other words, partial functional dependency means that some attributes can be removed without affecting the dependency.

> For example: In a student basic information table $R$ (student ID, passport number, name), of course, the student ID attribute values are unique. In relation $R$, (student ID, passport number) → (name), (student ID) → (name), (passport number) → (name); therefore, the name is partially functionally dependent on (student ID, passport number).

- Full Functional Dependency: Let $X,Y$ be two attribute sets of relation $R$. If $X→Y$, $X' \subsetneq X$, and for all $X'$, $X'→Y$, then $Y$ is said to be fully functionally dependent on $X$, denoted as $X \overset{F}{\rightarrow} Y$. In other words, for full functional dependency, no extra attributes can be deleted, otherwise, the property of dependency will not be maintained.

> Example: In a student basic information table $R$ (student ID, class, name), assuming different classes can have the same student ID, and student IDs within a class cannot be the same. In relation $R$, (student ID, class) → (name), but (student ID) → (name) does not hold, and (class) → (name) does not hold either. Therefore, the name is fully functionally dependent on (student ID, class).

- Transitive Functional Dependency: Let $X,Y,Z$ be three attribute sets of relation $R$, where $X→Y (Y \cancel{\rightarrow} X)$, and for all $Y$, $Y→Z$. Then $Z$ is said to be transitively functionally dependent on $X$. This means that $Z$ indirectly depends on $X$.

> Example: In relation $R$ (student ID, dormitory, fee), (student ID) → (dormitory), dormitory ≠ student ID, (dormitory) → (fee), fee ≠ dormitory. Thus, it meets the requirements of transitive functional dependency.

## Multi-Valued Dependencies

The previous section introduced functional dependencies, which are actually a special case of multi-valued dependencies. Multi-valued dependencies extend the concept of functional dependencies.

Let $R(U)$ be a relational schema over the attribute set $U$, and let $X$, $Y$, and $Z$ be subsets of $U$ such that $Z = U - X - Y$. A multi-valued dependency $X \twoheadrightarrow Y$ holds if and only if for any relation $r$ in $R$, each value on $(X, Z)$ corresponds to a set of values on $Y$, and this set of values depends only on the values of $X$ and is independent of the values of $Z$.

Consider a relational schema $R$ with the attribute set $\{Student, Course, Textbook\}$, representing students' course enrollments and the textbooks they use. If a student uses multiple textbooks for a single course, and the combination of student and course uniquely determines the textbooks used, while the combination of student and course is independent, then we have a multi-valued dependency.

Suppose we have the following relation instance:

| Student | Course  | Textbook       |
| ------- | ------- | -------------- |
| Alice   | Math    | Calculus       |
| Alice   | Math    | Linear Algebra |
| Alice   | Physics | Mechanics      |
| Bob     | Math    | Calculus       |

In this example, the choice of textbook depends on the combination of student and course. For instance, Alice uses both Calculus and Linear Algebra textbooks for her Math course, while she uses Mechanics for her Physics course. However, whether Linear Algebra and Calculus are chosen depends solely on whether the course is Math.
This scenario demonstrates a multi-valued dependency, where the combination of student and course uniquely determines the set of textbooks used, while the relationship between student and course is independent, yet textbooks are not independent of courses as one course can have multiple textbooks.

Therefore, in this scenario, there exists a multi-valued dependency relationship $Course \twoheadrightarrow Textbook$.

## Keys

- Let $K$ be an attribute or a combination of attributes in $R<U, F>$, and $K \overset{F}{\rightarrow} U$, then $K$ is a candidate key for $R$.
- If there are multiple candidate keys, one of them can be designated as the primary key.
- Any attribute set that contains a candidate key is called a prime attribute. Otherwise, it is a non-prime attribute.
- If the entire attribute set constitutes the candidate key, then this attribute set is called a superkey.
- Both primary keys and candidate keys are commonly referred to as keys.

## Database Normalization

### 1NF

$1NF$ (First Normal Form) is one of the fundamental normal forms in relational databases. It requires that each attribute in a relation schema is atomic, meaning it cannot be further divided. In other words, each attribute in the relation schema should be single-valued, rather than containing multiple values or complex data types.

Specifically, $1NF$ requires that each cell in the relation contains only one value, rather than multiple values or complex data types. This helps ensure the atomicity of data, simplifying data processing and querying.

For example, consider a student table containing names and phone numbers. If phone numbers are stored as a comma-separated list of multiple numbers, then this table does not conform to $1NF$. To adhere to $1NF$, phone numbers should be split into separate attributes, with each attribute containing only one phone number.

### 2NF

$2NF$ (Second Normal Form) is another normal form in relational databases, built upon the foundation of the first normal form ($1NF$). $2NF$ requires that each non-prime attribute in a relation schema is fully functionally dependent on the candidate key, rather than partially dependent on the candidate key.

Specifically, if a relation schema has multiple attributes forming the candidate key, then each non-prime attribute should depend on all combinations of these attributes, rather than just depending on some of them.

For example, consider a relation schema containing the following attributes: StudentID, CourseID, CourseName, StudentName, and Grade. In this schema, (StudentID, CourseID) forms the candidate key, representing the enrollment of students in courses.

| StudentID | CourseID | CourseName | StudentName | Grade |
| --------- | -------- | ---------- | ----------- | ----- |
| 101       | 001      | Math       | Alice       | A     |
| 101       | 002      | Physics    | Alice       | B     |
| 102       | 001      | Math       | Bob         | A     |
| 102       | 003      | Chemistry  | Bob         | C     |

In this example, the StudentName attribute is a non-prime attribute and is partially dependent on the candidate key (StudentID), rather than fully dependent on all attributes of the candidate key (StudentID, CourseID). For instance, the name of student Alice is only associated with Student ID 101, irrespective of the course enrollment.

Therefore, this relation schema does not satisfy the second normal form ($2NF$). To adhere to $2NF$, we should remove the StudentName attribute from this relation schema and place it in a separate table, where the candidate key is $StudentID$. This way, the student name becomes fully dependent on the candidate key, rather than partially dependent on it.

### 3NF

Given a relation schema $R<U,F> \in 1NF$ and no set of attributes $X$, attribute group $Y$, and non-candidate attribute $Z$ such that $X \rightarrow Y, Y \rightarrow Z, Y \cancel{\rightarrow} X$, it belongs to $3NF$. In other words, if a relation is in $2NF$ and each non-candidate attribute does not transitively depend on the candidate key, then it is in $3NF$.

Let's continue with the example of student course enrollment mentioned earlier and attempt to conform to the third normal form ($3NF$).

In this example, we have already removed the student name from the main table and placed it in a separate table as follows:

**Student Table**:

| StudentID | StudentName |
| --------- | ----------- |
| 101       | Alice       |
| 102       | Bob         |

**Enrollment Table**:

| StudentID | CourseID | Grade |
| --------- | -------- | ----- |
| 101       | 001      | A     |
| 101       | 002      | B     |
| 102       | 001      | A     |
| 102       | 003      | C     |

Now, let's see if it conforms to $3NF$. In this relation schema, we have a transitive dependency: Student ID (StudentID) determines Student Name (StudentName), while Course ID (CourseID) determines Student ID (StudentID). Hence, there exists a transitive functional dependency: $CourseID \rightarrow StudentName$.

To conform to $3NF$, we need to eliminate this transitive dependency. One way to do this is by creating a new table that maps $CourseID$ and $StudentID$ to $StudentName$ to eliminate this transitive dependency. This way, we can ensure that each non-prime attribute is fully dependent on the primary key.

**Student Enrollment Relation Table**:

| StudentID | CourseID | Grade |
| --------- | -------- | ----- |
| 101       | 001      | A     |
| 101       | 002      | B     |
| 102       | 001      | A     |
| 102       | 003      | C     |

**Student Table**:

| StudentID | StudentName |
| --------- | ----------- |
| 101       | Alice       |
| 102       | Bob         |

**Course Table**:

| CourseID | CourseName  |
| -------- | ----------- |
| 001      | Mathematics |
| 002      | Physics     |
| 003      | Chemistry   |

Now, each table conforms to the third normal form ($3NF$). The student table and the course table are associated with the student enrollment relation table without any transitive dependency.

### BCNF

$BCNF$ (Boyce-Codd Normal Form) is a more stringent form of normalization in relational databases, resulting from normalizing relation schemas further from the third normal form ($3NF$). $BCNF$ requires that every non-trivial functional dependency (non-trivial $X \rightarrow Y$, where $Y$ is not a superset of $X$) is determined by the keys of the relation.

In other words, if $R$ is a relation schema and $X \rightarrow Y$ is a non-trivial functional dependency of $R$, and $X$ does not contain any candidate keys, then $R$ does not conform to $BCNF$, meaning every determinant must include a key.

For example, consider a scheduling table now, recording student ID, course ID, and teacher ID. A teacher teaches only one course, and a course can be taught by multiple teachers, and each student selects a specific course, which corresponds to a fixed teacher. Assuming the candidate key is student ID, course ID. We can list the following functional relationships:

- $(StudentID,CourseID) \rightarrow TeacherID$
- $(StudentID,TeacherID) \rightarrow CourseID$
- $TeacherID \rightarrow CourseID$

This relation does not conform to $BCNF$ because we find that in the third functional dependency, $TeacherID$ does not contain any keys. While the first and second have keys.

### 4NF

$4NF$ is a form of database normalization that further emphasizes the elimination of multi-valued dependencies on top of $BCNF$. A relation schema satisfies $4NF$ if, in addition to satisfying the requirements of $BCNF$, it also has no non-trivial multi-valued dependencies. Non-trivial multi-valued dependencies refer to those where neither the left side nor the right side is a superkey of the relation.

Let's consider an example that complies with $BCNF$ but not with $4NF$.

Suppose we have a relation schema $R$ containing attributes: Student, Course, Grade, and Teacher. And there exist the following functional dependencies:

1. $(Student, Course) \rightarrow Grade$
2. $Course \rightarrow Teacher$
3. $Student \twoheadrightarrow Teacher$

Assume that the candidate key for the relation schema is $Student, Course$.

This schema conforms to $BCNF$ because every functional dependency is determined by the candidate key.

However, it does not conform to $4NF$ due to the presence of the third multi-valued dependency. This is because each student may attend multiple courses, and each course may have different teachers.

Therefore, although this relation schema satisfies $BCNF$, it does not satisfy $4NF$.

### Relationship

Understanding from $1NF$ to $4NF$ is progressive. The relationship between them is as follows:

- $1NF$ eliminates partial functional dependencies of non-prime attributes on the candidate key to achieve $2NF$.
- $2NF$ eliminates transitive functional dependencies of non-prime attributes on the candidate key to achieve $3NF$.
- $3NF$ eliminates partial and transitive functional dependencies of prime attributes on the candidate key to achieve $BCNF$.
- $BCNF$ eliminates non-trivial and functional dependencies of multi-valued dependencies to achieve $4NF$.


Introduces functional dependencies, and the database paradigms 1NF, 2NF, 3NF, BCNF, and 4NF. and use examples to explain their concepts and connections.

Data Table Relation's Normalization

This article mainly introduces the content and connection between the four concepts of Taylor's formula, Taylor's theorem, Taylor series and Taylor's expansion.

Taylor Formula, Taylor Theorem, Taylor Series, Taylor Expansion


## Theorem

Let $n, p \in \mathbb{Z}_{>0}$ be (strictly) positive integers.

Then:

$$
\sum_{k = 1}^n k^p = \frac{1}{p + 1} \sum_{i = 0}^p (-1)^i \binom{p + 1}{i} B_i n^{p + 1 - i} \\
= \frac{n^{p + 1}}{p + 1} - \frac{B_1 \cdot n^p}{1!} + \frac{B_2 \cdot p \cdot n^{p - 1}}{2!} + \frac{B_4 \cdot p \cdot (p - 1) \cdot (p - 2) \cdot n^{p - 3}}{4!} + \cdots
$$

where:

- $B_i$ denotes the $i$th Bernoulli number.

## Proof

Let $x \ge 0$.

$$
\sum_{k = 0}^{n - 1} e^{k x} = \sum_{k = 0}^{n - 1} \sum_{p = 0}^\infty \frac{(k x)^p}{p!}
$$

$$
= \sum_{p = 0}^\infty \left(\sum_{k = 0}^{n - 1} k^p\right) \frac{x^p}{p!}
$$

We also have:

$$
\sum_{k = 0}^{n - 1} e^{k x} = \frac{1 - e^{n x}}{1 - e^x}
$$

Sum of Geometric Sequence

$$
= \frac{e^{n x} - 1}{x} \frac{x}{e^x - 1}
$$

multiplying numerator and denominator by $x$

$$
= \frac{1}{x} \left(\sum_{p = 0}^\infty \frac{(n x)^p}{p!} - 1\right) \sum_{p = 0}^\infty \frac{B_p x^p}{p!}
$$

Definition of _Bernoulli Numbers_ and _Power Series Expansion_ for Exponential Function

$$
= \frac{1}{x} \left(\sum_{p = 1}^\infty \frac{(n x)^p}{p!}\right) \sum_{p = 0}^\infty \frac{B_p x^p}{p!}
$$

Factorial of $0$ and Zeroth Power

$$
= \frac{1}{x} \left(\sum_{p = 0}^\infty \frac{(n x)^{p + 1}}{(p + 1)!}\right) \sum_{p = 0}^\infty \frac{B_p x^p}{p!}
$$

Translation of Index Variable of Summation

$$
= \sum_{p = 0}^\infty \frac{n^{p + 1} x^p}{(p + 1)!} \sum_{p = 0}^\infty \frac{B_p x^p}{p!}
$$

Power of Product

$$
= \sum_{p = 0}^\infty \sum_{i = 0}^p \frac{n^{p + 1 - i} x^{p - i}}{(p + 1 - i)! i!} B_i n^{p + 1 - i} x^p
$$

Definition of Cauchy Product

$$
= \sum_{p = 0}^\infty \left(\frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i}\right) \frac{x^p}{p!}
$$

multiplying by $1$ and Product of Powers

$$
\sum_{k = 0}^{n - 1} k^p = \frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i}
$$

Definition of Binomial Coefficient

$$
\implies \sum_{k = 1}^n k^p = \frac{1}{p + 1} \sum_{i = 0}^p (-1)^i \binom{p + 1}{i} B_i n^{p + 1 - i}
$$

Equating coefficients:

$$
\sum_{k = 0}^{n - 1} k^p = \frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i}
$$

$$
\implies \sum_{k = 0}^{n - 1} k^p + n^p = \frac{1}{p + 1} \sum_{i = 0}^p \binom{p + 1}{i} B_i n^{p + 1 - i} + \left(\frac{1}{p + 1} \binom{p + 1}{1} n^p\right)
$$

adding $n^{p}$ to both sides and Binomial Coefficient with One

$$
\implies \sum_{k = 1}^n k^p = \frac{1}{p + 1} \sum_{i = 0}^p (-1)^i \binom{p + 1}{i} B_i n^{p + 1 - i}
$$

as $B_{1}=-\frac{1}{2}$ and Odd Bernoulli Numbers Vanish

**Q.E.D.**


Faulhaber's Formula, which provides a method to compute the sum of the p-th powers of the first n positive integers.

Proof of Faulhaber's Formula


## Catalan Numbers

Catalan numbers $H_n$ can be applied to the following problems:

1. There are $2n$ people queuing up to enter a theater. The entrance fee is 5 yuan. Among them, only $n$ people have a 5 yuan bill, while the other $n$ people only have a 10 yuan bill. The theater has no other bills. How many ways are there to ensure that whenever a person with a 10 yuan bill buys a ticket, the ticket office has a 5 yuan bill for change?
2. There is a grid of size $n\times n$ with the lower left corner at $(0, 0)$ and the upper right corner at $(n, n)$. Starting from the lower left corner, you can only move one unit to the right or up each time, without going above the diagonal line $y=x$. How many possible paths are there to reach the upper right corner without crossing the line $y=x$?
3. Choose $2n$ points on a circle and connect these points pairwise to obtain $n$ line segments. How many ways are there to ensure that the $n$ line segments obtained do not intersect?
4. Without intersecting diagonals, how many ways are there to divide a convex polygon area into triangular regions?
5. If the stack (infinite) has a push sequence of $1,2,3, \cdots ,n$, how many different pop sequences are there?
6. How many different binary trees can be constructed with $n$ nodes?
7. Given $2n$ numbers consisting of $n$ $+1$s and $n$ $-1$s, denoted as $a_1,a_2, \cdots ,a_{2n}$, such that the partial sum satisfies $a_1+a_2+ \cdots +a_k \geq 0~(k=1,2,3, \cdots ,2n)$, how many sequences satisfy this condition?

The corresponding sequence is:

| $H_0$ | $H_1$ | $H_2$ | $H_3$ | $H_4$ | $H_5$ | $H_6$ | ... |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :-: |
|   1   |   1   |   2   |   5   |  14   |  42   |  132  | ... |

## Recurrence Relation

The solution to this recurrence relation is:

$$
H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})
$$

Common formulas for Catalan numbers are:

$$
H_n = \begin{cases}
    \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\
    1 & n = 0, 1
\end{cases}
$$

$$
H_n = \frac{H_{n-1} (4n-2)}{n+1}
$$

$$
H_n = \binom{2n}{n} - \binom{2n}{n-1}
$$

> A common application: for a stack, the push sequence is $1,2, \ldots ,n$, find the total number of possible pop sequences.

```cpp
#include <iostream>
using namespace std;
int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // Here, formula 2 is used
  cout << f[n] << endl;
  return 0;
}
```

## Closed Form

The recurrence relation of Catalan numbers is

$$
H_n=\sum_{i=0}^{n-1}H_{i}H_{n-i-1} \quad (n\ge 2)
$$

where $H_0=1$ and $H_1=1$. Let its ordinary generating function be $H(x)$.

We find that the recurrence relation of Catalan numbers is similar to the form of convolution. Therefore, we construct an equation about $H(x)$ using convolution:

$$
\begin{aligned}
H(x)&=\sum_{n\ge 0}H_nx^n\\
&=1+\sum_{n\ge 1}\sum_{i=0}^{n-1}H_ix^iH_{n-i-1}x^{n-i-1}x\\
&=1+x\sum_{i\ge 0}H_{i}x^i\sum_{n\ge 0}H_{n}x^{n}\\
&=1+xH^2(x)
\end{aligned}
$$

Solving this equation, we get

$$
H(x)=\frac{1\pm \sqrt{1-4x}}{2x}
$$

Now, we have a question: which root should we take? Rationalizing the numerator, we get

$$
H(x)=\frac{2}{1\mp \sqrt{1-4x}}
$$

Substituting $x=0$, we obtain the constant term of $H(x)$, which is $H_0$. When $H(x)=\dfrac{2}{1+\sqrt{1-4x}}$, we have $H(0)=1$, satisfying the requirement. The other root leads to the denominator being $0$ (non-convergence), so it is discarded.

Therefore, we obtain the closed form of the generating function of Catalan numbers:

$$
H(x)=\frac{1- \sqrt{1-4x}}{2x}
$$

Next, we need to expand it. But note that its denominator is not in the form of a polynomial like the Fibonacci sequence, so it is not convenient to use the expansion form of geometric sequences. Here we need to use Newton's binomial theorem. Let's first expand $\sqrt{1-4x}$:

$$
\begin{aligned}
(1-4x)^{\frac{1}{2}}
&=\sum_{n\ge 0}\binom{\frac{1}{2}}{n}(-4x)^n\\
&=1+\sum_{n\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{n}}}{n!}(-4x)^n
\end{aligned} \tag{1}
$$

Note that

$$
\begin{aligned}
\left(\frac{1}{2}\right)^{\underline{n}}
&=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\\
&=\frac{(-1)^{n-1}(2n-3

)!!}{2^n}\\
&=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\
&=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!}
\end{aligned}
$$

Here, we use the simplification technique of double factorials. Then, substitute into $(1)$, we get

$$
\begin{aligned}
(1-4x)^{\frac{1}{2}}
&=1+\sum_{n\ge 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\
&=1-\sum_{n\ge 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\
&=1-\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n
\end{aligned}
$$

Substitute back into the original expression, we get

$$
\begin{aligned}
H(x)&=\frac{1- \sqrt{1-4x}}{2x}\\
&=\frac{1}{2x}\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n\\
&=\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}x^{n-1}\\
&=\sum_{n\ge 0}\binom{2n+1}{n+1}\frac{1}{(2n+1)}x^{n}\\
&=\sum_{n\ge 0}\binom{2n}{n}\frac{1}{n+1}x^{n}\\
\end{aligned}
$$

Thus, we obtain the general formula for Catalan numbers.

## Path Counting Problem

Non-decreasing paths refer to paths that can only move upwards or to the right.

1. The number of non-decreasing paths from $(0,0)$ to $(m,n)$ is equal to the number of permutations of $m$ $x$ and $n$ $y$, i.e., $\dbinom{n + m}{m}$.

2. The number of non-decreasing paths from $(0,0)$ to $(n,n)$ that do not touch the line $y=x$ except at endpoints:

   First, consider the paths below the line $y=x$, which all start from $(0, 0)$, pass through $(1, 0)$ and $(n, n-1)$, and reach $(n,n)$. This can be seen as the number of non-decreasing paths from $(1,0)$ to $(n,n-1)$ without touching $y=x$.

   All non-decreasing paths total $\dbinom{2n-2}{n-1}$. For any path that touches $y=x$, we can symmetrically transform the part from the point where it leaves this line to $(1,0)$, obtaining a non-decreasing path from $(0,1)$ to $(n,n-1)$. The reverse is also true. Hence, the number of non-decreasing paths below $y=x$ is $\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}$. Due to symmetry, the answer is $2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}$.

3. The number of non-decreasing paths from $(0,0)$ to $(n,n)$ that do not cross the line $y=x$: Similarly, we can obtain $\dfrac{2}{n+1}\dbinom{2n}{n}$ using similar methods.

> NOTE: This article is rewritten by [OI WIKI](https://oi-wiki.org/math/combinatorics/catalan/).


The article discusses Catalan numbers, a sequence used in combinatorial problems. It covers their recurrence relation, closed form, and applications in path counting. It provides insights into problem-solving using Catalan numbers.

NOTE & BLOG

ALL POSTS

System Reliability Model

Equivalence of Rectangular and Trapezoidal Approximations

我没有离去

Let's Implement a Video Server with node.js and Ffmpeg

汉字的前端字体体积优化方案

Coding and Error Checking of Binary Data

Data Table Relation's Normalization

Taylor Formula, Taylor Theorem, Taylor Series, Taylor Expansion

Proof of Faulhaber's Formula

The Catalan Series

NOTE & BLOG

ALL POSTS

TAG FILTER

System Reliability Model

Equivalence of Rectangular and Trapezoidal Approximations

我没有离去

Let's Implement a Video Server with node.js and Ffmpeg

汉字的前端字体体积优化方案

Coding and Error Checking of Binary Data

Data Table Relation's Normalization

Taylor Formula, Taylor Theorem, Taylor Series, Taylor Expansion

Proof of Faulhaber's Formula

The Catalan Series