0%

前几天看了酷壳上的一篇文章如何测试洗牌程序,之后仔细看了Wikipedia对Fisher–Yates shuffle算法的介绍,这里简单的总结一下,基本是翻译Wikipedia。

Fisher and Yates’ original method

该算法最初是1938年由Ronald A. Fisher和Frank Yates在《Statistical tables for biological, agricultural and medical research》一书中描述,算法生成1-N个数的随机排列的过程如下:

  1. 原始数组中有数字1到N
  2. 设原始数组未被标记的数字个数为k,生成一个1到k之间的随机数
  3. 取出原始数组未被标记数字中的第k个,将其标记并插入到新的排列数组尾端。
  4. 重复过程2直到原始数组中没有未被标记的数字
  5. 过程3中生成的新数组就是一个对原始数组的随机排列

该算法可以理解为已知有n个元素,先从n个元素中任选一个,放入新空间的第一个位置,然后再从剩下的n-1个元素中任选一个,放入第二个位置,依此类推。算法在过程3查找未被标记的第k个数字有很多重复操作,导致算法效率并不高,总的时间复杂度为O(N^2 ),空间复杂度为O(N)。算法的python实现如下所示:

Read more »

背景

最近在做的数据库活动检测引擎,要实现一个异常行为检测的模块。简单的说异常行为检测就是先确定描述用户访问数据库的行为模型,然后定义一系列描述正常访问数据库的行为,检测过程中一旦用户行为与正常行为轮廓不符,则被认定为攻击行为。在实际系统中,正常行为轮廓会组成正常行为知识库,这个知识库会很大,所以正常行为轮廓不能简单的人工定义,于是一个自动挖掘正常行为知识库的需求被提了出来。

在系统实现过程中,会将用户对数据库产生影响的原子性操作,比如一次select,一次update抽象成为一个item,用户访问数据库的一系列行为可以抽象成为一个item的序列,由此引出了通过频繁序列挖掘来获得正常行为知识库的想法。

频繁序列挖掘

Read more »

似乎应该在这里说些什么。。。