Очень мало действительно умирает в интернете. У Archive.org просто есть один снимок этого сообщения в блоге с момента его появления . Скопировано здесь:
Некоторая корректирующая информатика для аудиторов PCI в моей аудитории.
Я вручаю вам массив случайных чисел. Как вы можете определить, есть ли в нем номер три?
Ну, есть очевидный способ: проверяйте числа последовательно, пока не найдете «3» или не исчерпаете массив. Линейный поиск. Учитывая 10 чисел, вы должны предположить, что это может сделать 10 шагов; N номеров, N шагов.
Picture 1.png
Линейный поиск это плохо. Трудно сделать хуже, чем линейный. Давайте улучшим это. Сортировать массив.
Изображение 2.png
Сортированный массив предлагает другую стратегию: перейдите в середину массива и посмотрите, меньше ли значение, которое вы ищете, меньше (слева) или больше (справа). Повторите, сокращая массив пополам каждый раз, пока не найдете значение.
Бинарный поиск. Учитывая 10 чисел, потребуется 3 шага - log2 of 10 - чтобы найти один из них в отсортированном массиве. O (log n) поиск потрясающий. Если у вас есть 65 000 элементов, для поиска одного из них потребуется всего 16 шагов. Удвойте элементы, и это 17 шагов.
Но отсортированные массивы - отстой; С одной стороны, сортировка обходится дороже, чем линейный поиск. Таким образом, мы мало используем бинарный поиск; вместо этого мы используем двоичные деревья.
Изображение 3.png
Чтобы найти двоичное дерево, вы начинаете сверху и спрашиваете себя «мой ключ меньше (слева) или больше (справа) текущего узла», и повторяете до тех пор, пока все хорошо, хорошо, хорошо, вы уже знаете этот материал. Но это дерево красивое, не так ли?
Поиск с (сбалансированным) бинарным деревом - это O (log n), как и бинарный поиск, в зависимости от количества элементов в дереве. Двоичные деревья потрясающие: вы получаете быстрый поиск и сортированный обход, то, что вы не получаете из хеш-таблицы. Двоичные деревья - лучшая реализация таблицы по умолчанию, чем хеш-таблицы. 2.
Но двоичные деревья - не единственный древовидный механизм поиска. Двоичные радикальные попытки, также называемые деревьями PATRICIA, работают как двоичные деревья с одним принципиальным отличием. Вместо того, чтобы сравнивать больше / меньше, чем на каждом узле, вы проверяете, установлен ли бит, переходя вправо, если он установлен, и оставляя, если он не установлен.
Изображение 4.png
Я много пропускаю о том, как работает двоичный корень. Это позор, потому что основополагающие попытки общеизвестно недокументированы - Седжвик позорно облажался с ними в «Алгоритмах», и страница Википедии для них - отстой. Люди до сих пор спорят о том, как их назвать! Вместо объяснения обратных ссылок и краев, помеченных позициями битов, приведем крошечную реализацию Ruby.
Вот почему попытки Radx - это круто:
Search performance varies with the key size, not the number of elements in the tree. With 16 bit keys, you’re guaranteed 16 steps
независимо от количества элементов в дереве, без балансировки.
More importantly, radix tries give you lexicographic matching, which is a puffed-up way of saying “search with trailing wildcard”, or
«Поиск в стиле командной строки». В основополагающем дереве вы можете быстро найти «ro *» и получить «rome», «ramulous» и «roswell».
3.
Я потерял тебя.
Давайте поместим это в контекст. Попытки являются важной структурой данных для интернет-маршрутизации. Проблема маршрутизации выглядит так:
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”
Это сложная проблема, которую нужно решить с помощью простого двоичного дерева, но с основанием, вы просто запрашиваете «1010.0000.0000.0000.0000.0001.0100» (для 10.0.1.20) и «1010» (для 10.0.0.0). ). Лексикографический поиск дает вам «лучшее соответствие» для маршрутизации. Вы можете попробовать это в коде Ruby выше; добавьте * "10.0.0.0" .to_ip в список и найдите «10.0.0.1» .to_ip.
Соответствие между маршрутизацией и попытками radix настолько сильное, что самая популярная универсальная библиотека radix trie (библиотека CPAN) фактически украдена из GateD. Это беспорядок, кстати, и не используйте его.
Если вы понимаете, как работает дерево, вы также понимаете, как работают регулярные выражения. Попытки являются частным случаем детерминированных конечных автоматов (DFA), где ветви основаны исключительно на сравнениях битов и всегда переходят вперед. Хороший движок регулярных выражений просто обрабатывает DFA с большим количеством «функций». Если мои снимки имеют для вас смысл, то снимки в этой превосходной статье о алгоритме сокращения NFA-DFA Томпсона тоже подойдут, и эта статья сделает вас умнее. 4.
Вы оператор сети в магистральном интернет-провайдере. Ваш мир в основном состоит из «префиксов» - пар IP-сети / сетевой маски. Маски сети в этих префиксах очень важны для вас. Например, 121/8 принадлежит Корее; 121.128 / 10 принадлежит Korea Telecom, 121.128.10 / 24 принадлежит клиенту KT, а 121.128.10.53 - это один компьютер внутри этого клиента. Если вы отслеживаете бот-сеть, спам-операцию или распространение червя, этот номер маски сети очень важен для вас.
К сожалению, что бы это ни было важно, нигде в IP-пакете нет отметки «сетевая маска» - сетевые маски являются полностью деталями конфигурации. Итак, когда вы наблюдаете за трафиком, у вас по существу есть эти данные для работы:
ips.png
Удивительно, но при наличии достаточного количества пакетов для просмотра этой информации достаточно для угадывания сетевых масок. Работая в Sony, Кенджиро Чо придумал действительно элегантный способ сделать это, основываясь на попытках. Вот как:
Возьмите базовый двоичный файл, такой же, как те, которые используются программными маршрутизаторами. Но ограничить количество узлов в дереве, скажем, до 10000. На магистральной линии, записывая адреса из заголовков IP, вы мгновенно исчерпаете 10000 узлов.
Сохраните список узлов в списке, отсортированном в порядке LRU. Другими словами, когда вы сопоставляете IP-адрес с узлом, «дотроньтесь» до узла, поместив его в верхнюю часть списка. Постепенно часто просматриваемые адреса всплывают наверх, а редко встречающиеся узлы опускаются на дно.
Изображение 6.png
Теперь хитрость. Если у вас закончились узлы, и вам нужен новый, восстановите их в нижней части списка. Но когда вы это сделаете, сверните данные из узла в его родительский элемент, вот так:
Изображение 5.png
10.0.1.2 и 10.0.1.3 - это братья и сестры / 32, две половины 10.0.1.2/31. Чтобы вернуть их, объедините их в 10.0.1.2/31. Если вам нужно вернуть 10.0.1.2/31, вы можете объединить его с 10.0.1.0/31 для формирования 10.0.1.0/30.
Сделайте это, скажем, за минуту, и выдающиеся источники будут защищать свою позицию в дереве, оставаясь наверху списка LRU, в то время как окружающий / 32 шум поднимается до / 0. Для необработанного списка IP-адресов выше, с деревом из 100 узлов, вы получите это.
Чо называет это эвристическим Агури. 5.
Агури имеет лицензию BSD. Вы можете скачать его и программу-драйвер, которая просматривает пакеты через pcap, со старой домашней страницы Чо. 6.
Я собираюсь куда-то с этим, но я сейчас в этом сообщении 1300 слов, и если вы человек алгоритмический, вы уже устали от меня, а если нет, вы устали от меня сейчас. Итак, позвольте Агури войти, и я дам вам кое-что классное и бесполезное, чтобы сделать это позже на этой неделе.
Там разбросаны многочисленные ссылки. К сожалению, Archive.org не хранит изображения, только текст, поэтому некоторые из них были потеряны. Вот те, которые он заархивировал:
