Subversor
4/30/2007 10:26:00 PM
"Janek!" <3447435@gg.pl> wrote in message
news:f15h96$paa$1@opal.futuro.pl...
> Witam!
>
> Mam tekst, chcê wyci±gn±æ z niego powtarzaj±ce siê frazy.
>
> Przeszuka³em archiwum, nie uda³o mi siê znale¼æ opisu takiego problemu, a
> jako ¿e posiadam niewielk± wiedzê z zakresu algorytmiki, chcia³bym
> zweryfikowaæ swoje w³asne pomys³y. A oto co wymy¶li³em:
>
> 1. Ca³y tekst zapisujê jako tablicê wyrazów [A].
> 2. W tablicy [B] zapisujê wszystkie wyrazy które wyst±pi³y conajmniej 2
> razy.
>
> Porównujê s±siedztwo wszystkich wyst±pieñ kolejnych wyrazów z tablicy [B].
> Oddalam siê w obie strony od danego wyrazu a¿ do znalezienia unikalnego
> ci±gu wyrazów. Powtarzaj±ce siê ci±gi zapisujê w nowej tablicy. Wybieram
> unikalne.
>
> W ten sposób ka¿d± frazê zbadam tyle razy z ilu sk³ada siê wyrazów. Mo¿e
> kto¶ wymy¶li³ ju¿ co¶ bardziej sprytnego?
>
witam
tak na szybko co mi przyszlo do glowy:
1) od ilu wyrazow "zaczyna sie fraza" od trzech? bo dwoch na pewno nie.
2) rozumiem ze chcesz znac tylko powtarzajace sie frazy nie ich liczbe
wystapienia
uwaga tworze na biezaco ;) :
0) traktuje tekst wejsciowy jako tablice T zeby bylo latwiej wytlumaczyc
1)
tworze tablice A z wyrazami wystepujacymi wyrazami w tekscie z liczba
wystapien.
i sortuje ja dla szybszego wyszukiwania;
2) szukam 2 wyrazowych fraz:
- tworze tablice dwu fraz dwuFraza; //nie wiem czego uzywasz ale mozna uzyc
hashMap czy czogos w tym stylu ale to tylko dla zobrazowania szczegoly
zostawiam Tobie
for(int i=1;i<T.length;i++}{ //przelatuje przez tekst
if (ileRazyWystepuje(T[i])==1) continue;
if(ileRazyWystepuje(T[i-1]==1 continue;
dwuFraza.add(T[i-1],T[i]);
}
---
function: ileRazyWystepuje (wyraz)->int
3)dwuFraza zamieniamy na dwuFrazaIle (wyraz,wyraz,ilosc)
czyli w skrocie liczymy ile razy dana dwufraza wystapila(oczywiscie gdy mamy
cos w stylu hashMap pomijamy ten punkt)
jezeli tablica jest pusta badz, wszystkie wystepuja raz to koniec
4)szukam 3 wyrazowych fraz:
- tworze tablice trzyFraza;
for(int i=2;i<T.length;i++){
if(ileRazyWystepuje(T[i],T[i-1)==1) continue;
if(ileRazyWystepuje(T[i-2]==1) continue;
trzyFraza.add(T[i-2],T[i-1],T[i]);
}
5) to samo co punkt 3 , liczymy ile razy frazy wystepuja
jezeli tablica jest pusta badz, wszystkie wystepuja raz to koniec
i tak w kolko az tablica bedzie pusta badz wszystkie frazy beda wystepowaly
jeden raz.
nastepnie:
jedziemy od tylu ;)
sprawdzamy np. piecFraza wyciagamy wszystkie ktore powtarzaja sie wiecej niz
raz (hehe jezeli sie powtarzaja to musi byc wiecej niz raz) dodajemy do
tablicy Wyjscie
nastepnie robimy podobnie z czteryFraza ale zanim dodamy do TablicyWyjscie
sprawdzamy czy nie jest przypadkiem podciagiem z Wyjscia(tam jzu sa elementy
z piecFraza)
itd.
ogolnie przez tablice tekstu przelatujemy tyle razy ilu wyrazowa jest
najdluzsza fraza
trzeba by bylo pomyslec jakos nad eleminacja wyrazow z tablicy T (a raczej
ciagow ktore na pewno nie beda ciagami)
w sumie lato to osiagnac ale nie mam teraz czasu tego napisac
Pozdrawiam
Subversor