13.7.1 String Matching

Chapter Contents (Back)
String Matching. Not really computer vision, but some related papers.

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 Reference 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 Reference 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 Reference
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. 0212Solving 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 Reference 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 Reference
IEEE DOI Reference
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 Reference 0608 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

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

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

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

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

Bunke, H.[Horst], Riesen, K.[Kaspar],
A Family of Novel Graph Kernels for Structural Pattern Recognition,
CIARP07(20-31).
Springer DOI Reference 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 Reference 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 Reference 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 Reference 0409 BibRef

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

Martínez-Hinarejos, C.D., Juan, A., Casacuberta, F.,
Use of Median String for Classification,
ICPR00(Vol II: 903-906).
IEEE DOI Reference
HTML Version. 0009 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 Reference 9608(Univ. de Alicante, E) BibRef

Melichar, B.[Borivoj],
String Matching with K Differences by Finite Automata,
ICPR96(II: 256-260).
IEEE DOI Reference 9608 BibRef
Earlier:
Approximate string matching by finite automata,
CAIP95(342-349).
Springer DOI Reference 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 .

Last update:Jan 1, 2009 at 17:09:16