search

apache / lucene

Apache Lucene open-source search software
https://lucene.apache.org/
Apache License 2.0
2.6k stars 1.01k forks source link

Co-occurrence filter [LUCENE-2749] #3823

Open asfimport opened 13 years ago

asfimport commented 13 years ago

The co-occurrence filter to be developed here will output sets of tokens that co-occur within a given window onto a token stream.

These token sets can be ordered either lexically (to allow order-independent matching/counting) or positionally (e.g. sliding windows of positionally ordered co-occurring terms that include all terms in the window are called n-grams or shingles).

The parameters to this filter will be:

One use case for co-occurring token sets is as candidates for collocations.

Migrated from LUCENE-2749 by Steven Rowe (@sarowe), updated Apr 05 2018 Linked issues:

asfimport commented 13 years ago

Elmar Pitschke (migrated from JIRA)

Hi, i am fairly new to Lucene development, but i have plenty experience using it :). I would like to make some contribution and think this would be a good task for me to start, as i am fairly interested in the analysis part. Can i work on this task or has there been any work done on this yet? Regards Elmar

asfimport commented 13 years ago

Steven Rowe (@sarowe) (migrated from JIRA)

Hi Elmar,

I haven't had a chance to do more than an hour or two of work on this, and that was a while back, so please feel free to run with it.

You should know, though, that Robert Muir and Yonik Seeley (both Lucene/Solr developers) expressed skepticism (on #lucene IRC) about whether this filter belongs in Lucene itself, because in their experience, collocations are used by non-search software, and they believe that Lucene should remain focused exclusively on search.

Robert Muir also thinks that components that support Boolean search (i.e., not ranked search) should go elsewhere.

I personally disagree with these restrictions in general, and I think that a co-occurrence filter could directly support search. See this solr-user@lucene.apache.org mailing list discussion for an example I gave (and one of the reasons I made this issue): http://www.lucidimagination.com/search/document/f69f877e0fa05d17/how_do_i_this_in_solr#d9d5932e7074d356 . In this thread, I described a way to solve the original poster's problem using a co-occurrence filter exactly like the one proposed here.

I mention all this to caution you that work you put in here may never be committed to Lucene itself.

The mailing list thread I mentioned above describes the main limitations a filter like this will have: combinatoric explosion of generated terms. I haven't figured out how to manage this, but it occurs to me that the two-term-collocation case is less problematic in this regard than the generalized case (whole-field window, all possible combinations). I had a vague implementation conception of incrementing a fixed-width integer to iterate over the combinations, using the integer's bits to include/exclude input terms in the output "termset" tokens. Using a 32-bit integer to track combinations would limit the length of an input token stream to 32 tokens, but in the generalized case of all combinations, I'm pretty sure that the number of bits available would not be the limiting factor, but rather the number of generated terms. I guess the question is how to handle cases that produce fewer terms than all combinations of terms from an input token stream, e.g. the two-term-collocation case, without imposing the restrictions necessary in the generalized case.

Here are a couple of recent information retrieval papers using "termset" to mean "indexed token containing multiple input terms":

"TSS: Efficient Term Set Search in Large Peer-to-Peer Textual Collections" http://www.cs.ust.hk/\~liu/TSS-TC.pdf

"Termset-based Indexing and Query Processing in P2P Search" http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5384831

(Sorry, I couldn't find a free public location for the second paper.)

asfimport commented 13 years ago

Elmar Pitschke (migrated from JIRA)

Hi Steven, thanks for the info, i will work through it and get back here with some questions. As i have a lot to do with Lucene at my work, this filter would definitely something that i could use. So the work would not be lost ;) Regards Elmar

asfimport commented 13 years ago

Steven Rowe (@sarowe) (migrated from JIRA)

this filter would definitely something that i could use

What use case(s) are you thinking of?

asfimport commented 13 years ago

Elmar Pitschke (migrated from JIRA)

The first use case that comes into my mind is the filtering of possible names. One of the request i always get is the automatic generation of tag-clouds with a consideration in the search results. I think this would be one possibility to get names without the need to maintain a word list. Another thing of course would be to get some kind of semantic combination of words. So you could get to more "natural" search experience. I think if a user search for two words and these are quite near in a text it may be more useful than a lot of occurances of the two words but with no combination. Which use cases do you have in mind?

asfimport commented 13 years ago

Steven Rowe (@sarowe) (migrated from JIRA)

Which use cases do you have in mind?

So far just the solution I proposed in the email thread mentioned in my previous comment and the P2P distributed search use case described in the two papers mentioned in the same comment.

asfimport commented 11 years ago

Steven Rowe (@sarowe) (migrated from JIRA)

Bulk move 4.4 issues to 4.5 and 5.0

asfimport commented 10 years ago

Uwe Schindler (@uschindler) (migrated from JIRA)

Move issue to Lucene 4.9.