DevOps
23.9K subscribers
1.26K photos
161 videos
15 files
1.1K links
По всем вопросам- @workakkk

@itchannels_telegram - 🔥полезные ит-каналы

https://t.iss.one/Golang_google - Golang программирование

@golangl - golang chat

@GolangJobsit - golang channel jobs

@golang_jobsgo - jobs

РКН: clck.ru/3FmvZA

#VRHSZ
Download Telegram
В ядре Linux есть поиск строки, который ускоряется за счёт пропуска символов

В lib/ts_bm.c реализован алгоритм Бойера - Мура. Он сравнивает шаблон с текстом справа налево и при несовпадении может перескочить сразу через несколько позиций.

Допустим, ищем ERROR:


Текст: ABCDXERROR
Шаблон: ERROR
↑


Первое сравнение: последняя R шаблона против X в тексте. Символа X в ERROR вообще нет.

Можно сдвинуть шаблон сразу на пять позиций. При меньшем сдвиге X всё ещё находился бы внутри проверяемого участка, поэтому совпадение невозможно.

Реализация ядра заранее строит две таблицы: для сдвига по несовпавшему символу и по уже совпавшему суффиксу. Затем выбирает больший из допустимых сдвигов.

Но у этой реализации есть ограничение: она может пропустить совпадение на границе двух блоков данных. Например, если один блок заканчивается на ERR, а следующий начинается с OR.

Поэтому прямо в комментарии к исходнику для фильтрации и обнаружения вторжений рекомендуют KMP, который умеет находить такие совпадения.

Выбор алгоритма здесь зависит и от скорости, и от того, как данные поступают на обработку.
❤1👍1