Struktura do kodowania słownikowego

Odpowiedz Nowy wątek
2019-06-23 12:29
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.

Chyba 4 bity dlugosci. - lion137 2019-06-23 12:58

Pozostało 580 znaków

2019-06-23 12:45
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


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)

Pozostało 580 znaków

2019-06-23 12:51
0

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

Pozostało 580 znaków

2019-06-23 14:46
0

Mozesz uzyc hashset.


Pozostało 580 znaków

2019-06-23 18:49
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ę.

Pozostało 580 znaków

2019-06-23 19:04
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?


Pozostało 580 znaków

2019-06-23 19:11
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"

Pozostało 580 znaków

2019-06-23 19:16
0

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


edytowany 1x, ostatnio: lion137, 2019-06-23 19:16

Pozostało 580 znaków

2019-06-23 19:45
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 :)


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)
edytowany 2x, ostatnio: superdurszlak, 2019-06-23 19:46

Pozostało 580 znaków

2019-06-24 16:03
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?

Pozostało 580 znaków

2019-06-24 18:26
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

edytowany 1x, ostatnio: Borneq, 2019-06-24 19:40

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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