Refinement of the results of recognition of mathematical formulas using the Levenshtein distance

A. Yu. Saparov   ; A. P. Beltyukov   ; S. G. Maslov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 30 (2020) no. 3, pp. 513-529

Résumé

The article deals with the problem of recognizing scanned mathematical texts with repeating formulas or formulas with same fragments. A method for comparing recognition results is described, which allows one to select similar elements from a variety of recognition options. The method is based on calculating the Levenshtein distances between individual fragments with additional parameters. The proposed method differs from the usual method in that, in the presence of uncertainties in comparison, all possible recognition options are used, presented as a symbol-weight pair. In the case of nonlinear formulas, numerical parameters that specify the location of individual symbols on the plane are also used in comparison. This comparison will allow you to group the formulas, and the data obtained will be useful in making decisions both by a user and by a program. Using this method will simplify the process of manual error correction, which will be based on the dynamic management of intermediate results in the process of close man-machine interaction.

Détail

Keywords: Levenshtein distance, replacement weight, displacement weight, variety of recognition options, formulas with common fragments.

Bibliographie

[1] Saparov A. Yu., Shirobokova I. Yu., “User interface development to manage the process of handwritten mathematical formula recognition”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2016, no. 1, 141–152 (in Russian) | DOI | MR

[2] Specht D. F., “Probabilistic neural networks”, Neural Networks, 3:1 (1990), 109–118 | DOI

[3] Rutkowski L., “Adaptive probabilistic neural networks for pattern classification in time-varying environment”, IEEE Transactions on Neural Networks, 15:4 (2004), 811–827 | DOI

[4] Savchenko A. V., “Statistical pattern recognition based on probabilistic neural network with homogeneity check”, Iskusstvennyi Intellekt i Prinyatie Reshenii, 2013, no. 4, 45–56 (in Russian)

[5] Ray A., Rajeswar S., Chaudhury S., “A hypothesize-and-verify framework for text recognition using deep recurrent neural networks”, 2015 13th International Conference on Document Analysis and Recognition (ICDAR) (Tunis, 2015), 936–940 | DOI

[6] Ray A., Rajeswar S., Chaudhury S., “OCR for bilingual documents using language modeling”, 2015 13th International Conference on Document Analysis and Recognition (ICDAR) (Tunis, 2015), 1256–1260 | DOI

[7] Kiryushina A. E., “The methods of processing of the image which contains mathematic formulas”, Fundamental'nye Issledovaniya, 2015, no. 9-2, 240–246 (in Russian)

[8] Thorelli L. E., “Automatic correction of errors in text”, BIT Numerical Mathematics, 2:1 (1962), 45–52 | DOI

[9] Yang Z., Xiaobing Z., “Automatic error detection and correction of text: the state of the art”, 2013 6th International Conference on Intelligent Networks and Intelligent Systems (ICINIS), 2013, 274–277 | DOI | MR

[10] Bassil Y., Alwani M., “OCR post-processing error correction algorithm using Google's online spelling suggestion”, Journal of Emerging Trends in Computing and Information Sciences, 3:1 (2012), 90–99 http://www.cisjournal.org/journalofcomputing/archive/vol3no1/vol3no1_7.pdf

[11] Han B., Cook P., Baldwin T., “Lexical normalization for social media text”, ACM Transactions on Intelligent Systems and Technology, 4:1 (2013), 5 | DOI

[12] Hadzic D., Sarajlic N., “Methodology for fuzzy duplicate record identification based on the semantic-syntactic information of similarity”, Journal of King Saud University — Computer and Information Sciences, 32:1 (2020), 126–136 | DOI

[13] Prasetya D. D., Prasetya Wibawa A., Hirashima T., “The performance of text similarity algorithms”, International Journal of Advances in Intelligent Informatics, 4:1 (2018), 63–69 | DOI

[14] Gomaa W. H., Fahmy A. A., “A survey of text similarity approaches”, International Journal of Computer Applications, 68:13 (2013), 13–18 | DOI

[15] Boitsov L. M., “Classification and experimental study of the vocabulary of modern algorithms for fuzzy search”, 6th all-Russian Scientific Conference “Electronic Libraries: Promising Methods and Technologies, Electronic Collections” (Pushchino, Russia, 2004) (in Russian)

[16] Frolov A. S., “Development of fuzzy search algorithm based on hashing”, Molodoi Uchenyi, 2016, no. 13 (117), 357–360 (in Russian)

[17] Kolesov D. A., “Development of an algorithm for searching information in databases using the fuzzy string comparison function”, Issledovaniya po Informatike, 2004, no. 7, 125–132 (in Russian)

[18] Sochenkov I. V., “Text comparison method for solving search and analytical problems”, Iskusstvennyi Intellekt i Prinyatie Reshenii, 2013, no. 2, 32–43 (in Russian)

[19] Grinchenkov D. V., Kushchii D. N., “Solution to problem of constructing inquiries in a thematic search based on recognition of partial structured texts”, Izvestiya Vysshikh Uchebnykh Zavedenii. Severo-Kavkazskii Region. Ser. Tekhnicheskie Nauki, 2019, no. 1, 10–16 (in Russian) | DOI

[20] Povolotskii M. A., Tropin D. V., Chernov T. S., Savelyev B. I., “Dynamic programming approach to textual structured objects segmentation in images”, Informatsionnye Tekhnologii i Vychislitel'nye Sistemy, 2019, no. 3, 66–78 (in Russian) | DOI

[21] Levenshtein V. I., “Binary codes capable of correcting deletions, insertions, and reversals”, Sov. Phys., Dokl., 10 (1965), 707–710 | MR | Zbl

[22] Winkler W. E., String comparator metrics and enhanced decision rules in the Fellegi–Sunter model of Record Linkage, Reports — Evaluative/Feasibility, No 142, 1990, 8 pp. http://files.eric.ed.gov/fulltext/ED325505.pdf

[23] Hamming R. W., “Error detecting and error correcting codes”, The Bell System Technical Journal, 29:2 (1950), 147–160 | DOI | MR | Zbl

[24] Damerau F. J., “A technique for computer detection and correction of spelling errors”, Communications of the ACM, 7:3 (1964), 171–176 | DOI

[25] Kondrak G., “$N$-gram similarity and distance”, String Processing and Information Retrieval, 2005, 115–126 | DOI | MR

[26] Saparov A. Yu., Beltyukov A. P., “Regular expressions in the mathematical text recognition problem”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2012, no. 2, 63–73 (in Russian) | DOI | Zbl

[27] Beltyukov A. P., Maslov S. G., “The understanding in the framework of the ergatic system”, III International Conference “International cooperation: integration of educational areas”, Udmurt State University, Izhevsk, 2016, 145–151 (in Russian)

[28] Lyutikova L. A., Shmatova E. V., “The logical correction algorithms for the qualitative analysis of the subject area in pattern recognition”, Kibernetika i Programmirovanie, 2015, no. 5, 1–127 (in Russian) | DOI

[29] Wagner R. A., Fischer M. J., “The string-to-string correction problem”, Journal of the ACM, 21:1 (1974), 168–173 | DOI | MR | Zbl