The week's pick
Random Articles
Reseach Article
Novel Devaki-Paul Algorithm for Multiple Pattern Matching
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 13 - Number 3 |
| Year of Publication: 2011 |
| Authors: Devaki Pendlimarri, Paul Bharath Bhushan Petlu, Dr. Ramesh Babu Satrasala |
10.5120/1758-2397
|
Devaki Pendlimarri, Paul Bharath Bhushan Petlu, Dr. Ramesh Babu Satrasala . Novel Devaki-Paul Algorithm for Multiple Pattern Matching. International Journal of Computer Applications. 13, 3 ( January 2011), 37-42. DOI=10.5120/1758-2397
Abstract
Pattern matching is one of the major issues in the area of network security and also in many other areas. The increase in network speed and traffic may cause the existing algorithms to become a performance bottleneck. Therefore, it is very necessary to develop more efficient pattern matching algorithm, in order to overcome troubles on performance. There are several algorithms in use, in which, DP algorithm (Devaki – Paul algorithm) is yielding good results in many cases. However, this algorithm was proposed only for the single pattern matching. But, now-a-days it is very necessary to find the multiple patterns in NIDS etc. In this paper, we are giving a new proposal to the DP algorithm (Devaki – Paul algorithm) to make it efficient and works also for the multiple pattern matching. The algorithm was tested and validated and the results have proved that the performance of DP algorithm is better than BM algorithm (Boyer – Moore algorithm) and the Quick Search algorithm. In case of tests with repeated character, its performance is greater than 1%~50% with BM and Quick Search algorithms. In case of tests with the English Text and Random Pattern, it’s greater than 33%~91% with BM and 37%~85% with Quick Search algorithms. In case of tests with the English Text and Random Pattern of an unsuccessful search, its performance is greater than BM and Quick Search algorithms with 100%, if either the first and/or the last character of the pattern in the given text were not present.
References
- Devaki Pendlimarri and Paul Bharath Bhushan Petlu: “Novel Pattern Matching algorithm for Single Pattern Matching”, (IJCSE) International Journal on Computer Science and Engineering, Vol. 02. No. 08. 2010, 2698-2704.
- Knuth D, J. Morris and V. Pratt: “Fast Pattern Matching in String”, SIAM J. Computing 6(1977) 323-350.
- M. Fisk, and G. Varghese: “Fast content-based packet handling for intrusion detection”, UCSD Technical Report CS2001-0670, May 2001
- U. Manber: “Finding Similar Files in a Large File System”, USENIX Winter 1994 Technical Conference, San Fransisco (January 1994), pp 110.
- U. Manber and S. Wu: “GLIMPSE: A Tool to search through entire file systems”, USENIX Winter 1994 Technical Conference, San Fransisco (January 1994).
- Wu S., and U. Manber: “Agrep – A Fast Approximate Pattern-Matching Tool”, USENIX Winter 1992 Technical Conference, San Francisco (January 1992), pp 153 162.
- Wu S., and U. Manber: “Fast Text Searching Allowing Errors”, Communications of the ACM 35 (October 1992), pp 83 91.
- R. S. Boyer and J. S. Moore: “A fast String Searching algorithm”, Communications of the ACM, Vol 20, no. 10, pp. 762-772, 1977.
- C. Charras and T. Lecroq: “Exact string matching algorithms”, http://www.igm.univ-mlv.fr/~lecroq/string/, 1997.
- M. Fisk and G. Varghese: “An analysis of fast string matching applied to content-based forwarding and intrusion detection”, Technical Report CS2001-0670 (updated version), 2002.
- M. Crochemore, C. Hancart: “Pattern Matching in Algorithms and Theory of Computation Handbook”, CRC Press Inc. Bocaaton, FL. 1999.
- Knuth, D. and J. Morris, V. Pratt, “Fast pattern matching in strings”, SIAM J. Computing 6(1977) 323-350.
Index Terms
Keywords