lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Robert Muir (JIRA)" <>
Subject [jira] Commented: (LUCENE-2265) improve automaton performance by running on byte[]
Date Sat, 03 Apr 2010 00:03:27 GMT


Robert Muir commented on LUCENE-2265:


I'd say that your highlevel operations like intersection and union remain exactly the same
regardless of the alphabet you're operating on.
The primitive automata, like AnyChar will have to cease being so primitive and generate a
pair of states instead of one, but that's essentially it - after primitive automatas are fixed
to recognize utf-8 bytes, you don't even have to change parsing code that much.

The only true problem I see is that you lose the ability to operate on char[]. But then, I
ask that again, do you write a generic library, or you borrowed automata code from one with
a single aim of having fast lucene queries?

Well this is a borrowed library, but that doesnt really matter. The trick is that UTF-16 and
UTF-32 are much more efficient for the kind of processing the high-level component needs:
doing things like NFA->DFA conversion and minimization. Its much better to do some of these
quadratic algorithms on high-level unicode instead of byte, and get a minimal DFA. At the
same time the intervals represent real things, so its debuggable, etc.

So to me it makes perfect sense to change the transition's min/max from 'char' to 'int', which
is trivial and won't require me to rewrite all the primitive automata. Things like NFA-DFA
conversion will be actually faster, never slower for some text.

This gives us the opportunity to 'compile' to UTF-8 or UTF-32 RunAutomata (although for the
latter we cannot use the classmap trick since the alphabet will be large). This way, it can
be used effectively at both a high and low level, and the code is easy to maintain.

I can debug the code now with things like toString and toDot, I certainly cannot do this if
the high-level code is changed to byte/UTF-8. It would be completely unmaintainable, and most
likely slower overall due to doing quadratic things like determinism on exploded UTF-8 automata.

> improve automaton performance by running on byte[]
> --------------------------------------------------
>                 Key: LUCENE-2265
>                 URL:
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: Search
>    Affects Versions: Flex Branch
>            Reporter: Robert Muir
>            Priority: Minor
>             Fix For: Flex Branch
>         Attachments: LUCENE-2265.patch
> Currently, when enumerating terms, automaton must convert entire terms from flex's native
utf-8 byte[] to char[] first, then step each char thru the state machine.
> we can make this more efficient, by allowing the state machine to run on byte[], so it
can return true/false faster.

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message