Back

ⓘ Vagner-Fišerov algoritam




                                     

ⓘ Vagner-Fišerov algoritam

Levenštajnovo rastojanje ima nekoliko prostih gornjih i donjih granica koje su korisne u primenama u kojima se računaju i uporeduju. Ovo uključuje da:

  • Ako su niske istih veličina, Hamingovo rastojanje je gornja granica Levenštajnovog rastojanja.
  • Nula je ako i samo ako su niske identične.
  • Uvek je barem razlika u veličini dve niske.
  • U većini slučajeva je dužina duže niske.
                                     

1. Literatura

  • R.A. Wagner and M.J. Fischer. 1974. The String-to-String Correction Problem. Journal of the ACM, 211:168–173.
  • Gusfield, Dan 1997. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-58519-4.
                                     
  • podniz dužine 3. Levenštajnovo rastojanje Najduži zajednički podniz Vagner - Fišerov algoritam Hunt, James W. McIlroy, M. Douglas 1976 An Algorithm for Differential
  • рачуна помоћу алгоритма динамичког програмирања званог Вагнер - Фишер. Након завршетка Вагнер - Фишеровог алгоритма, минимални низ операција уређивања може да