English
Tag "algorytmy"
18:56
Transformata Burrowsa-Wheelera
Bazuje na wcześniej, nigdzie nie publikowanej transformacie Wheelera z 1983 roku. Na wejście algorytmu podaje się dane (ciąg znaków) w kodzie ASCII. Rezultatem transformaty jest posortowany blokowo ciąg znaków.
Algorytm
Algorytm operuje na blokach. Im bloki są większe (więcej danych), tym algorytm jest skuteczniejszy. Na wejście algorytmu wprowadzamy ciąg bitów, które są przetwarzane przez algorytm według schematu:
Schemat blokowy algorytmu Burrowsa-Wheelera.
W pierwszej kolejności generowane są wszystkie rotacje kompresowanego bloku. Kolejnym krokiem jest posortowanie leksykograficzne wygenerowanych łańcuchów. Aby otrzymać ciąg wyjściowy zapamiętujemy ostatni bajt każdej rotacji po sortowaniu. Aby umożliwić rozkodowanie takiego ciągu znaków należy w wyniku przekazać pozycję z posortowanej tablicy rotacji, na której znajduje się kodowana informacja.
Funkcje wewnętrzne
Przedstawiony wyżej algorytm posiada dwie funkcje wewnętrzne odpowiadające za generowanie rotacji, oraz ich sortowanie. Poniżej zaprezentowana jest struktura wewnętrzna funkcji realizująca te zadania.
Funkcja generująca - GenerateRotations
Funkcja sortująca - SortRotations
W wyniku wywołania funkcji generującej otrzymamy tablicę wielowymiarową przechowującą wszystkie rotacje bloku o rozmiarach {n} x {n}, gdzie n jest długością (length) kompresowanego bloku. Funkcja sortująca realizuje prosty algorytm sortowania leksykograficznego (ciągi znaków są sortowane rosnąco, gdzie A < Z < a < z).
Algorytm transformaty odwrotnej
Algorytm transformaty odwrotnej pozwala na odkodowanie przekształconej informacji, w taki sposób, aby otrzymać dane wejściowe. Do tego celu wymagane są zaszyfrowane dane, oraz uzyskana podczas szyfrowania pozycja na której znajduje się prawidłowe trafienie. W czasie dekodowania danych odtwarzane są wszystkie wygenerowane rotacje. Przebiega to w kilku krokach, w zależności od długości danych wejściowych. W każdym kroku dodawana jest najpierw kolumna z zakodowanym ciągiem (po znaku dla każdej rotacji), a następnie dane są sortowane leksykograficznie podobnie jak w przypadku kodowania.
Funkcja dodająca kolumnę dla bloku rotacji – AddColumn.
Na koniec wybierany jest ostateczny rezultat na podstawie przekazanego do algorytmu numeru wiersza N.
Zastosowanie
Transformata Burrowsa-Wheelera sama w sobie nie jest metodą kompresji. Wygenerowany w ten sposób ciąg bitów ma taki sam rozmiar, jak dane wejściowe. Jest on jednak często podstawą przy kompresji bezstratnej. Aby dodatkowo obniżyć poziom entropii wygenerowanych danych używa się innego algorytmu transformacji – Move To Front. Następnie kompresuje się to wszystko wybraną metodą kompresji bezstratnej. Przykładem takiej kompresji jest algorytm Huffmana, który połączony z wymienionymi transformacjami w takiej kolejności tworzy algorytm BZIP2.
22:28
Algorytmy geometryczne
Dział informatyki, który zajmuje się problematyką algorytmów geometrycznych nazywamy geometrią obliczeniową. We współczesnej inżynierii i matematyce geometria obliczeniowa znajduje zastosowanie między innymi w grafice komputerowej, robotyce, systemach projektowania wspomaganego komputerowo i statystyce. Danymi wejściowymi zazwyczaj są punkty, odcinki, czy wierzchołki wielokąta. Rozwiązaniami są często odpowiedzi na pytania dotyczące obiektów: czy którekolwiek z danych prostych się przecinają, albo np. wypukła otoczka zbioru punktów. Podstawowymi obiektami geometrycznymi o których będę tu mówić są punkt, odcinek, wektor, prosta. Przez sgn(x) oznaczamy znak liczby x, a przez det(p,q,r) wyznacznik macierzy:
gdzie p,q,r, są różnymi punktami: p = (x,y), q = (x',y'), r=(x,y).
Powiemy, że punkt r:
- leży po lewej stronie wektora p->q, jeżeli det(p,q,r) > 0;
- leży po prawej stronie wektora p->q jeżeli det(p,q,r) < 0;
- jest współliniowy z wektorem p->q jeżeli det(p,q,r) = 0;
Przedstawianie algorytmów geometrycznych rozpocznę od prezentacji trzech bardzo prostych, ale istotnych problemów, które często są podstawą w bardziej zaawansowanych algorytmach geometrycznych.
Sprawdzić, czy punkty p1 i p2 leża po tej samej stronie prostej p-q.
Aby rozwiązać ten problem należy wyliczyć wyznacznik det(p,q,p1) i det(p,q,p2), a następnie sprawdzić, czy znaki przy wyznacznikach są takie same: sgn(det(p,q,p1)) == sgn(det(p,q,p2))
Sprawdzić, czy punkt r należy do odcinka p-q
Aby rozwiązać ten problem należy najpierw z rzutować punkty p,q,r na osie OX i OY. Następnie sprawdzamy, czy rzut punktu r na oś OX znajduje się między rzutami punktów p i q i tak samo w przypadku rzutu na oś OY. Kolejnym krokiem jest sprawdzenie, czy punkty p,q,r są współliniowe.
Gdy wszystkie warunki są spełnione oznacza to, że punkt r należy do odcinka p-q.
Sprawdzić, czy dwa odcinki p-q i s-r się przecinają.
Należy tutaj zauważyć, że dwa odcinki przecinają się, wtedy, gdy punkty p,q leżą po przeciwnych stronach odcinka r-s, a punkty r,s po przeciwnych stronach odcinka p-q.
W przypadku spełniania obu warunków oznaczać to będzie, że proste się przecinają.
Problem przynależności
Jest to jeden z najczęściej spotykanych problemów w geometrii obliczeniowej. Dany jest obiekt geometryczny W oraz punkt p. Mamy zbadać, czy p należy do W. Przyjmijmy, że W jest dowolnym wielokątem. Aby wykazać, że punkt p znajduje się wewnątrz wielokąta należy poprowadzić półprostą l wzdłuż osi OX, która swój początek ma w punkcie p. Dla uproszczenia przyjmijmy, że prosta nie przecina wielokąta w żadnym z wierzchołków. Jeżeli półprosta przecina się z bokami wielokąta nieparzystą ilość razy wtedy można powiedzieć, że punkt p znajduje się wewnątrz wielokąta, w przeciwnym wypadku jest on na zewnątrz. Aby sprawdzić, czy półprosta przecina się z danym bokiem, wystarczy zastosować algorytm zaprezentowany wcześniej, który sprawdzania, czy dwa dane odcinki się przecinają. Jeżeli współrzędne y na końcach odcinka są sobie równe, wtedy wiadomo, że dany odcinek nie przecina się z prostą l (jest do niej równoległy). W przeciwnym wypadku należy ograniczyć półprostą z jednej strony do punktu:
i sprawdzić, czy:
Źródła
- L. Banachowski - "Algorytmy i struktury danych" - Wydawnictwa Naukowo-Techniczne, 2003r
- T. Cormen - "Wprowadzenie do algorytmów" - Wydawnictwa Naukowo-Techniczne, 2001r
Nazywam się Tomasz Chudyk i witam na mojej stronie. Z zawodu jestem programistą. Moje zainteresowania krążą głównie wokół open-source, Linuksa i technologi internetowych.
