Tối ưu không gian trạng thái của thuật toán AhoCorasick sử dụng kỹ thuật nén dòng và bảng chỉ số

  • Lê Đắc Nhường Khoa Công nghệ thông tin, Đại học Hải Phòng.
  • Lê Đăng Nguyên Đại học Hải Phòng.
  • Lê Trọng Vĩnh Khoa Toán-Cơ-Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQG Hà Nội.

Abstract

The  pattern  matching  algorithms  are important  roles  in  most  applications  of  informationtechnology. For example, Network Intrusion Detection System looks for evidence of malicious behavior based on  matching  packet  contents  with  known  patterns. Therefore, the study of the pattern-matching algorithm is a hot topic many researchers are interested. In  this paper, we propose a new method to optimize the state storage  of  the  pattern  matching  algorithms,  AhoCorasick  by  using  compressed  row  and  index  table techniques. The experimental results that compare the efficacy performed between the original Aho-Corasick algorithm  and  the  improved  algorithm  installed  in Snort showed that our method achieved better results.

Author Biographies

Lê Đắc Nhường, Khoa Công nghệ thông tin, Đại học Hải Phòng.

Sinh năm 1983 tại Hải Phòng.

Tốt nghiệp Thạc sĩ CNTT tại Đại học Công nghệ, ĐHQG Hà Nội năm 2009.

Hiện là giảng viên Khoa Công nghệ thông tin, Đại học Hải Phòng.

Lĩnh vực nghiên cứu chính là: Lý thuyết thuật toán, Mạng máy tính và An ninh mạng.

Email: Nhuongld@hus.edu.vn

Lê Đăng Nguyên, Đại học Hải Phòng.

Sinh năm 1976 tại Hải Phòng.

Tốt nghiệp Thạc sĩ CNTT tại Đại học Công nghệ, ĐHQG Hà Nội năm 2005.

Hiện công tác tại Đại học Hải Phòng.

Lĩnh vực quan tâm: Lý thuyết thuật toán, Mạng máy tính

Email: Nguyenld@hus.edu.vn

Lê Trọng Vĩnh, Khoa Toán-Cơ-Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQG Hà Nội.

Sinh năm 1973 tại Thanh Hóa.

Nhận học vị Tiến sĩ năm 2006, tại Viện khoa học và công nghệ tiên tiến Nhật bản, chức danh PGS năm 2012.

Hiện là giảng viên Khoa Toán-Cơ-Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQG Hà nội.

Lĩnh vực nghiên cứu chính là: Lý thuyết thuật toán và mạng máy tính.

Email: Vinhlt@vnu.edu.vn

Published
2014-09-12
Section
Bài báo