A new iterative algorithm for computing a quality approximate median of strings based on edit operations
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/37803
Title: | A new iterative algorithm for computing a quality approximate median of strings based on edit operations |
---|---|
Authors: | Abreu Salas, José Ignacio | Rico-Juan, Juan Ramón |
Research Group/s: | Reconocimiento de Formas e Inteligencia Artificial |
Center, Department or Service: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Keywords: | Approximate median string | Edit distance | Edit operations |
Knowledge Area: | Lenguajes y Sistemas Informáticos |
Issue Date: | 15-Jan-2014 |
Publisher: | Elsevier |
Citation: | Pattern Recognition Letters. 2014, 36: 74-80. doi:10.1016/j.patrec.2013.09.014 |
Abstract: | 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. |
Sponsor: | 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 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Peer Review: | si |
Publisher version: | http://dx.doi.org/10.1016/j.patrec.2013.09.014 |
Appears in Collections: | INV - GRFIA - Artículos de Revistas |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2014_Abreu_Rico_PRL_final.pdf | Versión final (acceso restringido) | 639,85 kB | Adobe PDF | Open Request a copy |
2014_Abreu_Rico_PRL.pdf | Versión revisada (acceso abierto) | 145,1 kB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.