Show simple item record

Professor Guidedc.contributor.advisorKiwi Krauskopf, Marcos es_CL
Professor Guidedc.contributor.advisorNavarro Badino, Gonzalo
Authordc.contributor.authorTelha Cornejo, Claudio Andrés es_CL
Staff editordc.contributor.editorFacultad de Ciencias Físicas y Matemáticases_CL
Staff editordc.contributor.editorDepartamento de Ciencias de la Computación; Departamento de Ingeniería Matemáticaes_CL
Associate professordc.contributor.otherPoblete Olivares, Patricio 
Associate professordc.contributor.otherVillanueva Ilufi, Mónica
Admission datedc.date.accessioned2012-09-12T18:12:20Z
Available datedc.date.available2012-09-12T18:12:20Z
Publication datedc.date.issued2007es_CL
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/102947
Abstractdc.description.abstractEl problema de la búsqueda aproximada en texto consiste en buscar las ocurrencias de un patrón en un texto, permitiendo que las ocurrencias no sean necesariamente copias exactas del patrón, sino que sean su cientemente próximas de acuerdo a alguna métrica particular. El problema tiene gran importancia en áreas como recuperación de la información, biología computacional y bases de datos de texto. El algoritmo de Chang y Marr (1994) es un algoritmo teóricamente óptimo en la complejidad de tiempo promedio para este problema. Posteriormente, Fredriksson y Navarro (2004) diseñan un algoritmo teóricamente óptimo que además es competitivo en la práctica. Esto hace pensar que el desarrollo de algoritmos exactos para este problema está llegando a su límite. El objetivo de este trabajo es enfrentar el problema de búsqueda utilizando una formulación débil que tiene potenciales aplicaciones prácticas y admite soluciones más e cientes que aquellas que se obtienen con algoritmos exactos, a cambio de posibles errores en la respuesta. Denominamos nuestra formulación búsqueda aproximada permitiendo errores. La principal contribución de este trabajo es la introducción y de nición formal del problema de búsqueda aproximada permitiendo errores para el caso en-línea, es decir, cuando se asume que no hay tiempo o espacio su ciente como para preprocesar el texto. Se presentan algoritmos para esta formulación, apoyados por análisis teóricos y experimentales que permiten entender su competitividad con respecto a algoritmos exactos para búsqueda aproximada. Los algoritmos propuestos son probabilísticos, permitiendo perder ocurrencias con cierta probabilidad y disminuyendo el tiempo de ejecución a cambio. Por ejemplo, sobre lenguaje natural estos algoritmos pueden recuperar el 95 % de las ocurrencias ocupando sólo el 15 % del tiempo utilizado por algoritmos exactos similares. El trabajo se complementa con algunas extensiones de las ideas desarrolladas para el caso en línea a otros problemas relacionados. En particular, se estudia cómo adaptar las ideas planteadas al problema de búsqueda aproximada múltiple, donde varios patrones se buscan sobre un mismo texto y a la búsqueda fuera de línea, en la cual se permite preprocesar el texto. Ambas extensiones muestran la robustez de los conceptos introducidos en este trabajo.
Lenguagedc.language.isoeses_CL
Publisherdc.publisherUniversidad de Chilees_CL
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
Keywordsdc.subjectComputaciónes_CL
Keywordsdc.subjectBúsqueda avanzada de textoes_CL
Keywordsdc.subjectAlgoritmoses_CL
Títulodc.titleBúsqueda Aproximada Permitiendo Erroreses_CL
Document typedc.typeTesises_CL


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile