[es] - Pronalazenje delova istog texta u vise .txt fajlova?

arsa xx
Srdjan Arsic
Beograd

Član broj: 14203
Poruke: 452
*.air.tehnicom.net

ICQ: 247217004
Sajt: webdizajn.arsic.biz

Profil

Pronalazenje delova istog texta u vise .txt fajlova?

^{09.01.2004. u 15:00}

Da li postoji algoritan koji bi u n fajlova pronasao u kojima se nalaze isti delovi texta?
U mom slucaju isti delovi su na pocetku(i kraju) tekstualnih fajlova.

Flash komponenta za atraktivan prikaz vesti na sajtu:
www.flash-news-ticker.com

^{09.01.2004. u 15:00}

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
62.108.111.*

Profil

Re: Pronalazenje delova istog texta u vise .txt fajlova?

^{12.01.2004. u 13:57}

Nekada davno (u srednjoj skoli) radio sam na temu stringova i svh (koriscenih) operacija nad istima.

Sto se tvog problema tice radio sam nesto slicno a to je pronalazenje podudaranja svih sekvenci izmedju 2 polazna stringa. Naravno ti svaki text file mozes predstaviti kao jedan string (niz karaktera), a sto se tice podudaranj n datoteka to je samo uopstavanje slucaja i mislim da je izvodljivo.

E sada:
Pitanje u vezi procesorskog vremena/memorije (citaj optimizacije):

1. Postoji algoritam koji je memorijski totalno nezahtevan i radi u cistih O(n^2) za dva stringa i taj algoritam dao je Knuth.

2. Drugi algoritam koji sam opisivao je nesto sto am ja napravio i radi brze od prvobitno opisanog (mada razlika nije prevelika, ali je broj poredjenja optimalan) ali koristi dodatan memorijski prostor. E sad, ako nisi stisnut nekim ogranicenjima ovo bi mozda bilo i bolje resenje obzirom da poredjenje treba prosiriti na n sekvenci texta. U tom dodatnom prostoru upravo se cuvaju informacije o pronadjenim podudaranjima i zgodno je za prosirivanje jer svako novo poredjenje koristi vec odradjeni set informacija i cela stvar se drasticno ubrzava.

Inace izlaz oba algoritma koje imam odradjene su sve ponovljene frekvence.

Sto se tice pocetka / kraja datoteke to samo mozes iskoristiti kao dodatnu optimizaiju.

Da ne bi smarao forum nepotrebnim kilobajtima, javi se preko priv. poruke ili na loggzy@yahoo.com ako hoces da ti posaljem neki od navedenih algoritama. Obzirom da je to bio neki vid NI rada imam i tekstualno detaljno objasnjenje oba algoritma, mada ni ceo rad nije nesto ultra veliki.

Pozdrav !

^{12.01.2004. u 13:57}