Publications
Start of topic | Skip to actions
Thomas Claveirole. Smart Automaton Implementations. CSI Seminar May 2003
The aim of this document is to present an overview of techniques to
optimize memory usage when constructing automaton from regular
expressions. However, it is essential to keep a decent time complexity
when processing text i.e. better than the classical O(l * n)
(With l the length of the text, and n the number of state)
for non-deterministic automaton.
This document will focus on partial determinization used with the
Glushkov algorithm in order to produce lightweight and efficient
automata. Navarro-Raffinot and Champarnaud-Coulon-Paranthoën method
will be studied.
- claveirole0604_smart_automaton_implementation_slides.pdf
- Source tarball: claveirole0604_smart_automaton_implementation_slides.tar.bz2
to top
| PublicationForm | |
|---|---|
| Logo: | |
| Category: | |
| Title: | Smart Automaton Implementations |
| Authors: | Thomas Claveirole |
| Type: | OralPresentation |
| Whereprefix: | |
| Where: | CSI Seminar |
| Ref: | |
| Place: | |
| Date: | May 2003 |
| Note: | |
| Lang: | english |
| Keywords: | Partial Determinization, Regular Expression Search, Pattern Matching, Homogeneous Automaton, Navarro-Raffinot method, Bitset |
| Status: | published |
Edit | Attach image or document | Printable version | Raw text | More topic actions
Revisions: | r1.3 | > | r1.2 | > | r1.1 | Total page history | Backlinks
Revisions: | r1.3 | > | r1.2 | > | r1.1 | Total page history | Backlinks