Lucene Query (with shingles ? )

Question

I have a Lucene Index containing documents like these :

_id     |           Name            |        Alternate Names      |    Population

123       Bosc de Planavilla               (some names here in          5000
345       Planavilla                       other languages)             20000
456       Bosc de la Planassa                                           1000
567       Bosc de Plana en Blanca                                       100000

What's the best Lucene query type I should use and how should I structure it considering I need the following :

1. If a user queries for : "Italian Restaurant near Bosc de Planavilla" I want document with id 123 to be returned because its contains an exact match with the name of the doc.

2. If a user queries for : "Italian Restaurant near Planavilla" I want document with id 345 because query contains an exact match AND it has the highest population.

3. If a user queries for "Italian Restaurant near Bosc" I want 567 because query contains "Bosc" AND of the 3 "Bosc" it has the highest pop.

there are probably many other use cases ... but you get the feeling of what i need ...

What kind of query will do this form me ? Should I generate word N grams (shingles) and create an ORed boolean query using the shingles then apply custom scoring ? or will a regular phrase query will do ? I also saw DisjunctionMaxQuery but dont know if its what im looking for ...

The idea, as you might have anderstood by now, is to find the exact Location a user implied in his query. From that I can start my Geo search and add some further querying around that.

What's the best approach ?

Thanks in advance .

Answer 1

How do you tokenize the fields? Do you store them as complete string? Also, how do you parse the query?

Okay, so I am playing around a bit with this. I have been using a StopFilter to remove la, en, de. I then used a shingle filter to get multiple combination in order to do the "exact matches". So for example Bosc de Planavilla gets tokenized as [Bosc] [Bosc Planavilla] and Bosc de Plana en Blanca gets tokenized to [Bosc] [Bosc Plana] [Plana Blanca] [Bosc Plana Blanca]. This is so that you can have "exact matches" on parts of the query.

I then query the exact string the user passed, although there could be some adaptation there as well. I went with the simple case to make the results better match what you were looking for.

Here is code I am using (lucene 3.0.3):

public class ShingleFilterTests {
    private Analyzer analyzer;
    private IndexSearcher searcher;
    private IndexReader reader;

    public static Analyzer createAnalyzer(final int shingles) {
        return new Analyzer() {
            @Override
            public TokenStream tokenStream(String fieldName, Reader reader) {
                TokenStream tokenizer = new WhitespaceTokenizer(reader);
                tokenizer = new StopFilter(false, tokenizer, ImmutableSet.of("de", "la", "en"));
                if (shingles > 0) {
                    tokenizer = new ShingleFilter(tokenizer, shingles);
                }
                return tokenizer;
            }
        };
    }

    @Before
    public void setUp() throws Exception {
        Directory dir = new RAMDirectory();
        analyzer = createAnalyzer(3);

        IndexWriter writer = new IndexWriter(dir, analyzer, IndexWriter.MaxFieldLength.UNLIMITED);
        ImmutableList<String> cities = ImmutableList.of("Bosc de Planavilla", "Planavilla", "Bosc de la Planassa",
                                                               "Bosc de Plana en Blanca");
        ImmutableList<Integer> populations = ImmutableList.of(5000, 20000, 1000, 100000);

        for (int id = 0; id < cities.size(); id++) {
            Document doc = new Document();
            doc.add(new Field("id", String.valueOf(id), Field.Store.YES, Field.Index.NOT_ANALYZED));
            doc.add(new Field("city", cities.get(id), Field.Store.YES, Field.Index.ANALYZED));
            doc.add(new Field("population", String.valueOf(populations.get(id)),
                                     Field.Store.YES, Field.Index.NOT_ANALYZED));
            writer.addDocument(doc);
        }
        writer.close();

        searcher = new IndexSearcher(dir);
        reader = searcher.getIndexReader();
    }

    @After
    public void tearDown() throws Exception {
        searcher.close();
    }

    @Test
    public void testShingleFilter() throws Exception {
        System.out.println("shingle filter");

        QueryParser qp = new QueryParser(Version.LUCENE_30, "city", createAnalyzer(0));

        printSearch(qp, "city:\"Bosc de Planavilla\"");
        printSearch(qp, "city:Planavilla");
        printSearch(qp, "city:Bosc");
    }

    private void printSearch(QueryParser qp, String query) throws ParseException, IOException {
        Query q = qp.parse(query);

        System.out.println("query " + q);
        TopDocs hits = searcher.search(q, 4);
        System.out.println("results " + hits.totalHits);
        int i = 1;
        for (ScoreDoc dc : hits.scoreDocs) {
            Document doc = reader.document(dc.doc);
            System.out.println(i++ + ". " + dc + " \"" + doc.get("city") + "\" population: " + doc.get("population"));
        }
        System.out.println();
    }
}

I am now looking into sorting per population.

This prints out:

query city:"Bosc Planavilla"
results 1
1. doc=0 score=1.143841 "Bosc de Planavilla" population: 5000

query city:Planavilla
results 2
1. doc=1 score=1.287682 "Planavilla" population: 20000
2. doc=0 score=0.643841 "Bosc de Planavilla" population: 5000

query city:Bosc
results 3
1. doc=0 score=0.5 "Bosc de Planavilla" population: 5000
2. doc=2 score=0.5 "Bosc de la Planassa" population: 1000
3. doc=3 score=0.375 "Bosc de Plana en Blanca" population: 100000

Answer 2

Here is the code for sorting as well. Although I think it would make more sense to add a custom scoring taking into account the city size rather than bruteforcing the sort on the population. Also please note that this uses the FieldCache, which may not be the best solution regarding memory usage.

public class ShingleFilterTests {
    private Analyzer analyzer;
    private IndexSearcher searcher;
    private IndexReader reader;
    private QueryParser qp;
    private Sort sort;

    public static Analyzer createAnalyzer(final int shingles) {
        return new Analyzer() {
            @Override
            public TokenStream tokenStream(String fieldName, Reader reader) {
                TokenStream tokenizer = new WhitespaceTokenizer(reader);
                tokenizer = new StopFilter(false, tokenizer, ImmutableSet.of("de", "la", "en"));
                if (shingles > 0) {
                    tokenizer = new ShingleFilter(tokenizer, shingles);
                }
                return tokenizer;
            }
        };
    }

    public class PopulationComparatorSource extends FieldComparatorSource {
        @Override
        public FieldComparator newComparator(String fieldname, int numHits, int sortPos, boolean reversed) throws IOException {
            return new PopulationComparator(fieldname, numHits);
        }

        private class PopulationComparator extends FieldComparator {
            private final String fieldName;
            private Integer[] values;
            private int[] populations;
            private int bottom;

            public PopulationComparator(String fieldname, int numHits) {
                values = new Integer[numHits];
                this.fieldName = fieldname;
            }

            @Override
            public int compare(int slot1, int slot2) {
                if (values[slot1] > values[slot2]) return -1;
                if (values[slot1] < values[slot2]) return 1;
                return 0;
            }

            @Override
            public void setBottom(int slot) {
                bottom = values[slot];
            }

            @Override
            public int compareBottom(int doc) throws IOException {
                int value = populations[doc];
                if (bottom > value) return -1;
                if (bottom < value) return 1;
                return 0;
            }

            @Override
            public void copy(int slot, int doc) throws IOException {
                values[slot] = populations[doc];
            }

            @Override
            public void setNextReader(IndexReader reader, int docBase) throws IOException {
                /* XXX uses field cache */
                populations = FieldCache.DEFAULT.getInts(reader, "population");
            }

            @Override
            public Comparable value(int slot) {
                return values[slot];
            }
        }
    }

    @Before
    public void setUp() throws Exception {
        Directory dir = new RAMDirectory();
        analyzer = createAnalyzer(3);

        IndexWriter writer = new IndexWriter(dir, analyzer, IndexWriter.MaxFieldLength.UNLIMITED);
        ImmutableList<String> cities = ImmutableList.of("Bosc de Planavilla", "Planavilla", "Bosc de la Planassa",
                                                               "Bosc de Plana en Blanca");
        ImmutableList<Integer> populations = ImmutableList.of(5000, 20000, 1000, 100000);

        for (int id = 0; id < cities.size(); id++) {
            Document doc = new Document();
            doc.add(new Field("id", String.valueOf(id), Field.Store.YES, Field.Index.NOT_ANALYZED));
            doc.add(new Field("city", cities.get(id), Field.Store.YES, Field.Index.ANALYZED));
            doc.add(new Field("population", String.valueOf(populations.get(id)),
                                     Field.Store.YES, Field.Index.NOT_ANALYZED));
            writer.addDocument(doc);
        }
        writer.close();

        qp = new QueryParser(Version.LUCENE_30, "city", createAnalyzer(0));
        sort = new Sort(new SortField("population", new PopulationComparatorSource()));
        searcher = new IndexSearcher(dir);
        searcher.setDefaultFieldSortScoring(true, true);
        reader = searcher.getIndexReader();
    }

    @After
    public void tearDown() throws Exception {
        searcher.close();
    }

    @Test
    public void testShingleFilter() throws Exception {
        System.out.println("shingle filter");

        printSearch("city:\"Bosc de Planavilla\"");
        printSearch("city:Planavilla");
        printSearch("city:Bosc");
    }

    private void printSearch(String query) throws ParseException, IOException {
        Query q = qp.parse(query);
        System.out.println("query " + q);
        TopDocs hits = searcher.search(q, null, 4, sort);
        System.out.println("results " + hits.totalHits);
        int i = 1;
        for (ScoreDoc dc : hits.scoreDocs) {
            Document doc = reader.document(dc.doc);
            System.out.println(i++ + ". " + dc + " \"" + doc.get("city") + "\" population: " + doc.get("population"));
        }
        System.out.println();
    }
}

This gives the following results:

query city:"Bosc Planavilla"
results 1
1. doc=0 score=1.143841[5000] "Bosc de Planavilla" population: 5000

query city:Planavilla
results 2
1. doc=1 score=1.287682[20000] "Planavilla" population: 20000
2. doc=0 score=0.643841[5000] "Bosc de Planavilla" population: 5000

query city:Bosc
results 3
1. doc=3 score=0.375[100000] "Bosc de Plana en Blanca" population: 100000
2. doc=0 score=0.5[5000] "Bosc de Planavilla" population: 5000
3. doc=2 score=0.5[1000] "Bosc de la Planassa" population: 1000