You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Paul Elschot <pa...@xs4all.nl> on 2005/11/23 21:42:42 UTC
Test code for regex queries
Dear readers,
I'd like to add regex queries to the surround parser, so I had a look
at the test code for the regex queries.
I refactored it to have a few more tests, and all seems to work well.
It also includes the tests from TestSpanRegexQuery.java .
Two questions:
Can I assume the APL2 on Test{,Span}RegexQuery.java?
If so, I'll post the refactored version with it.
To parse a regex query term, the surround parser will have to
be extended a bit so it recognizes a reasonable subset of the
java regular expressions.
Any preferences for the syntax for a regex term in the
surround parser?
Kind regards,
Paul Elschot
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Paul Elschot <pa...@xs4all.nl>.
On Friday 25 November 2005 11:14, Erik Hatcher wrote:
>
> On 24 Nov 2005, at 20:26, Erik Hatcher wrote:
> >> There are some older regex implementations in java, but I
> >> have no idea about the licences and the availabiility.
> >> Doesn't apache have one somewhere?
> >
> > Two actually! ORO and Regexp. Here's ORO - <http://
> > jakarta.apache.org/oro/> (link to Regexp from there)
> >
> > I'll dig into those soon and see what useful goodies lurk within.
>
> From perusing the API via Javadocs, Regexp mentioned just what we
> need, but I didn't see the same sort of thing with ORO. So I pulled
> down Jakarta Regexp and dropped it in. I had to add a getter for a
> package protected internal "prefix" to REProgram, but once I did
> that, here are some passing tests...
>
> assertEquals(1, getPrefix("a[bc]*"));
> assertEquals(2, getPrefix("a\\$[bc]*"));
> assertEquals(0, getPrefix("r?over"));
>
>
> private int getPrefix(String expression) {
> REProgram program = new RECompiler().compile(expression);
> char[] prefix = program.getPrefix();
> return prefix == null ? 0 : prefix.length;
> }
>
> Quite promising! The REProgram has the full parse tree as
> "instructions", so it'd be possible to use this for clever rotation
> also, I believe. I'm sure Regexp doesn't support the full Perl5
> syntax that Java's regex package does, but it seems to be good enough
> for the basic regex syntax.
>
> A couple of issues... 1) to use this additional library, (Span)
> RegexQuery should be pulled into contrib/regex, 2) It'd be a little
> awkward to use Jakarta Regexp to determine the prefix and potentially
> be used for rotation logic, and then use JDK regex for the actual
> matching. I have no data to say which has faster matching, or
> another pros/cons, just that it could potentially mismatch. I'm
> inclined to swap completely to Jakarta Regexp for matching as well,
> at least for the time being in order to keep things in sync and
> benefit from more clever term enumeration. The time saved in term
> enumeration seems likely to more than make up for matching speed
> differences.
>
> Thoughts?
I think I'll add a prefix regex facility to the surround language first.
That is, I'll try and make a token definition for a prefixed regex in the
surround parser.
The operator I mentioned before is too verbose. Perhaps
double quotes can be used to enclose a regex, possibly prefixed
by literal characters. The prefix may also need quotes.
Double quotes would work to enclose a regex when they
have no special meaning in a regex, which I think is the case.
Using another regex package for the actual parsing and matching
might then be possible by overriding some methods in the parser.
I hope the regex compiler and matcher from java.util.regex have
interfaces, otherwise interfaces will have to made to allow
different regex implementations.
To have term rotation built into a query parser requires some
way to know which field is being queried, eg. by an overridable
getFieldQuery(fieldName, queryTerm) method in the parser,
and let this method rotate the queryTerm when rotation is needed
for the field.
Regards,
Paul Elschot
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Erik Hatcher <er...@ehatchersolutions.com>.
Following up on the (Span)RegexQuery topic, I've started working on
moving this code to contrib/regex so that it can leverage various
regex implementations. I'm making a generic interface that currently
(though subject to change) has these methods:
void compile(String pattern);
boolean match(String string);
int prefixLength();
I'm going to initially create an implementation for both Jakarta
Regexp and java.util.regex, and probably Jakarta ORO also. I've been
able to extract the prefix length using Jakarta Regexp, but I don't
believe this is possible with java.util.regex. I haven't looked into
Jakarta ORO deep enough yet to see if it makes this available.
(Span)RegexQuery will have a setter for specifying which
implementation to use, probably with the default for java.util.regex
to allow running without any dependencies.
An interesting thing to note...
Jakarta Regex: "a.c" matches "abcd"
java.util.regex: "a.c" does not match "abcd" using Matcher.matches
(), but it does match using Matcher.lookingAt()
In other words, if you want "a.*" to only match terms that begin with
"a", the regex logically must be specified as "^a.*". This is of no
real concern to the regex query really, but the underlying matching
implementation. And for query parsing, it would likely be desirable
to wrap all regex expressions with ^...$ (which is generally what
users would mean when saying "a.*").
I'm also considering having the implementation independent interface
specify a method to rotate an expression, though this is a more
advanced feature that perhaps belongs at a different layer.
I'm open to suggestions on all of this, with my main goal to provide
a general purpose regular expression query that can be as fast as
possible by minimizing term enumeration.
Erik
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Erik Hatcher <er...@ehatchersolutions.com>.
On 24 Nov 2005, at 20:26, Erik Hatcher wrote:
>> There are some older regex implementations in java, but I
>> have no idea about the licences and the availabiility.
>> Doesn't apache have one somewhere?
>
> Two actually! ORO and Regexp. Here's ORO - <http://
> jakarta.apache.org/oro/> (link to Regexp from there)
>
> I'll dig into those soon and see what useful goodies lurk within.
From perusing the API via Javadocs, Regexp mentioned just what we
need, but I didn't see the same sort of thing with ORO. So I pulled
down Jakarta Regexp and dropped it in. I had to add a getter for a
package protected internal "prefix" to REProgram, but once I did
that, here are some passing tests...
assertEquals(1, getPrefix("a[bc]*"));
assertEquals(2, getPrefix("a\\$[bc]*"));
assertEquals(0, getPrefix("r?over"));
private int getPrefix(String expression) {
REProgram program = new RECompiler().compile(expression);
char[] prefix = program.getPrefix();
return prefix == null ? 0 : prefix.length;
}
Quite promising! The REProgram has the full parse tree as
"instructions", so it'd be possible to use this for clever rotation
also, I believe. I'm sure Regexp doesn't support the full Perl5
syntax that Java's regex package does, but it seems to be good enough
for the basic regex syntax.
A couple of issues... 1) to use this additional library, (Span)
RegexQuery should be pulled into contrib/regex, 2) It'd be a little
awkward to use Jakarta Regexp to determine the prefix and potentially
be used for rotation logic, and then use JDK regex for the actual
matching. I have no data to say which has faster matching, or
another pros/cons, just that it could potentially mismatch. I'm
inclined to swap completely to Jakarta Regexp for matching as well,
at least for the time being in order to keep things in sync and
benefit from more clever term enumeration. The time saved in term
enumeration seems likely to more than make up for matching speed
differences.
Thoughts?
Erik
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Erik Hatcher <er...@ehatchersolutions.com>.
On 24 Nov 2005, at 11:57, Paul Elschot wrote:
> Capturing groups and special contexts need normal brackets ().
Maybe we have a terminology mismatch. I call these (parentheses) and
these [brackets].
> Capturing groups are used for replacements, and I don't see a use
> for that in a query language.
Right.
> Special constructs with () brackets are used for non capturing groups,
> match flags, and lookahead/lookbehind.
> Would you know a use for these in a query language?
I meant a construct using something like [Tt]his as a "character
class" according to the JDK Pattern documentation.
> I also missed things like \u2014, which only add to the problem.
Yeah, I gave up looking for more problems, as there are many.
> There are some older regex implementations in java, but I
> have no idea about the licences and the availabiility.
> Doesn't apache have one somewhere?
Two actually! ORO and Regexp. Here's ORO - <http://
jakarta.apache.org/oro/> (link to Regexp from there)
I'll dig into those soon and see what useful goodies lurk within.
> Btw. $ also has a special meaning in regexes.
Quite true.
For my particular query language, I'm not supporting full regex, just
*, ?, and [...] syntax. I convert the expression into regex before
handing it to RegexQuery (* -> .*, ? -> .?).
Erik
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Index-time translation
Posted by Murray Altheim <m....@open.ac.uk>.
Hi,
Pardon me if this has been asked before (couldn't find any
references), but has anyone developed an index-time translation
service for Lucene, such that the indexer could translate a
page in a known natural language into English (or whatever
the indexing language is) and use that to provide the index
content?
Thanks much for any assistance,
Murray
......................................................................
Murray Altheim http://www.altheim.com/murray/
Strategic Services Development Manager
The Open University Library and Learning Resources Centre
The Open University, Milton Keynes, Bucks, MK7 6AA, UK .
Empty handed, holding a hoe,
Walking, riding a water buffalo,
A man is crossing over a bridge;
The bridge, not the water, flows.
-- Mahasattva Fu, The Blue Cliff Record [96]
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Paul Elschot <pa...@xs4all.nl>.
On Thursday 24 November 2005 10:25, Erik Hatcher wrote:
>
> On 24 Nov 2005, at 03:17, Paul Elschot wrote:
> >> I must admit that I haven't used the surround parser. For my custom
> >> parser (a legacy syntax that no one here would want), I take any term
> >> that has an *, ?, or [...] syntax as a regex term.
> >
> > I had another look at the javadocs of java regex package.
> > The normal brackets in a regex are not needed for queries, so they
> > can be left as they are.
>
> I don't understand what you mean about brackets not being needed.
> Brackets certainly factor in greatly into regular expressions:
>
> <http://java.sun.com/j2se/1.4.2/docs/api/java/util/regex/Pattern.html>
>
> What am I missing?
Capturing groups and special contexts need normal brackets ().
Capturing groups are used for replacements, and I don't see a use
for that in a query language.
Special constructs with () brackets are used for non capturing groups,
match flags, and lookahead/lookbehind.
Would you know a use for these in a query language?
> >> There are still some TODO's with the (Span)RegexQuery - such as being
> >> wise about the prefix length. Right now it is not wise enough. I've
> >> spent some time looking for a regex parser that could parse a regex
> >> expression into an AST so that it could be used for determining the
> >> last static character to start term enumeration. This would also
> >> come in very handy in being able to rotate a regular expression
> >> string to maximize the static prefix when indexing with an analyzer
> >> that rotates terms. If anyone has suggestions/pointers to how this
> >> could be accomplished, it'd be most appreciated!
> >
> > I think I'll simply treat each term as a potential regex and
> > use alphanumeric characters for the prefix. I'll try and leave
> > parsing of the regex to the java regex package as much as possible.
>
> Simply using alphanumeric to determine the prefix doesn't work in all
> cases though. Here's an example I just added, commented out, to
> TestRegexQuery:
>
> assertEquals(1, regexQueryNrHits("r?over"));
>
> The 'r' is optional, yet it is chosen as a prefix and thus no
> documents match even though "over" does match that regex. The quick
You're right, I missed the suffix meaning of ? .
> fix for this is, like FuzzyQuery, to enumerate all terms blindly.
> Another option is to allow the user of (Span)RegexQuery to provide
> the prefix, at least pushing the burden back a bit.
>
> I still think a regex parser would be mighty useful for this issue,
> as well as the next...
>
> > Rotating from the suffix should also be straightforward for
> > alphanumerical chars.
>
> It's not as trivial as this, if you want the rotated prefixes to be
> maximized. Take, for example, the regex expression
>
> ThisContainsTwo[abc]RegexPieces.*Total
>
> Using rotation to maximize the prefix and speeding up term
> enumeration a calculation of of the maximum non-regex piece is
> needed, including a calculation on whether the head and tail combined
> make a larger prefix. For example, using '$' to denote the end of
> the string, the rotated version of this should be:
>
> Total$ThisContainsTwo[abc]RegexPieces.*
>
> With a regex parse tree, it should be possible to be wise about what
> is a static prefix and to compute the size of all the static pieces
> allowing for clever rotation to make regex queries as efficient as
> possible. Now where is that regex parser grammar?! :/
I also missed things like \u2014, which only add to the problem.
There are some older regex implementations in java, but I
have no idea about the licences and the availabiility.
Doesn't apache have one somewhere?
Without a regex parser a prefix regex operator like
PRE(prefix,regex)
in the surround parser would just do what is needed,
except for the comma and the brackets, and a regular expression
can work around these by using \xhh or \0nn .
Btw. $ also has a special meaning in regexes.
Regards,
Paul Elschot
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Erik Hatcher <er...@ehatchersolutions.com>.
On 24 Nov 2005, at 03:17, Paul Elschot wrote:
>> I must admit that I haven't used the surround parser. For my custom
>> parser (a legacy syntax that no one here would want), I take any term
>> that has an *, ?, or [...] syntax as a regex term.
>
> I had another look at the javadocs of java regex package.
> The normal brackets in a regex are not needed for queries, so they
> can be left as they are.
I don't understand what you mean about brackets not being needed.
Brackets certainly factor in greatly into regular expressions:
<http://java.sun.com/j2se/1.4.2/docs/api/java/util/regex/Pattern.html>
What am I missing?
>> There are still some TODO's with the (Span)RegexQuery - such as being
>> wise about the prefix length. Right now it is not wise enough. I've
>> spent some time looking for a regex parser that could parse a regex
>> expression into an AST so that it could be used for determining the
>> last static character to start term enumeration. This would also
>> come in very handy in being able to rotate a regular expression
>> string to maximize the static prefix when indexing with an analyzer
>> that rotates terms. If anyone has suggestions/pointers to how this
>> could be accomplished, it'd be most appreciated!
>
> I think I'll simply treat each term as a potential regex and
> use alphanumeric characters for the prefix. I'll try and leave
> parsing of the regex to the java regex package as much as possible.
Simply using alphanumeric to determine the prefix doesn't work in all
cases though. Here's an example I just added, commented out, to
TestRegexQuery:
assertEquals(1, regexQueryNrHits("r?over"));
The 'r' is optional, yet it is chosen as a prefix and thus no
documents match even though "over" does match that regex. The quick
fix for this is, like FuzzyQuery, to enumerate all terms blindly.
Another option is to allow the user of (Span)RegexQuery to provide
the prefix, at least pushing the burden back a bit.
I still think a regex parser would be mighty useful for this issue,
as well as the next...
> Rotating from the suffix should also be straightforward for
> alphanumerical chars.
It's not as trivial as this, if you want the rotated prefixes to be
maximized. Take, for example, the regex expression
ThisContainsTwo[abc]RegexPieces.*Total
Using rotation to maximize the prefix and speeding up term
enumeration a calculation of of the maximum non-regex piece is
needed, including a calculation on whether the head and tail combined
make a larger prefix. For example, using '$' to denote the end of
the string, the rotated version of this should be:
Total$ThisContainsTwo[abc]RegexPieces.*
With a regex parse tree, it should be possible to be wise about what
is a static prefix and to compute the size of all the static pieces
allowing for clever rotation to make regex queries as efficient as
possible. Now where is that regex parser grammar?! :/
> I'd like the surround parser to be a power tool that provides
> everything that Lucene has under the hood. Regexes fit well,
> because they are already used for truncation, only the
> truncation syntax will have a dot added as far as I can see now.
I'm still missing why brackets don't factor into the equation.
Erik
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Paul Elschot <pa...@xs4all.nl>.
On Thursday 24 November 2005 00:06, Erik Hatcher wrote:
>
> On 23 Nov 2005, at 15:42, Paul Elschot wrote:
> > I refactored it to have a few more tests, and all seems to work well.
> > It also includes the tests from TestSpanRegexQuery.java .
> >
...
>
> > To parse a regex query term, the surround parser will have to
> > be extended a bit so it recognizes a reasonable subset of the
> > java regular expressions.
> > Any preferences for the syntax for a regex term in the
> > surround parser?
>
> I must admit that I haven't used the surround parser. For my custom
> parser (a legacy syntax that no one here would want), I take any term
> that has an *, ?, or [...] syntax as a regex term.
I had another look at the javadocs of java regex package.
The normal brackets in a regex are not needed for queries, so they
can be left as they are.
All the rest could stay the same, except for the current surround truncation *
and ? (same as lucene) for which the equivalent regexes are .* and .? .
> There are still some TODO's with the (Span)RegexQuery - such as being
> wise about the prefix length. Right now it is not wise enough. I've
> spent some time looking for a regex parser that could parse a regex
> expression into an AST so that it could be used for determining the
> last static character to start term enumeration. This would also
> come in very handy in being able to rotate a regular expression
> string to maximize the static prefix when indexing with an analyzer
> that rotates terms. If anyone has suggestions/pointers to how this
> could be accomplished, it'd be most appreciated!
I think I'll simply treat each term as a potential regex and
use alphanumeric characters for the prefix. I'll try and leave
parsing of the regex to the java regex package as much as possible.
Rotating from the suffix should also be straightforward for
alphanumerical chars.
I'd like the surround parser to be a power tool that provides
everything that Lucene has under the hood. Regexes fit well,
because they are already used for truncation, only the
truncation syntax will have a dot added as far as I can see now.
Regards,
Paul Elschot
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Test code for regex queries
Posted by Erik Hatcher <er...@ehatchersolutions.com>.
On 23 Nov 2005, at 15:42, Paul Elschot wrote:
> I refactored it to have a few more tests, and all seems to work well.
> It also includes the tests from TestSpanRegexQuery.java .
>
> Two questions:
>
> Can I assume the APL2 on Test{,Span}RegexQuery.java?
> If so, I'll post the refactored version with it.
Yes, those files should have had APL2 in them, my apologies for
missing it.
> To parse a regex query term, the surround parser will have to
> be extended a bit so it recognizes a reasonable subset of the
> java regular expressions.
> Any preferences for the syntax for a regex term in the
> surround parser?
I must admit that I haven't used the surround parser. For my custom
parser (a legacy syntax that no one here would want), I take any term
that has an *, ?, or [...] syntax as a regex term.
There are still some TODO's with the (Span)RegexQuery - such as being
wise about the prefix length. Right now it is not wise enough. I've
spent some time looking for a regex parser that could parse a regex
expression into an AST so that it could be used for determining the
last static character to start term enumeration. This would also
come in very handy in being able to rotate a regular expression
string to maximize the static prefix when indexing with an analyzer
that rotates terms. If anyone has suggestions/pointers to how this
could be accomplished, it'd be most appreciated!
Erik
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org