Efficient String Matching: An Aid to Bibliographic Search

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

About this paperEnglishTiếng Việt中文beside Englishbeside Tiếng Việtbeside 中文

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.

効率的な文字列照合：書誌検索への一助

Alfred V. Aho and Margaret J. Corasick Bell Laboratories

本論文では、テキストの文字列中から、有限個のキーワードのいずれについてもそのすべての出現箇所を特定する、単純かつ効率的なアルゴリズムについて述べる。このアルゴリズムは、キーワードから有限状態のパターン照合機械を構成し、その後、パターン照合機械を用いてテキストの文字列を一回の走査で処理するものである。パターン照合機械の構成に要する時間は、キーワードの長さの総和に比例する。テキストの文字列を処理する際にパターン照合機械が行う状態遷移の数は、キーワードの数に依存しない。このアルゴリズムは、図書館の書誌検索プログラムの速度を5倍から10倍向上させるために使用されている。

キーワードと句：キーワードと句、文字列パターン照合、書誌検索、情報検索、テキスト編集、有限状態機械、計算量。

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 日本語 by gpt-5, against glossary version 6. Translated from the English.