Mam proste pakowanie: gdy jakiś ciąg długości 3-18 bajtów już wcześniej niedawno występował w pliku, jest zastępowany 16 bitami - 12 bitów pozycji wcześniejszego wystąpienia i 4 bajty długości. Dekodowanie jest proste, ale jak szybko wyszukiwać wcześniejsze pozycje?
Dla trzech bajtów mam listę wystąpień, dodaję bajt i sprawdzam, czy wszystkie wystąpienia znikną czy też będzie wcześniejsze z długością równą cztery.
Możesz wykorzystać dowolny algorytm wyszukiwania wzorca.
Z tego co pamiętam algorytm Knutha-Morrisa-Pratta miał złożoność O(n + k), gdzie k to długość wzorca. Inne - np. Boyer-Moore czy Rabin-Karp - mają w najgorszym razie O(n * k) więc już gorszą.
Nie polecam popełniać bardziej naiwnych form wyszukiwania wzorca dla kodowania słownikowego, bo się zdziwisz ile czasu potrafi zająć np. kompresja 1MB tekstu z 2kB słownikiem :D
Ale wyszukuję wiele razy. Najlepiej opłacało by się tworzyć jakieś hasz-listy.
Mozesz uzyc hashset.
W jaki sposób użyć haszy? Pytanie niezależne czy C/C++ czy Java. Chodzi mi o to, jak zrobic przy pomocy haszy cos takiego: pyta sie o stringi dwubajtowe - mam jeden lub ileś wyników, pytam się o trzy bajtowe - mam mniej, aż pyta się o najdłuższy, Gdy pytam się o trzybajtowe, szuka tylko w wynikach tych dwubajtowych a nie od poczatku. Najdłużej trwało by przeszukanie bufora np. 4kB na te dwubajtowe, chyba ze mam jakąś strukturę.
Teraz to się zgubiłem:) Opisz dokładnie co Masz na wejściu w tym pliku i co Chcesz zrobić? Te stringi są w kolejnych linijkach, czy jak?
Nie, po prostu mam ciag "abrakadabra", ^ niech oznacza biezącą pozycję:, wtedy będąc "abrakad^abra" znajduje poprzednia poztycję 0 a "string" 4 literowy "abra"
Na pozycji zero jest również: ab
i abr
; Masz zapamiętać je wszystkie? To tutaj @superdurszlak jest na właściwym tropie!:)
Wait, wait. Mówimy o kodowaniu słownikowym.
W kodowaniu słownikowym (już mniejsza z tym, jaki konkretnie wariant, czy LZ77, LZW czy inne LZMA) masz "okienko". Okienko to, jak dobrze pamiętam, N
ostatnich bajtów za bieżącym położeniem "wskaźnika". Teraz napotykając na nowy znak tworzysz trójkę:
- następny bajt
Z
- pozycja pasującego pod-ciągu w słowniku
K
- długość pod-ciągu w słowniku
L
Pod-ciąg to jest co, co następuje po napotkanym znaku i może zostać znalezione w słowniku. Teraz nie interesuje Cię znalezienie wszystkich możliwych dopasowań, bo to nie ma sensu - jedynie najdłuższego ;) Zatem to, co chciałbyś zrobić, to znaleźć jak najdłuższy pod-ciąg zaczynający się zaraz po Z
, który zarazem znajduje się w słowniku. Zatem chcąc znaleźć najlepsze dopasowanie możesz to zrobić naiwnie:
- Przymij
M = N
- weź pod-ciąg
A
długościM
- sprawdź, czy pod-ciąg znajduje się w słowniku
- jeżeli tak, zwróć pozycję pod-ciągu i długość, przesuń "okienko" o odpowiednią liczbę znaków
- w przeciwnym razie przyjmij
M = M - 1
i wróć do punktu 2
Teraz jeśli chodzi o efektywność, dużo zależy od punktu 3. :) Biorąc dopasowanie wzorca (z haszami czy bez) o złożoności pesymistycznej O(M * N) i redukując pod-ciąg do rozmiaru P
duużo mniejszego od N
(czyli w większości przypadków) Dostaniesz sumarycznie złożoność O(M * N * M) ---> O(N^3), czyli dość konkretna lipa. Dużo lepiej by to wyglądało, gdyby wziąć algorytm wyszukiwania O(M + N), bo w najgorszym razie dostaniesz O((M + N) * M) ---> O(N^2), czyli niedobrze, ale już lepiej.
Teraz zauważ, że biorąc algorytm KMP bierzesz coś, co nie zwraca informacji 0-1 czyli "tak, tu znajduje się podciąg" / "nie, nie ma tutaj podciągu" - jeśli algorytm trafi na znak niezgodny z ciągiem, to "cofa" tylko o tyle, o ile to konieczne, by móc kontynuować dopasowywanie. Nie wytłumaczę Ci tego dokładnie, bo akurat ten algorytm jest moją zmorą z AiSD na studiach, nigdy nie mogłem przetrawić tych akrobacji z prefikso-sufiksami :) W każdym razie dzięki niemu nic nie musisz haszować, wystarczy, że w przypadku "pudła" zapamiętasz podciąg, do którego się cofasz, jeżeli jest dłuższy niż dotychczas zapamiętany. Dzięki temu dostaniesz swój podciąg w O(M + N) bez zapamiętywań haszy itp, które chyba i tak niewiele by dały :)
Należy zrobic specjalne drzewo suffiksowe:
Warto zobaczyć DOT generujacy
Udaje się tworzyć strukturę drzewiastą ale najdłużej trwa alokowanie pamięci na stogu, poza tym jest pamięciochłonne.
Myślę że zrobie to inaczej: wszystkie strzałki z literami" zrobię w tablicy hasz wspołnej dla całości zamiast 1->256 możliwości->256..itd
Pytanie: Mam 11 pozycji drzewa suffixowego
*Mississippi
*ississippi
*ssissippi
*sissippi
*issippi
*ssippi
*sippi
*ippi
*ppi
*pi
*i
Ale zarówno węzłów oznaczonych kółkiem jak i strzałek mam rpawie dwukroteni więcej. Pytanie: czy można dowieść , że te dwie ilości nieprzekroczą podwojonej ilości suffixów czyli 2*11?
Dobry algorytm jest z sortowaniem listy prefiksów: ten pdf
Ma tylko wadę, że buduje się strukturę na podstawie ciagu, ale nie mozna korzystać z częściowo zbudowanego oraz nie działa okno przesuwne , chyba żęby wstawiac i usuwać rekord po każdym znaku, ale to nieefektywne.
A tu generator plików DOT: makeDot
Ma szybkie pytanie w tym wątku aby nie mnożyć wątków: szukam testowego ciągu, na którym warto ćwiczyć kompresje. 11 znakowy "mississippi" trochę za krótki, przydałby się 40-60 znakowy, Trochę dłuższy jest "Misissippi Missouri", gdzie w drugim członie powtarza się Miss, ale chciałbym coś dłuższego, gdzie powtarzają się pojedyncze litery, są cykle w cyklach oraz jest co takiego jak niedokładne powtarzanie "Ala ma kota a Ola mam psa"
A może coś takiego "Miss Mississippi Ala ma kota a miss Missouri Ola ma psa", może być?
Potrzebuje jeszcze coś większego - tak kilkaset - tysiąc bajtów, aby dobrze się kompresowało, nie tekst typu "aaaaaa" ale lepiej kompresowało się niż przeciętny tekst , bo przy tym rozmiarze dopiero kompresory się rozpedzają
Napisz sobie generator i tyle... :) ewentualnie skorzystaj z generatora lorem ipsum
online
Generatory bełkotu działają przeważnie na zasadzie łańcucha Markowa. Nietrudno coś takiego napisać. A jeśli wyjściowy zbiór tekstowy będzie nieduży, to i generator wypluje tekst, w którym będzie gęsto od powtórzeń.