论文研究;.pdf

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