专利进阶(二)：专利撰写常用技术及算法汇总（持续更新中）

一、前言

专利撰写过程中使用已有技术或算法解决新问题非常常见，本篇博文主要梳理软件发明专利撰写过程中涉及的常用技术及算法。

二、常用技术及算法

2.1 区跨链技术

2.2 聚类算法

2.3 边缘算法

2.4 蚁群算法

蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明：一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体之间的行为是相互作用相互影响的。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为信息素的物质,而此物质恰恰是蚂蚁个体之间信息传递交流的载体。蚂蚁在运动时能够感知这种物质,并且习惯于追踪此物质爬行,当然爬行过程中还会释放信息素。一条路上的信息素踪迹越浓,其它蚂蚁将以越高的概率跟随爬行此路径,从而该路径上的信息素踪迹会被加强,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。某一路径上走过的蚂蚁越多,则后来者选择该路径的可能性就越大。蚂蚁个体之间就是通过这种间接的通信机制实现协同搜索最短路径的目标的。

群蚁算法的2个核心步骤是：路径构建 和 信息素更新。

2.4.1 路径构建

每个蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。

上述公式就是计算当前点到每一个可能的下一个节点的概率。分子是信息素强度和能见度的幂乘积，而分母则是所有分子的和值。这个刚开始是很不容易理解的，我们在最后实例计算的时候，可以看得很清楚，再反过来理解公式。注意每次选择好节点后，就要从可用节点中移除选择的节点。

2.4.2 信息素更新

信息素更新是群蚁算法的核心。也是整个算法的核心所在。算法在初始期间有一个固定的浓度值，在每一次迭代完成之后，所有出去的蚂蚁回来后，会对所走过的路线进行计算，然后更新相应的边的信息素浓度。很明显，这个数值肯定是和蚂蚁所走的长度有关系的，经过一次次的迭代，近距离的线路的浓度会很高，从而得到近似最优解。

信息素更新的作用：

1. 信息素挥发(evaporation)信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。
2. 信息素增强(reinforcement)增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。基本蚁群算法的离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问后，统一对残留信息进行更新处理。

迭代与停止

迭代停止的条件可以选择合适的迭代次数后停止，输出最优路径，也可以看是否满足指定最优条件，找到满足的解后停止。最重要的是，我刚开始理解这个算法的时候，以为每一只蚂蚁走一条边就是一次迭代，其实是错的。这里算法每一次迭代的意义是：每次迭代的m只蚂蚁都完成了自己的路径过程，回到原点后的整个过程。

2.5 哈希算法

Hash算法或称为散列算法，是将任意长度的二进制值映射为较短的固定长度的二进制值，这个映射值称为哈希值。

例如计算一段话“hello blockchain world，this is yeasy@github”的SHA-256 Hash值。

这意味着对于某个文件，无需查看其内容，只要其SHA-256 Hash计算后结果同样为db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90，则说明文件内容极大概率上就是“hello blockchain world，this is yeasy@github”。

Hash值在应用中又常被称为指纹（fingerprint）或摘要（digest）。Hash算法的核心思想也经常被应用到基于内容的编址或命名算法中。

一个优秀的Hash算法将能实现如下功能：

• 正向快速：给定明文和Hash算法，在有限时间和有限资源内能计算得到Hash值；

• 逆向困难：给定（若干）Hash值，在有限时间内很难（基本不可能）逆推出明文；

• 输入敏感：原始输入信息发生任何改变，新产生的Hash值都应该出现很大不同；

• 冲突避免：很难找到两段内容不同的明文，使得它们的Hash值一致（发生碰撞）。

冲突避免有时候又称为“抗碰撞性”，分为“弱抗碰撞性”和“强抗碰撞性”。如果给定明文前提下，无法找到与之碰撞的其他明文，则算法具有“弱抗碰撞性”；如果无法找到任意两个发生Hash碰撞的明文，则称算法具有“强抗碰撞性”。

2.5.1 常见算法

目前常见的Hash算法包括MD5和SHA系列算法。

MD4（RFC 1320）是MIT的Ronald L.Rivest在1990年设计的，MD是Message Digest的缩写。其输出为128位。MD4已被证明不够安全。

MD5（RFC 1321）是Rivest于1991年对MD4的改进版本。它对输入仍以512位进行分组，其输出是128位。MD5比MD4更加安全，但过程更加复杂，计算速度要慢一点。MD5已被证明不具备“强抗碰撞性”。

SHA（Secure Hash Algorithm）并非一个算法，而是一个Hash函数族。NIST（National Institute of Standards and Technology）于1993年发布其首个实现。目前知名的SHA-1算法在1995年面世，它的输出为长度160位的Hash值，抗穷举性更好。SHA-1设计时模仿了MD4算法，采用了类似原理。SHA-1已被证明不具备“强抗碰撞性”。

为了提高安全性，NIST还设计出了SHA-224、SHA-256、SHA-384和SHA-512算法（统称为SHA-2），跟SHA-1算法原理类似。SHA-3相关算法也已被提出。

目前，MD5和SHA1已经被破解，一般推荐至少使用SHA2-256或更安全的算法。

提示⚠️：MD5是一个经典的Hash算法，和SHA-1算法一起都被认为安全性已不足应用于商业场景。

Hash算法一般都是计算敏感型的。意味着计算资源是瓶颈，主频越高的CPU运行Hash算法的速度也越快。因此可以通过硬件加速来提升Hash计算的吞吐量。例如采用FPGA来计算MD5值，可以轻易达到数十Gbps的吞吐量。

也有一些Hash算法不是计算敏感型的。例如scrypt算法，计算过程需要大量的内存资源，节点不能通过简单地增加更多CPU来获得Hash性能的提升。这样的Hash算法经常用在避免算力攻击的场景。

2.6 数字摘要

数字摘要是将任意长度的消息变成固定长度的短消息，它类似于一个自变量是消息的函数，也就是Hash函数。数字摘要就是采用单向Hash函数将需要加密的明文“摘要”成一串固定长度（128位）的密文。这一串密文又称为数字指纹，它有固定的长度，而且不同的明文摘要成密文，其结果总是不同的，而同样的明文其摘要必定一致。

顾名思义，数字摘要是对数字内容进行Hash运算，获取唯一的摘要值来指代原始完整的数字内容。数字摘要是Hash算法最重要的一个用途。利用Hash函数的抗碰撞性特点，数字摘要可以解决确保内容未被篡改过的问题。

细心的小伙伴可能会注意到，从网站下载软件或文件时，有时会提供一个相应的数字摘要值。用户下载原始文件后可以在本地自行计算摘要值，并与提供的摘要值进行比对，可检查文件内容是否被篡改过。

数字摘要使用场景如下：

1. 被发送文件用SHA编码加密产生128bit的数字摘要。
2. 发送方用自己的私用密钥对摘要再加密，这就形成了数字签名。
3. 将原文和加密的摘要（数字签名）同时传给对方。
4. 对方用发送方的公共密钥对摘要解密，同时对收到的文件用SHA编码加密产生又一摘要。
5. 将解密后的摘要和收到的文件在接收方重新加密产生的摘要相互对比。如两者一致，则说明传送过程中信息没有被破坏或篡改过。否则不然。

2.7

2.8

2.9

2.10

三、拓展阅读

• 《专利进阶(一)：软件专利工程师浅谈如何针对计算机软件类专利申请进行技术挖掘》