利用Bloom filter达到次线性运算时间的字串比对系统及方法

摘要

本发明系揭露一种字串比对系统,其包含一待测字串、复数个特征字串、一M位元组搜寻视窗及复数个过滤模组。其中,M位元组搜寻视窗系用以由待测字串中撷取一M位元组字串,而每一过滤模组系包含复数个特征字串之子字串,用以与M位元组字串进行比对,以输出M位元组搜寻视窗之一位移长度。藉由一次移动搜寻视窗多个位元组,可达到同时比对多个位元组的加速效果。同时,利用Bloom filter这种较节省空间的储存特征字串方式,可以让大量的特征字串能存在单一晶片的内嵌式记忆体当中。