Suffix Arrays are a neat data structure, to say the least. They allow us to perform efficient substring searchs, "keyword in context" searches, in addition to enabling us to compute the longest common prefix of a string in linear time. Suffix arrays ar
B+ trees are used heavily to implement index structures for many of the leading RDBMS vendors, traditionally for externally stored data. As computer architectures have evolved B+ trees are increasingly finding use as in-memory data structures
In my past projects when needed I have always implemented AST building parsers for regular expressions bottom-up by using the shunting yard algorithm. I've covered the process of doing so in my post on Thompsons Construction. While this approach certai
When it comes to data structures - especially self balancing data structures - it is no secret that the algorithms for removing an entry are often many, many times more complex than the algorithms for adding a value. Anyone w
This post was originally featured as a section of my post on implementing Thompsons Construction for NFA from a regular expression. Having since implemented several FA constructions, all of which utilized an AST representation of the given exp
-
Improving the Space Efficiency of Suffix Arrays
-
Augmenting B+ Trees For Order Statistics
-
Top-Down AST Construction of Regular Expressions with Recursive Descent
-
Balanced Deletion for in-memory B+ Trees
-
Building an AST from a Regular Expression Bottom-up
-
The Aho, Sethi, Ullman Direct DFA Construction Part 2: Building the DFA from the Followpos Table
-
The Aho, Sethi, Ullman Direct DFA Construction, Part 1: Constructing the Followpos Table
-
Procedural Map Generation with Binary Space Partitioning
-
Exact Match String Searching: The Knuth-Morris-Pratt Algorithm
-
The visitor pattern: OOP takes on the Expression Problem