Поиск байта []

Question

Поиск строки в строке чрезвычайно хорошо поддерживается в .NET, но что делать, если данные, которые нужно искать, не являются строкой?

У меня есть двоичные данные, поступающие обычными порциями через NetworkStream. Пакеты являются двоичными, но все они начинаются с сигнатурной последовательности байтов. Я собираю куски в больший буфер и ищу подпись начала пакета.

Что я действительно ищу, так это byte[] эквивалент String.IndexOf(ss) метода. У меня неприятное ощущение, что мне придется реализовать это самостоятельно с помощью цикла и конечного автомата.

Есть предложения? За вами!

---

Как и предполагалось, Array.IndexOf (byte) по крайней мере спасет меня от явного цикла. После публикации мне пришло в голову найти первый байт сигнатуры, затем проверить, где должен быть последний байт сигнатуры, а затем, если они оба совпадают, попробуйте сравнение грубой силы для остальной части строки. Преимущество этого подхода состоит в дешевом отклонении ложных совпадений и в возможности дешевого отклонения, когда у меня есть частичная подпись в ожидании другого фрагмента.

Google показывает, что приведенный выше блестящий план является вырожденным случаем алгоритма "KMP" или алгоритма Кнута-Морриса-Пратта. С другой стороны, если Кнут написал свое имя, это, вероятно, смазанная молния, а с другой стороны, почему, когда у меня появляется хорошая идея, Дональд Кнут думал об этом 25 лет назад?

Поскольку я не могу присудить очки Дональду Кнуту, я полагаю, они отправляются в Нельсон.

Answer 1

Вы можете использовать Array.IndexOf, чтобы найти один байт.

Однако я хотел бы предупредить вас, что некоторые действительные данные могут случайно стать вашей подписью и полностью отбросить ваше приложение. На мой взгляд, лучшим решением было бы всегда посылать четырехбайтовое целое число, которое содержит размер пакета. Затем прочитайте столько байтов, чтобы очистить буфер этого пакета.

Если вы используете TCP, вполне допустимо отключить клиента, если он лжет о размере пакета или запрашивает глупый объем памяти:)

Answer 2

Самыми быстрыми алгоритмами поиска шаблонов в байтовых массивах и строках, которые я использовал, являются Бойер-Мур и простой Бойер-Мур (полезно, когда шаблон значительно отличается от искомого текста). Я использовал это для реализации быстрого парсера MIME в Java. Код можно легко перенести на .Net (лицензия LGPL).

Answer 3

Можно ли использовать неуправляемый / небезопасный код? Если это так, я бы, вероятно, предложил использовать арифметику указателей для поиска в вашем байтовом массиве. Вот как строки эффективны. Вы можете сделать подобное.

другим решением может быть использование словаря для хранения ваших пакетных данных. Ключ должен быть вашей подписью. Тогда его довольно быстро и легко найти. Несколько способов использовать байт в качестве ключа, например base64string, оболочка simepl (используйте KeyedCollection, если вы это делаете) и т. Д.