Kuvaajan muokkausetäisyys

Kuvaajan muokkausetäisyys on kahden kaavion samankaltaisuus (tai erilaisuus) kerroin . Kuvaajan muokkausetäisyyden käsitteen muotoilivat ensimmäisen kerran matemaattisesti Alberto Sanfeliu ja King-San Fu vuonna 1983 [1] . Kuvaajan muokkausetäisyyden pääasiallinen sovellus on epätäsmällinen kuvaajasovitus , kuten koneoppimisen robusti kuviontunnistus [2] .

Kuvaajan muokkausetäisyys kahden kaavion välillä on suhteessa rivien väliseen muokkausetäisyyteen . Kun nieluja tulkitaan kytketyiksi suunnatuiksi asyklisiksi kuvaajiksi , joiden maksimiaste on kaksi, klassiset muokkausetäisyyden määritelmät, kuten Levenshteinin etäisyys [3] , Hammingin etäisyys [4] ja Jaro-Winkler-etäisyys , voidaan tulkita graafin muokkausetäisyyksiksi välillä sopivat kaaviot. Vastaavasti kaavion muokkausetäisyys on yleistys puun muokkausetäisyydestä juurtuneiden puiden välillä [5] [6] [7] [8] .

Muodolliset määritelmät ja ominaisuudet

Kuvaajan muokkausetäisyyden matemaattinen määritelmä riippuu niiden kuvaajien määritelmästä, joille etäisyys on määritelty. Se riippuu esimerkiksi siitä, onko ja miten graafin kärjet ja reunat on merkitty , ja myös siitä, onko graafi suunnattu . Yleensä ottaen huomioon joukko graafin muokkaustoimintoja (tunnetaan myös nimellä alkeiskuvaajan operaatiot ), kaavion muokkausetäisyys kahden kaavion välillä ja , kirjoitettuna muodossa , voidaan määritellä seuraavasti

,

jossa tarkoittaa joukkoa muunnospolkuja kohteeseen ( kuvaajan isomorfinen ) ja on yhtä suuri kuin kunkin muokkaustoimenpiteen hinta .

Perusgraafisten operaatioiden joukko sisältää yleensä:

vertexin lisäys — yksi uusi merkitty kärkipiste lisätään kuvaajaan. kärjen poisto — yksi (usein toisiinsa liittymätön) kärki poistetaan graafista. kärkipisteen korvaaminen - tietyn kärjen etiketin (tai värin) muuttaminen. reunan lisäys — uusi värillinen reuna lisätään graafiin kärkiparin väliin. reunan poisto — yhden reunan poistaminen kärkiparin välistä. reunan korvaaminen - muuta tietyn reunan etikettiä (tai väriä).

Lisäksi, mutta harvemmin, toiminnot, kuten reunan jakaminen , joka lisää uuden kärjen reunaan (jolloin syntyy kaksi reunaa), ja reunan kutistuminen , joka poistaa toisen asteen kärjen reunojen väliltä (samanväriset), kun taas yhdistämällä kaksi reunaa, sisältyvät yhteen. Vaikka tällaiset monimutkaiset toiminnot voidaan määritellä yksinkertaisemmilla muunnoksilla, niiden käyttö mahdollistaa kustannusfunktion paremman parametrisoinnin, kun operaattori on halvempi kuin osiensa summa.

Sovellukset

Kuvaajan muokkausetäisyydellä on sovelluksia käsinkirjoituksen tunnistuksessa [9] , sormenjälkien tunnistuksessa [10] ja kemoinformatiikassa [11] .

Algoritmit ja monimutkaisuus

Tarkat algoritmit kuvaajaparin välisen kaavion muokkausetäisyyden laskemiseksi yleensä muuttavat ongelman ongelmaksi löytää pienin muunnospolku kahden kaavion välillä. Optimaalisen muokkauspolun laskeminen rajoittuu polun etsintään tai lyhimmän polun ongelmaan , joka usein toteutetaan A*-hakualgoritmina .

Tarkkojen algoritmien lisäksi tunnetaan monia tehokkaita approksimaatioalgoritmeja [12] [13] .

Vaikka yllä olevat algoritmit toimivat joskus hyvin käytännössä, yleensä graafin muokkausetäisyyden laskentaongelma on NP-täydellinen [14] (todiste tästä löytyy Zeng et al.:n verkkosivuilta osiosta 2 ) ja jopa vaikea approksimoida (muodollisesti se on APX -hard [15] ).

Muistiinpanot

  1. ↑ Sanfeliu, Fu, 1983 , s. 353-363.
  2. ↑ Gao, Xiao, Tao, Li, 2010 , s. 113-129.
  3. ↑ Levenshtein, 1965 , s. 845–848.
  4. ↑ Hamming, 1950 , s. 147-160.
  5. ↑ Shasha ja Zhang 1989 , s. 1245–1262.
  6. ↑ Zhang, 1996 , s. 205–222.
  7. ↑ Bille, 2005 , s. 22–34.
  8. ↑ Demaine, Mozes, Rossman, Weimann, 2010 , s. A2.
  9. ↑ Fischer, Suen, Frinken, Riesen, Bunke, 2013 , s. 194-203.
  10. ↑ Neuhaus, Bunke, 2005 , s. 191-200.
  11. ↑ Birchall, Gillet, Harper, Pickett, 2006 , s. 557–586.
  12. ↑ Neuhaus, Bunke, 2007 .
  13. ↑ Riesen, 2016 .
  14. ↑ Garey, Johnson, 1979 .
  15. ↑ Lin, 1994 , s. 74–82.

Kirjallisuus