Duplikaty w tekście

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.

zrobic kontener set i po kolei wrzucac do niego slowa

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

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.

w porzadku, ale co gdy powtorzenia nakladaja sie na siebie?

np. tamtamt

powtarza sie tam i amt, huh?

Analiza statystyczna reszty... co powtarza się częściej....

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.

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

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.

// 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,...

// 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) * ?

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

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)

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.

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.

Xitami napisał(a)

Mój ?pierwszy krok? to właśnie kontener set robiony ?na piechotę? :)

spox, po prostu jestem zwolennikiem gotowych rowiazan ;)

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]