Check whether a list of list of string fits a regex efficiently

Question

I have the following structure for my object:

Word (Object)

• Word (String)
• List<Symbol>

Symbol (Object)

• Symbol (String)
• List<SymbolChoice>

SymbolChoice (Object)

• Symbol (String)

The background of this is that this is processed OCR output and I want to force a word to match a certain regex. If it cannot find a match, it should return an empty List<SymbolChoice>, otherwise it should return all List<SymbolChoice> that match the specified regex.

Example:

• Found word: "1o0"
• Symbols: "1", "o" and "0"
• Choices of "1": "1"
• Choices of "o": "o", "0"
• Choices of "0": "0"

When forcing this word to abide regex "\\d{3}", it has to return [["1", "0", "0"]], here I am denoting the SymbolChoice objects as strings.

I have a solution, however it is not fast enough, more details after the method:

public List<List<SymbolChoice>> forceFitRegex(final String regex) {
    Objects.requireNonNull(regex, "regex");

    if (getSymbols().size() <= 1) {
        return new ArrayList<List<SymbolChoice>>();
    }

    int combinations = 1;
    for (Symbol symbol : getSymbols()) {
        combinations *= symbol.getSymbolChoices().size();
    }
    System.out.println("Combinations: " + combinations);

    List<List<SymbolChoice>> listOfSymbolChoices = new ArrayList<List<SymbolChoice>>();
    for (SymbolChoice symbolChoice : getSymbols().get(0).getSymbolChoices()) {
        List<SymbolChoice> symbolChoices = new ArrayList<SymbolChoice>();
        symbolChoices.add(symbolChoice);
        listOfSymbolChoices.add(symbolChoices);
    }

    int i = 1;
    while (i < getSymbols().size()) {
        List<List<SymbolChoice>> listOfSymbolChoicesCopy = new ArrayList<List<SymbolChoice>>(listOfSymbolChoices);
        for (SymbolChoice symbolChoice : getSymbols().get(i).getSymbolChoices()) {
            for (List<SymbolChoice> symbolChoicesCopy : listOfSymbolChoicesCopy) {
                List<SymbolChoice> symbolChoices = new ArrayList<SymbolChoice>(symbolChoicesCopy);
                symbolChoices.add(symbolChoice);
                listOfSymbolChoices.add(symbolChoices);
            }
        }
        i++;
    }

    Pattern pattern = Pattern.compile(regex);
    ListIterator<List<SymbolChoice>> symbolChoicesListIterator = listOfSymbolChoices.listIterator();
    while (symbolChoicesListIterator.hasNext()) {
        List<SymbolChoice> symbolChoices = symbolChoicesListIterator.next();
        StringBuilder stringBuilder = new StringBuilder();
        for (SymbolChoice symbolChoice : symbolChoices) {
            stringBuilder.append(symbolChoice.getSymbol());
        }
        if (!pattern.matcher(stringBuilder.toString()).matches()) {
            symbolChoicesListIterator.remove();
        }
    }
    return listOfSymbolChoices;
}

Let n be the number of combinations possible, calculated as the product of the size of all symbol choices. In my example that would be 1 * 2 * 1 = 2.

For n <= 288 I observe it to run very quick, however with for example n = 5760 it takes a few minutes to process. I also spot here another case of n = 311040 and have a feeling that it will never finish.

What can I do to solve my problem efficiently? I need to stick to Java 6 for Android compatibility.

(Bonus points if someone can calculate the asymptotic time my algorithm takes)

Answer 1

This is probably a bug:

  if (getSymbols().size() <= 1) {
      return new ArrayList<List<SymbolChoice>>();
  }

should be isEmpty().... not <= 1.

As for your algorithm, you are building up all possible results in to your list, then you are discarding the ones that do not match.

I recommend reversing the process, and only add combinations that do match.

You can streamline the process by organizing your possibilities in to a 'ragged' 2D array. Using your input of "1o0", the array would look like:

0:  ["1"]
1:  ["o","0"]
2:  ["0"]

Then, we create a 'stack' counter, which is just an array, where each int in the array points to which option is used from he input. The stack would start with:

[0, 0, 0]

Which means this combination is: "1" "o" "0".

We test that combination to match (which it does not).

Then, we 'increment' the stack, by starting at the right:

[0, 0, 1]

But, there is no 1 member in the last option, so, we set it back to 0, and increment the second-to-last option, and get:

[0, 1, 0]

This is the option: "1", "0", "0". We test that, and find it matches, and add it to the result!

Then we increment the stack again, first to:

[0, 1, 1]

which does not exist.... so we try:

[0, 2, 0]

which also does not exist, so we try:

[1, 0, 0]

which also does not exist, and we discover there's nothing left to do, so we exit.

Roughing up the code, it would look something like:

public List<List<SymbolChoice>> forceFitRegex(final String regex) {
    Objects.requireNonNull(regex, "regex");

    final List<Symbol> symbols = getSymbols();

    SymbolChoice[][] options = new SymbolChoice[symbols.size()][];
    int pos = 0;
    int combinations = 1;
    final SymbolChoice[] emptyChoice = new SymbolChoice[0];
    for (Symbol symbol : getSymbols()) {
        options[pos] = symbol.getSymbolChoices().toArray(emptyChoice);
        combinations *= options[pos].length;
        pos++;
    }

    System.out.println("Combinations: " + combinations);

    Pattern pattern = Pattern.compile(regex);
    int[] stack = new int[options.length];
    boolean done = false;
    List<List<SymbolChoice>> listOfSymbolChoices = new ArrayList<List<SymbolChoice>>();
    StringBuilder sb = new StringBuilder(stack.length);
    while (!done) {
        sb.setLength(0);
        // check the stack as a match.
        for (int i = 0; i < stack.length; i++) {
            sb.append(options[i][stack[i]]);
        }
        if (pattern.matcher(sb.toString()).matches()) {
            List<SymbolChoice> match = new ArrayList<>(stack.length);
            for (int i = 0; i < stack.length; i++) {
                match.add(options[i][stack[i]]);
            }
            listOfSymbolChoices.add(match);
        }
        // increment the stack
        int depth = stack.length;
        done = true;
        while (--depth >= 0) {
            stack[depth]++;
            if (stack[depth] > options[depth].length) {
                stack[depth] = 0;
            } else {
                done = false;
                break;
            }
        }
    }

    return listOfSymbolChoices;
}

---

---

Edit: Based on the hitEnd() hint from maaartinus

if you are reading this, then consider upvoting his answer...

I have played with the code, and it is significantly faster... Consider this revised method (I won't pretend it is easy to read... - it is basically a state machine, though). I have put a test up on Ideone that processes 380M combinations in less than 2 seconds.....

public List<List<SymbolChoice>> forceFitRegex(final String regex) {
    return forceFitRegex(regex, false);
}

public List<List<SymbolChoice>> forceFitRegex(final String regex, boolean debug) {
    Objects.requireNonNull(regex, "regex");

    final List<Symbol> symbols = getSymbols();

    SymbolChoice[][] options = new SymbolChoice[symbols.size()][];
    int pos = 0;
    int combinations = 1;
    final SymbolChoice[] emptyChoice = new SymbolChoice[0];
    for (Symbol symbol : getSymbols()) {
        options[pos] = symbol.getSymbolChoices().toArray(emptyChoice);
        combinations *= options[pos].length;
        pos++;
    }

    Pattern pattern = Pattern.compile(regex);
    int[] stack = new int[options.length];
    int[] sbsize = new int[options.length + 1];

    List<List<SymbolChoice>> listOfSymbolChoices = new ArrayList<List<SymbolChoice>>();
    StringBuilder sb = new StringBuilder(stack.length);
    int depth = 0;
    int testcnt = 0;
    while (depth >= 0) {
        if (stack[depth] >= options[depth].length) {
            stack[depth] = 0;
            depth--;
            if (depth >= 0) {
                sb.setLength(sbsize[depth]);
                stack[depth]++;
            }
        } else {
            sb.append(options[depth][stack[depth]].symbol.value);
            Matcher matcher = pattern.matcher(sb);
            testcnt++;
            boolean found = matcher.matches();
            if (depth == options.length - 1) {
                if (found) {
                    // we have a viable answer here, we can report it....
                    List<SymbolChoice> match = new ArrayList<>(stack.length);
                    for (int i = 0; i < stack.length; i++) {
                        match.add(options[i][stack[i]]);
                    }
                    listOfSymbolChoices.add(match);
                }
                sb.setLength(sbsize[depth]);
                stack[depth]++;
            } else if (found || matcher.hitEnd()) {
                // we have a viable answer here, we can descend....
                depth++;
                sbsize[depth] = sb.length();
            } else {
                // nothing viable down here....
                sb.setLength(sbsize[depth]);
                stack[depth]++;
            }
        }
    }

    if (debug) {
        System.out.println("Combinations: " + combinations + " actual tests " + testcnt);
    }

    return listOfSymbolChoices;
}

Answer 2

Bonus points if someone can calculate the asymptotic time my algorithm takes.

Too much. It's exponential, as you're generating the whole candidate set. Even the improvement by rolfl doesn't change it.

You could do much better by analyzing the regex. For example "\\d{3}" will never match anything starting with a letter and you could cut off many possibilities. However, doing this in general is pretty complicated.

There's a method which might do this for you: hitEnd. I'm not sure if it does the right thing, but I guess so:

Returns true if the end of input was hit by the search engine in the last match operation performed by this matcher.

When this method returns true, then it is possible that more input would have changed the result of the last search.

So you could test you incomplete candidates against the regex and possibly save yourself the work with expanding them.