Efficient String Matching: An Aid to Bibliographic Search

Alfred V. Aho, Margaret J. Corasick, 1975, Communications of the ACM

About this paperEnglish中文日本語beside Englishbeside 中文beside 日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Đối sánh chuỗi hiệu quả: Một công cụ hỗ trợ tìm kiếm thư mục tài liệu

Alfred V. Aho and Margaret J. Corasick Bell Laboratories

Bài báo này mô tả một thuật toán đơn giản, hiệu quả để xác định tất cả các lần xuất hiện của bất kỳ số hữu hạn nào các từ khóa trong một chuỗi văn bản. Thuật toán bao gồm việc xây dựng một máy đối sánh mẫu trạng thái hữu hạn từ các từ khóa, sau đó sử dụng máy đối sánh mẫu để xử lý chuỗi văn bản trong một lần duyệt. Việc xây dựng máy đối sánh mẫu cần thời gian tỷ lệ với tổng độ dài của các từ khóa. Số phép chuyển trạng thái được thực hiện bởi máy đối sánh mẫu khi xử lý chuỗi văn bản không phụ thuộc vào số lượng từ khóa. Thuật toán đã được sử dụng để cải thiện tốc độ của một chương trình tìm kiếm thư mục tài liệu trong thư viện lên một hệ số từ 5 đến 10.

Từ khóa và Cụm từ: từ khóa và cụm từ, đối sánh mẫu chuỗi, tìm kiếm thư mục tài liệu, truy hồi thông tin, chỉnh sửa văn bản, máy trạng thái hữu hạn, độ phức tạp tính toán.

Phân loại CR: 3.74, 3.71, 5.22, 5.25

References

  1. Aho, A.V., Hopcroft, J.E., and Ullman, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.
  2. Booth, T.L. Sequential Machines and Automata Theory. Wiley, New York, 1967.
  3. Brzozowski, J.A. Derivatives of regular expressions. J. ACM 11:4 (October 1964), 481-494.
  4. Bullen, R.H., Jr., and Millen, J.K. Microtext - the design of a microprogrammed finite state search machine for full-text retrieval. Proc. Fall Joint Computer Conference, 1972, pp. 479-488.
  5. Fischer, M.J., and Paterson, M.S. String matching and other products. Technical Report 41, Project MAC, M.I.T., 1974.
  6. Gimpel, J.A. A theory of discrete patterns and their implementation in SNOBOL4. Comm. ACM 16:2 (February 1973), 91-100.
  7. Harrison, M.C. Implementation of the substring test by hashing. Comm. ACM 14:12 (December 1971), 777-779.
  8. Johnson, W.L., Porter, J.H., Ackley, S.I., and Ross, D.T. Automatic generation of efficient lexical processors using finite state techniques. Comm. ACM 11:12 (December 1968), 805-813.
  9. Kernighan, B.W., and Cherry, L.L. A system for typesetting mathematics. Comm. ACM 18:3 (March 1975), 151-156.
  10. Kleene, S.C. Representation of events in nerve nets. In Automata Studies, C.E. Shannon and J. McCarthy (eds.), Princeton University Press, 1956, pp. 3-40.
  11. Knuth, D.E. Fundamental Algorithms, second edition, The Art of Computer Programming 1, Addison-Wesley, Reading, Mass., 1973.
  12. Knuth, D.E. Sorting and Searching, The Art of Computer Programming 3, Addison-Wesley, Reading, Mass., 1973.
  13. Knuth, D.E., Morris, J.H., Jr., and Pratt, V.R. Fast pattern matching in strings. TR CS-74-440, Stanford University, Stanford, California, 1974.
  14. Kohavi, Z. Switching and Finite Automata Theory. McGraw-Hill, New York, 1970.
  15. McNaughton, R., and Yamada, H. Regular expressions and state graphs for automata. IRE Trans. Electronic Computers 9:1 (1960), 39-47.
  16. Rabin, M.O., and Scott, D. Finite automata and their decision problems. IBM J. Research and Development 3, (1959), 114-125. Read it here
  17. Thompson, K. Regular search expression algorithm. Comm. ACM 11:6 (June 1968), 419-422.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.