利用Bloom filter達到次線性運算時間的字串比對系統及方法

Abstract

本發明係揭露一種字串比對系統,其包含一待測字串、複數個特徵字串、一M位元組搜尋視窗及複數個過濾模組。其中,M位元組搜尋視窗係用以由待測字串中擷取一M位元組字串,而每一過濾模組係包含複數個特徵字串之子字串,用以與M位元組字串進行比對,以輸出M位元組搜尋視窗之一位移長度。藉由一次移動搜尋視窗多個位元組,可達到同時比對多個位元組的加速效果。同時,利用Bloom filter這種較節省空間的儲存特徵字串方式,可以讓大量的特徵字串能存在單一晶片的內嵌式記憶體當中。