Search for a substring of characters using the theory of non-deterministic finite automata and vector-character architecture
| Autor: | Alexey I. Martyshkin, Dmitry Trokoz, Dmitry V. Pashchenko, Boris L. Svistunov, Mihail P. Sinev |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Control and Optimization
Theoretical computer science Finite-state machine Computational complexity theory Computer Networks and Communications Computer science Character (computing) business.industry Vector character architecture String (computer science) Big data Hyperdimensional vector Substring Information retrieval algorithms Hardware and Architecture Control and Systems Engineering Nondeterministic finite automata Computer Science (miscellaneous) Nondeterministic finite automaton Electrical and Electronic Engineering Architecture business Instrumentation Information Systems |
| Popis: | The paper proposed an algorithm which purpose is searching for a substring of characters in a string. Principle of its operation is based on the theory of non-deterministic finite automata and vector-character architecture. It is able to provide the linear computational complexity of searching for a substring depending on the length of the searched string measured in the number of operations with hyperdimensional vectors when repeatedly searching for different strings in a target line. None of the existing algorithms has such a low level of computational complexity. The disadvantages of the proposed algorithm are the fact that the existing hardware implementations of computing systems for performing operations with hyperdimensional vectors require a large number of machine instructions, which reduces the gain from this algorithm. Despite this, in the future, it is possible to create a hardware implementation that can ensure the execution of operations with hyperdimensional vectors in one cycle, which will allow the proposed algorithm to be applied in practice. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|