Untitled
unknown
plain_text
4 years ago
5.0 kB
4
Indexable
import React from 'react'; import classes from '../Lesson.module.scss'; const Lesson223 = () => ( <div className={classes.root}> <h1> NOVO REŠENJE ZA PROBLEM PRIBLIŽNOG PODUDARANJA </h1> <p className={classes.indent1x}> Radili smo algoritam dinamičkog programiranja koji nam omogućava da nađemo edit rastojanje između dve niske. Sada ćemo videti njegovu primenu na problem traženja približnog podudaranja šablona P sa tekstom T. </p> <p className={classes.indent1x} /> <p className={classes.indent1x}> Matrica za dve niske X i Y je u prethodnom delu izgledala na sledeći način: </p> <img alt="" src="/assets/lesson223/pic1.svg" className={classes.indent2x} /> <p className={classes.indent1x}>Sada ćemo, umesto niski X i Y, imati šablon P i tekst T:</p> <img alt="" src="/assets/lesson223/pic2.svg" className={classes.indent2x} /> <p className={classes.indent2x}> Ovde, za razliku od prethodnog, inicijalizujemo prvu vrstu na sve nule. To radimo jer ne znamo na početku na kojoj poziciji će se naš šablon pojaviti, stoga je svaka pozicija jednako verovatna, odnosno ne dajemo prednost ni jednoj poziciji u tekstu T. Prva kolona se inicijalizuje na isiti način kao što smo to i radili za niske X i Y: </p> <img alt="" src="/assets/lesson223/pic3.svg" className={classes.indent3x} /> <p className={classes.indent2x}> Posle inicijalizacije možemo popuniti datu matricu na isti način kao što smo to radili i za niske X i Y: </p> <img alt="" src="/assets/lesson223/pic4.svg" className={classes.indent3x} /> <p className={classes.indent2x}>Tražimo minimum u poslednjoj vrsti:</p> <img alt="" src="/assets/lesson223/pic5.svg" className={classes.indent3x} /> <p className={classes.indent2x}> Minimum, koji je ovde 2, predstavlja najbliže podudaranje šablona P sa tekstom T (između njih ima samo 2 razlike). Sada znamo edit rastojanje između šablona i teksta, ali ne znamo na kojoj poziciji se to približno podudaranje desilo. Prvo što treba da uradimo jeste da vidimo kako smo došli do polja gde nam se nalazi 2. To ćemo uraditi primenom inverznog postupka računanja edit rastojanja: </p> <p className={classes.indent2x}>korak1</p> <img alt="" src="/assets/lesson223/pic6.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak2</p> <img alt="" src="/assets/lesson223/pic7.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak3</p> <img alt="" src="/assets/lesson223/pic8.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak4</p> <img alt="" src="/assets/lesson223/pic9.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak5</p> <img alt="" src="/assets/lesson223/pic10.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak6</p> <img alt="" src="/assets/lesson223/pic11.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak7</p> <img alt="" src="/assets/lesson223/pic12.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak8</p> <img alt="" src="/assets/lesson223/pic13.svg" className={classes.indent3x} /> <p className={classes.indent2x}>korak9</p> <img alt="" src="/assets/lesson223/pic14.svg" className={classes.indent3x} /> <p className={classes.indent2x}> Dobili smo da se približno podudaranje sa 2 razlike između šablona P i teksta T događa na poziciji 5 jer je to pozicija polja koje se nalazi u vrsti gde je početak šablona, a na koje smo prvo naišli u inverznom postupku. </p> <p className={classes.indent2x}> Putanju koja se sastoji od narandžastih kvadrata zovemo <b>putanja povratka</b> i ona govori o promenama do kojih je došlo između šablona P i teksta T. Jedino vertikalno pomeranje (sva ostala su dijagonalna) nam označava da se desilo umetanje. Samim tim, osim što možemo odrediti poziciju gde se desilo približno podudaranje, možemo odrediti i koje su se to promene (razlike) desile između šablona i teksta. </p> <img alt="" src="/assets/lesson223/pic15.svg" className={classes.indent3x} /> <p className={classes.indent1x}> Ovaj metod predstavlja <b>veliko memorijsko zauzeće</b> O(mn), gde je m dužina šablona, a n dužina teksta, a kao što smo videli tekst (genom) može biti dugačak i 3 milijarde (kod čoveka). Samim tim, ovo se ne može koristiti bez pomoćnih algoritama za rešavanje problema poravnanja očitavanja. Jedan od pomoćnih algoritama koji koristimo u kombinaciji sa dinamičkim programiranjem jeste indeksiranje. Na koji to način radimo videćemo u poslednjem delu koji je posvećen ovom problemu. </p> </div> ); export default Lesson223;
Editor is loading...