Pewna zaradcza informatyka dla audytorów PCI na moich odbiorców.
Daję ci tablicę losowych liczb całkowitych. Jak rozpoznać, czy jest w nim liczba trzy?
Cóż, istnieje oczywisty sposób: sprawdzaj liczby kolejno, aż znajdziesz „3” lub wyczerpujesz tablicę. Wyszukiwanie liniowe. Biorąc pod uwagę 10 liczb, musisz założyć, że może to zrobić 10 kroków; N liczb, N kroków.
Zdjęcie 1.png
Wyszukiwanie liniowe jest złe. Trudno jest gorzej niż liniowo. Poprawmy to. Posortuj tablicę.
Zdjęcie 2.png
Posortowana tablica sugeruje inną strategię: przeskocz na środek tablicy i sprawdź, czy szukana wartość jest mniejsza niż (po lewej) lub większa niż (po prawej). Powtarzaj, przecinając tablicę za każdym razem o połowę, aż znajdziesz wartość.
Binary wyszukiwania. Biorąc pod uwagę 10 liczb, zajmie to aż 3 kroki - log2 z 10 - - znalezienie jednego z nich w posortowanej tablicy. Wyszukiwanie O (log n) jest niesamowite. Jeśli masz 65 000 elementów, wystarczy tylko 16 kroków, aby znaleźć jeden z nich. Podwój elementy, a to 17 kroków.
Ale posortowane tablice są do kitu; po pierwsze, sortowanie jest droższe niż wyszukiwanie liniowe. Dlatego nie używamy dużo wyszukiwania binarnego; zamiast tego używamy drzew binarnych.
Zdjęcie 3.png
Aby przeszukać drzewo binarne, zacznij od góry i zadaj sobie pytanie: „czy mój klucz jest mniejszy niż (lewy) lub większy niż (prawy) bieżący węzeł”, i powtarzaj, aż ok, ok, ok, znasz już te rzeczy. Ale to drzewo jest ładne, prawda?
Wyszukiwanie z (zrównoważonym) drzewem binarnym to O (log n), podobnie jak wyszukiwanie binarne, zmieniające się w zależności od liczby elementów w drzewie. Drzewa binarne są niesamowite: masz szybki przegląd i posortowane przechodzenie, coś, czego nie wyciągniesz ze stołu haszującego. Drzewa binarne są lepszą domyślną implementacją tabel niż tabele skrótów. 2)
Ale drzewa binarne nie są jedynym mechanizmem wyszukiwania o strukturze drzewa. Próbki binarnych podstaw, zwane także drzewami PATRICIA, działają jak drzewa binarne z jedną zasadniczą różnicą. Zamiast porównywać więcej niż / mniej niż w każdym węźle, sprawdzasz, czy bit jest ustawiony, rozgałęzia się w prawo, jeśli jest ustawiony, i w lewo, jeśli nie jest.
Zdjęcie 4.png
Często pomijam sposób, w jaki stara się podstawa binarna. Szkoda, ponieważ próby rzutu są notorycznie mało udokumentowane - Sedgewick niesławnie spieprzył je w „Algorytmach”, a strona Wikipedii jest do bani. Ludzie wciąż kłócą się o to, jak je nazwać! Zamiast wyjaśnienia linków zwrotnych i krawędzi oznaczonych pozycjami bitów, oto mała implementacja Ruby.
Oto, dlaczego próby Radix są fajne:
Search performance varies with the key size, not the number of elements in the tree. With 16 bit keys, you’re guaranteed 16 steps
niezależnie od liczby elementów w drzewie, bez równoważenia.
More importantly, radix tries give you lexicographic matching, which is a puffed-up way of saying “search with trailing wildcard”, or
„Wyszukiwanie w stylu zakończenia wiersza poleceń”. W drzewie radix możesz szybko wyszukać „ro *” i uzyskać „Rome”, „romulous” i „roswell”.
3)
Zgubiłem cię
Umieśćmy to w kontekście. Próby są kluczową strukturą danych dla routingu internetowego. Problem z routingiem wygląda następująco:
You have a routing table with entries for “10.0.1.20/32 -> a” and “10.0.0.0/16 -> b”.
You need packets for 10.0.1.20 to go to “a”
You need packets for 10.0.1.21 to to to “b”
Jest to trudny problem do rozwiązania z podstawowym drzewem binarnym, ale w przypadku trix radix, po prostu pytasz o „1010.0000.0000.0000.0000.0001.0100” (dla 10.0.1.20) i „1010.” (dla 10.0.0.0 ). Wyszukiwanie leksykograficzne zapewnia „najlepsze dopasowanie” do routingu. Możesz spróbować w powyższym kodzie Ruby; dodaj * ”10.0.0.0” .to_ip do trie i wyszukaj „10.0.0.1” .to_ip.
Zgodność między routingiem a próbami radix jest tak silna, że najpopularniejsza biblioteka trie radix ogólnego przeznaczenia (ta z CPAN) jest faktycznie wykradziona z GateD. Nawiasem mówiąc, to bałagan i nie używaj go.
Jeśli rozumiesz, jak działa trie, rozumiesz również, jak działają wyrażenia regularne. Próby są szczególnym przypadkiem deterministycznych automatów skończonych (DFA), w których rozgałęzienia oparte są wyłącznie na porównaniach bitów i zawsze rozgałęziają się do przodu. Dobry silnik regex to po prostu obsługa DFA z większą liczbą „funkcji”. Jeśli moje zdjęcia mają dla ciebie sens, zdjęcia w tym doskonałym artykule na temat algorytmu redukcji NFA-DFA Thompsona również będą, a ten artykuł sprawi, że będziesz mądrzejszy. 4
Jesteś operatorem sieci szkieletowej dostawcy usług internetowych. Wasz świat składa się głównie z „prefiksów” - par sieci IP / maski sieci. Maski sieciowe w tych prefiksach są dla Ciebie niezwykle ważne. Na przykład 121/8 należy do Korei; 121.128 / 10 należy do Korea Telecom, 121.128.10 / 24 należy do klienta KT, a 121.128.10.53 to jeden komputer w tym kliencie. Jeśli śledzisz botnet, operację spamowania lub rozprzestrzenianie robaków, ten numer maski sieci jest dla Ciebie bardzo ważny.
Niestety, choć są ważne, nigdzie w pakiecie IP nie ma wytłoczonej „maski sieci” - maski sieciowe są całkowicie szczegółami konfiguracji. Tak więc, kiedy oglądasz ruch, zasadniczo masz te dane do pracy z:
ips.png
Zaskakujące, biorąc pod uwagę wystarczającą liczbę pakietów do obejrzenia, jest to wystarczająca ilość informacji, aby odgadnąć maski sieciowe. Pracując w Sony, Kenjiro Cho wymyślił naprawdę elegancki sposób na zrobienie tego, w oparciu o próby. Oto jak:
Wypróbuj podstawową wersję binarną trix radix, podobnie jak te używane przez routery programowe. Ale ogranicz liczbę węzłów w drzewie, powiedzmy do 10 000. Łączem szkieletowym, rejestrującym adresy poza nagłówkami IP, w ciągu kilku chwil wyczerpiesz 10 000 węzłów.
Przechowuj listę węzłów na liście, posortowaną w kolejności LRU. Innymi słowy, gdy dopasujesz adres IP do węzła, „dotknij” węzła, umieszczając go na górze listy. Stopniowo często widoczne adresy bąbelkują do góry, a rzadko widoczne węzły opadają na dół.
Zdjęcie 6.png
Teraz sztuczka. Kiedy zabraknie węzłów i potrzebujesz nowego, odzyskaj z dołu listy. Ale kiedy to zrobisz, zwiń dane z węzła do jego elementu nadrzędnego, w ten sposób:
Zdjęcie 5.png
10.0.1.2 i 10.0.1.3 to rodzeństwo / 32s, dwie połówki 10.0.1.2/31. Aby je odzyskać, połącz je w 10.0.1.2/31. Jeśli chcesz odzyskać 10.0.1.2/31, możesz połączyć ją z 10.0.1.0/31, aby utworzyć 10.0.1.0/30.
Zrób to, powiedzmy, przez minutę, a wyjątkowe źródła będą bronić swojej pozycji w drzewie, pozostając na szczycie listy LRU, podczas gdy otoczenie / 32 szumy bąbelkowe do / 0. Dla surowej listy adresów IP powyżej, ze drzewem 100 węzłów, otrzymujesz to.
Cho nazywa to heurystycznym Aguri. 5
Aguri ma licencję BSD. Możesz go pobrać, a także sterownik, który ogląda pakiety przez pcap, ze starej strony domowej Cho. 6.
Idę gdzieś z tym, ale mam teraz 1300 słów do tego postu, a jeśli jesteś osobą algorytmiczną, jesteś już mną zmęczony, a jeśli nie, jesteś zmęczony mną przez teraz. Wpuść Aguri, a dam ci coś fajnego i bezużytecznego do zrobienia z tym w tym tygodniu.
Jest tam rozrzuconych wiele linków. Niestety Archive.org nie przechowuje obrazów, tylko tekst, więc kilka z nich zostało utraconych. Oto te, które zostały zarchiwizowane: