CODEWITHSUNDEEP
javastringalgorithmdata-structuresboggle
user3107774
user3107774

Reputation: 101

What is the fastest way to match string prefixes for the building of a Radix search tree?

Full disclosure this is for an assignment in an algorithms class, but I'm not looking for someone to write any code for me or hold my hand. Anyways we have to do the Boggle game. For those unaware, basically you are given a Boggle board and have to find as many words as possible, which can take huge amounts of time given the string possibilities with recursion.

To bring down OP time, we were encouraged to utilize whatever algorithm we'd like to try and "weed out" strings as we go along. Currently I have a system that will find all possible 3 letter suffixes possible by storing them in a dictionary, and if the string has 3 letters but doesn't match any valid suffixes, recursion is stopped.

Getting to the crux of the question, I'm trying to implement a Radix suffix tree, and currently it looks something like this

public static class BoggleRadix
{
    private Node root;

    public BoggleRadix()
    {

    }

    public class Node
    {
        public Node()
        {
           List<Edge> nodeEdges = new List<Edge>() 
           {

           }
        }

    }

    public class Edge
    {
        public String edgeString;
        public Node edgeNode;

        public Edge()
        {

        }
        public Edge(String s, Edge e)
        {
            this.edgeString = s;
            this.edgeNode = e;
        }

    }

}

So I'm storing the pointers in an unordered list, which means if I'm checking for suffixes, I could expect, worse case, 26 operations to even find the suffix pointer I need to continue down the tree.

Is there any way to speed the insertions up, stream line the process? Is it worth building a small dictionary in memory for each node that would check for the first letter of the suffix's existence? Is this so trivial it wouldn't even matter?

Upvotes: 0

Views: 469

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

I agree with jimktrains's suggestion of using array instead of a linked list for the suffixes. You can convert a capital ASCII letter c to an array index with (int)c - (int)'A'. Tests on my system dictionary suggest that there are only a few thousand three-letter prefixes, so space usage should not be a concern.

On the other hand, you could store the whole dictionary as a deterministic acyclic finite state automaton. Then it might be wise to try to save space. Instead of binary search, which branches unpredictably, I would suggest a bitmap. In each node, have a field int bitmap; equal to the bitwise OR (the | operator, with identity element 0) of (1 << i) for each occupied index i in the uncompressed array. Then, to test the presence of an uncompressed index i, check whether bitmap & (1 << i) is nonzero. If so, then the index into the compressed array is Integer.bitCount(bitmap & ((1 << i) - 1)).

Upvotes: 1

Related Questions