Jak porządnie wyszukać, możliwie efektywnie duplikaty w tekście o długości nie przekraczającej 2147483648 znaków? Nie chodzi tu bynajmniej o powtarzające się litery/znaki (to też) ale głównie o słowa/zdania itp.
0
0
zrobic kontener set i po kolei wrzucac do niego slowa
0
wziasc pierwsze slowo i szukac go do konac textu, a duplikaty usuwac, pozniej drugie slowo...slowa <ort>porownoj </ort>dopoki literki sie zgadzaja, jak nie to wyskakuj z petli do porownywania slow
0
NO troche niedokładnie się wyraziłem. Nie chodzi mi tu o dosłowne duplikaty słów, ale np jeżeli w tekście jest coś takiego "kons tańcz poli konstantynopolitańczykowianeczka" to po skończeniu przejścia tekst powinien wyglądać teoretyczne "kons tańcz poli (wskaźnik do kons)tantyno(wskaźnik do poli)(wskaźnik do tańcz)ykowianeczka"
w każdym razie jakoś tak.
0
w porzadku, ale co gdy powtorzenia nakladaja sie na siebie?
np. tamtamt
powtarza sie tam i amt, huh?
0
Analiza statystyczna reszty... co powtarza się częściej....
0
Nie będzie to szybki algorytm :] . Można to zrobić tak:
Zaczynasz przeglądać tekst od poczatku. Jeśli chodzi o słowa o długości conajmniej 2 to będzie to troche dużo roboty. Ale Tobie chodzi chyba o to że trzeba wyszukiwać słow takich samych. Tak wnioskuje z podanego przykładu:
"kons tańcz poli konstantynopolitańczykowianeczka"
Zaczynasz przeszukiwać tekst od początku znak po znaku az napotkasz znak spacji. Wtedy wstrzymujesz wyszukiwanie i szukasz tego wzorca w całym tekscie zaczynając od miejsca po danym słowie, w naszym przypadku "kons". Porównujesz po kolei wszystki wzorce dlugosci 4 gdyż nasze słowo "kons" składa sie z 4 liter. A więc podaje przykład:
kons != tańc
kons != ańcz
kons != ńcz
kons != cz p
...
kons == kons
...
kons != czka
Aby zrobić to tak jak mówisz, czyli zapamietywać wskazniki musisz mieć tablice typu **char. W przypadku znalezienia danego wzorca kopiujesz wzorzec do *char, a następnie ten *char przypisujesz w miejcu zastąpienia wzorca i skracasz tablice. Kontynuujesz tak samo do końca tekstu. Mam nadzieje że dobrze wyjaśniłem :) . Powodzenia.
0
Kompresja LZW z 1 zrobi 2, a to może by przerobić na 3?
1.kons tańcz poli konstantynopolitańczykowianeczka
2.kons tańcz poli [ko][ns][ta]ntyno[po][li][ta][ńc]zy[ko]wiane[cz]ka
3.kons tańcz poli [kons][ta]ntyno[poli][tańc]zy[ko]wiane[cz]ka
0
z tym set'em to dobrze myslalem:
najpierw bierzesz slowa 1-literowe:
i wrzucasz do kontenera
[k][o][n][s][t][a][n][t][y][n][o][p][o][l][i][t][a][ń][c][z][y][k][o][w][i][a][n][e][c][z][k][a]
wtedy zostana usuniete duplikaty liter
nastepnie dwuwyrazowe:
konstantynopolitańczykowianeczka
[ko][on][ns][st][ta][an][nt] itd...
znow wrzucasz do kontenera kazdy wyraz
analogicznie trzyliterowe i wiecej
a usuwaniem duplikatow zajmie sie kontener set.
0
// Pierwsza przymiarka
//czytamy
// tekst składa się z "n" słów, różnych słów jest "m"
// t[1..n] to cały tekst, w tablicy znajdują się numery słów
// s[1..m] słownik
// c[1..m] licznik wystąpień słowa w tekście
m=0
n=0
while !eof {
n++
czytaj(slowo)
s[m+1]=slowo //wartownik
c[m+1]=1
i=1
while (s[i] != slowo)
i++
if (i>m) m++ // nowe słowo
else c[i]++ // już było, powiększamy tylko licznik
t[n]=i
}
// takie budowanie słownika (n*m/2) można i należy ulepszyć
// np. drzewo binarne (n * log m), mieszanie,...
0
// Krok drugi
for i=1..m
preprocesing(s[i]); //np. przy QuickSearch czy Knuth Moris Pratt
for j=1..m
if i != j && len(s[i]) < len(s[j])
szukaj(s[i],s[j])
// m*(m-1) * ?
0
xitami: jesli dobrze rozumiem twoj algorytm, to wczytujesz slowa oddzielone spacjami (lub inaczej) i liczysz je,
twoj zlozonosc to (n*m/2), a wrzucenie do set to jeden przebieg przez zbior slow a reszta zajmie sie implementacja set
0
Ja rozumiem, że pytającemu chodzi o powtórki pełnych słów.
Co do ?set?:
Dwuliterowych słowa to nie tylko
[ko][ns][ta][nt]... ale też
[on][st][an][t....,
jest ich ?n?-1, trzyliterowych n-2 ....., n-literowych 1.
tak działając set wołamy n*(n+1)/2 razy (dla n=1e6 to liczba 12-cyfrowa)
zapotrzebowanie na pamięć to pi razy oko n**3/6 (liczba 18-cyfrowa)
0
Xitami napisał(a)
Ja rozumiem, że pytającemu chodzi o powtórki pełnych słów.
i jezeli tak jest to wystarczy je wrzucac do set.
Sposob, kotry podalem wczesniej jest pomocny w wyszukiwaniu dowolnych duplikatow w tekscie, czy sa ta slowa czy jakiekolwiek dowolne ciagi liter.
0
Mój ?pierwszy krok? to właśnie kontener set robiony ?na piechotę? :) .
Krok drugi to coś co pierwsze przychodzi na myśl, ale dla 2MB tekstu? Ciekawe jakie może być ?m??
Co do Twojego pomysłu Vixen, to dla tekstu o długości 6363 znaków tylko by przechować znaki wszystkich ?podsłów? potrzeba 40 GB (może ich być ponad dwa miliony (n*n+n)/2, tyle razy dodajemy do kontenera), więc sposób raczej kiepski.
Co prawda różnych słów 1-literowych może być nie ?n? lecz tylko 256, 2-literowych nie ?n?-1 tylko 65536 (256**2), itd. Ale rośnie to na tyle szybko, że można to pominąć.
Wszystkich liter wszystkich podsłów jest:
(n-1)n(n+1)/6 = dwumian_newtona(n+1,3) = newton(n,3)+newton(n,2).
Ciekawa jest ta ostatnia tożsamość, ciekawym czy coś z tego wynika?
Kombinuję właśnie nad czymś takim (najdłuższe dwa zgodne podciągi), mam już coś chyba lepszego, ale to jeszcze nie to.
0
Xitami napisał(a)
Mój ?pierwszy krok? to właśnie kontener set robiony ?na piechotę? :)
spox, po prostu jestem zwolennikiem gotowych rowiazan ;)
0
Jaśli chodzi o kompresję to ja bym raczej proponował zacząć od wyszukania powtórzeń dłuższych 'słów', a potem dopiero tych krótszych.
Do przeszukiwania tekstu urzywamy KMP :) (a nie naiwnego porównywania - tak jak w jednym z poprzednich postów :P )
Więc najpierw należało by sprawdzić czy text nie składa się z dwóch identycznych części (tzn czy pierwsza połowa == druga)
I tak dalej do powtórzeń 2literkowych (o ile samo zapisanie wskaźnika nie zajmuje więcej niż te słowo ;) )
a złożoność jest mniejsza niż O(n!) << ale to strasznie dużo [sciana]