CAJ | 학술논문

正则表达式匹配技术在网络应用中面临两方面的制约，一方面，复杂或大规模规则导致DFA存储空间急剧膨胀，现有的内存容量难以支撑；另一方面，传统计算机架构的DFA处理能力有限，很难满足高速网络流的线速处理需求。因此，提出一种基于FPGA使用改进游程编码压缩DFA的高速正则表达式匹配算法。实现了基于改进游程编码的DFA引擎架构、分组存储与多路并行比较器技术。该算法不仅具有游程编码的压缩效果，而且压缩后的DFA实现一次状态转移只需2个时钟周期。
정칙표체식필배기술재망락응용중면림량방면적제약，일방면，복잡혹대규모규칙도치DFA존저공간급극팽창，현유적내존용량난이지탱；령일방면，전통계산궤가구적DFA처리능력유한，흔난만족고속망락류적선속처리수구。인차，제출일충기우FPGA사용개진유정편마압축DFA적고속정칙표체식필배산법。실현료기우개진유정편마적DFA인경가구、분조존저여다로병행비교기기술。해산법불부구유유정편마적압축효과，이차압축후적DFA실현일차상태전이지수2개시종주기。
DFA for regular expression matching has the advantage of speed; however, it has the disadvantage of space expansion caused by the complex semanteme of the rule or the large-scale rule set. This seriously constrains the application of regular expression matching based on network flow which requires wire-speed matching packages. Consequently, this paper proposes a new algorithm using an improved run length encoding (iRLE) to compress the DFA memory space based on FPGA, which can dynamically access to the element of the compressed DFA. For the implementation of the new algorithm, this paper designs a DFA engine, group-store (for iRLE items) and multi-way parallel comparators techniques. The algorithm has good compression ratio as RLE; and its time complexity, 2 cycles per state transition, is equivalent to the original DFA's O (1).