Distanța de editare a graficului

Distanța de editare a graficului este coeficientul de similitudine (sau disimilare) dintre două grafice . Conceptul de distanță de editare a graficului a fost formulat pentru prima dată matematic de Alberto Sanfeliu și King-San Fu în 1983 [1] . Aplicația principală a distanței de editare a graficului este potrivirea inexactă a graficului , cum ar fi recunoașterea robustă a modelelor în învățarea automată [2] .

Distanța de editare a graficului dintre două grafice este legată de distanța de editare dintre rânduri . Atunci când interpretăm chiuvetele ca grafice aciclice direcționate conectate cu un grad maxim de doi, definițiile clasice ale distanței de editare, cum ar fi distanța Levenshtein [3] , distanța Hamming [4] și distanța Jaro-Winkler , pot fi interpretate ca distanțe de editare a graficului între grafice adecvate. În mod similar, distanța de editare a graficului este o generalizare a distanței de editare a arborelui dintre arborii înrădăcinați [5] [6] [7] [8] .

Definiții și proprietăți formale

Definiția matematică a distanței de editare a graficului depinde de definiția graficelor pentru care este definită distanța. De exemplu, depinde dacă și cum sunt etichetate vârfurile și muchiile graficului și, de asemenea, dacă graficul este direcționat . În general, având în vedere un set de operații de editare a graficelor (cunoscute și ca operații elementare de grafic ), distanța de editare a graficului dintre două grafice și , scrisă ca , poate fi definită ca $g_{1)$ $g_{2)$ $GED(g_{1},g_{2})$

GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P))(g_{1}, g_{2})}\sum _{i=1}^{k}c(e_{i})

unde înseamnă setul de căi de transformare către ( izomorf la grafic) și este egal cu costul fiecărei operațiuni de editare . ${\mathcal {P}}(g_{1},g_{2})$ $g_{1)$ $g_{2)$ $c(e)\geqslant 0$ $e$

Setul de operații elementare grafice include de obicei:

inserarea nodurilor — un nou vârf etichetat este inserat în grafic. eliminarea vârfurilor — un vârf (adesea fără legătură) este eliminat din grafic. înlocuirea unui vârf - schimbarea etichetei (sau a culorii) unui vârf dat. inserarea muchiei — o nouă muchie colorată este inserată în grafic între o pereche de vârfuri. edge removal — îndepărtarea unei muchii între o pereche de vârfuri. înlocuire margine - schimbați eticheta (sau culoarea) unei margini date.

În plus, dar mai rar, operațiuni precum împărțirea unei muchii , care inserează un nou vârf într-o muchie (rezultând două muchii) și micșorarea unei muchii , care elimină un vârf de gradul doi între muchii (de aceeași culoare) în timp ce îmbinarea celor două margini, sunt incluse într-una. Deși astfel de operații complexe pot fi definite în termeni de transformări mai simple, utilizarea lor permite o mai bună parametrizare a funcției de cost atunci când operatorul este mai ieftin decât suma părților sale. $c$

Aplicații

Distanța de editare a graficelor are aplicații în recunoașterea scrisului de mână [9] , recunoașterea amprentei [10] și chimioinformatică [11] .

Algoritmi și complexitate

Algoritmii exacti pentru calcularea distanței de editare a graficului dintre o pereche de grafice transformă de obicei problema într-o problemă de găsire a căii minime de transformare între două grafice. Calcularea căii optime de editare se reduce la identificarea căii sau la problema căii celei mai scurte , adesea implementată ca algoritm de căutare A* .

Pe lângă algoritmii exacti, sunt cunoscuți mulți algoritmi de aproximare eficienți [12] [13] .

Deși algoritmii de mai sus funcționează uneori bine în practică, în general, problema calculării distanței de editare a unui grafic este NP-complet [14] (o dovadă a acestui lucru este disponibilă în secțiunea 2 de pe site-ul lui Zeng și colab. ) și chiar greu de aproximat (formal, este APX -hard [15] ).

Note

↑ Sanfeliu, Fu, 1983 , p. 353–363.
↑ Gao, Xiao, Tao, Li, 2010 , p. 113-129.
↑ Levenshtein, 1965 , p. 845–848.
↑ Hamming, 1950 , p. 147–160.
↑ Shasha și Zhang 1989 , p. 1245–1262.
↑ Zhang, 1996 , p. 205–222.
↑ Bille, 2005 , p. 22–34.
↑ Demaine, Mozes, Rossman, Weimann, 2010 , p. A2.
↑ Fischer, Suen, Frinken, Riesen, Bunke, 2013 , p. 194–203.
↑ Neuhaus, Bunke, 2005 , p. 191–200.
↑ Birchall, Gillet, Harper, Pickett, 2006 , p. 557–586.
↑ Neuhaus, Bunke, 2007 .
↑ Riesen, 2016 .
↑ Garey, Johnson, 1979 .
↑ Lin, 1994 , p. 74–82.

Literatură

Alberto Sanfeliu, King-Sun Fu. O măsură a distanței dintre graficele relaționale atribuite pentru recunoașterea modelelor // IEEE Transactions on Systems, Man and Cybernetics . - 1983. - T. 13 , nr. 3 . — S. 353–363 . - doi : 10.1109/TSMC.1983.6313167 .
Xinbo Gao, Bing Xiao, Dacheng Tao, Xuelong Li. Un studiu al distanței de editare a graficului // Analiza modelelor și aplicații. - 2010. - T. 13 . — p. 113–129 . - doi : 10.1007/s10044-008-0141-y .
Vladimir I. Levenshtein. Coduri binare cu corectarea ștergerilor, inserărilor și substituirilor de simboluri // Rapoarte ale Academiilor de Științe ale CCCP. - 1965. - T. 163 , nr. 4 . — S. 845–848 .
Richard W. Hamming. Codurile de detectare și corectare a erorilor // Jurnal tehnic Bell System . - 1950. - T. 29 , nr. 2 . — S. 147–160 . - doi : 10.1002/j.1538-7305.1950.tb00463.x . Arhivat din original pe 25 mai 2006.
Shasha D., Zhang K. Algoritmi simpli și rapidi pentru distanța de editare dintre arbori și probleme aferente // SIAM J. Comput. . - 1989. - T. 18 , nr 6 . - S. 1245-1262 . - doi : 10.1137/0218082 .
Zhang K. O distanță de editare restrânsă între arbori etichetați neordonați // Algorithmica . - 1996. - T. 15 , nr 3 . — S. 205–222 . - doi : 10.1007/BF01975866 .
Bille P. A survey on tree edit distance and related problems // Theor. Calculator. sci. . - 2005. - T. 337 , nr. 1–3 . — S. 22–34 . - doi : 10.1016/j.tcs.2004.12.030 .
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann. Un algoritm de descompunere optim pentru distanța de editare a arborelui // ACM Transactions on Algorithms . - 2010. - T. 6 , nr. 1 . - S. A2 . - doi : 10.1145/1644015.1644017 .
Andreas Fischer, Ching Y. Suen, Volkmar Frinken, Kaspar Riesen, Horst Bunke. Un algoritm de potrivire rapidă pentru recunoașterea scrisului de mână bazat pe grafic // Reprezentări bazate pe grafic în recunoașterea modelelor. - 2013. - T. 7877. - S. 194-203. — ( Note de curs în Informatică ). — ISBN 978-3-642-38220-8 . - doi : 10.1007/978-3-642-38221-5_21 .
Michel Neuhaus, Horst Bunke. O abordare bazată pe potrivirea grafică a clasificării amprentei folosind variația direcțională // Autentificarea persoanei biometrice pe bază de audio și video. - 2005. - T. 3546. - S. 191-200. — ( Note de curs în Informatică ). — ISBN 978-3-540-27887-0 . - doi : 10.1007/11527923_20 .
Kristian Birchall, Valerie J. Gillet, Gavin Harper, Stephen D. Pickett. Măsuri de similaritate de instruire pentru activități specifice: aplicare la grafice reduse // Journal of Chemical Information and Modeling . - 2006. - ianuarie ( vol. 46 , nr. 2 ). — S. 557–586 . - doi : 10.1021/ci050465e . — PMID 16562986 .
Michel Neuhaus, Horst Bunke. Reducerea decalajului dintre Distanța de editare a graficului și Mașinile Kernel. - World Scientific, 2007. - V. 68. - (Machine Perception and Artificial Intelligence). — ISBN 978-9812708175 .
Kaspar Riesen. Recunoașterea modelelor structurale cu editarea graficelor Distanța: algoritmi și aplicații de aproximare. - Springer, 2016. - (Advances in Computer Vision and Pattern Recognition). — ISBN 978-3319272511 .
Garey MR, Johnson DS Computers and Intractability: A Guide to the Theory of NP-Completeness . - W.H. Freeman and Company, 1979. - ISBN 978-0-7167-1045-5 .
Chih Long Lin. Duritatea problemei de transformare a grafului de aproximare // Algoritmi și calcul / Ding-Zhu Du, Xiang-Sun Zhang. - Springer Berlin Heidelberg, 1994. - T. 834. - (Lecture Notes in Computer Science). — ISBN 9783540583257 . - doi : 10.1007/3-540-58325-4_168 .