13.7.2 String Matching, Text 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

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

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

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 DOI 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.
Elsevier DOI 0401
BibRef

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

Valiveti, R.S., Oommen, B.J.,
Recognizing sources of random strings,
PAMI(13), No. 4, April 1991, pp. 386-394.
IEEE DOI 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

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 DOI
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 DOI 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.
Elsevier DOI 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 DOI 9607
BibRef

Kuo, S.[Shufen], Cross, G.R.[George R.],
A Two-Step String Matching Procedure,
PR(24), No. 7, 1991, pp. 711-716.
Elsevier DOI 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.
Elsevier DOI 9705
BibRef

Parizeau, M.[Marc], Ghazzali, N.[Nadia], Hébert, J.F.[Jean-François],
Optimizing the Cost Matrix for Approximate String Matching Using Genetic Algorithms,
PR(31), No. 4, April 1998, pp. 431-440.
Elsevier DOI 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 DOI 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 DOI 9806
BibRef
Earlier: Conference: Machine Learning: Fourteenth International Conference, July 8-11, 1997, pp. 287-295. BibRef

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 BibRef 9907

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.
Elsevier DOI 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.
Elsevier DOI 0105
BibRef
Earlier:
Efficient Best-first Dictionary Search Given Graph-based Input,
ICPR00(Vol IV: 434-437).
IEEE DOI 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.
Elsevier DOI 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.
Elsevier DOI 0208
BibRef

Schulz, K.U.[Klaus U.], Mihov, S.[Stoyan],
Fast string correction with Levenshtein automata,
IJDAR(5), No. 1, 2002, pp. 67-85.
Springer DOI 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. 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.
Elsevier DOI 0209
BibRef

Juan, A., Vidal, E.,
Bernoulli mixture models for binary images,
ICPR04(III: 367-370).
IEEE DOI 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
IEEE DOI 0009
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. 0412
BibRef

Navarro, G.[Gonzalo],
A guided tour to approximate string matching,
Surveys(33), No. 1, March 2001, pp. 31-88.
WWW Link. 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 0903
BibRef

Jiang, X.Y.[Xiao-Yi], Wentker, J.[Jöran], Ferrer, M.[Miquel],
Generalized Median String Computation by Means of String Embedding in Vector Spaces,
PRL(33), No. 7, 1 May 2012, pp. 842-852.
Elsevier DOI 1203
Award, King Sun Fu, Related. An invited related paper. String; Generalized median; Embedding; Vector space; Lower bound
See also Generalized Median Graph Computation by Means of Graph Embedding in Vector Spaces. BibRef

Faro, S.[Simone], Lecroq, T.[Thierry],
The exact online string matching problem: A review of the most recent results,
Surveys(45), No. 2, February 2013, pp. Article No 13.
DOI Link 1303
Survey, String Matching. BibRef

Boudaren, M.E.[M. El_Yazid], Monfrini, E., Pieczynski, W., Aissani, A.,
Phasic Triplet Markov Chains,
PAMI(36), No. 11, November 2014, pp. 2310-2316.
IEEE DOI 1410
Bayes methods BibRef

Azmi, A.M.[Aqil M.], Al-Ssulami, A.M.[Abdulrakeeb M.],
Discovering common recurrent patterns in multiple strings over large alphabets,
PRL(54), No. 1, 2015, pp. 75-81.
Elsevier DOI 1502
String motifs BibRef

Man, D.[Duhu], Nakano, K.[Koji], Ito, Y.[Yasuaki],
An Optimal Implementation of the Approximate String Matching on the Hierarchical Memory Machine, with Performance Evaluation on the GPU,
IEICE(E97-D), No. 12, December 2014, pp. 3063-3071.
WWW Link. 1503
BibRef

Carvalho, J.M.[João M.], Brás, S.[Susana], Pratas, D.[Diogo], Ferreira, J.[Jacqueline], Soares, S.C.[Sandra C.], Pinho, A.J.[Armando J.],
Extended-alphabet finite-context models,
PRL(112), 2018, pp. 49-55.
Elsevier DOI 1809
ECG biometric identification and compute a similarity measure between DNA sequences. BibRef

Nienkötter, A., Jiang, X.,
Distance-preserving vector space embedding for the closest string problem,
ICPR16(1530-1535)
IEEE DOI 1705
Approximation algorithms, Clustering algorithms, Computational complexity, Hamming distance, Interpolation, Measurement, Prototypes BibRef

Liang, S., Chen, J., Li, Z., Bai, G.,
Linear time symmetric axis search based on palindrome detection,
ICIP16(1799-1803)
IEEE DOI 1610
Computational complexity BibRef

Febrer-Hernández, J.K.[José Kadir], Hernández-León, R.[Raudel], Hernández-Palancar, J.[José], Feregrino-Uribe, C.[Claudia],
SPaR-FTR: An Efficient Algorithm for Mining Sequential Patterns-Based Rules,
CIARP15(643-650).
Springer DOI 1511
BibRef
Earlier: A1, A3, A2, A4:
SPaMi-FTS: An Efficient Algorithm for Mining Frequent Sequential Patterns,
CIARP14(470-477).
Springer DOI 1411
BibRef

Liu, Y.Q.[Yun-Qiang], Caselles, V.[Vicent],
Supervised Visual Vocabulary with Category Information,
ACIVS11(13-21).
Springer DOI 1108
BibRef

Amayri, O.[Ola], Bouguila, N.[Nizar],
Improved Online Support Vector Machines Spam Filtering Using String Kernels,
CIARP09(621-628).
Springer DOI 0911
BibRef

Berkovich, S., Inayatullah, M.,
A fuzzy find matching tool for image text analysis,
AIPR04(101-105).
IEEE DOI 0410
BibRef

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

Arica, N.[Nafiz],
Cyclic Sequence Comparison Using Dynamic Warping,
CIVR05(328-335).
Springer DOI 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 0812
BibRef

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

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

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

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

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

Lourenco, A.[Andre], Fred, A.L.N.[Ana L.N.], Jain, A.K.[Anil K.],
On the Scalability of Evidence Accumulation Clustering,
ICPR10(782-785).
IEEE DOI 1008
BibRef

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

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

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

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

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

Ohta, M., Takasu, A., Adachi, J.,
Retrieval Methods for English-Text with Misrecognized OCR Characters,
ICDAR97(950-956).
IEEE DOI 9708
BibRef

Takasu, A.,
An Approximate String Match for Garbled Text with Various Accuracies,
ICDAR97(957-961).
IEEE DOI 9708
BibRef

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

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

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

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