Algorithms for string searching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for string searching

Full text

Pdf (1.12 MB)

Source

ACM SIGIR Forum archive
Volume 23 , Issue 3-4 (Spring 1989) table of contents

Pages: 34 - 58

Year of Publication: 1989

ISSN:0163-5840

Author

R. A. Baeza-Yates

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 29, Downloads (12 Months): 198, Citation Count: 7

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/74697.74700 What is a DOI?

ABSTRACT

We survey several algorithms for searching a string in a piece of text. We include theoretical and empirical results, as well as the actual code of each algorithm. An extensive bibliography is also included.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alberto Apostolico , Raffaele Giancarlo, The Boyer Moore Galil string searching strategies revisited, SIAM Journal on Computing, v.15 n.1, p.98-105, Feb. 1986 [doi>10.1137/0215007]
	2	{Aho80} A. V. Aho. Pattern matching in strings. In R. Book, editor, <i>Formal Language Theory: Perspectives and Open Problems</i>, pages 325--347. Academic Press, London, 1980.
	3	{AYS85} J. Aoe, Y. Yamamoto, and R. Shimada. An efficient implementation of static string pattern matching machines. In <i>IEEE Int. Conf. on Supercomputing Systems</i>, volume 1, pages 491--498, St. Petersburg, Fla, 1985.
	4	{Bar81} G. Barth. An alternative for the implementation of Knuth-Morris-Pratt algorithm. <i>Inf. Proc. Letters</i>, 13:134--137, 1981.
	5	Gerhard Barth, An analytical comparison of two string searching algorithms, Information Processing Letters, v.18 n.5, p.249-256, June 1984 [doi>10.1016/0020-0190(84)90003-6]
	6	A. Blumer , J. Blumer , D. Haussler , R. McConnell , A. Ehrenfeucht, Complete inverted files for efficient text retrieval and analysis, Journal of the ACM (JACM), v.34 n.3, p.578-595, July 1987 [doi>10.1145/28869.28873]
	7	O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73036]
	8	{BBH+85} A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and J. Seiferas. The smallest automaton recognizing the subwords of a text. <i>Theoretical Computer Science</i>, 40:31--55, 1985.
	9	{BD80} T. A. Bailey and R. G. Dromey. Fast string searching by finding subkeys in subtext. <i>Inf. Proc. Letters</i>, 11:130--133, 1980.
	10	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	11	R. A. Baeza-Yates, Improved string searching, Software—Practice & Experience, v.19 n.3, p.257-271, March 1989 [doi>10.1002/spe.4380190305]
	12	R. L. Baeza-Yates, Efficient text searching, University of Waterloo, Waterloo, Ont., Canada, 1989
	13	Ricardo A. Baeza-Yates, String Searching Algorithms Revisited, Proceedings of the Workshop on Algorithms and Data Structures, p.75-96, August 17-19, 1989
	14	R. A. Baeza-Yates , G. H. Gonnet, A new approach to text searching, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.168-175, June 25-28, 1989, Cambridge, Massachusetts, United States
	15	H. D. Cheng , K. S. Fu, VLSI architectures for string matching and pattern matching, Pattern Recognition, v.20 n.1, p.125-144, 1987 [doi>10.1016/0031-3203(87)90023-9]
	16	{CP88} M. Crochemore and D. Perrin. Pattern matching in strings. In Di Gesu, editor, <i>4th Conference on Image Analysis and Processing</i>, pages 67--79. Springer Verlag, 1988.
	17	{CP89} M. Crochemore and D. Perrin. Two way pattern matching. Technical Report 98-8, L.I.T.P., Univ. Paris 7, Feb 1989. (submitted for publication).
	18	Maxime Crochemore, String Matching with Constraints, Proceedings of the Mathematical Foundations of Computer Science 1988, p.44-58, August 29-September 02, 1988
	19	Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
	20	G Davies , S Bowsher, Algorithms for pattern matching, Software—Practice & Experience, v.16 n.6, p.575-601, June. 1986 [doi>10.1002/spe.4380160608]
	21	Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
	22	Zvi Galil, On improving the worst case running time of the Boyer-Moore string matching algorithm, Communications of the ACM, v.22 n.9, p.505-508, Sept. 1979 [doi>10.1145/359146.359148]
	23	Zvi Galil, String Matching in Real Time, Journal of the ACM (JACM), v.28 n.1, p.134-149, Jan. 1981 [doi>10.1145/322234.322244]
	24	Zvi Galil, Optimal parallel algorithms for string matching, Information and Control, v.67 n.1-3, p.144-157, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80031-0]
	25	{GBY89} G. H. Gonnet and R. A. Baeza-Yates. An analysis of the Karp-Rabin string matching algorithm. (submitted for publication), April 1989.
	26	{GO80} L. Guibas and A. Odlyzko. A new proof of the linearity of the Boyer-Moore string searching algorithm. <i>SIAM J on Computing</i>, 9:672--682, 1980.
	27	Gaston H. Gonnet, Unstructured data bases or very efficient text searching, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588074]
	28	{Gon88} G. H. Gonnet. Private communication, 1988.
	29	{GS80} Z. Galil and J. Seiferas. Saving space in fast string-matching. <i>SIAM J on Computing</i>, 9:417--438, 1980.
	30	{GS83} Z. Galil and J. Seiferas. Time-space-optimal string matching. <i>JCSS</i>, 26:280--294, 1983.
	31	Malcolm C. Harrison, Implementation of the substring test by hashing, Communications of the ACM, v.14 n.12, p.777-779, Dec. 1971 [doi>10.1145/362919.362934]
	32	Roger Haskin, Hardware for searching very large text databases, Proceedings of the fifth workshop on Computer architecture for non-numeric processing, p.49-56, March 11-14, 1980, Pacific Grove, California, United States
	33	{Hol79} L. A. Hollaar. Text retrieval computers. <i>IEEE Computer</i>, 12:40--50, 1979.
	34	{Hor80} N. Horspool. Practical fast searching in strings. <i>Software - Practice and Experience</i>, 10:501--506, 1980.
	35	{IA80} S. Iyengar and V. Alia. A string search algorithm. <i>Appl. Math. Comput.</i>, 6:123--131, 1980.
	36	{KBG87} M. Kemp, R. Bayer, and U. Guntzer. Time optimal left to right construction of position trees. <i>Acta Informatica</i>, 24:461--474, 1987.
	37	Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72977]
	38	{KMP77} D. E. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. <i>SIAM J on Computing</i>, 6:323--350, 1977.
	39	B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
	40	Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
	41	Ming Li, Lower Bounds on String-Matching, Cornell University, Ithaca, NY, 1984
	42	Ming Li , Y. Yesha, String-matching cannot be done by a two-head one-way deterministic finite automation, Information Processing Letters, v.22 n.5, p.231-235, April 1986 [doi>10.1016/0020-0190(86)90099-2]
	43	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	44	{Mey85} B. Meyer. Incremental string matching. <i>Inf. Proc. Letters</i>, 21:219--227, 1985.
	45	Peter Moller-Nielsen , Jorgen Staunstrup, Experiments with a fast string searching algorithm, Information Processing Letters, v.18 n.3, p.129-135, March 1984 [doi>10.1016/0020-0190(84)90015-2]
	46	Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
	47	{MP70} J. H. Morris and V. R. Pratt. A linear pattern matching algorithm. Technical Report 40, Computing Center, University of California, Berkeley, 1970.
	48	{MR80} M. Majster and A. Reiser. Efficient on-line construction and correction of position trees. <i>SIAM J on Computing</i>, 9:785--807, 1980.
	49	{Reg88} M. Regnier. Knuth-Morris-Pratt algorithm: An analysis. INRIA, Rocquencourt, France (unpublished), 1988.
	50	{Riv77} R. Rivest. On the worst-case behavior of string-searching algorithms. <i>SIAM J on Computing</i>, 6:669--674, 1977.
	51	{Ryt80} W. Rytter. A correct preprocessing algorithm for Boyer-Moore string-searching. <i>SIAM J on Computing</i>, 9:509--512, 1980.
	52	R. Schaback, On the expected sublinearity of the Boyer-Moore algorithm, SIAM Journal on Computing, v.17 n.4, p.648-658, August 1988 [doi>10.1137/0217041]
	53	{Sed83} R. Sedgewick. <i>Algorithms.</i> Addison-Wesley, Reading, Mass., 1983.
	54	{Sli80} A. Slisenko. Determination in real time of all the periodicities in a word. <i>Sov. Math. Dokl.</i>, 21:392--395, 1980.
	55	{Sli83} A. Slisenko. Detection of periodicities and string-matching in real time. <i>Journal of Soviet Mathematics</i>, 22:1316--1386, 1983.
	56	{Smi82} G. V. Smit. A comparison of three string matching algorithms. <i>Software - Practice and Experience</i>, 12:57--66, 1982.
	57	T Takaoka, An on-line pattern matching algorithm, Information Processing Letters, v.22 n.6, p.329-330, May 30,1986 [doi>10.1016/0020-0190(86)90075-X]
	58	Uzi Vishkin, Optimal parallel pattern matching in strings, Information and Control, v.67 n.1-3, p.91-113, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80028-0]
	59	{Wei73} P. Weiner. Linear pattern matching algorithm. In <i>FOCS</i>, volume 14, pages 1--11, 1973.
	60	{WKY85} S. Wakabayashi, T. Kikuno, and N. Yoshida. Design of hardware algorithms by recurrence relations. <i>Systems and Computers in Japan</i>, 8:10--17, 1985.
	61	{Yao79} A. C. Yao. The complexity of pattern matching for a random string. <i>SIAM J on Computing</i>, 8:368--387, 1979.

CITED BY 7

	Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Bing Liu , Robert Grossman , Yanhong Zhai, Mining data records in Web pages, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Kaidi Zhao , Bing Liu , Thomas M. Tirpak , Andreas Schaller, V-Miner: using enhanced parallel coordinates to mine product design and test data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Yanhong Zhai , Bing Liu, Web data extraction based on partial tree alignment, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Weifeng Su , Jiying Wang , Frederick H. Lochovsky, ODE: Ontology-assisted data extraction, ACM Transactions on Database Systems (TODS), v.34 n.2, p.1-35, June 2009
	Siddu P. Algur , P. S. Hiremath, Extraction of flat and nested data records from web pages, Proceedings of the fifth Australasian conference on Data mining and analystics, p.163-168, November 29-30, 2006, Sydney, Australia
	Bing Liu , Robert Grossman , Yanhong Zhai, Mining Web Pages for Data Records, IEEE Intelligent Systems, v.19 n.6, p.49-55, November 2004