[数据结构与算法]一种基于遗传算法的正则推断实现

敏感数据发现

数据安全问题已经逐渐成为全行业关注的问题，尤其是个人信息保护相关法律即将开始实行的阶段，使得数据安全几乎与每一个人息息相关。在行业已经普遍认可数据安全的前提是对企业内部所有数据进行敏感数据发现和分类分级的情形下，不管在技术上还是产品上都会热衷于讨论一个问题，如何发现企业内的敏感数据，或者说如何更有效，更智能，更自动地发现企业内任何一种想要识别的数据信息。业界不乏有各种创新的思路来推进这个方向，其中根据一批样本，自动推断出能够尽量匹配这些样本的一个正则表达式，我们就可以做到，敏感数据发现和分类分级过程中，在已知某一字段属于某一数据类型，那么就很容易自动生成一个特征正则串，以此来发现更多未知的数据，并且优化在于，这种方法相比于通用匹配算法来讲，会更加适应于某一个企业的特殊数据。今天要讨论的就是这个话题。

正则自动推断

故名思议，正则自动推断就是根据数据样本来自动生成能够匹配样本的合法正则。通常情况下是根据一条数据样本来生成正则来提取重要信息。一般出现在日志采集过程中。因为日志采集中重要的步骤是把原日志文件中的第一行记录，通过预设的正则来提取关键信息。这个过程往往需要使用人员熟悉正则的语法，然后根据不同规范的日志文件配置不同的正则提取。有些比较智能的产品就可以直接实现根据用户对关键信息的框选，自动生成一个满足用户意图的正则。
但在敏感数据发现场景下，根据一条记录去生成正则意义不大，我们需要的是充分计算目标数据集的特征来生成一条尽量匹配所有数据的正则。此时的思路是完全不一样的。

难点

根据一批相同类型数据样本，生成一条正则的难点有以下几处：

• 根据每条样本生成的信息片断更深多，当组成候选正则时导致解空间非常大，计算资源消耗在通用平台上无法接受，即使使用动态规划之类的优化算法，效果也不太理想
• 不同类型的数据在表现形式上很可能类似，一些与该类型特性的信息不好提取，比如同是 18 位的身份证和银行卡号。某些位上的特殊定义信息需要提取出来
• 正则是有自己的语法规则的，生成的正则表达式需要满足语法规范

实现思路

我们可以分以下几步来简化解决方案，目前仅以等长样本为例。

1. 主成份分析。对目标样本进行主成份提取，比如每一位上字符类型，字符频率，是否为高频字符对(BPE算法)，以此生成该位的候选正则片断；
2. 语法树。通过语法树建模从一个样本随机生成一棵正则树，该树可以通过相同的遍历算法（如深度优选）来还原出来正则表达式；
3. 评分体系。设计评分体系来判定每一个正则的优劣。可以考虑多个维度，比如目标样本命中率，正则长度（越接近样本平均长度，分数越高），正则中字符或者范围表达式所占的比例。评分体系对后面的遗传算法有极大影响；
4. 遗传算法。把生成的候选正则，通过遗传算法，经过杂交，变异等方式，产生新的候选种群，根据评分体系评选出优质的种子进入到下一轮迭代，进而收敛到优质解。

主成份分析

主成份分析是根据每一位字符的特征确定该位的候选正则片断。比如如果样本中第一位都是数字，那么就可以初始化为 \d，以此类推。主成份分析的方法的角度有很多，这里只提其中两个。

字符统计

如果某一位始终没有出现过某个数字或者字符，或者某一位只出现过一个字符，我们就可以根据这个特征来确定候选正则。并且也可以通过字符统计挖掘出其它信息。

BPE

BPE 一般被用于自然语言处理中用来提取常用的字符对的。思路见下图。

1. 目标字符 {"low":5, "lower":2, "newest":6, "widest":3}, 这里的数字代表该单词出现次数
2. 拆分字符,每个单词拆成单个字符 {"l o w":5, "l o w e r":2, "n e w e s t":6, "w i d e s t":3}
3. 依次合并第一个字符形成字节对，{"lo ow":5, "lo ow we er":2, "ne ew we es st":6, "wi id de es st":3}
4. 计算得到，出现频率最高的为 es, 出现的频数为 9 = 6 + 3, 频率为 7/16。因此合并成一个对，那么当前情况为 {"l o w":5, "l o w e r":2, "n e w es t":6, "w i d es t":3}
5. 再次把字符或字符对前后合并，这次会发现，需要合并的为 est，依次迭代
6. 直到收敛为不能合并，或者达到最大合并限定次数为准，结果为 {"low":5, "low e r":2, "n e w est":6, "w i d est":3}

此时组成字节对的就是我们需要使用的候选集，当为某一个样本生成正则时，如果遇到 BPE 就需要直接初始化为字符对。另外常规的 BPE 算法没有位置信息，而在敏感数据发现时，某一个 BPE 所出现的位置本身来讲就表征着一些信息在，可以为每一个字节对添加上位置信息，然后再对比是否合并操作，这样得到字节对串就更适用于样本特征信息。

语法树

可以按照以下思路构建一个语法树，比如叶子节点只放范围表达式，非叶子节点只放限制符，或者其它需求节点。并且生成树的时候可以附带一些随机性。代码片断见下图。

public void grow(String regexSegment, boolean isKeyFeature) {

        TerminalNode node = new TerminalNode(regexSegment);

        node.setKeyFeature(true);

        // Should recompute the length of tree
        length = -1;

        if (current == null) {
            // If the tree is none
            current = node;
            root = current;
            return;
        }

        if (Math.random() > 0.5) {
            // Grow up
            ConcatNode concatNode = new ConcatNode();
            concatNode.setLeft(root);
            concatNode.setRight(node);
            current = node;
            root = concatNode;
        } else {
            // Grow down
            if (!(root instanceof FunctionNode)) {
                ConcatNode concatNode = new ConcatNode();
                concatNode.setLeft(root);
                concatNode.setRight(node);
                current = node;
                root = concatNode;
            } else {
                ConcatNode concatNode = new ConcatNode();
                ((FunctionNode)current.getParent()).setRight(concatNode);
                concatNode.setLeft(current);
                concatNode.setRight(node);
                current = node;
            }
        }
    }

评分体系

评分体系对最后甄选合适种子至关重要，需要精心定义到底哪些候选正则可以迭代到下一代。可以考虑以下维度。

1. 候选正则长度
2. 范围表达式所占比例
3. 正样本命中率，负样本不命中率，即查全率和查准率
   需要注意，需要把多个维度规范化到一个评分区间，比如第一个维度取值区间都泛化为 0~1，也可以调整权重用来突显某一个维度。

遗传算法

一般步骤如下：

1. 随机选择两个亲本，选择策略是上一轮分高的需要被更大概率选中，可以使用轮盘选择算法
2. 随机保留一些亲本进入到下一代种群
3. 对语法树上某些节点进行杂交处理，交换一些特征信息，重要特征信息可以不杂交。产生两个个体
4. 对每个个数上，根据变异率，随机变异某个节点，重要特征可以不变异
5. 迭代出足量种群，计算适应率（评分），选出若干个得分高的种群个体，进入到下一轮迭代
6. 如果达到迭代限制或者，样本评分满分了即得到目标解。

private List<Tree> epoch() {

        List<Tree> newGenomes = new ArrayList<>();

        while (newGenomes.size() < populationSize << 1) {

            Tree dad = rouletteWheelSelection();
            Tree mum = rouletteWheelSelection();

            // Keep
            if (Math.random() < RATE_KEEP) {
                newGenomes.add(dad);
                newGenomes.add(mum);
                continue;
            }

            // Crossover
            TupleTree children = crossover(dad, mum);
            if (children == null) {
                continue;
            }

            Tree child0 = children.getFirst();
            Tree child1 = children.getSecond();

            // Mutate
            mutate(child0);
            mutate(child1);

            newGenomes.add(child0);
            newGenomes.add(child1);
        }

        return newGenomes;
    }

后语

遗传算法是一个不利用现有狭义的编程思维，即线性解题思维来设计的算法，是通过生物学理念来收敛答案，得到目标解的，非常有意思。它可以只要求把问题解抽象成目标解编码。然后交给遗传理念来择优解，然后不断迭代来解决问题的。当然它不保证每次得到最优解，但生物理论中的“物况天择”已经证明，适应率更高的基因信息总是会在竞争中保存下来。这种思路会给我们解决问题一个另外的视野。

引用：
https://xueshu.baidu.com/usercenter/paper/show?paperid=662e899f4a27bf3dce3bd882cd2c6535

From: 观安信息无限实验室