Approximate string matching using factor automata
Given a text \(T\) over alphabet \(\Sigma\) and a complete index for \(T\) constructed using the finite automaton (called the factor automaton or DAWG) accepting all the substrings (factors) of text \(T.\) An answer to the query whether a pattern \(P\) occurs in text \(T\) with \(k\) differences is discussed to be done by an algorithm having the time complexity independent on the length of text \(T.\) The algorithm searches for the final state of the finite automaton accepting the intersection of languages \(\text{Fac}(T)\) (the set of all factors of \(T)\) and \(L_{k}(P)\) (the set of all strings having at most \(k\) differences with respect to pattern \(P\)).
- Algorithms for approximate string matching
- Approximate string matching using factor automata
- Complete inverted files for efficient text retrieval and analysis
- scientific article; zbMATH DE number 801745 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Approximate string matching using factor automata
- On-line construction of compact directed acyclic word graphs
- Weighted automata for full-text indexing
- The finite automata approaches in stringology
- An artificial neural network based approach for online string matching/filtering of large databases
- scientific article; zbMATH DE number 1045407 (Why is no real title available?)
- Special factors and the combinatorics of suffix and factor automata
- Approximate string matching with suffix automata
This page was built for publication: Approximate string matching using factor automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583536)
