Struktura do kodowania słownikowego

0

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.

0

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

0

Ale wyszukuję wiele razy. Najlepiej opłacało by się tworzyć jakieś hasz-listy.

0

Mozesz uzyc hashset.

0

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ę.

0

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?

0

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"

0

Na pozycji zero jest również: ab i abr; Masz zapamiętać je wszystkie? To tutaj @superdurszlak jest na właściwym tropie!:)

0

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ę:

  1. następny bajt Z
  2. pozycja pasującego pod-ciągu w słowniku K
  3. 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:

  1. Przymij M = N
  2. weź pod-ciąg A długości M
  3. sprawdź, czy pod-ciąg znajduje się w słowniku
  4. jeżeli tak, zwróć pozycję pod-ciągu i długość, przesuń "okienko" o odpowiednią liczbę znaków
  5. 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 :)

0

Należy zrobic specjalne drzewo suffiksowe:
Graphviz

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?

0

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

0

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ą

0

Napisz sobie generator i tyle... :) ewentualnie skorzystaj z generatora lorem ipsum online

0

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ń.

1 użytkowników online, w tym zalogowanych: 0, gości: 1