Efficient String Matching: An Aid to Bibliographic Search

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

About this paperTiếng Việt中文

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.

日本語
English

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

Alfred V. Aho and Margaret J. Corasick Bell Laboratories

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

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

CR分類：3.74, 3.71, 5.22, 5.25

This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.

Keywords and Phrases: keywords and phrases, string pattern matching, bibliographic search, information retrieval, text-editing, finite state machines, computational complexity.

CR Categories: 3.74, 3.71, 5.22, 5.25

This section is missing here.

1 Introduction

This section is missing here.

2 A Pattern Matching Machine

This section is missing here.

3 Construction of Goto, Failure, and Output Functions

This section is missing here.

4 Properties of Algorithms 1, 2, and 3

This section is missing here.

5 Time Complexity of Algorithms 1, 2, and 3

This section is missing here.

6 Eliminating Failure Transitions

This section is missing here.

7 An Application to Bibliographic Search

This section is missing here.

8 Concluding Remarks

This section is missing here.

Acknowledgments

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.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.