I have some results of a handwriting recognition system, I need a string matching algorithm or something similar to correct mistake results, but if it's possible I want to learn that string matching system based on class labels using training data. Is there any learnable string matching algorithm?
A lot depends on the error characteristics of your recognizer. You may want to build first a character-level HMM, with the emission probabilities obtained from your confusion matrix, and build this into your word-level model
One might add, it also depends how many hands are writing on your handwriting recognition system. If there is a single person then 'simple' HMM is the best choice. If there are more than one writer then errors come from different handwritings may take into account. That is, you might want to build a parametrized HMM which is configured (personalized) by in-text (text per single person) errors.
The easiest way is the algorith of grammar correction of office applications. You can download APIs from the Internet
Strings are in broad sense patterns. There are so many state of the art pattern matching algorithms. I just put a hint; you choose a suitable tree data structure; and that's it...ur requisite fulfilled...I hope you got the hint. Else knock at me once more.
Suffix trees and suffix arrays do great job in string-matching. Here's a collection of pattern-matching algorithms: http://www.cs.ucdavis.edu/~gusfield/strmat.html
Thanks all!
@Andras: I didn't get the point, could you please give me an example or an internet source?
@Jakic: Could you elaborate that method or give a an example preferably in an article?
@Salvatore: Is there any code for Matlab or description of the way that method works?
@Tusar: I haven't worked with trainable decision trees yet if you mean. Does the method you mean needs manual work or not?
If you want to learn string matching system from basics then there are many algorithms for string matching, you may have know those algorithms. learn that it contains different method to look for string u were searching... and specially for handwriting recognition. here I m attaching few papers, see this it may help u.
Hi,
I work in wireless network,so idont know much about NLP. But I guess you can use N gram,bi gram, tri-gram or SVM
Thanks. I need some time to read articles and compare methods. By the way I emphasis I'm looking for an automatic (trainable) algorithm for pattern matching, I know basic edit distance but it has constant weight for all substitutions, deletion and insertion but I want an algorithm which can assign weights based on confusion matrix (I don't have any idea about weighting changes that don't occur in training data) and if possible can consider changes like 'cl' to 'd' and vice versa.
I think, string kernels would work great here. Check this paper [1] on fast implementation of string kernels: http://books.nips.cc/papers/files/nips15/AA11.pdf . Also, check papers on spectrum, mismatch, etc. string kernel papers from Leslie lab [2]. One is mentioned here: http://cseweb.ucsd.edu/~yfreund/papers/final-profile-kernel.pdf
[1] S. V. N. Vishwanathan and Alexander J. Smola. Fast Kernels for String and Tree Matching. In S. Becker, Sebastian Thrun, and Klaus Obermayer, editors, Advances in Neural Information Processing Systems 15, pp. 569–576, MIT Press, Cambridge, MA, 2003.
[2] http://cbio.mskcc.org/leslielab/software/string-kernels
@Natarajan: I don't know what is soundex. I need an algorithm or Matlab mfile to correct segmentation mistakes of handwriting recognition.
Hi
Try to create a language model first. n-grams (Uni, bi or tri). It will take time to do it. However, Google has made its 5-gram language model open and free to use. Download it and obtain the probabilities from their model. I have wrote an Arabic language model which ha a million tokens. If you are working with arabic language I can share it with you.
Simpler One - www-inst.eecs.berkeley.edu/~cs61b/su06/lecnotes/lec28.pdf
Advanced with realtime usage - http://www.eui.upm.es/~fmartin/webpgomez/Docencia/Pattern-Recognition/PR-Notes-Chapter-3.pdf
Hi
I would suggest KMP string matching, a powerful and intelligent string matching, you could add weights (for insertion , deletion,...).
Structural similarity is a procedure of matching with form feature by curvature and slope of trajectories
You can use mine (Artificial Bee Colony Algorithm) i suggested, you can find the link to the paper in my profile.
- Badges
- Science topic