Search for a substring of characters using the theory of non-deterministic finite automata and vector-character architecture

Pashchenko Dmitry Vladimirovich, Trokoz Dmitry Anatolievich, Martyshkin Alexey Ivanovich, Sinev Mihail Petrovich, Svistunov Boris Lvovich

Abstract


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.

Keywords


Big Data; Hyperdimensional Vector; Information Retrieval Algorithms Nondeterministic Finite Automata; Vector-Character Architecture


Refbacks

  • There are currently no refbacks.


Bulletin of EEI Stats