TrieSet with Wildcard Search

Question

What I'm ultimately trying to accomplish is a tool in which I pour some documents. Then I mark #x documents as desired and #y documents as undesired. My tool now is to analyse and compare the documents and give me search strings that would find me many of the desired and few of the undesired.

What the code at hand is supposed to do:

• Save words in a TrieSet
• Conduct wildcard searches on that TrieSet

Limitations:

• Is not supposed to work with entries containing [^a-Z]

What I would like to know:

1. What should I have done better? What could I have done worse?
2. How do you estimate/compare my codes performance?
3. What about interfaces like collection, iterable, serializable? Should I have implemented those?
4. Are there sections that can lead to runtime errors?
5. How could I have distributed the code better/over more classes.
6. Anything else I did not even think of right now.

The TrieSet (including a main used for some testing):

package linguist.model.datastructure;

import java.util.ArrayList;
import java.util.HashSet;

public class TrieSet {
    private final Node root;
    private int countOfUniqueKeys = 0; //The number of unique entries
    private int countOfAdds = 0; //The number of entries

    private void countUniques(){
        countOfUniqueKeys+=1;
    }

    private void countAdds(){
        countOfAdds+=1;
    }

    TrieSet(){
        root=new Node("",this);
    }


    /**
     * @param newEntry Word that is added
     */
    public void add(String newEntry){
        newEntry=ParseStrings.normalizeAddString(newEntry);
        root.add(newEntry,0);
    }

    /**
     * @param searchstring The searchstring
     * @return A HashSet of hit nodes as result of the search operation
     */
    public HashSet<Node> getNodes(String searchstring){
        searchstring=ParseStrings.normalizeLookupString(searchstring);
        return root.getNodes(searchstring, 0);
    }


    /**
     * @author S761
     *
     */
    private final class Node{
        private Node parent;
        private Node[] children = new Node[26];
        private TrieSet container; //The TrieSet containing this and relating Nodes
        private String entry; //A string representing the character sequence leading up to this node
        private Boolean isEndOfWord = false; //Flag signing the final node of an entry
        private int minDepth = Integer.MAX_VALUE; //Minimal depth to a final node
        private int maxDepth = 0; //Maximal depth to a final node


        private int countOfChildren = 0; //Number of children
        private int uniqueCount = 0; //Number of entries with this Node as final Node
        private int countOfAdds = 0; //Number of entries having traversed through or ended at this node
        private int countOfUniqueAdds = 0; //Number of final nodes below this node


        /**
         * @param entry The entry respectively the remaining entry
         * @param trieSet The TrieSet that will contain this node
         */
        Node(String entry, TrieSet trieSet){
            this.entry=entry;
            this.container=trieSet;
        }

        /**
         * @param entry
         * @param trieSet
         * @param parentNode parent node
         * @param depth remaining length of the entry at hand
         */
        Node(String entry, TrieSet trieSet, Node parentNode, int depth){
            this.entry=entry;
            this.container=trieSet;
            this.parent = parentNode;
            minDepth=depth;
            maxDepth=depth;
        }


        private String getEntry(){
            return this.entry;
        }

        /**
         * @param string
         * @param index
         * @return
         */
        private Node getOrCreateChild (String string,int index){
            int childIndex = ParseStrings.getIndex(string.charAt(index));
            if (children[childIndex]==null) {
                int depth = string.length()-(index+1);
                String key = string.substring(0, index+1);
                children[childIndex]=new Node(key,container,this,depth);
                countOfChildren+=1;
            }
            return children[childIndex];
        }

        private void setDepth(int depth){
            if (depth<0) throw new IllegalArgumentException();
            if (depth<minDepth) minDepth = depth;
            if (depth>maxDepth) maxDepth = depth;
        }

        private Boolean isDepthEnough(int depth){
            return (depth<=maxDepth)&&(depth>=minDepth);
        }

        private void add(String string, int index) {
            if(string==""){} else if(string.length()==index){
                this.setAsWord();
            }else{
                this.setDepth(string.length()-index);
                //              this.countAdd(); // Ommitted for recursive implementation
                Node childNode = getOrCreateChild(string, index);
                childNode.add(string, index+1);
            }
        }

        private void setAsWord(){
            if (!isEndOfWord) {
                parent.countUniqueAdd();
                isEndOfWord=true;
            }
            parent.countAdd();
            uniqueCount+=1;
            countOfAdds+=1;
        } // +=1's probably should go in the counting methods

        private void countAdd(){
            //          countOfAdds+=1;
            countOfAdds+=1;
            if (parent!=null){
                parent.countAdd();
            }else{
                container.countAdds();
            }
        }
        private void countUniqueAdd(){
            countOfUniqueAdds+=1;
            if (parent!=null){
                parent.countUniqueAdd();
            }else{
                container.countUniques();
            }
        }







        private ArrayList<Node> getNodeArrayList(String string, int index){
            ArrayList<Node> returnArrayList = new ArrayList<Node>();
            if (ParseStrings.stringMinLength(string.substring(index)) > this.maxDepth) {
            }else if (ParseStrings.stringMaxLength(string.substring(index)) < this.minDepth) {
            }else if(string.length()==index){
                if(this.isEndOfWord){
                    returnArrayList.add(this);
                }
            }else if (string.charAt(index)=='V'){
                int[] childIndex = ParseStrings.indexVOCAL;
                for(int i:childIndex){
                    if (children[i]!=null) returnArrayList.addAll(children[i].getNodes(string, index+1));

                }
            }else if (string.charAt(index)=='C'){
                int[] childIndex = ParseStrings.indexCONSONANT;
                for(int i:childIndex){
                    if (children[i]!=null) returnArrayList.addAll(children[i].getNodes(string, index+1));

                }
            }else if (string.charAt(index)=='?')/*exactly one character*/{
                returnArrayList.addAll(this.getNodesAll(string,index));
            }else if (string.charAt(index)=='#')/*one or no character*/{
                //              One character
                returnArrayList.addAll(this.getNodesAll(string,index));
                //              No character
                returnArrayList.addAll(this.getNodes(string, index+1));
            }else if (string.charAt(index)=='*'){
                returnArrayList.addAll(this.getNodesWildcard(string, index));
            }else{
                int i = ParseStrings.getIndex(string.charAt(index));
                if (children[i]!=null) returnArrayList.addAll(children[i].getNodes(string, index+1));

            }
            return returnArrayList;
        }

        private ArrayList<Node> getNodeArrayListAll(String string, int index) {
            ArrayList<Node> returnArrayList = new ArrayList<Node>();
            for (Node child:this.children){
                if (child!=null) returnArrayList.addAll(child.getNodes(string, index+1));
            }
            return returnArrayList;
        }



        private ArrayList<Node> getNodeArrayListWildcard(String string, int index){
            ArrayList<Node> returnArrayList = new ArrayList<Node>();
            for (Node child:this.children){
                if (child!=null) returnArrayList.addAll(child.getNodesWildcard(string, index));
            }
            returnArrayList.addAll(this.getNodes(string, index+1));
            return returnArrayList;
        }

        private HashSet<Node> getNodes(String string, int index){
            HashSet<Node> returnHashSet = new HashSet<Node>();
            if (ParseStrings.stringMinLength(string.substring(index)) > this.maxDepth) {
            }else if (ParseStrings.stringMaxLength(string.substring(index)) < this.minDepth) {
            }else if(string.length()==index){
                if(this.isEndOfWord){
                    returnHashSet.add(this);
                }
            }else if (string.charAt(index)=='V'){
                int[] childIndex = ParseStrings.indexVOCAL;
                for(int i:childIndex){
                    if (children[i]!=null) returnHashSet.addAll(children[i].getNodes(string, index+1));

                }
            }else if (string.charAt(index)=='C'){
                int[] childIndex = ParseStrings.indexCONSONANT;
                for(int i:childIndex){
                    if (children[i]!=null) returnHashSet.addAll(children[i].getNodes(string, index+1));

                }
            }else if (string.charAt(index)=='?')/*exactly one character*/{
                returnHashSet.addAll(this.getNodesAll(string,index));
            }else if (string.charAt(index)=='#')/*one or no character*/{
                //              One character
                returnHashSet.addAll(this.getNodesAll(string,index));
                //              No character
                returnHashSet.addAll(this.getNodes(string, index+1));
            }else if (string.charAt(index)=='*'){
                returnHashSet.addAll(this.getNodesWildcard(string, index));
            }else{
                int i = ParseStrings.getIndex(string.charAt(index));
                if (children[i]!=null) returnHashSet.addAll(children[i].getNodes(string, index+1));

            }
            return returnHashSet;
        }

        private HashSet<Node> getNodesAll(String string, int index) {
            HashSet<Node> returnHashSet = new HashSet<Node>();
            for (Node child:this.children){
                if (child!=null) returnHashSet.addAll(child.getNodes(string, index+1));
            }
            return returnHashSet;
        }



        private HashSet<Node> getNodesWildcard(String string, int index){
            HashSet<Node> returnHashSet = new HashSet<Node>();
            for (Node child:this.children){
                if (child!=null) returnHashSet.addAll(child.getNodesWildcard(string, index));
            }
            returnHashSet.addAll(this.getNodes(string, index+1));
            return returnHashSet;
        }





    }



    public static void main(String[] args) {
        TrieSet test = new TrieSet();
        test.add("a");
        System.out.println("\"a\" added");

        test.add("abcdefghi");
        System.out.println("\"abcdefghi\" added");
        test.add("abcdefghi");
        System.out.println("\"abcdefghi\" added");
        test.add("");
        System.out.println("\"\" ignored");

        System.out.println("Uniquekeys: "+test.countOfUniqueKeys);
        System.out.println();
        System.out.println("Adds: "+test.countOfAdds);
        System.out.println();

        String normalTestStrings[]={"a", "abcdefgh", "abcdefghi"};

        String vocalTestStrings[]={"{v}bcdefghi", "abcd{v}fghi", "abcdefgh{v}", "abc{v}efgh{v}"};
        String consonantTestStrings[]={"abcdefghi", "abcd{c}fghi", "ab{c}defghi", "ab{c}de{c}ghi", "ab{c}{c}efghi"};

        String QuestionmarkTestStrings[]={"?bcdefghi", "abcdefgh?", "abc??fghi", "abcde?ghi"};

        String consecutiveWildcardsStartTestStrings[]={"**abcdefghi", "*2*abcdefghi", "**2abcdefghi", "*3*4abcdefghi" };
        String consecutiveWildcardsEndTestStrings[]={"abcdefghi**", "abcdefghi*2*", "abcdefghi**2", "abcdefghi*3*4" };
        String consecutiveWildcardsMidTestStrings[]={"abcde**fghi", "abcd*2*efghi", "abc**2defghi", "abcde*3*4fghi", "ab*2cdef*4ghi" };

        String wildcardStartTestStrings[]={"*cdefghi", "*1cdefghi", "*2cdefghi", "*3cdefghi" };
        String wildcardEndTestStrings[]={"abcdefg*", "abcdefg*1", "abcdefg*2", "abcdefg*3" };
        String wildcardMidTestStrings[]={"abc*fghi", "abc*1fghi", "abc*2fghi", "abc*3fghi"};

        for(String s:wildcardMidTestStrings){
            HashSet<Node> testList = test.getNodes(s);
            System.out.println(s+":");
            for(Node n: testList){
                System.out.println(n.getEntry());
            }
        }
    }
}

The auxiliary ParseStrings class:

package linguist.model.datastructure;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public abstract class ParseStrings {
    static public int getIndex(char character){
        return ((int) character) - 97;
    }
    static public char getCharacter(int index){
        return (char) (index + 97);
    }

    //Arrays of precomputed character values to be used by {c} and {v} wildcards.
    static final int[] indexVOCAL={
     0,          4,          8,
       14,               20
    };
    static final int[] indexCONSONANT={
        1, 2, 3,    5, 6, 7,    9,10,11,12,
    13,   15,16,17,18,19,   21,22,23,24,25
    };


//TODO: äöü () et cetera ?
    static public String normalizeLookupString(String string){
        string=string.toLowerCase();
        string=string.replaceAll("[^a-z0-9\\{\\}\\*\\?]", "");

        string=string.replaceAll("\\{c\\}", "C");
        string=string.replaceAll("\\{v\\}", "V");

        string=string.replaceAll("[\\{\\}]", "");

//      String string = "*2*abc*13str*ing*32***14a***regex**2** bo*2*th **2si*2**3des*2*3* at least oneng*32***14**1***223*222a*fewfwe*2";
//      System.out.println(string);
        string=string.replaceAll("(\\*\\d*)*\\*(?!\\d)(\\*\\d*)*", "*"); //überflüssige '*' zu einem '*' zusammenführen
//      System.out.println(string);

        Pattern pattern = Pattern.compile("(\\*)(\\d+)");

        Matcher matcher = pattern.matcher(string);
        // Check all occurrences
        //      "*n" durch n '#' ersetzen
        int number;
        StringBuilder b = new StringBuilder();
        String replacement;
        while(matcher.find()){
            number = Integer.parseInt(matcher.group(2));
            for (int i = 0; i < Math.min(number, 99); i++) b.append('#');
            replacement = b.toString();
            string=matcher.replaceFirst(replacement);
            matcher=pattern.matcher(string);
        }
//      System.out.println(string);


        return string;
    }
    static public String normalizeAddString(String string){
        string=string.toLowerCase();
        string=string.replaceAll("[^a-z0-9]", "");
        return string;
    }
    static public int stringMinLength(String string){
        string=string.replaceAll("[\\*#]+", "");
        return string.length();
    }

    static public int stringMaxLength(String string){
        if(string.contains("*")){
            return Integer.MAX_VALUE;
        }else{
            return string.length();
        }
    }

}

Answer 1

I can give you some feedback on your regexes. There are a number of times in Java regex, where you cannot avoid using the "evil escaped escape", but you can refactor most of them out in your case.

First of all, you don't need any backslashes in these three:

string=string.replaceAll("[^a-z0-9\\{\\}\\*\\?]", "");
string=string.replaceAll("[\\{\\}]", "");
string=string.replaceAll("[\\*#]+", "");

You are inside a [] char class, so most of the normal meta characters loose their meaning. You could use:

string=string.replaceAll("[^a-z0-9{}*?]", "");
string=string.replaceAll("[{}]", "");
string=string.replaceAll("[*#]+", "");

Personally, I would try to avoid some of these backslashes:

string=string.replaceAll("(\\*\\d*)*\\*(?!\\d)(\\*\\d*)*", "*");

You could just use a char class, which I think is more readable:

string=string.replaceAll("([*]\\d*)*[*](?!\\d)([*]\\d*)*", "*");

---

The only other comment I have is about, well, your comments.

I notice that you have some comments in English, and some comments like this one:

//überflüssige '*' zu einem '*' zusammenführen

You should probably stick to one language. (Although I suspect you may have translated all the comments, but just forgot this one.)

The other thing I suggest is that you remove some of the commented out code, and also remove some of the excessive blank lines (like the ones towards the end of the first class).