Computing the Expected Edit Distance from a String to a PFA
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/56997
Título: | Computing the Expected Edit Distance from a String to a PFA |
---|---|
Autor/es: | Calvo-Zaragoza, Jorge | Higuera, Colin de la | Oncina, Jose |
Grupo/s de investigación o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Palabras clave: | Edit distance | Probabilistic finite state automata |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos |
Fecha de publicación: | 2016 |
Editor: | Springer International Publishing Switzerland |
Cita bibliográfica: | 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 |
Resumen: | 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. |
Patrocinador/es: | Spanish Ministerio de Educación, Cultura y Deporte through a FPU grant (Ref. AP2012-0939) and the Spanish Ministerio de Economía y Competitividad through Project No. TIN2013-48152-C2-1-R (supported by UE FEDER funds). This work was partly done while the second author was supported by the University of Kyoto. |
URI: | http://hdl.handle.net/10045/56997 |
ISBN: | 978-3-319-40945-0 |
ISSN: | 0302-9743 |
DOI: | 10.1007/978-3-319-40946-7_4 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/conferenceObject |
Derechos: | © Springer International Publishing Switzerland 2016. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-40946-7_4 |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1007/978-3-319-40946-7_4 |
Aparece en las colecciones: | INV - GRFIA - Comunicaciones a Congresos, Conferencias, etc. |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2016_Calvo_etal_LNCS_final.pdf | Versión final (acceso restringido) | 396,05 kB | Adobe PDF | Abrir Solicitar una copia |
2016_Calvo_etal_LNCS_preprint.pdf | Preprint (acceso abierto) | 384,54 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.