Project topics and materials
Get Complete Project Material File(s) Now! »
Time and space performance
From Chapter 5, procedure add_wordN 0 takes O(jwj) time and space when adding word w. Using a clever coding of eq0, an invocation visit_min0(s, « ,w) also takes O(jwj) time and space — see [WD03]. It follows that add_wordI can also be implemented in O(jwj) time and space.
There are three relatively easy improvements:
1. Given Property 2.70, we can use invocation visit_min0((s, head(w)), head(w), tail(w)) when w 6= « .
2. While adding w with add_wordN 0, we already traverse path [s w ;] and need not compute it anew within visit_min0.
3. Another minor improvement can be made in the invocation of add_wordN 0: we need not create new states if they will subsequently be merged by visit_min0. This approach, which is used in practice, requires some additional book-keeping, and has been presented in [Wat03b Wat01d].
Avoiding cloning while adding words
Performance profiling of an implementation of the algorithm presented in Chapter 6, shows that most of the execution time is spent on two operations:
1. Cloning confluence states.
2. Merging states found to be equivalent. (Creating new states is a cheap operation in practice.) While the merging operation is generally unavoidable in constructing a MADFA, in the subsequent chapters, we focus on a performance improvement by eliminating cloning. Cloning is only applied to confluence states. In those chapters, the structural invariants and the word-orders will be chosen in such a way that the preconditions of the add_word variants are strengthenings of Con _free([s w ;]) when adding word w.
As a result, the body of each add_word variant will use add_wordT (from Chapter 4), followed by further operations to restore the appropriate structural invariant and prepare for the next word to be added.
Time and space performance
Sorting the words requires up to O(jWj log jWj) space and time; this is typically not taken into account in the MADFA construction time as W can be kept sorted in real-life applications. From Chapter 4, procedure add_wordT is time and space linear in the length of the word being added. As noted in Chapter 6, visit_min can be implemented to take linear time and space. It follows that add_wordS and cleanupS are linear in the total lengths of the words.
1 Introduction
1.1 Problem statement
1.2 To the reader
1.3 Related work and a short history
1.4 Links to the literature
1.5 Future work
2 Preliminaries
2.1 General definitions
2.2 Algorithm presentation
2.3 Strings and languages
2.4 Automata
2.5 Minimality of automata
3 A MADFA-construction skeleton
3.1 Specific instantiations
3.2 Commentary
4 Trie intermediate ADFA
4.1 Procedure add_wordT
4.2 Procedure cleanupT
4.3 An example
4.4 Time and space performance
4.5 Commentary
5 Arbitrary intermediate ADFA
5.1 Procedure add_wordN
5.2 Procedure cleanupN
5.3 Time and space performance
5.4 Commentary
6 Minimal intermediate ADFA
6.1 Procedure add_wordI
6.2 Procedure cleanupI
6.3 An example
6.4 Time and space performance
6.5 Commentary
7 Reversed trie intermediate ADFA
7.1 Procedure add_wordR
7.2 Procedure cleanupR
7.3 An example
7.4 Time and space performance
7.5 Commentary
8 Avoiding cloning while adding words
9 Words in lexicographic order
9.1 Procedure add_wordS
9.2 Procedure cleanupS
9.3 An example
9.4 Time and space performance
9.5 Commentary
10 Minimizing depth layers
10.1 Procedure add_wordD
10.2 Procedure cleanupD
10.3 An example
10.4 Time and space performance
10.5 Commentary
11 Minimizing semi-incrementally 83
11.1 Procedure add_wordW
11.2 Procedure cleanupW
11.3 An example
11.4 Time and space performance
11.5 Commentary
Bibliography
Index
Colophon
