원문정보
보안공학연구지원센터(IJHIT)
International Journal of Hybrid Information Technology
Vol.6 No.4
2013.07
pp.83-94
피인용수 : 0건 (자료제공 : 네이버학술정보)
초록
영어
Most of the current string matching algorithms behave slowly when the amount of patterns increases. In this paper a fast matching algorithm named SSEMatch was designed. PHADDW instruction from SSE (Streamed SIMD Extension) set was used in SSEMatch to produce data confusion, by which the patterns can be distributed into pseudo hash address such that there will be less patterns left for verification matching. With the help of PHADDW, the whole matching time was reduced. Our SSEMatch holds a O(n/m) complexity. Experiment shows that similarly to WM algorithm, SSEMatch performs better when the length of the shortest pattern increases. Also when the amount of patterns increases SSEMatch performs better than WM.
목차
Abstract
1. Introduction
2. Related Work
2.1. The Characters of SSE Instructions Set
2.2. The Characters of AC and WM
3. String Matching Algorithm Based On Horizontal Instruction
3.1. Evenly Distribution of 2 rounds of PHADDW
4. Experimental Results
4.1. The Memory’s Demand of SSEMatch
4.2. The Amount of Patterns Needs to be Verified of SSEMatch and WM
4.3. The Matching Speed of SSEMatch and WM
5. Conclusion
Acknowledgements
References
1. Introduction
2. Related Work
2.1. The Characters of SSE Instructions Set
2.2. The Characters of AC and WM
3. String Matching Algorithm Based On Horizontal Instruction
3.1. Evenly Distribution of 2 rounds of PHADDW
4. Experimental Results
4.1. The Memory’s Demand of SSEMatch
4.2. The Amount of Patterns Needs to be Verified of SSEMatch and WM
4.3. The Matching Speed of SSEMatch and WM
5. Conclusion
Acknowledgements
References
저자정보
참고문헌
자료제공 : 네이버학술정보