13.7.1 String Matching

Aho, A.V., Corasick, M.J.,
Efficient String Matching: An Aid to Bibliographic Search,
CACM(18), 1975, pp. 333-340. The dictionary is a finite automation whose states correspond to prefixes. BibRef 7500

Hirschberg, D.S.,
A Linear Space Algorithm for Computing Maximal Common Subsequences,
CACM(18), 1975, pp. 341-343. BibRef 7500

Aho, A.V., Hirschberg, D.S., Ullman, J.D.,
Bounds on the complexity of the Longest Common subsequence Problem,
JACM(23), 1976, pp. 1-12. BibRef 7600

Wagner, R., and Fischer, M.,
The String-to-String Correction Problem,
JACM(21), No. 1, 1974, pp. 168-173. BibRef 7400

Lowrance, R., Wagner, R.A.,
An Extension of the String-to-String Correction Problem,
JACM(23), No. 2, 1975, pp. 177-183. BibRef 7500

Wong, C.K., Chandra, A.K.,
Bounds for the String Editing Problem,
JACM(23), 1976, pp. 13-16. BibRef 7600

Bird, R.S.,
Two-Dimensional Pattern Matching,
IPL(6), No. 5, October 1977, pp. 168-170. BibRef 7710

Boyer, R.S., Moore, J.S.,
A Fast String Searching Algorithm,
CACM(20), No. 10, October 1977, pp. 762. BibRef 7710

Knuth, D.E., Morris, J.H., Pratt, V.R.,
Fast Pattern Matching in Strings,
SIAM_JC(6), No. 2, June 1977, pp. 323-350. BibRef 7706

Findler, N.V., van Leeuwen, J.,
A Family of Similarity Measures Between Two Strings,
PAMI(1), No. 1, January 1979, pp. 116-118. BibRef 7901

Hall, P.A., and Dowling, G.R.,
Approximate String Matching,
Surveys(12), No. 4, December 1980, pp. 381-402. Survey, String Matching. BibRef 8012

Galil, Z.,
On Improving the Worst Case Running Time of the Boyer-Moore String Matching Algorithm,
CACM(22), 1979, pp. 505-508. See also Fast String Searching Algorithm, A. BibRef 7900

Galil, Z.,
String Matching in Real Time,
JACM(28), 1981, pp. 134-149. See also Efficient Algorithms for Finding Maximum Matching in Graphs. BibRef 8100

Nakatsu, N., Kambayashi, Y., Yajima, S.,
A Longest Common Subsequence Algorithm Suitable for Similar Text Strings,
Acta Inf.(18), 1982, pp. 171-179. BibRef 8200

Rytter, W.,
A Correct Preprocessing Algorithm for Boyer-Moore String-Searching,
SIAM_JC(9), 1980, pp. 509-512. BibRef 8000

Guibas, L.J., Odiyzko, A.M.,
A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm,
SIAM_JC(9), 1980, pp. 672-682. BibRef 8000

Galil, Z., Seiferas, J.,
Time-Space-Optimal String Matching,
CompSysSci(26), 1983, pp. 280-294. BibRef 8300

Apostolico, A., Preparata, F.P.,
Optimal Off-Line Detection of Repetitions in a String,
TCS(22), 1983, pp. 297-315. BibRef 8300

Rosenfeld, A., Hyde, P.D.,
Parallel String Acceptance Using Lattice Graphs,
PRL(1), 1983, pp. 237-243. BibRef 8300

Hsu, W.J., Du, M.W.,
Computing a Longest Common Subsequence for a Set of Strings,
BIT(24), 1984, pp. 45-59. BibRef 8400

Moller-Nielsen, P., Staunstrup, J.,
Experiments with a Fast String Searching Algorithm,
IPL(18), 1984, pp. 129-135. BibRef 8400

Barth, G.,
An Analytical Comparison of Two String Searching Algorithms,
IPL(18), 1984, pp. 249-256. BibRef 8400

Main, M.G., Lorentz, R.J.,
An O(N Log N) Algorithm For Finding All Repetitions In A String,
Algorithms(5), 1984, pp. 422-432. BibRef 8400

Aoe, J., Yamamoto, Y., Shimada, R.,
A Method for Improving String Pattern Matching Machines,
SE(10), 1984, pp. 116-120. BibRef 8400

Apostolico, A., Giancarlo, R.,
The Boyer-Moore-Galli String Searching Strategies Revisited,
SIAM_JC(15), No. 1, February 1986, pp. 98-105. See also Fast String Searching Algorithm, A. BibRef 8602

Zhu, R.F., Takaoka, T.,
A Technique for Two-Dimensional Pattern Matching,
CACM(32), No. 9, September 1989, pp. 1110-1120. Reduce an array matching problem to string matching and apply efficient string matching to arrays. Good summary of string matching algorithms and others. BibRef 8909

Sunday, D.M.,
A Very Fast Substring Search Algorithm,
CACM(33), No. 2, February 1990, pp. 132-142. BibRef 9002

Landraud, A.M., Avril, J.F., Chretienne, P.,
An algorithm for finding a common structure shared by a family of strings,
PAMI(11), No. 8, August 1989, pp. 890-895.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0401
BibRef

Fong, D.Y.S.[David Yu-Shan], Chu, J.L.[Jwo-Liang],
A string pattern recognition approach to polygon clipping,
PR(23), No. 8, 1990, pp. 879-892.
WWW Version. 0401
BibRef

Chung, K.L.[Kuo-Liang],
A randomized parallel algorithm for string matching on hypercube,
PR(25), No. 10, October 1992, pp. 1265-1268.
WWW Version. 0401
BibRef

Oommen, B.J., Zgierski, J.R.,
Breaking substitution cyphers using stochastic automata,
PAMI(15), No. 2, February 1993, pp. 185-192.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0401
BibRef

Valiveti, R.S., Oommen, B.J.,
Recognizing sources of random strings,
PAMI(13), No. 4, April 1991, pp. 386-394.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0401
BibRef

Bunke, H., Bühler, U.,
Applications of approximate string matching to 2D shape recognition,
PR(26), No. 12, December 1993, pp. 1797-1812.
WWW Version. 0401
BibRef

Idury, R.M.[Ramana M.], Schaffer, A.A.[Alejandro A.],
Dynamic Dictionary Matching with Failure Functions,
TCS(131), 1994, pp. 295-310. Allow insertions and deletions in the dictionary. BibRef 9400

Bunke, H., Csirik, J.,
Parametric string edit distance and its application to pattern recognition,
SMC(25), No 1, January 1995 pp.202-206.
IEEE DOI Link BibRef 9501

Idury, R.M.[Ramana M.], Schaffer, A.A.[Alejandro A.],
Multiple Matching of Parameterized Patterns,
TCS(154), No. 2, 5 February 1996, pp. 203-224. Find all occurrences. BibRef 9602

Sastry, R., Ranganathan, N., Remedios, K.,
CASM: A VLSI Chip for Approximate String-Matching,
PAMI(17), No. 8, August 1995, pp. 824-830.
IEEE Abstract. IEEE Top Reference.
WWW Version. See also PMAC: A Polygon Matching Chip. BibRef 9508

Gregor, J., Thomason, M.G.,
Dynamic programming alignment of sequences representing cyclic patterns,
PAMI(15), No. 2, February 1993, pp. 129-135.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0401
BibRef

Gregor, J., Thomason, M.G.,
Efficient Dynamic-Programming Alignment of Cyclic Strings by Shift Elimination,
PR(29), No. 7, July 1996, pp. 1179-1185.
WWW Version. 9607
BibRef

Kashyap, R.L., Oommen, B.J.,
The Noisy Substring Matching Problem,
SE(9), 1983, pp. 365-370. BibRef 8300

Oommen, B.J., Zhang, K.,
The Normalized String Editing Problem Revisited,
PAMI(18), No. 6, June 1996, pp. 669-672.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9607
BibRef

Kuo, S., Cross, G.R.,
A Two-Step String Matching Procedure,
PR(24), No. 7, 1991, pp. 711-716.
WWW Version. BibRef 9100

Maes, M.,
Polygonal Shape Recognition Using String-Matching Techniques,
PR(24), No. 5, 1991, pp. 433-440.
WWW Version. BibRef 9100

Takefuji, Y., Tanaka, T., Lee, K.C.,
A Parallel String Search Algorithm,
SMC(22), 1992, pp. 332-336. BibRef 9200

Crochemore, M., Perrin, D.,
Two-Way String-Matching,
JACM(38), 1991, pp. 651-675. BibRef 9100

Rice, S.V., Kanai, J., Nartker, T.A.,
An Algorithm for Matching OCR-Generated Text Strings,
PRAI(8), No. 5, 1994, pp. 1259-1268. BibRef 9400

Oommen, B.J., Loke, R.K.S.,
Pattern-Recognition of Strings with Substitutions, Insertions, Deletions and Generalized Transposition,
PR(30), No. 5, May 1997, pp. 789-800.
WWW Version. 9705
BibRef

Pao, D.C.W., Sun, M.C., Lam, M.C.H.,
An Approximate String-Matching Algorithm for Online Chinese Character-Recognition,
IVC(15), No. 9, September 1997, pp. 695-703.
WWW Version. 9709
BibRef

Parizeau, M., Ghazzali, N., Hebert, J.F.,
Optimizing the Cost Matrix for Approximate String Matching Using Genetic Algorithms,
PR(31), No. 4, April 1998, pp. 431-440.
WWW Version. 9803
BibRef

Sarukkai, R.R., Ballard, D.H.,
Phonetic set indexing for fast lexical access,
PAMI(20), No. 1, January 1998, pp. 78-82.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0401
BibRef

Ristad, E.S.[Eric Sven], and Yianilos, P.N.[Peter N.],
Learning String Edit Distance,
PAMI(20), No. 5, May 1998, pp. 522-532.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9806
BibRef
Earlier: Conference: Machine Learning: Fourteenth International Conference, July 8-11, 1997, pp. 287-295. BibRef

Chen, S.W., Tung, S.T., Fang, C.Y., Cherng, S.[Shen], Jain, A.K.[Anil K.],
Extended Attributed String Matching for Shape Recognition,
CVIU(70), No. 1, April 1998, pp. 36-50.
WWW Version. BibRef 9804

Wu, W.Y., Wang, M.J.J.,
Two-Dimensional Object Recognition Through Two-Stage String Matching,
IP(8), No. 7, July 1999, pp. 978-981.
IEEE DOI Link BibRef 9907

Torr, P.H.S., Zisserman, A.,
MLESAC: A New Robust Estimator with Application to Estimating Image Geometry,
CVIU(78), No. 1, April 2000, pp. 138-156. 0004

WWW Version. BibRef

Kaygin, S.[Serkan], Bulut, M.M.[M. Mete],
Shape recognition using attributed string matching with polygon vertices as the primitives,
PRL(23), No. 1-3, January 2002, pp. 287-294.
HTML Version. 0201
BibRef

Ye, X.Y.[Xiang-Yun], Cheriet, M.[Mohamed], Suen, C.Y.[Ching Y.],
StrCombo: combination of string recognizers,
PRL(23), No. 4, February 2002, pp. 381-394.
HTML Version. 0202
BibRef

Lucas, S.[Simon],
Efficient graph-based dictionary search and its application to text-image searching,
PRL(22), No. 5, April 2001, pp. 551-562.
HTML Version. 0105
BibRef
Earlier:
Efficient Best-first Dictionary Search Given Graph-based Input,
ICPR00(Vol IV: 434-437).
IEEE DOI Link
HTML Version. 0009
BibRef

Hodge, V.J.[Victoria J.], Austin, J.[Jim],
A comparison of a novel neural spell checker and standard spell checking algorithms,
PR(35), No. 11, November 2002, pp. 2571-2580.
WWW Version. 0208
BibRef

Porto, A.H.L.[Alexandre H.L.], Barbosa, V.C.[Valmir C.],
Finding approximate palindromes in strings,
PR(35), No. 11, November 2002, pp. 2581-2591.
WWW Version. 0208
BibRef

Schulz, K.U.[Klaus U.], Mihov, S.[Stoyan],
Fast string correction with Levenshtein automata,
IJDAR(5), No. 1, 2002, pp. 67-85.
HTML Version. 0211
BibRef

Lee, D.S.[Dar-Shyang],
Substitution Deciphering Based on HMMs with Applications to Compressed Document Processing,
PAMI(24), No. 12, December 2002, pp. 1661-1666.
IEEE Abstract. IEEE Top Reference. 0212
Solving substitution ciphers with noise. BibRef

Juan, A., Vidal, E.,
On the use of Bernoulli mixture models for text classification,
PR(35), No. 12, December 2002, pp. 2705-2710.
WWW Version. 0209
BibRef

Juan, A., Vidal, E.,
Bernoulli mixture models for binary images,
ICPR04(III: 367-370).
IEEE DOI Link 0409
BibRef

Juan, A., Vidal, E.,
On the Use of Normalized Edit Distances and an Efficient K-nn Search Technique (k-aesa) for Fast and Accurate String Classification,
ICPR00(Vol II: 676-679).
IEEE DOI Link
IEEE DOI Link
HTML Version. 0009
BibRef

Rico-Juan, J.R.[Juan Ramón], Micó, L.[Luisa],
Comparison of AESA and LAESA search algorithms using string and tree-edit-distances,
PRL(24), No. 9-10, June 2003, pp. 1417-1426.
WWW Version. 0304
BibRef

Rico-Juan, J.R.[Juan Ramón], Iñesta, J.M.[José M.],
Edit Distance for Ordered Vector Sets: A Case of Study,
SSPR06(200-207).
Springer DOI Link 0608
BibRef

Abreu Salas, J.I.[José Ignacio], Rico-Juan, J.R.[Juan Ramón],
Contour Regularity Extraction Based on String Edit Distance,
IbPRIA09(160-167).
Springer DOI Link 0906
BibRef

Prado, J.,
A new fast bit-reversal permutation algorithm based on a symmetry,
SPLetters(11), No. 12, December 2004, pp. 933-936.
IEEE Abstract. IEEE Top Reference. 0412
BibRef

Navarro, G.[Gonzalo],
A guided tour to approximate string matching,
Surveys(33), No. 1, March 2001, pp. 31-88.
WWW Version. 0805
Survey, String Matching. BibRef

Pratt, K.B.[Kevin B.], Fink, E.[Eugene],
Search For Patterns In Compressed Time Series,
IJIG(2), No. 1, January 2002, pp. 89-106. 0201
BibRef

Dobrišek, S.[Simon], Žibert, J.[Janez], Pavešic, N.[Nikola], Mihelic, F.[France],
An Edit-Distance Model for the Approximate Matching of Timed Strings,
PAMI(31), No. 4, April 2009, pp. 736-741.
IEEE DOI Link 0903
BibRef

Portnoy, D., Bock, P.,
Unsupervised fuzzy-membership estimation of terms in semantic and syntactic lexical classes,
AIPR04(95-100).
IEEE DOI Link 0410
BibRef

Arica, N.[Nafiz],
Cyclic Sequence Comparison Using Dynamic Warping,
CIVR05(328-335).
Springer DOI Link 0507
more like cyclic strings. BibRef

Wang, Y.[Yang],
A new method to obtain the shift-table in Boyer-Moore's string matching algorithm,
ICPR08(1-4).
IEEE DOI Link 0812
BibRef

Rebecchi, S.[Sebastien], Jolion, J.M.[Jean-Michel],
On the gaussian distribution of strings,
ICPR08(1-4).
IEEE DOI Link 0812
BibRef

Olivares-Rodríguez, C.[Cristian], Oncina, J.[Jose],
A Stochastic Approach to Median String Computation,
SSPR08(431-440).
Springer DOI Link 0812
BibRef

Campos, M.[Marcelino], López, D.[Damián], Peris, P.[Piedachu],
Incremental Multiple Sequence Alignment,
CIARP07(604-613).
Springer DOI Link 0711
BibRef

Mirzaei, A.[Abdolreza], Zaboli, H.[Hamidreza], Safabakhsh, R.[Reza],
A Neural Network String Matcher,
CAIP07(784-791).
Springer DOI Link 0708
BibRef

Riesen, K.[Kaspar], Fankhauser, S.[Stefan], Bunke, H.[Horst], Dickinson, P.[Peter],
Efficient Suboptimal Graph Isomorphism,
GbRPR09(124-133).
Springer DOI Link 0905
BibRef

Bunke, H.[Horst], Riesen, K.[Kaspar],
Graph Classification Based on Dissimilarity Space Embedding,
SSPR08(996-1007).
Springer DOI Link 0812
BibRef
And:
Graph Classification on Dissimilarity Space Embedding,
SSPR08(2).
Springer DOI Link 0812
BibRef

Bunke, H.[Horst], Riesen, K.[Kaspar],
A Family of Novel Graph Kernels for Structural Pattern Recognition,
CIARP07(20-31).
Springer DOI Link 0711
BibRef

Riesen, K.[Kaspar], Neuhaus, M.[Michel], Bunke, H.[Horst],
Graph Embedding in Vector Spaces by Means of Prototype Selection,
GbRPR07(383-393).
Springer DOI Link 0706
BibRef

Spillmann, B.[Barbara], Neuhaus, M.[Michel], Bunke, H.[Horst], Pekalska, E.[Elzbieta], Duin, R.P.W.[Robert P. W.],
Transforming Strings to Vector Spaces Using Prototype Selection,
SSPR06(287-296).
Springer DOI Link 0608
BibRef

Bombach, N.[Nachum], Gans, H.[Harold],
Patterns of Co-Linear Equidistant Letter Sequences and Verses,
ICPR06(III: 149-151).
WWW Version. 0609
BibRef
And: ICPR06(III: 1248-1250).
WWW Version. 0609
BibRef
And: ICPR06(IV: 961).
WWW Version. 0609
BibRef

Lourenço, A.[André], Fred, A.[Ana],
Ensemble Methods in the Clustering of String Patterns,
WACV05(I: 143-148).
WWW Version. 0502
BibRef

Mollineda Cardenas, R.A.,
A learning model for multiple-prototype classification of strings,
ICPR04(IV: 420-423).
IEEE DOI Link 0409
BibRef

Mollineda, R.A., Vidal, E., Casacuberta, F.,
A windowed weighted approach for approximate cyclic string matching,
ICPR02(IV: 188-191).
IEEE DOI Link 0211
BibRef

Martínez-Hinarejos, C.D., Juan, A., Casacuberta, F.,
Use of Median String for Classification,
ICPR00(Vol II: 903-906).
IEEE DOI Link
HTML Version. 0009
BibRef

Takasu, A.[Atsuhiro],
Bayesian Similarity Model Estimation for Approximate Recognized Text Search,
ICDAR09(611-615).
IEEE DOI Link 0907
BibRef

Ohta, M., Takasu, A., Adachi, J.,
Retrieval Methods for English-Text with Misrecognized OCR Characters,
ICDAR97(We-2B) 9708
BibRef

Takasu, A.,
An Approximate String Match for Garbled Text with Various Accuracies,
ICDAR97(We-2B) 9708
BibRef

Oncina, J.,
The Cocke-Younger-Kasami Algorithm for Cyclic Strings,
ICPR96(II: 413-416).
IEEE DOI Link 9608
(Univ. de Alicante, E) BibRef

Melichar, B.[Borivoj],
String Matching with K Differences by Finite Automata,
ICPR96(II: 256-260).
IEEE DOI Link 9608
BibRef
Earlier:
Approximate string matching by finite automata,
CAIP95(342-349).
Springer DOI Link 9509
(Czech Technical Univ., CZ) BibRef

Califano, A., Rigoutsos, I.,
FLASH: a fast look-up algorithm for string homology,
CVPR93(353-359).
IEEE Abstract. IEEE Top Reference. 0403
BibRef

Chapter on Matching and Recognition Using Volumes, High Level Vision Techniques, Invariants continues in
Other Feature Matching Techniques .