Применение конечных автоматов для нечеткого бинарного поиска И. В. Панкратов
Material type: ArticleSubject(s): автоматы конечные | бинарный поиск | поиск подстроки | Кнута-Морриса-Пратта алгоритм | Ахо-Корасик алгоритмGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика. Приложение № 11. С. 117-122Abstract: Рассматривается задача нечёткого поиска булевых векторов в потоке данных. Под нечётким вхождением искомого вектора понимается вхождение вектора, близкого к искомому в смысле расстояния Хемминга. Предлагается метод построения конечного автомата для решения данной задачи по заданному набору искомых шаблонов в виде булевых векторов (возможно, частично определённых) и допустимого отклонения для каждого шаблона. Возможно построение автомата, принимающего на вход отдельные биты данных, и автомата, принимающего сразу группы битов. Приводятся оценки размеров таблиц переходов и выходов автомата. Представлены экспериментальные данные производительности поисковых автоматов, принимающих на вход отдельные биты данных, четвёрки битов и восьмёрки битов, а также производительность классического подхода к задаче нечёткого поиска, основанного на регистре сдвига.Библиогр.: 4 назв.
Рассматривается задача нечёткого поиска булевых векторов в потоке данных. Под нечётким вхождением искомого вектора понимается вхождение вектора, близкого к искомому в смысле расстояния Хемминга. Предлагается метод построения конечного автомата для решения данной задачи по заданному набору искомых шаблонов в виде булевых векторов (возможно, частично определённых) и допустимого отклонения для каждого шаблона. Возможно построение автомата, принимающего на вход отдельные биты данных, и автомата, принимающего сразу группы битов. Приводятся оценки размеров таблиц переходов и выходов автомата. Представлены экспериментальные данные производительности поисковых автоматов, принимающих на вход отдельные биты данных, четвёрки битов и восьмёрки битов, а также производительность классического подхода к задаче нечёткого поиска, основанного на регистре сдвига.
There are no comments on this title.