嵌入式系统的海量信息高效正则匹配算法

摘要：

受嵌入式系统的软硬件资源限制,目前在路由器中对于海量路由表的正则匹配查找,各大网络厂商普遍存在处理效率较低问题.目的是研究一种应用于实时嵌入式软件系统中,符合正则匹配语法的海量路由信息搜索技术.提供的高效正则匹配搜索算法的方法关键是减少正则匹配的路由搜索范围,为此需要建立一个以数字为索引的快速倒排索引结构.基于快速倒排索引结构.首先确定符合部分正则匹配摘要的路由较小范围,然后进一步对此小范围的每条路由进行精确正则匹配,以确定符合条件的所有路由.研究结果表明,对于一般正则匹配长度10-30的查找,平均查找时间快了约30倍,且随着正则匹配长度增加,查找效率呈指数级提高.当采用内存方式记录时,索引位置信息的内存平均约占总路由容量内存空间的3%.由此可见,以海量路由信息为研究对象,给出的数字正则匹配算法,不仅在索引搜索时间上而且在索引信息存储空间上都十分理想,可广泛应用于嵌入式软件系统中的海量信息快速正则匹配.

关键词：嵌入式系统、海量信息搜索、正则匹配查找

所属期刊栏目：45

分类号：TP301(计算技术、计算机技术)

在线出版日期：2009-05-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：114-116