En matemáticas e informática , la distancia de edición de gráficos ( GED ) es una medida de similitud (o disimilitud) entre dos gráficos . El concepto de distancia de edición de gráficos fue formalizado matemáticamente por primera vez por Alberto Sanfeliu y King-Sun Fu en 1983. [1] Una aplicación importante de la distancia de edición de gráficos es la coincidencia de gráficos inexactos , como el reconocimiento de patrones tolerante a errores en el aprendizaje automático . [2]
La distancia de edición de gráficos entre dos gráficos está relacionada con la distancia de edición de cadenas entre cadenas . Con la interpretación de cadenas como conectados , gráficos acíclicos dirigidos de grado máximo uno, definiciones clásicas de la distancia de edición tales como la distancia Levenshtein , [3] [4] distancia de Hamming [5] y Jaro-Winkler distancia pueden interpretarse como gráfico de edición distancias entre gráficos adecuadamente restringidos. Asimismo, la distancia de edición de gráficos también es una generalización de la distancia de edición de árboles entre árboles enraizados . [6] [7] [8][9]
Definiciones y propiedades formales
La definición matemática de la distancia de edición del gráfico depende de las definiciones de los gráficos sobre los que se define, es decir, si se etiquetan los vértices y los bordes del gráfico y cómo se dirigen los bordes . Generalmente, dado un conjunto de operaciones de edición de gráficos (también conocidas como operaciones de gráficos elementales ), la distancia de edición de gráficos entre dos gráficos y , Escrito como Puede ser definido como
dónde denota el conjunto de rutas de edición que se transforman en (un grafo isomorfo a) y es el costo de cada operación de edición de gráficos .
El conjunto de operadores de edición de gráficos elementales generalmente incluye:
- inserción de vértice para introducir un único vértice etiquetado nuevo en un gráfico.
- eliminación de vértices para eliminar un único vértice (a menudo desconectado) de un gráfico.
- sustitución de vértices para cambiar la etiqueta (o el color) de un vértice dado.
- inserción de borde para introducir un nuevo borde de color entre un par de vértices.
- eliminación de borde para eliminar un solo borde entre un par de vértices.
- sustitución de bordes para cambiar la etiqueta (o el color) de un borde determinado.
Los operadores adicionales, pero menos comunes, incluyen operaciones como la división de aristas que introduce un nuevo vértice en una arista (también creando una nueva arista) y la contracción de aristas que elimina vértices de grado dos entre aristas (del mismo color). Aunque estos operadores de edición complejos pueden definirse en términos de transformaciones más elementales, su uso permite una parametrización más precisa de la función de coste. cuando el operador es más barato que la suma de sus componentes.
En [10] [11] se presenta un análisis profundo de los operadores de edición de gráficos elementales .
Y se han presentado algunos métodos para deducir automáticamente estos operadores de edición de gráficos elementales [12] [13] [14] [15] [16]
Aplicaciones
La distancia de edición de gráficos encuentra aplicaciones en el reconocimiento de escritura a mano , [17] el reconocimiento de huellas dactilares [18] y la química informática . [19]
Algoritmos y complejidad
Los algoritmos exactos para calcular la distancia de edición de gráficos entre un par de gráficos normalmente transforman el problema en uno de encontrar la ruta de edición de costo mínimo entre los dos gráficos. El cálculo de la ruta óptima de edición se presenta como una búsqueda de caminos de búsqueda o problema del camino más corto , a menudo implementado como un A * algoritmo de búsqueda .
Además de los algoritmos exactos, también se conocen varios algoritmos de aproximación eficientes. La mayoría de ellos tienen tiempo de cálculo cúbico [20] [21] [22] [23] [24]
Además, existe un algoritmo que deduce una aproximación del GED en tiempo lineal [25]
A pesar de que los algoritmos anteriores a veces funcionan bien en la práctica, en general el problema de calcular la distancia de edición de gráficos es NP-completo [26] (para una prueba que está disponible en línea, consulte la Sección 2 de Zeng et al. ), E incluso es difícil de aproximar (formalmente, es APX -hard [27] ).
Referencias
- ^ Sanfeliu, Alberto; Fu, King-Sun (1983). "Una medida de distancia entre gráficos relacionales atribuidos para el reconocimiento de patrones". Transacciones IEEE sobre sistemas, hombre y cibernética . 13 (3): 353–363. doi : 10.1109 / TSMC.1983.6313167 .
- ^ Gao, Xinbo; Xiao, Bing; Tao, Dacheng; Li, Xuelong (2010). "Un estudio de la distancia de edición del gráfico". Análisis de patrones y aplicaciones . 13 : 113-129. doi : 10.1007 / s10044-008-0141-y .
- ^ Влади́мир И. Левенштейн (1965).Двоичные коды с исправлением выпадений, вставок и замещений символов[Códigos binarios capaces de corregir eliminaciones, inserciones y reversiones]. Доклады Академий Наук СССР (en ruso). 163 (4): 845–848.
- ^ Levenshtein, Vladimir I. (febrero de 1966). "Códigos binarios capaces de corregir eliminaciones, inserciones y reversiones". Física soviética Doklady . 10 (8): 707–710.
- ^ Hamming, Richard W. (1950). "Códigos de detección y corrección de errores" (PDF) . Revista técnica de Bell System . 29 (2): 147–160. doi : 10.1002 / j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . Señor 0035935 . Archivado desde el original el 25 de mayo de 2006.CS1 maint: bot: estado de URL original desconocido ( enlace )
- ^ Shasha, D; Zhang, K (1989). "Algoritmos sencillos y rápidos para la edición de la distancia entre árboles y problemas relacionados". SIAM J. Comput. 18 (6): 1245-1262. CiteSeerX 10.1.1.460.5601 . doi : 10.1137 / 0218082 .
- ^ Zhang, K (1996). "Una distancia de edición limitada entre árboles etiquetados desordenados". Algoritmica . 15 (3): 205–222. doi : 10.1007 / BF01975866 .
- ^ Bille, P (2005). "Una encuesta sobre la distancia de edición de árboles y problemas relacionados" . Theor. Computación. Sci. 337 (1-3): 22-34. doi : 10.1016 / j.tcs.2004.12.030 .
- ^ Demaine, Erik D .; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2010). "Un algoritmo de descomposición óptimo para la distancia de edición del árbol". Transacciones ACM sobre algoritmos . 6 (1): A2. CiteSeerX 10.1.1.163.6937 . doi : 10.1145 / 1644015.1644017 . Señor 2654906 .
- ^ Serratosa, Francesc (2019). Distancia de edición del gráfico: restricciones para ser una métrica . Reconocimiento de patrones, 90, págs: 250-256.
- ^ Serratosa, Francesc; Cortés, Xavier (2015). Distancia de edición de gráficos: pasar de la estructura global a la local para resolver el problema de coincidencia de gráficos . Cartas de reconocimiento de patrones, 65, págs: 204-210.
- ^ Santacruz, Pep; Serratosa, Francesc (2020). Aprender los costos de edición de gráficos basados en un modelo de aprendizaje aplicado a la coincidencia de gráficos subóptima . Neural Processing Letters, 51, págs: 881–904.
- ^ Algabli, Shaima; Serratosa, Francesc (2018). Incrustar las asignaciones de nodo a nodo para aprender los parámetros de distancia de edición del gráfico . Cartas de reconocimiento de patrones, 112, págs: 353-360.
- ^ Xavier, Cortés; Serratosa, Francesc (2016). Gráfico de aprendizaje que empareja los pesos de sustitución basados en la correspondencia del nodo de verdad del terreno . Revista Internacional de Reconocimiento de Patrones e Inteligencia Artificial, 30 (2), pp: 1650005 [22 páginas].
- ^ Xavier, Cortés; Serratosa, Francesc (2015). Aprendizaje de los costos de edición de coincidencia de gráficos basados en la optimización de las correspondencias de nodos de Oracle . Cartas de reconocimiento de patrones, 56, págs: 22-29.
- ^ Conte, Donatello; Serratosa, Francesc (2020). Aprendizaje interactivo en línea para el emparejamiento de gráficos utilizando estrategias activas . Sistemas basados en el conocimiento, 105, págs: 106275.
- ^ Fischer, Andreas; Suen, Ching Y .; Frinken, Volkmar; Riesen, Kaspar; Bunke, Horst (2013), "A Fast Matching Algorithm for Graph-Based Handwriting Recognition", Representaciones basadas en gráficos en el reconocimiento de patrones , Lecture Notes in Computer Science , 7877 , págs. 194-203, doi : 10.1007 / 978-3- 642-38221-5_21 , ISBN 978-3-642-38220-8
- ^ Neuhaus, Michel; Bunke, Horst (2005), "A Graph Matching Based Approach to Fingerprint Classification using Directional Variance", Autenticación biométrica de persona basada en audio y video , Lecture Notes in Computer Science , 3546 , págs. 191-200, doi : 10.1007 / 11527923_20 , ISBN 978-3-540-27887-0
- ^ Birchall, Kristian; Gillet, Valerie J .; Harper, Gavin; Pickett, Stephen D. (enero de 2006). "Medidas de similitud de formación para actividades específicas: aplicación a gráficos reducidos". Revista de información química y modelado . 46 (2): 557–586. doi : 10.1021 / ci050465e . PMID 16562986 .
- ^ Neuhaus, Michel; Bunke, Horst (noviembre de 2007). Reduciendo la brecha entre la distancia de edición de gráficos y las máquinas de kernel . Percepción de máquinas e inteligencia artificial. 68 . World Scientific. ISBN 978-9812708175.
- ^ Riesen, Kaspar (febrero de 2016). Reconocimiento de patrones estructurales con distancia de edición de gráficos: algoritmos de aproximación y aplicaciones . Avances en Visión por Computador y Reconocimiento de Patrones. Saltador. ISBN 978-3319272511.
- ^ Serratosa, Francesc (2014). Cálculo rápido de la correspondencia de gráficos bipartitos . Cartas de reconocimiento de patrones, 45, págs: 244 - 250.
- ^ Serratosa, Francesc (2015). Aceleración de la comparación rápida de gráficos bipartitos a través de una nueva matriz de costos . Revista Internacional de Reconocimiento de Patrones e Inteligencia Artificial, 29 (2), 1550010, [17 páginas].
- ^ Serratosa, Francesc (2015). Cálculo de la distancia de edición del gráfico: razonamiento sobre la optimización y la aceleración . Computación de imagen y visión, 40, pp: 38-48.
- ^ Santacruz, Pep; Serratosa, Francesc (2018). Coincidencia de gráficos tolerante a errores en el costo computacional lineal utilizando una pequeña coincidencia parcial inicial . Cartas de reconocimiento de patrones.
- ^ Garey y Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman and Company. ISBN 978-0-7167-1045-5.
- ^ Lin, Chih-Long (25 de agosto de 1994). "Dureza del problema de transformación de gráfico aproximado". En Du, Ding-Zhu; Zhang, Xiang-Sun (eds.). Algoritmos y Computación . Apuntes de conferencias en informática. 834 . Springer Berlín Heidelberg. págs. 74–82. doi : 10.1007 / 3-540-58325-4_168 . ISBN 9783540583257.