Automaton for prefix matching

Question

Using an open source Java automaton library, eg: org.apache.lucene.util.automaton or dk.brics.automaton, how can I build an automaton for prefix matching?

eg: an automaton created from the set of strings ["lucene", "lucid"], that will match when given "luc", or "luce", but not match when given "lucy" or "lucid dream".

This is exactly how a trie works. A similar idea can be used to construct the automaton. Usage of an "end of input" character might be useful as well - such as $. — Obicere
– Obicere, Commented Feb 12, 2017 at 21:56
I'm familiar with tries, although the implementations I've found in Java (eg: PatriciaTrie) are actually Maps, and will return a value associated with a prefix. I just want to check for the presence of a prefix. — tekumara
– tekumara, Commented Feb 22, 2017 at 0:13

tekumara · Accepted Answer · 2017-02-22 00:18:07Z

0

Prefix matching is possible using org.apache.lucene.util.automaton by setting all states to accept, eg:

    String[] strings = new String[]{"lucene", "lucid dream"};
    final List<BytesRef> terms = new ArrayList<>();
    for(String s : strings) {
        terms.add(new BytesRef(s));
    }
    Collections.sort(terms);
    final Automaton a = DaciukMihovAutomatonBuilder.build(terms);

    for (int i = 0; i < a.getNumStates(); i++) {
        a.setAccept(i, true);
    }

answered Feb 22, 2017 at 0:18

tekumara

8,87711 gold badges63 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

tonicebrian Over a year ago

Could you complete the example with the code that tests a string against the such created Automaton? I cannot find any examples with the DaciukMihovAutomatonBuilder

Collectives™ on Stack Overflow

Automaton for prefix matching

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related