Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Pronalazenje delova istog texta u vise .txt fajlova?

[es] :: Art of Programming :: Pronalazenje delova istog texta u vise .txt fajlova?

[ Pregleda: 5708 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

arsa xx
Srdjan Arsic
Beograd

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

ICQ: 247217004
Sajt: webdizajn.arsic.biz


Profil

icon Pronalazenje delova istog texta u vise .txt fajlova?09.01.2004. u 15:00 - pre 246 meseci
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
 
Odgovor na temu

dRock9
Kragujevac - Beograd

Član broj: 4217
Poruke: 54
62.108.111.*



Profil

icon Re: Pronalazenje delova istog texta u vise .txt fajlova?12.01.2004. u 13:57 - pre 246 meseci

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 [email protected] 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 !
 
Odgovor na temu

[es] :: Art of Programming :: Pronalazenje delova istog texta u vise .txt fajlova?

[ Pregleda: 5708 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.