A new iterative algorithm for computing a quality approximate median of strings based on edit operations

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10045/37803
Información del item - Informació de l'item - Item information
Título: A new iterative algorithm for computing a quality approximate median of strings based on edit operations
Autor/es: Abreu Salas, José Ignacio | Rico Juan, Juan Ramón
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: Approximate median string | Edit distance | Edit operations
Área/s de conocimiento: Lenguajes y Sistemas Informáticos
Fecha de publicación: 15-ene-2014
Editor: Elsevier
Cita bibliográfica: Pattern Recognition Letters. 2014, 36: 74-80. doi:10.1016/j.patrec.2013.09.014
Resumen: This paper presents a new algorithm that can be used to compute an approximation to the median of a set of strings. The approximate median is obtained through the successive improvements of a partial solution. The edit distance from the partial solution to all the strings in the set is computed in each iteration, thus accounting for the frequency of each of the edit operations in all the positions of the approximate median. A goodness index for edit operations is later computed by multiplying their frequency by the cost. Each operation is tested, starting from that with the highest index, in order to verify whether applying it to the partial solution leads to an improvement. If successful, a new iteration begins from the new approximate median. The algorithm finishes when all the operations have been examined without a better solution being found. Comparative experiments involving Freeman chain codes encoding 2D shapes and the Copenhagen chromosome database show that the quality of the approximate median string is similar to benchmark approaches but achieves a much faster convergence.
Patrocinador/es: This work is partially supported by the Spanish CICYT under project DPI2006-15542-C04-01, the Spanish MICINN through project TIN2009-14205-CO4-01 and by the Spanish research program Consolider Ingenio 2010: MIPRCV (CSD2007-00018).
URI: http://hdl.handle.net/10045/37803
ISSN: 0167-8655 (Print) | 1872-7344 (Online)
DOI: 10.1016/j.patrec.2013.09.014
Idioma: eng
Tipo: info:eu-repo/semantics/article
Revisión científica: si
Versión del editor: http://dx.doi.org/10.1016/j.patrec.2013.09.014
Aparece en las colecciones:INV - GRFIA - Artículos de Revistas

Archivos en este ítem:
Archivos en este ítem:
Archivo Descripción TamañoFormato 
Thumbnail2014_Abreu_Rico_PRL_final.pdfVersión final (acceso restringido)639,85 kBAdobe PDFAbrir    Solicitar una copia
Thumbnail2014_Abreu_Rico_PRL.pdfVersión revisada (acceso abierto)145,1 kBAdobe PDFAbrir Vista previa


Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.