start_mask это опечатка там star_mask везде. Точка не обрабатывается как любой символ тк у нас язык шаблонов и просто * без .* как в регулярках. shl да проскочил при конвертации кода в приличный Java-like язык.
Про размер слова верно, тут главное уместиться в L1 кеш, дальше большой выгоды получить будет трудно. 8*256 = 2кб при этом для чистого ASCII можно смело брать вдвое меньше. Скорость работы непосредственно битовых операций от размера не зависит. Так что при прочих равных брать меньше 64 на 64-битном процессоре смысла нет.
Про допилить до произвольного m, да можно, но нужно быть аккуратным чтобы не деградировать основной случай m < 64. По сути самое простое решение выбирать алгоритм по размеру паттерна и сделать отдельные реализации под 1 машинное слово, под 2 ну и под k штук.
Про команды, нет биты здесь не кодируют операции. Автомат поисковый и каждый бит соответствует тому сколько подходящих символов мы увидели. Это конечно до звездочек, там немного сложнее, я про ShiftOr.
Про 0/1 надеюсь теперь понятно. Грубо говоря мы поддерживает много вариантов сматченной строки. С каждым символом мы сдвигаем все биты вперед и с помощью маски для текущего символа отсекаем не корректные варианты.
Маски да для всех вариантов ASCII, но не стоит путать эти маски с финальной, она просто нужна чтобы проверить дошли ли мы до финального состояния
Насчет петабайт, как раз проблем не будет тк это данные а не шаблон. Просто пожужжит вашим SSD и выдаст что ничего не найдено. Биты кодируют состояние автомата, автомат по размеру пропорционален длине шаблона. 1 кодирует неактивное состояние, 0 активное. Про маску опять же маска это слово, и делается один раз для каждого символа алфавита. Советую посмотреть и может даже попробывать псевдокод для ShiftOr. Он может только строки, но петабайты данных ему не страшны)
Про m - как и ShiftOr алогритм не зависит от длины m, так что это никак не O(mn). То есть если шаблон уложится, то нет разницы в скорости было ли m равно 4 или скажем 60. Поэтому все же O(n), да это с ограничениями. Про DP все же отмечу что для представления в уме, оно все же будет посложнее, чем похоже и вызвана такая непривычная сложность описания того же ShiftOR. Когда таблицы не ложатся на простую для восприятия основу алгоритмы кажутся сложнее, и как следствие меньше людей ими интересуются.
Информация
В рейтинге
Не участвует
Зарегистрирован
Активность
Специализация
Бэкенд разработчик, Архитектор программного обеспечения
start_mask это опечатка там star_mask везде. Точка не обрабатывается как любой символ тк у нас язык шаблонов и просто * без .* как в регулярках. shl да проскочил при конвертации кода в приличный Java-like язык.
Про размер слова верно, тут главное уместиться в L1 кеш, дальше большой выгоды получить будет трудно. 8*256 = 2кб при этом для чистого ASCII можно смело брать вдвое меньше. Скорость работы непосредственно битовых операций от размера не зависит. Так что при прочих равных брать меньше 64 на 64-битном процессоре смысла нет.
Про допилить до произвольного m, да можно, но нужно быть аккуратным чтобы не деградировать основной случай m < 64. По сути самое простое решение выбирать алгоритм по размеру паттерна и сделать отдельные реализации под 1 машинное слово, под 2 ну и под k штук.
Про команды, нет биты здесь не кодируют операции. Автомат поисковый и каждый бит соответствует тому сколько подходящих символов мы увидели. Это конечно до звездочек, там немного сложнее, я про ShiftOr.
Про 0/1 надеюсь теперь понятно. Грубо говоря мы поддерживает много вариантов сматченной строки. С каждым символом мы сдвигаем все биты вперед и с помощью маски для текущего символа отсекаем не корректные варианты.
Маски да для всех вариантов ASCII, но не стоит путать эти маски с финальной, она просто нужна чтобы проверить дошли ли мы до финального состояния
Насчет петабайт, как раз проблем не будет тк это данные а не шаблон. Просто пожужжит вашим SSD и выдаст что ничего не найдено. Биты кодируют состояние автомата, автомат по размеру пропорционален длине шаблона. 1 кодирует неактивное состояние, 0 активное. Про маску опять же маска это слово, и делается один раз для каждого символа алфавита. Советую посмотреть и может даже попробывать псевдокод для ShiftOr. Он может только строки, но петабайты данных ему не страшны)
Про m - как и ShiftOr алогритм не зависит от длины m, так что это никак не O(mn). То есть если шаблон уложится, то нет разницы в скорости было ли m равно 4 или скажем 60. Поэтому все же O(n), да это с ограничениями. Про DP все же отмечу что для представления в уме, оно все же будет посложнее, чем похоже и вызвана такая непривычная сложность описания того же ShiftOR. Когда таблицы не ложатся на простую для восприятия основу алгоритмы кажутся сложнее, и как следствие меньше людей ими интересуются.