LLM 算法岗 | 八股问答（）· 强化学习与 RLHF战

. GIF文件结构相比于 WAV 文件的简单粗暴GIF 的结构要精密得多因为它天生是为了网络传输而设计的包含了压缩机制。当我们用二进制视角观察 GIF 时它是由一个个 数据块Block 组成的数据块 (Block Name) 中文名称 字节数 (Bytes) 作用与核心逻辑Header 头标识 6 一般为 GIF89a当然也有GIF87a,用于声明这是一个GIF文件采用xx标准。Logical Screen Descriptor 逻辑屏幕描述符 7 画布设定定义图像总宽高、背景色索引及是否使用全局调色板。Global Color Table 全局颜色表 3 × N 颜料盘存储 RGB 颜色如 00 FF 00N 为颜色数最大256。 默认使用RGB颜色时每个颜色均采用3个字节存储Application Extension 应用程序扩展 19 (通常) 最常用的是 Netscape 扩展用于“循环播放次数”。Graphic Control Extension 图形控制扩展 8 播放控制定义每一帧的延迟时间动画快慢和透明色。Image Descriptor 图像描述符 10 帧属性定义当前这一帧在画布上的位置x, y和尺寸。Image Data 图像数据 可变 用处如其名Trailer 结束标识 1 终点固定为 0x3B (分号)标志文件彻底结束。其中最重要的就是图像数据了其他的块用于规定这些图像数据应当如何呈现到我们眼中或是告知文件的开始结束因此对于我们来说其他块基本上都有固定模板只有图像数据需要我们自己定义。2.LZW-GIF强制使用的图像压缩算法搞定了GIF的文件结构接下来就需要我们解决另一个拦路虎LZW——一个经典的无损图像压缩算法为了解决他我们可以从他的原理入手。LZW通过为复杂数据构建简单索引来减少存储的数据量这一点是朴素的哈希算法当然这一算法的发明者通过一套特殊的规则使得其他人可以直接通过索引数据反推出复杂数据而在GIF中则是GIF发明公司将他所规定的规则写好编写GIF的人根据这一套规则构建数据然后其他人直接使用套用了这一套规则的解码器解码便能将数据还原成原来的样子。GIF的解码器又是如何读取数据的呢解码器初始时一次性读取9位数据然后从字典中添加这一对应关系根据GIF规范一旦字典里的条目达到 512 个解码器就会自动将读取位宽从 9 位增加到 10 位。如果我们直接存放数据那么结果就是数据读取错位解码出来的内容就会与我们想象中的不一样如果我们想要让他的数据读取正常通常做法就是我们构建一个同步状态机即模拟GIF解码器读取数据的过程写入数据构建一个字典以相同的标准增加写入位宽从而让解码器读取时能正确读取。但是这一过程看着就十分繁琐能不能用一个简单的方法来让解码器正常读取数据呢3.解决方案GIF 协议中有一个特殊的指令叫 Clear Code清除代码值为256。它的作用是告诉解码器“嘿把之前的字典都忘了吧我们重新开始。”利用这一点我们可以在代码中采用了一种偷鸡的策略我们不尝试去寻找复杂的重复模式。我们每写入一小段像素例如 125 个就立刻发送一个 Clear Code。这强制让 LZW 字典始终处于“初始状态”。在初始状态下LZW 的编码就等同于直接输出像素的颜色索引值。现在让我们来实现他4. 构建3d立方体在上一篇关于 3D 本质的文章中我们推导出了两个核心公式。在这个程序中我们将直接把它们转化为 C 代码。旋转公式为了让立方体动起来我们需要每一帧都改变顶点的坐标。这里使用旋转矩阵的简化版Point3D rotate(Point3D p, float angle) {// 绕 Y 轴旋转float nx p.x * cos(angle) - p.z * sin(angle);float nz p.x * sin(angle) p.z * cos(angle);// 绕 X 轴微调旋转让旋转看起来更立体float ny p.y * cos(angle * 0.8f) - nz * sin(angle * 0.8f);nz p.y * sin(angle * 0.8f) nz * cos(angle * 0.8f);return {nx, ny, nz};}投影公式透视如何把 3D 坐标变成屏幕上的像素点记得那个核心法则吗“近大远小本质就是除以 Z”。pair project(Point3D p, int W, int H) {float fov 160.0f; // 视野系数float viewer_dist 4.0f; // 眼睛离物体的距离// 核心逻辑除以 (z dist)float factor fov / (viewer_dist p.z);return { (int)(p.x * factor W / 2), (int)(p.y * factor H / 2) };}有了这两个函数我们就能在内存里的一个二维数组vector pixels上画线了。手写 GIF 编码器我们实现了一个极简的编码器struct GifBitStream。它的工作是把像素点的颜色索引0或1打包成变长的二进制码流。// GIF 的数据存储不仅是字节还需要处理“位操作”// 比如写入一个 9-bit 的代码可能跨越两个字节struct GifBitStream {vector byteData;u32 bitBuffer 0;int bitCount 0;void writeCode(u32 code, int size) {// 将数据移位并存入缓冲区...// 凑够8位就写入 byteData}// ...};特别说明绕过LZW的问题生成的GIF没有压缩体积较为大4. 完整代码下面是完整的 C 代码计算旋转 3D 点 - 投影成 2D 点。绘图在内存的黑板上画线Bresenham 直线算法。编码将内存的黑板按照 GIF 协议压缩并写入文件。(代码较长建议直接复制编译运行感受生成的快感)#includeusing namespace std;#define u8 uint8_t#define u16 uint16_t#define u32 uint32_tstruct Point3D {float x, y, z;};struct Edge {int u, v;};Point3D rotate(Point3D p, float angle) {float nx p.x * cos(angle) - p.z * sin(angle);float nz p.x * sin(angle) p.z * cos(angle);float ny p.y * cos(angle * 0.8f) - nz * sin(angle * 0.8f);nz p.y * sin(angle * 0.8f) nz * cos(angle * 0.8f);return {nx, ny, nz};}pair project(Point3D p, int W, int H) {float fov 160.0f;float viewer_dist 4.0f;float factor fov / (viewer_dist p.z);return { (int)(p.x * factor W / 2), (int)(p.y * factor H / 2) };}inline void drawLine(vector buffer, int W, int H, int x0, int y0, int x1, int y1) {int dx abs(x1 - x0), sx x0 x1 ? 1 : -1;int dy -abs(y1 - y0), sy y0 y1 ? 1 : -1;int err dx dy;while (true) {if (x0 0 x0 W y0 0 y0 H) buffer[y0 * W x0] 1;if (x0 x1 y0 y1) break;int e2 2 * err;if (e2 dy) { err dy; x0 sx; }if (e2 dx) { err dx; y0 sy; }}}// --- GIF 二进制协议部分 ---struct GifBitStream {vector byteData;u32 bitBuffer 0;int bitCount 0;// 写入指定位宽的代码inline void writeCode(u32 code, int size) {bitBuffer | (code bitCount);bitCount size;while (bitCount 8) {byteData.push_back(bitBuffer 0xFF);bitBuffer 8;bitCount - 8;}}inline void flush(ofstream f) {if (bitCount 0) byteData.push_back(bitBuffer 0xFF);// GIF 规定数据必须切成每块最大 255 字节的小块for (size_t i 0; i byteData.size(); i 255) {u8 blockSize (u8)min((size_t)255, byteData.size() - i);f.put(blockSize);f.write((char*)byteData[i], blockSize);}f.put(0); // 块结束}};inline void writeWord(ofstream f, u16 v) {f.put(v 0xFF);f.put((v 8) 0xFF);}inline void writeGifFrame(ofstream f, const vector pixels, int W, int H) {// 1. 图形控制扩展 (帧间隔)f.put(0x21);f.put(0xF9);f.put(0x04);f.put(0x09); // 属性还原背景不使用透明writeWord(f, 4); // 延迟 40ms (1/25 FPS)f.put(0);f.put(0);// 2. 图像描述符f.put(0x2C);// 偏移writeWord(f, 0);writeWord(f, 0);// 宽高writeWord(f, W);writeWord(f, H);f.put(0x00);// 3. 数据f.put(0x08); // 8位色GifBitStream stream;const int ClearCode 256; //清空指令const int EOICode 257;stream.writeCode(ClearCode, 9); // 清空解码器字典int pixCount 0;for (u8 p : pixels) {stream.writeCode(p, 9);pixCount;//每 125 个像素重置一次字典保证位宽不变不会提前读取到下一个字节if (pixCount 125) {stream.writeCode(ClearCode, 9);pixCount 0;}}stream.writeCode(EOICode, 9); // 结束stream.flush(f);}signed main(int argc,char* argv[]){const int W 200, H 200;ofstream f(cube_perfect.gif, ios::binary); //以二进制方式写入GIF文件// [Header]f GIF89a;//89a 标准// [Logical Screen Descriptor]writeWord(f, W); writeWord(f, H);f.put(0xF7); // 开启全局调色板 (256色)f.put(0);f.put(0);// [Global Color Table]全局调色板// 0: 背景黑f.put(0);f.put(0);f.put(0);// 1: 极客绿f.put(0);f.put(255);f.put(0);//只用到两种颜色其余填充黑色for(int i 2; i 256; i){f.put(0); f.put(0); f.put(0);}// [Netscape Loop] 循环动画扩展f.put(0x21); // Netscape块标识f.put(0xFF); // 扩展类型标识f.put(0x0B); // 信息长度f NETSCAPE2.0; //应用程序信息f.put(0x03); // 数据长度到结束符前f.put(0x01); //索引writeWord(f, 0); //无限循环不停止f.put(0); //结束符// 3D 立方体点数据vector verts {{-1,-1,1}, {1,-1,1}, {1,1,1}, {-1,1,1},{-1,-1,-1}, {1,-1,-1}, {1,1,-1}, {-1,1,-1}};vector edges {{0,1},{1,2},{2,3},{3,0}, {4,5},{5,6},{6,7},{7,4}, {0,4},{1,5},{2,6},{3,7}};cout Encoding 3D Cube to GIF... endl;for (int i 0; i 60; i) { // 60帧动画vector pixels(W * H, 0); // 黑色背景float angle i * 0.12f; // 每1/60s旋转角度vector p2d;for (auto v : verts)p2d.push_back(project(rotate(v, angle), W, H)); // 3D-2D投影for (auto e : edges)drawLine(pixels, W, H, p2d[e.u].first, p2d[e.u].second, p2d[e.v].first, p2d[e.v].second); // 画边writeGifFrame(f, pixels, W, H); // 写入帧数据cout .;}f.put(0x3B); // 文件结束符f.close(); //关闭cout \nSuccess! Open cube_perfect.gif in Chrome/Edge. endl;return 0;}运行这段代码你会惊讶地发现目录下多了一个 cube_perfect.gif。用浏览器打开它一个绿色的线框立方体正在黑色的背景中流畅地旋转。5. 打通认知的“任督二脉”回顾这个系列的三篇文章我们其实只做了一件事祛魅Demystification。WAV 篇我们发现声音文件只是记录振幅的二进制队列没有任何魔法。3D 篇我们发现那些酷炫的 3D 游戏底层只是初中几何的“相似三角形”运算。GIF 篇本文我们将数学运算的结果3D按照文件协议二进制封装成了人类可见的动画。这就是计算机科学最迷人的地方。无论是生成一段 440Hz 的正弦波还是渲染《黑神话悟空》中复杂的场景其本质都是一样的Input数据 Rules算法/格式 Output数字世界第忱植胰