Применение конечных автоматов для нечёткого бинарного поиска

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