## 绪论语音是人类交流的基本方式之一，它不仅传递信息，还蕴含着丰富的情感和身份特征。由于每个人生理结构与发声习惯存在细微差别，人们声色各不相同，这使得说话人的声音特征具有唯一性并在长时间内保持稳定，人们可以根据声音来判别说话人的身份。语音信号具有独特的声学特性，如频率、振幅和时序等，这些特性使得语音成为身份识别的有效工具。基于此的声纹识别和说话人认证技术在身份识别、权限验证等领域的有着广泛的应用。随着深度学习在语音生成领域的兴起促进了语音生成往质量高、速度快的方向发展，现有的技术已经能够生成出人耳难以分辨的生成语音。随着语音处理技术的不断发展与优化，生成语音在现代社会中的应用日渐广泛。一方面，自动化的语音播报技术为人们的生活带来了极大便利，满足了公众追求更加舒适生活方式的需求。另一方面，生成语音技术的不当使用甚至滥用也给人们的正常生活带来了一定影响，在某些极端情况下更可能对社会和国家造成不利后果，因而成为一种亟需关注的潜在安全隐患。就身份认知方面而言，结合深度视觉伪造技术，不法分子可能伪造他人或企业关键人物的形象，从而破坏相关个人或机构的声誉。更有甚者，针对国家重要人士的语音伪造行为甚至可能引发政治动荡和社会动乱。而在权限验证系统方面，罪犯可通过非法收集手机用户语音数据的方式，伪造语音并冒充真实用户，获取相应的访问控制权限，破解移动支付密码并窃取财物，从而严重降低系统的安全可靠性，现实世界中亦有此类案例发生。此外在听感上难以分辨的生成语音技术也提高了电信诈骗，敲诈勒索的防范难度，并为司法取证带来了新的挑战。在此背景下，如何实现生成语音的有效识别成为语音技术广泛应用不得不面临的重要问题。 ## 发展最传统的生成语音评估手段依赖于听者的直接评价，通过计算平均意见得分（Mean Opinion Score, MOS）来对音频的自然性和相似性进行量化。虽然这一方式直观且广泛应用于科研环境下对算法的性能进行评估提，但其对大量人力的依赖和主观性偏差的存在使其不适合应用于实际的生成语音检测工作中。随着近些年深度学习技术在语音仿冒领域的突破，生成语音的质量和效率得到了显著提升。面对这些新的挑战和变化，生成语音鉴别的研究亟需发展出更客观、精确且高效的评估方法。 ![生成语音检查领域的发展](timeline.png) 2013年，在语音领域国际顶级学术会议INTERSPEECH上，研究者们正式提出了针对自动说话人验证系统(Automatic speaker verification, ASV)的生成式语音欺诈攻击问题。随着现实场景下基于生成语音的案例的产生，生成语音的危害逐渐引起社会的广泛关注。为解决生成语音的检测问题，学术界与政府机构等组织联合举办了众多相关赛事，在国际上积极推动生成语音鉴别技术的研究和发展。ASVspoof (Automatic Speaker Verification Spoofing And Countermeasures Challenge) 是一系列由INTERSPEECH组委会主导的挑战赛，旨在促进自动说话人验证系统(ASV）免受欺骗威胁的研究。该竞赛自2015年起每两年举行一届，ASVspoof 2015 为该项赛事的第一届，其专注于对语音合成和语音转换系统生成的语音进行检测，ASVspoof 2017 则添加了对录音重放等攻击的考量。ASVspoof 2019 与 ASVspoof 2021 在考虑逻辑访问(Logical Access, LA)和物理访问（Physical, PA）情景以及三种主要形式欺骗攻击，即合成、转换和复制攻击方面取得了进展。ASVspoof 2019 是系列中的第一个将所有三种欺骗攻击类型放在单一挑战中的版本，其形成了一个大型公共数据集，为生成语音检测技术的研究与发展起到了推进作用。在国内，中国科学院自动化研究所、清华大学联合新加坡国立大学举办了语音深度合成检测挑战赛(Audio Deep Synthesis Detection Challenge, ADD)，其中包括含噪声低音质音频、部分生成音频拼接的检测任务。该项挑战赛自2022年起每年举办一届，其形成的中文生成语音数据集为中文合成语音检测技术的发展起到了推进作用。 ## 前沿当前需要检测的生成语音主要包括两大类别：录音与语音合成，录音即利用目标说话人的音频片段进行剪辑、重放等方法生成目标说话人特定内容的话语的生成方式。相较于录音方案，语音合成则是通过参数或机器学习等技术利用计算机将文本转换为语音的生成方式，该种方案所生成的语音相较于录音方法具有所需语料少、内容自由度高、合成效果好的特点。随着语音处理技术的发展，已有许多研究致力于解决生成语音的鉴别问题。生成语音鉴别的主要方法是利用生成语音与真实语音之间的分布差异来对输入的待检测语音进行分类。当前针对生成语音鉴别的手段主要分为基于声学特征的检测与端到端的鉴别两种。基于声学特征的检测方法通常会通过分析语音的频谱、相位谱、共振峰等声学特性并由分类器来判断其真实性。而端到端的检测方法则是直接从原始语音数据中学习生成语音与真实语音的差异，这种方法通常需要大量的标注数据进行训练，经过大量语料训练的检测模型能够很好的捕获生成语音与真实语音的差异，进一步提高检测的准确率。 ![一般检测管线](pipeline.png) 从本质上讲，生成语音的检测是一种分类任务，随着语音技术的不断进步，生成语音也在不断变化，在模型训练中未见过的生成语音样本在测试阶段同样也很难检测出。如果希望检测系统可以实现对新技术的应对，最简单直接的办法就是将最新的生成语音样本与之前的数据混合重新进行训练，这就导致了生成与检测成了一对攻防博弈，总会有新的生成方法被提出用以躲避既有鉴别方法的检测，而现有的鉴别模型又不得不不断地在训练集中纳入新方法所生成的语音样本。此外，这要求生成技术已知或模型公开易于获取，然而现实场景下生成语音通常种类多、样本少且生成技术未知，样本难以获取使得该方案在实际操作中可行性较低。在安全方面，面对新出现的攻击类型，在声纹密码等应用场景下，有着对新型攻击方式快速应对的需求，而这种传统的检测方法对算力与存储的开销会随着数据的扩充而线性增长，这使得训练时间久，参数更新不及时，难以快速部署上线应对新出现的攻击类型。目前，生成语音检测的主要方法主要包括基于特征的语音检测和基于波形的语音检测两种类型。基于特征的生成语音检测方法主要考虑经过傅立叶变换后的生成语音频谱经过手工或自动处理所提取的特征信息，基于波形的生成语音检测方法则是直接将原始波形作为输入进行端到端的检测。 ### 特征早期基于特征的检测方法主要考虑生成语音与真实语音频谱之间的差异，通过人类专家的先验知识手工设计特征，例如：在HMM基础的语音合成系统中，合成语音的参数序列是为了最大化输出概率而生成的，这导致合成语音的参数随时间的变化倾向于比自然语音小，进而导致合成语音的时间帧间差异（Inter-Frame Difference）变化小于真实语音样本。此外该类方案通常还会考虑语音生成系统固有的缺陷，例如：基于卷积神经网络(Convolutional Neural Networks, CNN)的语音合成系统的卷积核沿时域递推进行互相关运算，其会在频谱上产生棋盘状的伪影并导致合成语音频谱过于平滑；另外，语音合成系统通常应用刻画人耳听觉系统频率响应的梅尔滤波器组(Mel Filter Bin)以产生符合人类听觉的语音，由于，人耳对高频信息相对不敏感，大多数合成语音算法对对高频信息缺乏建模，这使得高频频谱信息存在瑕疵。此外，由于人耳听觉系统对相位相对不敏感，所以生成算法的声码器通常基于最小相位声道模型，通常不会重建语音的相位信息，由此导致合成语音与真实语音在相位信息上存在差异。当前，深度学习技术已经广泛应用于基于特征的生成语音鉴别的特征处理与神经网络分类器建模当中，接下来将详细介绍此类方法。早期基于深度学习的生成语音鉴别系统通常以频谱特征作为模型的输入。频谱特征可分为功率谱特征与相位谱特征，功率谱特征描述的是语音信号在频域的能量分布，通常包括平均功率谱、过零率、频率倒谱特性等。相位谱特征则描述的是语音信号在频域的相位信息，它体现了语音信号的波形包络，对于语音的感知有着重要的作用。语谱特征主要通过倒谱系数的形式描述，常用特征包括梅尔频率倒谱系数（Mel Frequency Cepstral Coefficients, MFCC），线性频率倒谱系数（Linear Frequency Cepstral Coefficients，LFCC），常数 Q 倒谱系数（Constant-Q Cepstral Coefficients，CQCC）和逆梅尔频率倒谱系数（Inverted Mel-Frequency Cepstral Coefficients，IMFCC）。MFCC 是一种对语音信号进行频谱分析后的特征提取方法，MFCC 可以很好地模拟人耳的听觉特性，因此在语音领域得到了广泛的应用。LFCC则在滤波器组的选取上选择了线性滤波器组，它不聚焦于人耳的听觉特性而是对高频特征与低频特征提供了相同的分辨率。CQCC 是常数 Q 变换（Constant Q Transform, CQT）提取出的倒谱系数，这种倒谱系数是通过施加一个指定的常数 Q 来将信号的幅度进行压缩以使其更加适合于倒谱分析而获得的，这种压缩可以看作是一种非线性缩放。Patel等人提出基于耳蜗滤波器倒谱系数和瞬时频率变化构造帧级特征, 再借助高斯混合模型进行判别, 以此捕获跨帧的特征变化，实验表明该特征对于噪声及不同类型的生成语音更鲁棒。IMFCC则是MFCC的一种变体，它通过对梅尔频率进行逆变换来获取频谱特征，这种方法试图更加贴近原始频率的分布，从而在某些应用场景下提供了更加准确的音频分析结果。与MFCC相比，IMFCC在处理具有复杂高频信息的音频信号时，能够提供更加细腻和精确的特征描述。通过使用这些不同的声学特征提取方法，可以更好地捕获和表示语音信号中的关键特征，从而提高生成语音鉴别的准确性。在上述频谱特征中，LFCC与CQCC特征在目前的生成式语音检测方法中最为常用。 #### LFCC特征提取流程下图简要描述了LFCC特征提取的过。首先对语音信号进行预加重处理，然后将语音信号分帧，每帧进行加窗处理，然后进行快速傅里叶变换（FFT）得到频谱图，最后对频谱图进行DCT变换得到LFCC特征。预加重是将语音信号通过一个高通滤波器，以提升高频部分，使整个频带中信号信噪比均匀，突出高频的共振峰。语音是连续的一维时间序列信号，为了提取语音的频谱特征，需要将语音信号分帧，每帧进行加窗处理，通常语音信号每帧长度取为 25 毫秒，相邻帧之间有 10 毫秒的重合以避免频谱泄露。然后进行FFT得到频谱图。之后对频谱取模平方得到功率谱，然后计算功率谱在线性频率滤波器组中的能量并取对数。线性频率滤波器组的滤波器组频率为线性频率分布。最后DCT变换是对频谱图进行离散余弦变换，并通过动态差分计算提取一阶差分和二阶差分系数，以更好地描述动态特性进而得到LFCC特征。 ![LFCC特征提取流程](lfcc.png) #### 数据驱动的自动特征表示随着自监督预训练模型技术的发展，由深度神经网络进行自动特征提取的方法被提出，该类特征无需依靠人类专家知识，通过在大尺度的数据集上进行训练，模型提取的特征往往包含更多高级信息，能够有效提升下游任务的性能。在语音领域被广泛应用的预训练模型包括Wav2Vec、HuBert、Whisper。Whisper是由OpenAI提出的自监督预训练模型，通过在68万小时的人类语音数据上训练，其在自动语音识别，语音翻译等多项任务上皆达到了领先水平。Wang等人探索了多种自监督预训练特征在生成式语音鉴别任务上的性能，实验展现出这些在大尺度音频数据集上由模型自主学习出的特征表示在下游任务的性能与泛化性上皆有显著提升。特别是在跨数据集的测试上其表现出了远超传统手工特征的泛化性。 ### 分类对于神经网络分类器模块，通常以时域卷积神经网络架构为基础，如轻量卷积神经网络（Light Convolutional Neural Network， LCNN）、挤压激励神经网络（Squeeze-and-Excitation Network，SENet）、残差神经网络（Residual Network，ResNet)等。LCNN网络在2017年与2019年的ASVspoof挑战赛上均取得了优异的表现，此外LCNN网络结构简单，参数较少，在保持较高准确率的同时，具有较快的推断速度，适合于实时性要求较高的场景。2020年，Li等人提出了基于Res2Net网络的检测方案，Res2Net通过将输入特征分成多个通道组，分别进行不同尺度的变换，并在不同组之间进行残差连接，用于学习多尺度的特征表示，以提升系统面对未知类型攻击的泛化能力。此外还存在一些直接基于波形对生成语音进行分类的神经网络，这些网络同样不依赖于专家知识，模型在原始波形数据上端到端学习高效且准确的特征表示。其中RawNet2是借鉴于ASV任务的端到端网络，它利用sinc函数作为滤波器，有效地在时频域内分离和提取音频信号的关键特征。这种多尺度的卷积操作使得模型能够在不同的频率和时间分辨率下捕捉信号的细微变化，从而获得丰富的音频表示。Jung等人于2021年提出了一种基于RawNet2的音频反欺骗系统，名为AASIST。该系统基于图神经网络（GNNs），特别关注于集成频谱和时间域的特征，以提高对欺骗攻击的检测能力。AASIST的核心贡献在于引入了异构堆叠图注意力层（HS-GAL），这是一种新颖的图注意力机制，能够同时处理来自不同域的异构图。通过这种机制，AASIST能够有效地捕捉和整合频谱和时间域中的关键特征，这些特征对于区分真实的和欺骗的语音至关重要。此外，该系统还包括最大图操作（MGO）和扩展的读出方案，进一步提升了模型的性能。在实验中，AASIST在ASVspoof 2019逻辑访问（LA）数据集上的表现显著优于现有的最先进的技术。值得注意的是，AASIST的轻量级版本（AASIST-L），尽管参数数量大幅减少至85K，仍然在所有竞争系统中保持领先性能。这一成果不仅展示了图神经网络在音频反欺骗领域的潜力，也为轻量级模型的设计提供了新的思路。损失函数同样对模型的性能有着显著影响。研究者们通过优化不同类型的损失函数，进一步提高了音频反欺骗系统的准确性和鲁棒性。生成语音鉴别任务可以被视作一种分类任务，虽然鉴别的结果存在真实与伪造两类，但区别于传统的二分类任务，合成语音的生成技术种类繁多，不同生成语音类型间的分布并不相似，Zhang等人提出单分类损失函数OC-Softmax（One-Class Softmax）。这一损失函数通过压缩真实语音分类边界并扩张生成语音边界有效地提升了系统对真实和合成语音的分类性能，使得系统在面对各种类型的生成语音时表现更为准确和稳健。三元组损失（triplet loss），已被证明在提取具有区分性的嵌入向量方面具有显著效果，Li等人将三元组损失引入生成语音鉴别任务中，通过最小化来自相同说话人的语音样本之间的距离，同时最大化来自不同说话人或欺骗样本之间的距离，模型能够学习到更具辨别力的特征表示，从而有效地区分真实语音和合成语音。 ## 数据 ASVspoof 2019是一个为研究反欺骗而设计的数据集。LA 子集包含真实样本以及不同类型的语音合成（TTS）和语音转换（VC）方法的逻辑访问攻击，其具体数据情况参见下表。 ![ASVspoof 2019 LA 数据集详细信息](dataset.png) 其中，训练集和开发集共享相同的 6 种攻击类型（A01-A06），包括 4 种 TTS 算法和 2 种 VC 算法。测试集包括 11 种新的未知攻击类型（A07-A15、A17、A18），其中包括不同的 TTS 和 VC 攻击组合。此外，测试集还包括 2 种攻击（A16、A19），与训练集中的 2 种攻击（A04、A06）使用相同的算法，但训练数据不同。 ![ASVspoof 2019 LA 数据集可视化](asvspoof2019.png) 上图是由ASVspoof组委会官方提供的数据集可视化，展示了全部数据在训练好的神经网络模型中的特征向量的分布，其中bona fide 为真实语音，圈外为生成语音。 ## 问题当前，生成语音鉴别方法的研究尚不成熟，现有系统面临的最大问题是泛化性不足。具体而言，传统的监督学习假设训练和测试数据具有相同的分布，当面对域迁移时，即当训练数据和测试数据具有非常不同的统计量时，模型表现不佳。现有的大多数研究从特征表示方向与损失函数设计方向进行改进以提高生成语音鉴别方法的泛化性。在特征表示方面，进行谱增广，时频域融合，利用自监督预训练特征等方案被提出。在损失函数设计方面，一些研究认为，生成语音检测并非传统的二分类问题，不同生成技术所生成的音频的分布假设不同，不应当归于一类，单分类损失，三元损失函数等方案被提出。此外，一些研究使用连续学习技术以实现鉴别系统在不同语音生成方案上的持续集成。 23:I[97479,["/_next/static/chunks/3t6okb9ev3d1-.js","/_next/static/chunks/1_18sqpr6ntmv.js","/_next/static/chunks/43kiu5ggf_nr-.js","/_next/static/chunks/1a1rtf8pkxnqn.js","/_next/static/chunks/2mmdbjr-2ln6k.js","/_next/static/chunks/1-lxkfx0xb5gs.js","/_next/static/chunks/00fjx4atij1x7.js","/_next/static/chunks/1-yfuda0m8nq7.js","/_next/static/chunks/3-rd_c78vpny5.js"],"default"] 24:I[42076,["/_next/static/chunks/3t6okb9ev3d1-.js","/_next/static/chunks/1_18sqpr6ntmv.js","/_next/static/chunks/43kiu5ggf_nr-.js","/_next/static/chunks/1a1rtf8pkxnqn.js","/_next/static/chunks/2mmdbjr-2ln6k.js","/_next/static/chunks/1-lxkfx0xb5gs.js","/_next/static/chunks/00fjx4atij1x7.js","/_next/static/chunks/1-yfuda0m8nq7.js","/_next/static/chunks/3-rd_c78vpny5.js"],"default"] 25:I[8749,["/_next/static/chunks/3t6okb9ev3d1-.js","/_next/static/chunks/1_18sqpr6ntmv.js","/_next/static/chunks/43kiu5ggf_nr-.js","/_next/static/chunks/1a1rtf8pkxnqn.js","/_next/static/chunks/2mmdbjr-2ln6k.js","/_next/static/chunks/1-lxkfx0xb5gs.js","/_next/static/chunks/00fjx4atij1x7.js","/_next/static/chunks/1-yfuda0m8nq7.js","/_next/static/chunks/3-rd_c78vpny5.js"],""] 26:I[30509,["/_next/static/chunks/3t6okb9ev3d1-.js","/_next/static/chunks/1_18sqpr6ntmv.js","/_next/static/chunks/43kiu5ggf_nr-.js","/_next/static/chunks/1a1rtf8pkxnqn.js","/_next/static/chunks/2mmdbjr-2ln6k.js","/_next/static/chunks/1-lxkfx0xb5gs.js","/_next/static/chunks/00fjx4atij1x7.js","/_next/static/chunks/1-yfuda0m8nq7.js","/_next/static/chunks/3-rd_c78vpny5.js"],"default"] 27:I[8704,["/_next/static/chunks/3t6okb9ev3d1-.js","/_next/static/chunks/1_18sqpr6ntmv.js","/_next/static/chunks/43kiu5ggf_nr-.js","/_next/static/chunks/1a1rtf8pkxnqn.js","/_next/static/chunks/2mmdbjr-2ln6k.js"],"IconMark"] 19:T14af, 生成音乐与生成图像和视频有一些明显的不同之处。 1. 首先，音乐是一种时间艺术，需要一个时间模型。 2. 其次，音乐通常由多种乐器/音轨组成，这些乐器/音轨都有各自的时间动态，但它们共同随着时间相互依存地展开。 ## MIDI - **音乐数字接口**（Musical Instrument Digital Interface，简称**MIDI**）是一个工业标准的电子[通信协议](https://zh.wikipedia.org/wiki/%E9%80%9A%E8%A8%8A%E5%8D%94%E5%AE%9A)，为电子乐器等演奏设备（如[合成器](https://zh.wikipedia.org/wiki/%E5%90%88%E6%88%90%E5%99%A8)）定义各种音符或弹奏码 - MIDI不发送声音，只发送像是音调和音乐强度的数据，音量，颤音和相位等参数的控制信号，还有设置节奏的主频信号。在不同的电脑上，输出的声音也因音源器不同而有差异。 - 许多音乐的[文件格式](https://zh.wikipedia.org/wiki/%E6%96%87%E4%BB%B6%E6%A0%BC%E5%BC%8F)，都建构于MIDI档之上。这些格式可说就是电子乐器在看的电子乐谱，所以通常一个文件只需几十KB，就能够让电子乐器演奏出一首很完整的音乐。 ## ABC 记谱法 ABC记谱法是19世纪出现的一种记谱法，以A到G的字母记录音高，再配以其他符号用来记录变化音、音长等，由克里斯·瓦尔莎发明。后来由于计算机使用ASCII字符集又要处理音乐，ABC记谱法再度受重视，并成为一部分音乐软件的信息存储法。该方法在可读性和结构表示方面优于 MIDI ## 符号音乐生成基于以上两种标记法，音乐生成任务可以被转化为一种特殊的文本生成任务，特别是在LLM被提出后，基于ABC记谱法的文本序列预测，即可以实现音乐生成功能。 ### 输入输出序列以下是一些常见模型的输入输出序列 ![ABC 记谱](abcnotes.png) ``` bach piano_strings start tempo90 piano:v72:G1 piano:v72:G2 piano:v72:B4 piano:v72:D4 violin:v80:G4 piano:v72:G4 piano:v72:B5 piano:v72:D5 wait:12 piano:v0:B5 wait:5 piano:v72:D5 wait:12 piano:v0:D5 wait:4 piano:v0:G1 piano:v0:G2 piano:v0:B4 piano:v0:D4 violin:v0:G4 piano:v0:G4 wait:1 piano:v72:G5 wait:12 piano:v0:G5 wait:5 piano:v72:D5 wait:12 piano:v0:D5 wait:5 piano:v72:B5 wait:12 ``` 此外，这类模型的设计通常会结合一些乐理知识。例如，音乐序列中的起始音符通常与最后一个音符不同。序列的第一个音符通常包含属于主和弦的音符，但音乐中的最后一个音符包含来自五和弦或下属七和弦的音符。如下图所示，第一个 C 大调和弦小节和最后一个 E 小调和弦小节，最好使用不同的 CNN 内核（Local Conv）。 ![Local Conv](local_conv.png) ## 文本到音乐假如将这个问题交给普通人来解决，相信很多没有基本乐理知识的人，都很难根据特定的文本，创作出一段长达几分钟的乐曲。但算法模型可以通过大量的数据，模仿文本和对应音乐的关联。此外，在复调音乐中，音符通常被组合成和弦、琶音或旋律，因此简单的音符时间序列并不自然合适。但是解决这个问题依然充满了挑战，主要集中在以下两方面： 1. 当前学术界的研究只能生成简单场景的短片段语音，因此将单文本转化为高保真和长时间连续的音乐片段具有很强的挑战 2. 缺乏丰富的“音乐-文本”结对的数据集下文介绍Google提出的MusicLM模型，MusicLM基于AudioLM的衍生工作，其生成的音乐可以以文本和旋律为条件，这意味着它可以接受以哼唱、歌唱、吹口哨或演奏乐器为形式的输入旋律，并生成遵循该旋律的音乐，同时也遵守文本描述。 ### MusicLM MusicLM使用三种模型来提取作为条件自回归音乐生成输入的音频表示。SoundStream，w2v-BERT，和MuLan。 ![models](models.png) #### MuLan 通过AudioEmbeding编码音频，通过TextEmbedding编码文本，将audio和text拉齐到同一维度空间，最后计算对比损失函数比较两者在同一维度空间的差别，其做法类似于clip。 ![MuLan](mulan.png) MusicLM是基于一个**层次化**的序列到序列的架构。 1. 第一阶段被称为语义建模阶段，学习从MuLan音频token到语义token的映射。这一阶段负责生成代表作为输入的文本描述的语义token序列。音频通过MuLan模型生成MuLan tokens，然后通过语义模型映射为w2v-BERT的Semantic tokens 用作MusicLM下一阶段的条件信号。 2. 第二阶段是声学模型阶段，将MuLan tokens和Semantic token一起输入声学模型，并映射为SoundStream的Acoustic tokens，为了保证长时间连续音频生成，生成过程是一个类似audioLM的coarse-to-fine阶段。 3. 最后，使用SoundStream的解码器解码Acoustic tokens，得到音乐。 ![Pipeline](pipeline.png) #### 推理在推理过程中，从文本提示中提取的MuLan文本嵌入被用作条件，并用与音频嵌入相同的RVQ进行量化。这个过程确保了音频和条件信号都有一个一致和同质的表示，这有助于模型生成与文本描述相一致的高质量音乐。1a:T2d5a, >本文源自 [https://sixplain.com/2020/11/08/jpeg/](https://sixplain.com/2020/11/08/jpeg/) \ >源网站无法访问，故备份于此 JPEG 是一种常见的图像压缩格式，它采用的是有损压缩技术，也就是为了让体积变小，丢掉了一部分图像信息。下面就来看下 JPEG 的实现原理。 ## 图像显示在了解 JPEG 的实现原理前，我们先来看下图像是如何显示的。计算机最常用的色彩空间是RGB（红绿蓝三原色），屏幕上每一个像素都是由红绿蓝三个颜色通道叠加最终显示出来。 ![](1-20220531160030-tos5ycu.jpg) RGB 虽然是计算机最常用的色彩空间，能够直接对应显示器的显示。但是对于数据传输而言，RGB色彩空间并不合适。于是就有了各种图片编解码格式，不同的图片格式，在解码之前会有各自的压缩方式，有的是无损压缩，有的是有损压缩，存储的格式也是各不相同： ![](2-20220531160030-y0dpeuj.jpg) 对于 JPEG 来说，它的主要过程是： 1. 把数据分成「重要部分」和「不重要部分」 2. 滤掉不重要部分 [[3]]. 将剩下重要的数据进行压缩存储 ## 色彩空间转换 (Color Space Convert) 这个词初听起来有点奇怪，色彩怎么还有空间，空间怎么还能转换？这里所说的色彩空间其实就是对颜色的不同表示方式。比如「红色」，可以从红黄蓝三原色的角度去描述，也可以从色相饱和度的角度去描述 ![](5-20220531160030-5ohaxd2.jpg) JPEG 在编码时充分考虑了人眼的特性：相对颜色而言，眼睛对亮度更加敏感（因为有更多的视杆细胞）。所以可以将颜色用亮度结合色度的方式来表示: `YUV` > Y 表示明亮度（Luminance）， U 和 V 分别表示色度(Chrominance)和浓度(Chroma)。和 RGB 类似，每个像素点都包含 Y、U、V 分量，但 Y 和 UV 是可以分离的，只有 Y 也可以显示完整的图像，只不过是黑白的。 > YUV/YCbCr 是一种电视信号传输所用的色彩空间，对应一个亮度通道 Y 和两个色差通道 Cb 和 Cr。早期只有黑白电视，所以电视信号只需要 Y 通道即可。后面出现了彩色电视，就加上 CbCr 这两个色差信号，而原本的黑白电视只需要处理 Y 通道即可，能够兼容黑白彩色电视的信号传输。 ## 取样 (Downsampling) 既然眼睛对亮度更敏感，且已经分离出了亮度和色度，那是不是可以去掉一些色度信息来节省空间呢，这就是「取样」做的事情：压缩 UV 值。比如 4:2:2 采样，它的含义是每 4 个 Y 采样点，有 2 个 U 和 2 个 V。也就是 UV 分量是 Y 分量采样的一半，假设 Y 分量用 X 表示，U 分量用黑圈表示，V 分量用红圈表示 ![](8-20220531160030-eks1ptk.jpg) ``` 假如图像像素为：[Y0 U0 V0]、[Y1 U1 V1]、[Y2 U2 V2]、[Y3 U3 V3] 那么采样的码流为：Y0 U0 Y1 V1 Y2 U2 Y3 V3 其中，每采样过一个像素点，都会采样其 Y 分量，而 U、V 分量就会间隔一个采集一个。最后映射出的像素点为 [Y0 U0 V1]、[Y1 U0 V1]、[Y2 U2 V3]、[Y3 U2 V3] ``` 这样原先 12 个单位的信息量，经过 4:2:2 采样后，只需存储 8 个单位的信息量，减少了 1/[[3]] 的体积。如果是 `4:1:1` 的话，则可以减少 50% 的体积。 ![](7-20220531160029-kp41aji.jpg) ## 分块分块的过程是把图像以 8 x 8 的大小分成多份，方便后续的矩阵操作。以 Lena 的 Y 分量（明度）为例: ![](lena-20220531160030-xpu7rx0.jpg) > 如果不能被 8 整除，会在图像的右边和底部增加额外的像素（因为矩阵操作对元素的数量有要求）。 ## 离散余弦变换 (DCT) 这是 JPEG 压缩算法的核心，这个变换的目的是将数据从空间域转换为频域，再结合眼睛对高频不敏感的特点，将高频数据去除。什么叫「从空间域转为频域」？这就要请出傅立叶老师了，傅立叶发现看似复杂的周期函数，其实可以用一系列简单的正弦、余弦波之和来表示，比如下面这个看起来有点奇怪的函数： ![](12-20220531160030-c581zvo.jpg) 它可以由多个不同频率/振幅的正弦/余弦波组成 ![](13-20220531160029-pbha9lq.jpg) 从正面（时域）看，这个波一直在动，但从侧面（频域）看，它其实就是几根线 ![](14-20220531160030-805luat.jpg) 那这跟我们要做的事情有什么关系呢？假设 Y 分量是一维数据，只有 X 方向的值： ``` [100, 50, 25, 75, 100, 0, 125, 200] ``` 将它们转换为坐标，看起来就像这样： ![](15-20220531160030-rpbk0ty.jpg) 可以将它构造为某个周期函数的一部分，就像这样： ![](16-20220531160029-k2zgmef.jpg) 你看，有了一条函数曲线，就可以将它转换为不同频率的正/余弦组成的结果，这就完成了时域转到频域的转换。但这里有 x，y 二维数据，又该如何做呢，那就把坐标系拓展成三维，看起来像是这样： ![](17-20220531160030-t80l4ac.jpg) 是不是很像一座座小山，如果把山谷用黑色标记，山峰用白色标记，就会得到这样的效果： ![](18-20220531160029-g7ny9cn.jpg) 黑白交错地越密，频率越高。接下来该有请主角离散余弦变换（DCT）上场了。它是离散傅立叶变换的精简版（去掉了虚数部分），方程式如下： ![](19-20220531160029-bzce74h.jpg) 不要被它吓到，我们只需知道：每一个变换后的结果 D(i, j) (第 i 行，第 j 列元素)，都跟原矩阵中的每一个元素与余弦函数的乘积有关。又因为我们只有 8 x 8 个元素，所以公式又可以精简为： ![](20-20220531160029-ffzalq6.jpg) 因为是离散函数，所以它的展示结果是这样的： ![](21-20220531160029-tz9g0iq.jpg) 还是按照上面俯视的方式来看，山峰为白，山谷为黑，那么它对应的频率表(64 个余弦函数)就像这样： ![](22-20220531160029-f1k4hp9.png) 对于图像的 8 x 8 数据，可以通过这 64 个 cos 函数乘以对应的系数(coefficient)来表示。系数越大表示该余弦函数对于图像数据的作用越大。同时注意到频率从左上角到右下角依次递增，这对于下一步要做的「量化」很重要。现在假设有一个 Y 分量的 8 x 8 block 数据如下： ![](11-20220531160029-x5f97ad.png) 因为明度的数据是从 0 - 255，但余弦函数需要数值在 -128 到 127 之间，所以需要先减去 128 ![](23-20220531160029-7vddrkv.png) 接下来就要计算系数了，这里会进行矩阵运算。用乘法简单类比的话，就是已知公式 `z = x·y`，且已知 `z` 和 `y` 的值，求 `x`。这里的 `z` 是 Y 分量的明度值（减了 128 之后），`y` 是频率表对应的矩阵，x 最终的计算结果为： ![](24-20220531160029-cujfht0.png) 这里每一个位置的值，分别表示该位置上的余弦函数对应的系数，值越大，表示该余弦函数对结果的作用越大。可以看到，左上角区域的值普遍大于右下角的值，这表示低频的贡献度比高频的大，在下一步的量化过程里，就可以对这些高频数值下手了。 > 左上角第一个数是个定值，所以也被称为 DC (直流分量)，是整个矩阵的平均值。剩下的 63 个数被称为 AC（交流分量），越往右下角频率越高。 ## 量化（Quantization） JPEG 的质量控制（如 50%, 75% 等）就是发生在量化阶段。量化是对经过 DCT 变换后的低频高频分量进行处理，略去不重要的部分。因为眼睛对高频的敏感度弱于低频，因此可以舍去部分高频数据。怎么舍呢，这就涉及到「标准量化表」，明度标准量化表(Q50，也就是 50% 的质量)是这样的： ![](26-20220531160029-qy06ls6.png) 为什么说它是「标准量化表」呢，因为更高或更低的质量都可以由这个表计算而来，对于质量高于 50% 的可以用 (100 - quality level)/50 的方式来算，低于 50% 的直接 50/qulity level，比如 10% 质量的表: ![](27-20220531160030-87aix3b.png) 对于上一步 DCT 得到的结果，我们将它应用标准量化表（每一个数除以量化表里对应位置的数，对小数结果四舍五入），可以得到如下结果： ![](28-20220531160029-adppqmd.png) 那些人眼不太敏感的高频数据已经被清零了。压缩质量越低，量化表的值就越大，最终结果出现的 0 就越多，也就是被丢弃的信息越多。 ## 压缩得到量化后的矩阵就要开始编码过程了，首先要把二维矩阵变为一维数组，这里采用了 zigzag 排列，将相似频率组在一起: ![](30-20220531160029-agkyn7d.png) 先对直流分量 DC 进行[差分编码](https://zh.wikipedia.org/zh-hans/%E5%B7%AE%E5%88%86%E7%B7%A8%E7%A2%BC)（因为相邻图像块的 DC 差别不大，只要保留第一个图像块的 DC 和以后每一个 DC 之间的差值即可）。再对交流分量 AC 进行[游程编码](https://zh.wikipedia.org/zh/%E6%B8%B8%E7%A8%8B%E7%BC%96%E7%A0%81)，避免连续重复的数据。 > 一组资料串"AAAABBBCCDEEEE”，由4个A、3个B、2个C、1个D、4个E组成，经过游程编码可将资料压缩为4A3B2C1D4E。在这里就是(1,4),(1,3)…(3,0)…(2,-1),BOE。BOE 表示这个位置之后全都是 0 最后再使用[哈夫曼编码](https://zh.wikipedia.org/zh/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81)对结果进一步无损压缩，至此 JPEG 的压缩流程就完成了。 > 这里还会涉及到 JPEG 内置的一些标准编码表用于信息的压缩和解压缩，就不展开讲了。 ![](31-20220531160030-wd95uvt.jpg) ## 解压解压的过程，先是将数据还原为量化后的 8 x 8 图像块，然后根据图像质量，计算量化表，得到 DCT 后的表格，再与 64 个余弦函数（实际运算中是两个矩阵的操作）运算得到被离散余弦函数转换前的数据，一路逆运算，最终得到图像的 RGB 信息。 ## 延伸由于 JPEG 压缩算法本身的问题，又衍生出了一些替代品，如可以实现渐进式加载效果的 Progressive JPEG（先展示模糊的内容，再逐步展示细节，但并没有减少文件尺寸，同时还增加了处理复杂度），可以实现无损压缩的 JPEG2000（这个用得比较少，有无损需求的通常会考虑 png / webp），完全兼容 JPEG API / ABI，同时能够实现更小尺寸的 [mozjpeg](https://github.com/mozilla/mozjpeg)（内部使用了 [libjpeg-turbo](https://github.com/libjpeg-turbo/libjpeg-turbo))，我自己使用下来效果还不错，可以看下这篇 webp 和 mozjpeg 的[对比文章](https://siipo.la/blog/is-webp-really-better-than-jpeg)。 ## 小结 JPEG 的压缩思路还是挺值得学习的，充分考虑使用者的特点（亮度优于色度，低频优于高频），用到了分治的思想，有损和无损压缩的结合，数学公式的使用等。虽然 20 多年前就在使用，且有了更多的图像格式选择，但依然是图片存储领域重要的一份子。 ## 参考 * [https://www.math.cuhk.edu.hk/~lmlui/dct.pdf](https://www.math.cuhk.edu.hk/~lmlui/dct.pdf) * [https://www.massey.ac.nz/~mjjohnso/notes/59731/presentations/jpeg.pdf](https://www.massey.ac.nz/~mjjohnso/notes/59731/presentations/jpeg.pdf) * [https://glumes.com/post/ffmpeg/understand-yuv-format/](https://glumes.com/post/ffmpeg/understand-yuv-format/) * [https://www.lfasd.top/archives/6/](https://www.lfasd.top/archives/6/) 1b:T1adb, 文本到言语（TTS），也称为语音合成，长期以来一直是人工智能，自然语言和语音处理领域中的一个研究方向。开发TTS系统需要有关语言和人类语音生产的知识，涉及多个学科，包括语言学，声学，数字信号处理和机器学习。 ## 历史人类对语音合成最早的尝试可以追溯到12世纪，18世界中叶匈牙利科学家沃尔夫冈·冯·肯佩伦（Wolfgang von Kempelen）构建了一台使用一系列波纹管，弹簧，风笛和共振盒的说话机器，以产生一些简单的单词和简短的句子。第一个基于计算机的语音合成系统出现在20世纪下半叶。早期基于计算机的语音合成方法包括关节模拟合成，共振峰合成和拼接合成。之后随着统计机器学习的发展。基于统计参数的语音合成（SPSS）方法被提出，它可以预测诸如频谱，基频和音素时长之类的参数。到了2010年左右，基于神经网络的合成方法被提出，因其较好的合成语音质量，逐渐成为语音合成领域的主流方法。 ## 关节模拟合成关节模拟合成是一个很自然的想法，其主要思想就是模拟人类器官进行发声，诸如嘴唇、舌头、共鸣腔和声带振动。理想情况下，关节模拟合成可能是合成语音的最有效方法，因为人类就是这样发声的。然而在工程实践中，这种方法存在诸多困难，例如，我们很难收集到足够多的数据对发声器官进行建模。因此该种方法的可行性较低。 ## 共振峰合成共振峰合成，是对关节模拟合成模型的一种简化，它是一种source-filter模型，其基本思想是将声带的震动看作语音信号的信号源，将嘴唇、舌头等一系列共鸣腔体看作是滤波器模型，即所谓语音就是声带振动产生的波形通过一系列的滤波器后得到的时序信号。这些滤波器通常是由专业的语言学家设置制定的，系统由多个具有不同参数的加性声学模型组合发出声音。但这样的合成系统合成出来的语音具有比较强烈的机械感，另外就是滤波器的设置需要大量的专业知识，难以设置。 ## 拼接合成拼接合成是指将录制的真实人类语音拆解成基本发音单元（例如音节、声韵母或音素）并储存在数据库中。在合成时，系统通过给定的文本输入在数据库中查找所需发音单元的记录并将其拼接在一起生成语音。一般而言，拼接合成的TTS生成的音频具有接近原始配音演员级别的高可理解性和正宗音色。然而，使用这种方法的系统需要大量的数据以涵盖口语发音中的所有组合。另一个缺点是，这种系统合成出来的语音不太自然，几乎没有任何的情感起伏。 ## 统计参数合成为了解决拼接合成的缺点，统计参数合成被提出。其基本思想是，相比于直接拼接合成语音波形，我们可以先生成产生语音所必须的声学参数，然后通过一些算法从这些声学参数中恢复出语音波形。 SPSS通常由三个组件组成：文本分析模块，参数预测模块（声学模型）和声码器 Analysis/Synthesis模块（Vocoder）。一般合成管线

文本分析模块作为语音合成系统的前端，起到对系统输入文本进行预处理的作用，例如，将 *“现在16：13了”* 这句话转换为 *“现在十六点十三分了”* 。并对文本进行分词、语义、韵律特征提取等工作。声学模型经过配对的语言特征和声学特征训练，其中声学特征包括F0(基频)，频谱或倒谱等。声码器负责将声学模型生成的声学特征还原成波形。 SPSS对比上面几种TTS系统有如下好处： 1. 声音听上去更自然 2. 更灵活，通过修改参数可以控制合成的语音。 3. 更低的数据开销（相较于拼接合成）但其生成的音频音质不是很好，另外依旧具有机械感，很容易被人类分辨出这段音频是合成的。 2010年之后，随着深度神经网络的发展，一些高级的网络结构被应用于参数预测模块之中用以替代传统的统计模型。 ### SPSS声学模型基于HMM的SPSS的一个主要缺点是，合成语音的质量还不够好，主要有以下两个原因： 1. 声学模型的准确性不好，预测的声学特征是过度平滑的，缺乏细节。 2. 声码技术还不够好。第一个原因主要是由于HMM缺乏建模能力，因此提出了基于DNN的SPSS，改善了合成质量。为了更好地模拟语音话语中的跨越长时上下文的效果，利用基于LSTM的循环神经网络被提出来，以更好地模拟上下文依赖性随着深度学习的发展，许多高级神经网络结构被用来预测声学特征，比如CBHG GAN啥的。相关研究者探索一种更端到端的方式，该方式利用了基于注意力的循环序列transducer模型直接从音素序列生成声学特征，可以避免在以前的基于神经网络的声学模型中所需的逐帧对齐。 ## 神经语音合成随着深度学习的发展，基于神经网络的TTS被提出，它采用神经网络作为语音合成的模型骨干。 SPSS中采用了一些早期的神经模型来代替HMM进行声学建模。后来，提议 WaveNet 直接从语言特征产生波形，这可以被视为第一个现代神经TTS模型。诸如DeepVoice 1/2 之类的其他模型仍然遵循统计参数合成中的三个组件，仅仅只是使用相应的基于神经网络的模型来升级了部分组件。此外，一些端到端模型被提出（例如Tacotron 1/2 ，Deep Voice 3和FastSpeech 1/2），以简化文本分析，并直接采用文本分析模块字符/音素序列作为输入，并用梅尔谱简化声学特征。后来，开发了完全端到端的TTS系统，以直接从文本中生成波形，例如 ClariNet，FastSpeech 2s 和 Eats。与以前基于拼接合成和统计参数合成的TTS系统相比，基于神经网络的语音合成的优势包括在清晰度和自然性方面具有很高的质量，并且对人类预处理和特征构建的需求较少。 ### 端到端TTS中的声学模型与SPSS相比，基于神经网络的端到端TTS中的声学模型具有以下优点： 1. 传统的声学模型需要在语言和声学特征之间进行对齐，而Seq2Seq的神经模型则通过注意力机制隐式地学习对齐方式或预测共同出现时间，更端到端，需要较少的预处理。 1. 受益于神经网络强大的建模能力，语义特征被简化为了仅仅只需要字符或音素序列的输入即可，同时声学特征的输出则由原本低维的倒谱上升到了更高维的线性语谱图。1c:T1513,## 前言最近接触了一种名叫“大富豪”(译名之一)的传统日式扑克牌游戏，国内好像知者甚少，故在此分享。 ## 简介 “大富豪”是一种类似我国斗地主规则的扑克游戏，游戏擅长以大逆转来炒热氛围。由于“大富豪”的名称、玩法规则各个地区都有差异（类似我国麻将）这里我主要介绍一种由我进行本地化改造的版本“大革命”。其实规则大体上和斗地主相似，如果会玩斗地主只需要看下相异之处即可。哦对了，游戏需要四个人来进行（当然你也可以自己修改 ## 基础规则 ### 场次一局游戏由多场组成，并由最后一场排名决定游戏最终排名，所以在最后一场之前即使是倒数第一也没关系！ **推荐一局游戏场数**：五场或十场 **单场胜利**：第一个出完手牌的人为第一名，其他人依次决出第二第三和第四名。 **在每场开局时**，随机抽出一张卡牌从游戏中除外，用来平衡卡牌数量并防止算牌。再下一场开始时，将上一场除外的这张牌加回牌堆并重新抽出一张牌除外。 ### 上下家 **上家**：在你之前出牌的那个人 **下家**：你出牌后出牌的那个人 ### 卡牌强度由弱到强依次为 3...K...2 即3最小，2最大，鬼牌稍后再说。 ### 出牌一场游戏由多轮出牌阶段构成。每轮的首位出牌者称为该轮的**主导者** 主导者可以打出如下所示的任意一种类型的任意牌，其他三家继续依照你的出牌类型接牌。第一场开始时由参赛玩家自行决定由谁当主导者，即由谁开始出牌。之后几场开始时由第四名率先出牌。 #### 可选出牌类型 **单牌**：一张牌 **对子**：两张一样的牌 **顺子**：三张一样的牌 **链子**：连续三张（或以上）**同样花色**的牌（例：红桃A 红桃2 红桃3 红桃4） **大革命**：四张相同的牌 ### 接牌你必须打出比你上家更大的同类型牌，即，你的上家出链子 3 4 5 时，你必须也出链子，且强度至少为 4 5 6，当然你也可以选择不出，来跳过你的回合，由下家出牌。 **当你打出牌后，其他三家都选择不出时，本轮接牌结束**。你成为新一轮的主导者。 ### 大革命当你打出大革命（即四张相同牌）时，**如果没有人接上**，将会进入革命阶段，此时卡牌强队将会发生反转！ **即由原来的 3最小2最大，变为2最小，3最大**。如果有人接上，卡牌强度将不会发生变化，视为革命发动失败，当然下家仍然可以继续接牌来发动大革命。（下下家还能接牌反制 ### 8切当你打出的牌型（单牌/对子/顺子/链子/大革命）中含有8时，其他三家不能接牌，必须选择不出。你成为主导者。 ### 鬼牌在本游戏中，鬼牌只有一张，所以游戏开始前请先将一张鬼牌除外。一副扑克牌54张，除外一张鬼牌 **并且** 每场开始前除外一张牌，正好剩下52张，每人13张牌，合理！鬼牌，视为最大的牌，并不受大革命影响，即它在平时比 2 大，在革命时比 3 大。鬼牌可以冒充任意一张牌使用，即它可以配牌，你可以**通过配牌发动大革命**，但当鬼牌冒充8的时候，**没有8切效果**。 **鬼牌不能最后打出，否则视为犯规，直接变成第四名！如果犯规者不是本场游戏的第一名，则此时不会触发一落千丈。** ### 黑桃3 黑桃3可以反制鬼牌，当鬼牌单张打出时，可以打出黑桃3进行反制，此时打出黑桃三者成为主导者。 ### 一落千丈上一场的第一如果本场没能成为第一，则当新的第一产生时他被迫成为第四名，手中的牌直接放入弃牌堆（扣着，不能公示给其他三家看）。剩下两人决出第二第三名。 ### 收税第四向第一交出最大的两张牌，第三向第二交出最大的一张牌。第一向第四交出任意的两张牌，第二向第三交出任意的一张牌。 **所有要交换的牌应在交换前选好，扣在桌子上，双方同时推给对方。** ## 可选规则 ### 抗税 **建议开启** **应用本项规则将提高大革命发动的频率** 即当缴税者手里存在三张相同的牌和鬼牌时，可以选择不交出鬼牌，由第二大的牌代替。但缴税者**仅可**将鬼牌用于配给其他三张牌来发动大革命。 ### 逃税即交出其他牌代替而不是最大的牌，当逃税者在游戏中使用逃掉的那张牌被应收税者发现时，将直接变成第四名。 ### 花色连锁 **建议专业人士开启** **应用本项规则将提高提高游戏难度，并对第一名产生一定程度的限制** 当你打出单张时，如果下家跟牌的花色与你打出的牌的花色相同则触发花色连锁，此时所有人只能出此花色的牌，当其他三家都不出时，你成为主导者。以上是基本连锁，又称两张触发连锁，同理还有三张触发连锁，可自行尝试。 ### 斗地主强度规则 **对于没玩过斗地主的玩家，可能更习惯于卡牌强度由1到13依次递增** 即强度由 3-2 变为由 A-K 此时 8切变为 6切黑桃3反击变为黑桃A反击 1d:T2830,今天自己写项目玩，想要实现一个类似邀请码的机制，没想到小小邀请码还真没那么简单 ## 需求分析首先是硬性需求： - 不可重复 - 单射看到这两点需求，我第一反应就是 Hash，但是Hash需要处理冲突，并不是一个很好的解决方案。另外出于美学之类的考虑，我们还有一些别的需求，毕竟谁也不想面对面分享邀请码的时候拿出来一串 ``18ce3ca04a725cc6b57d5ec0ae0ccd66`` 这样的~~乱码~~吧非硬性需求： - 定长 - 不易被推测出规律 - 效率高 - 支持并发 - 可溯源仔细思考了一下 Hash 的可行性后我决定放弃这种方案... ## 方案分析群里的菊苣给出了洗牌算法的方案，这是一个预生成的方案这里就预生成方案统一分析 ### 预生成讲真，不考虑别的因素，预生成方案确实不错，洗牌算法也非常的棒这种方案的思想是根据随机生成算法，预先生成一批邀请码，然后将这些邀请码缓存，当用户请求时将其分配给用户，当邀请码分配完时，再生成一批，如此循环。 #### 弊端 - 每次重新生成时都要检查是否重复 ~~而且多数情况下都为否~~ - 邀请码本身需要持久化存储 - 用户和邀请码的关系需要记录对于唯一性我啪的一下就想到了 UUID 和 MD5，~~很快啊~~ MD5作为一种 Hash 在一开始就被我放弃了，接下来我们看一下 UUID ## UUID 引用一下Wikipedia的说法 > 通用唯一识别码（英语：Universally Unique Identifier，缩写：UUID）是用于计算机体系中以识别信息数目的一个128位标识符，根据标准方法生成，不依赖中央机构的注册和分配，UUID具有唯一性，这与其他大多数编号方案不同。重复UUID码概率接近零，可以忽略不计。这下唯一性是真的强，但是分享一串128位标识符的画面确实也很美... 没啥好想法的我上网搜了一下，又得到了两种方案，一种类似于Base64，这种没啥好说的，接下来主要说一下另一种方案 ### 密码学方案这种方案本质上是一个实现了由用户ID空间到邀请码空间的双射，通过用户ID确定了邀请码的唯一性，同时又可通过反函数来对邀请码溯源，既不需要保存邀请码，又不需要保存关系，针不戳我们先来写个简单函数实现双射 ```go func test(id uint) { const Chars = "0123456789ABCDEF" const CodeLength = 6 const Base = 16 const Salt = 233 pid := id + Salt // 为了避免用户 ID的直接泄漏，我们可以先加点盐 var b [CodeLength] uint b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = b[i]% Base } fmt.Printf("ID: %-2d ---> %c %c %c %c %c %c\n",id, Chars[b[5]],Chars[b[4]],Chars[b[3]],Chars[b[2]],Chars[b[1]],Chars[b[0]]) } ``` 这个函数本质上和进制转换函数没什么区别，我们跑一下看看效果 ``` ➜ test go run test.go ID: 0 ---> 0 0 0 0 E 9 ID: 1 ---> 0 0 0 0 E A ID: 2 ---> 0 0 0 0 E B ID: 3 ---> 0 0 0 0 E C ID: 4 ---> 0 0 0 0 E D ID: 75 ---> 0 0 0 1 3 4 ID: 76 ---> 0 0 0 1 3 5 ID: 77 ---> 0 0 0 1 3 6 ID: 78 ---> 0 0 0 1 3 7 ID: 79 ---> 0 0 0 1 3 8 ``` 啊这...这完全在预料之中，~~换下Chars里字母的顺序也能当个凯撒密码用用~~ 好吧不就是看起来太规律了么，我们来把这个结果用密码学方法扩散和混淆一下 #### 扩散和混淆在密码学当中，混淆（confusion）与扩散（diffusion）是设计密码学算法的两种主要方法。这样的定义最早出现在克劳德·香农1945年的论文《密码学的数学理论》当中。在克劳德·香农的定义之中，混淆主要是用来使密文和对称式加密方法中密钥的关系变得尽可能的复杂；而扩散则主要是用来使用明文和密文关的关系变得尽可能的复杂，明文中任何一点小更动都会使得密文有很大的差异。混乱用于掩盖明文与密文之间的关系。这可以挫败通过研究密文以获取冗余度和统计模式的企图。做到这一点最容易的方法是“代替”。扩散通过将明文冗余度分散到密文中使之分散开来。即将单个明文或密钥位的影响尽可能扩大到更多的密文中去。产生扩散最简单的方法是换位（置换）。改进后的算法如下 ```go func test(id uint) { const Chars = "0123456789ABCDEF" const CodeLength = 6 const Base = 16 const Salt = 233 const Prime = 7 pid := id * Prime + Salt // 放大 var b [CodeLength] uint b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = (b[i] + uint(i) * b[0]) % Base } fmt.Printf("ID: %-2d ---> %c %c %c %c %c %c\n",id, Chars[b[5]],Chars[b[4]],Chars[b[3]],Chars[b[2]],Chars[b[1]],Chars[b[0]]) } ``` 这里我们给用户ID放大的时候乘了个和 Base 互质的数 Prime，这是基于循环群的性质：若 m 和 p 互质，则 ( id * m ) % p 的结果遍历[0, p) 的所有整数。这保证了放大后结果的分布和原数据的分布同样均匀。让我们来跑一下试试： ``` ➜ test go run test.go ID: 0 ---> 0 4 B 2 7 9 ID: 1 ---> 0 0 0 0 F 0 ID: 2 ---> 0 C 5 E 6 7 ID: 3 ---> 0 8 A C D E ID: 4 ---> 0 4 F B 5 5 ID: 75 ---> 0 8 2 E 5 6 ID: 76 ---> 0 4 7 C C D ID: 77 ---> 0 0 C B 4 4 ID: 78 ---> 0 C 1 9 B B ID: 79 ---> 0 8 6 7 3 2 ``` 啊这...怎么开头全是0啊...算了，正好拿它做校验位，顺便再给结果洗个牌最终代码如下 ```go func test(id uint) { const Chars = "0123456789ABCDEF" const CodeLength = 6 const Base = 16 const Salt = 233 const Prime = 7 const Prime2 = 5 pid := id * Prime + Salt // 放大 var b [CodeLength] uint b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = (b[i] + uint(i) * b[0]) % Base } // 校验位 for i := 0; i < CodeLength-1; i++ { b[CodeLength-1] += b[i] } b[CodeLength-1] = b[CodeLength-1] * Prime % CodeLength fmt.Printf("ID: %-2d ---> ",id) for i := 5; i >= 0; i-- { fmt.Printf(" %c",Chars[b[(i*Prime2) % CodeLength]]) // 洗牌 } fmt.Printf("\n") } ``` 这里用了一个和 CodeLength 互质的数 Prime2 对生成结果进行了洗牌，原因和之前的 Prime 一样跑一下看看效果 ``` ➜ test go run test.go ID: 0 ---> 7 2 B 4 3 9 ID: 1 ---> F 0 0 0 3 0 ID: 2 ---> 6 E 5 C 2 7 ID: 3 ---> D C A 8 3 E ID: 4 ---> 5 B F 4 4 5 ID: 75 ---> 5 E 2 8 5 6 ID: 76 ---> C C 7 4 0 D ID: 77 ---> 4 B C 0 1 4 ID: 78 ---> B 9 1 C 2 B ID: 79 ---> 3 7 6 8 2 2 ``` ohhhhhhhhh 效果相当不错！ #### 解码具体解码流程就是上面的最终函数倒过来写，可能反函数不太好理解，在纸上推一下就好了 ```go func test2(code string) int{ if len(code) != CodeLength { return -1 } var b [CodeLength] uint // 反洗牌 for i := 0; i < CodeLength; i++ { b[(i*Prime2) % CodeLength] = uint(i) } // 转换回 Chars 下标 for i := 0; i < CodeLength; i++ { j := strings.Index(Chars, string(code[b[i]])) if j == -1 { return -1 // 非法字符检查 } b[i] = uint(j) } // 校验 var expect uint for i := 0; i < CodeLength-1; i++ { expect += b[i] } expect = expect * Prime % CodeLength if b[5] != expect{ return -1 } // 反函数 for i := CodeLength-2; i >=0; i-- { b[i] = (b[i] - uint(i) * (b[0] - Base)) % Base } var res uint = 0 for i := CodeLength-2; i >0; i-- { res += b[i] res *= Base } // 反放大 res = ((res + b[0]) - Salt) / Prime fmt.Printf("%d\n",res) return int(res) } ``` 需要注意的是我们之前是从b[5]...b[0]反着print的所以解码的时候记得倒一下 ```go test(76) // CC740D test2("D047CC") // 因为我们之前是反着print的 ``` 最终输出如下 ``` ➜ test go run test.go ID: 76 ---> C C 7 4 0 D 76 ``` 稍微分析一下，6位16进制邀请码，1位校验，可用范围为0x00000到0xFFFFF，减去扩大和加盐带来的损耗，大概能生成14万个邀请码，对于我来说是够用了，如果你觉得少的话可以 - 扩大Base，比如用32进制或者64进制~~（其实我本人用的10进制，只有数字多好看啊小声bb）~~ - 增加邀请码位数，8位不也挺好的么？ ## 最终代码思路验证完毕，让我们把函数的输出补上，并把第一个函数的输出给倒回来，顺便润润色 ```go package main import ( "fmt" "strings" ) const Chars = "0123456789ABCDEF" const CodeLength = 6 const Salt = 233 const Prime = 7 const Prime2 = 5 const Base = uint(len(Chars)) func main() { str := genCode(76) decode(str) } func genCode(id uint) string{ var b [CodeLength] uint var res string pid := id * Prime + Salt //扩大 b[0] = pid for i := 0; i < CodeLength-1; i++ { b[i + 1] = b[i] / Base b[i] = (b[i] + uint(i) * b[0]) % Base } // 校验位 for i := 0; i < CodeLength-1; i++ { b[CodeLength-1] += b[i] } b[CodeLength-1] = b[CodeLength-1] * Prime % CodeLength for i := 0; i < CodeLength; i++ { res += string(Chars[b[(i*Prime2)%CodeLength]]) // 洗牌 } fmt.Println(res) return res } func decode(code string) int{ if len(code) != CodeLength { return -1 } var b [CodeLength] uint // 反洗牌 for i := 0; i < CodeLength; i++ { b[(i*Prime2) % CodeLength] = uint(i) } // 转换回 Chars 下标 for i := 0; i < CodeLength; i++ { j := strings.Index(Chars, string(code[b[i]])) if j == -1 { return -1 // 非法字符检查 } b[i] = uint(j) } // 校验 var expect uint for i := 0; i < CodeLength-1; i++ { expect += b[i] } expect = expect * Prime % CodeLength if b[5] != expect{ return -1 } // 反函数 for i := CodeLength-2; i >=0; i-- { b[i] = (b[i] - uint(i) * (b[0] - Base)) % Base } var res uint = 0 for i := CodeLength-2; i >0; i-- { res += b[i] res *= Base } // 反放大 res = ((res + b[0]) - Salt) / Prime fmt.Printf("%d\n",res) return int(res) } ``` ## Reference - https://my.oschina.net/bravozu/blog/1827254 ~~这老哥代码有问题（小声bb~~ - https://zh.wikipedia.org/wiki/P盒 - https://zh.wikipedia.org/wiki/循環群 - https://zh.wikipedia.org/wiki/通用唯一识别码 - https://www.knowpia.cn/pages/混淆与扩散

使用 JavaScript 实现一个基于 FSM 的 http 请求头 parser