Calvo-Zaragoza, Jorge, Higuera, Colin de la, Oncina, Jose
Computing the Expected Edit Distance from a String to a PFA
Han, Y.-S.; Salomaa, K. (Eds.). Implementation and Application of Automata: 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings. (Lecture Notes in Computer Science; 9705), 39-50. doi:10.1007/978-3-319-40946-7_4
URI: http://hdl.handle.net/10045/56997
DOI: 10.1007/978-3-319-40946-7_4
ISSN: 0302-9743
ISBN: 978-3-319-40945-0
Abstract: 
In a number of fields one is to compare a witness string with a distribution. One possibility is to compute the probability of the string for that distribution. Another, giving a more global view, is to compute the expected edit distance from a string randomly drawn to the witness string. This number is often used to measure the performance of a prediction, the goal then being to return the median string, or the string with smallest expected distance. To be able to measure this, computing the distance between a hypothesis and that distribution is necessary. This paper proposes two solutions for computing this value, when the distribution is defined with a probabilistic finite state automaton. The first is exact but has a cost which can be exponential in the length of the input string, whereas the second is a FPRAS.
Keywords:Edit distance, Probabilistic finite state automata
Springer International Publishing Switzerland
info:eu-repo/semantics/conferenceObject