2022-08-08-分享一波昨天的算法可视化分析

2022.08.07

• [第一二批] 反向位集可视化结果

  • 可视化分析：

    同样是一张可视化图，可以是一维的，可以是二维的，也可以是三维的、四维的。
    1d"y=k"：满1百分比，即所有属性上的所有位集的64位连续1出现的次数/总共有多少个64位
    2d"y=f(x)"：每个属性上的满1百分比，x维是属性，y维是属性上所有位集64位连续1出现的百分比
    3d"z=f(x,y)"：每个属性的每个位集上的满1百分比，x-属性，y-位集号，z-这个位集上出现64位连续1的百分比
    4d"v=f(x,y,z)"：每个属性的每个位集的每个64位单元号上是64个1则取1，有0则取0

    只考虑单个属性，可以在二维上用两种颜色画出3维的效果：x-位集号，y-单元号，值为0画白色正方形，为1画红色正方形，再在z维上每隔一个单位话一张二维图片，厚度为0，因为为1就看不到立方体里面的颜色了

    可以手动画许多个二维的图片可视化每个属性

    再考虑数据集，那就是5d了：（datasetNo, attributeNo, bitsetNo, unitNo, value）

         https://media.githubusercontent.com/media/shiwanghua/ACL/main/backward_bitsets_visualization.txt

  • 链接是17个数据集 反向匹配 8个属性的全部统计数据

  • 每个数据集分3种粒度可视化：

    1. 属性上64位个1的出现个数及百分比
    2. 属性--256个位集上每个位集里 64位1 出现次数
    3. 属性--256个位集上-- nrules/64 个单元 每个单元是否为64个1，是则取1不是则取0

• 反向位集查找之定量确定属性处理顺序

  • 背景
    • 不同属性上数据集倾斜度不一样：总体 1、0 的个数不一样、64位全为 1 的单元个数不一样
    • 同一属性上不同位集倾斜度不一样：64位全为 1 的单元个数不一样，这些全 1 单元的出现顺序即优先级不一样
  • 设每个位集有 u 个单元，每个属性上定义了 256 个位集，一共 8 个属性
  • 基本思路：对每个位集求加权指标，表示“查找成本”
    • 每个位集上从后往前，单元权重分别赋为 1，2，⋯，u
    • 如果单元里 64 位全为 1，则“查找成本”为 0，对其做或运算后无需继续往下和其他属性做或运算、无需检查
    • 如果单元里 64 位不全为 1，则“查找成本”为 其中 0 的个数乘以这个单元的权重
    • 第 i 个属性第 j 号位集的“查找成本”为 checkcost=∑uw=1w⋅zeros(Uu−w+1ij)
  • 静态顺序 static order
    • 求每个属性的“查找成本”，即属性上 256 个位集的“查找成本”之和
    • 对 8 个属性的“查找成本”排序，查找时优先对“查找成本”低的位集做或运算，得到 64 个 1 即可停止
  • 动态顺序 dynamic order
    • 初始化时求好 8*256 个位集的匹配成本
    • 处理每个报文时，先取出 8 个属性上对应的位集号，对应 8 个“查找成本”
    • 对这 8 个“查找成本”排序，即得到处理属性的先后顺序
  • 分析：
    • 没有减少检查次数（平均检查次数一般很少，1～20，成本相对做或运算的成本很小）
    • 减少的是纵向或运算次数
    • 横向或运算轮次没减少，还是得做到第一条匹配规则为止
    • 纵向每轮最多需要做 7 次或运算，由于优先对 1 更多的位集做或运算，所以可以更快得到 64 位 1