Байт поиска []
Поиск строки внутри строки очень хорошо поддерживается в .NET, но что делать, если данные, которые нужно искать, не являются строкой?
У меня есть двоичные данные, поступающие регулярными порциями через NetworkStream. Пакеты являются двоичными, но все они начинаются с последовательности байтов подписи. Я накапливаю куски в больший буфер и ищу сигнатуру начала пакета.
Я действительно ищу byte[], эквивалент метода String.IndexOf(ss). У меня неприятное предчувствие, что мне придется самому реализовать это с помощью цикла и конечного автомата.
Какие-либо предложения? К тебе!
Как и предполагалось, Array.IndexOf (byte), по крайней мере, избавит меня от явного цикла. С момента публикации мне пришло в голову найти первый байт подписи, затем попытаться найти совпадение, где должен быть последний байт подписи, а затем, если они оба совпадают, попробуйте сравнение грубой силы для остальной части строки. Этот подход имеет то преимущество, что дешево отклоняет ложные совпадения и позволяет мне дешево отклонять, когда у меня есть частичная подпись, ожидающая другого фрагмента.
Google показывает, что вышеприведенный блестящий план является вырожденным случаем алгоритма KMP или Кнута-Морриса-Пратта. С другой стороны, если Кнут написал на нем свое имя, это, вероятно, смазанная молния, с другой стороны, почему всякий раз, когда у меня появляется хорошая идея, Дональд Кнут думал об этом 25 лет назад?
Поскольку я не могу присудить очки Дональду Кнуту, думаю, они достаются Нельсону.
Ответы 3
Вы можете использовать Array.IndexOf, чтобы найти один байт.
Однако я хотел бы предупредить вас, что некоторые действительные данные могут случайно оказаться вашей подписью и полностью сбросить ваше приложение. На мой взгляд, лучшим решением было бы всегда отправлять четырехбайтовое целое число, содержащее размер пакета. Затем прочтите это количество байтов, чтобы очистить буфер этого пакета.
Если вы используете TCP, вполне допустимо отключать клиента, если он лжет о размере пакета или запрашивает тупой объем памяти :)
Можете ли вы использовать неуправляемый / небезопасный код? Если это так, я бы, вероятно, предложил изучить использование арифметики указателей для поиска в массиве байтов. Вот как действуют струны. Вы можете сделать то же самое.
другим решением может быть использование словаря для хранения ваших пакетных данных. Пусть ключ будет вашей подписью. Тогда его довольно быстро и легко найти. Несколько способов использовать байт в качестве ключа, например base64string, оболочку simepl (используйте KeyedCollection, если вы это сделаете) и т. д.
Фактически неуправляемый код - это PITA, поскольку у нас смешанная среда 32/64. Удивительно, насколько это меньше хлопот для чистого управляемого кода. Уловка-22: мне нужна подпись для разбора потока на пакеты.
Самыми быстрыми алгоритмами для поиска шаблонов в байтовых массивах и строках, которые я использовал, являются Бойер-Мур и простой алгоритм Бойера-Мура (полезен, когда шаблон значительно отличается от искомого текста). Я использовал это для реализации быстрого парсера mime на Java. код может быть легко перенесен в .Net (лицензия LGPL).
Я не могу писать протокол, я говорю о устаревшем оборудовании. Я должен написать следующую версию, и я уже уточнил ваше предложение.