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

Empreu sempre aquest identificador per citar o enllaçar aquest ítem http://hdl.handle.net/10045/37803
Información del item - Informació de l'item - Item information
Títol: A new iterative algorithm for computing a quality approximate median of strings based on edit operations
Autors: Abreu Salas, José Ignacio | Rico Juan, Juan Ramón
Grups d'investigació o GITE: Reconocimiento de Formas e Inteligencia Artificial
Centre, Departament o Servei: Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos
Paraules clau: Approximate median string | Edit distance | Edit operations
Àrees de coneixement: Lenguajes y Sistemas Informáticos
Data de publicació: 15-de gener-2014
Editor: Elsevier
Citació bibliogràfica: Pattern Recognition Letters. 2014, 36: 74-80. doi:10.1016/j.patrec.2013.09.014
Resum: 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.
Patrocinadors: 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
Tipus: info:eu-repo/semantics/article
Revisió científica: si
Versió de l'editor: http://dx.doi.org/10.1016/j.patrec.2013.09.014
Apareix a la col·lecció: INV - GRFIA - Artículos de Revistas

Arxius per aquest ítem:
Arxius per aquest ítem:
Arxiu Descripció Tamany Format  
Thumbnail2014_Abreu_Rico_PRL_final.pdfVersión final (acceso restringido)639,85 kBAdobe PDFObrir     Sol·licitar una còpia
Thumbnail2014_Abreu_Rico_PRL.pdfVersión revisada (acceso abierto)145,1 kBAdobe PDFObrir Vista prèvia


Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.