Changeset 8f4fd07de7bf767b30c219684608535cb9cb6f19

Timestamp:

04/28/08 11:06:13 (8 months ago)

Author:

David Balmain <dbalmain@…>

Parents:

56424f8d1cfd0e927e5e8f9e0c4329531221a966

Children:

e37ef045516872af81e36339debad2296a2d7506

git-committer:

David Balmain <dbalmain@gmail.com> / 2008-04-28T11:06:13Z+1000

Message:

Fixed repeated term bug in sloppy PhraseQuery

Repeated terms were breaking sloppy PhraseQueries?. For example, if you had the
query "one two one"~2 it would match "one two". This has now been fixed.

Location:

c

Files:

• .rake/gcov.history (modified) (previous)
• include/internal.h (modified) (1 diff)
• include/search.h (modified) (1 diff)
• src/q_phrase.c (modified) (10 diffs)
• test/test.c (modified) (1 diff)
• test/test_search.c (modified) (11 diffs)

c/include/internal.h

@@ -738 +738 @@
 #define phq_append_multi_term                   frt_phq_append_multi_term
 #define phq_new                                 frt_phq_new
+#define phq_set_slop                            frt_phq_set_slop
 #define pl_add_occ                              frt_pl_add_occ
 #define pl_cmp                                  frt_pl_cmp

c/include/search.h

@@ -326 +326 @@
 extern void frt_phq_add_term_abs(FrtQuery *self, const char *term, int position);
 extern void frt_phq_append_multi_term(FrtQuery *self, const char *term);
+extern void frt_phq_set_slop(FrtQuery *self, int slop);
 
 /***************************************************************************

c/src/q_phrase.c

@@ -164 +164 @@
     bool    first_time : 1;
     bool    more : 1;
+    bool    check_repeats : 1;
 } PhraseScorer;
 
@@ -291 +292 @@
 }
 
-static Scorer *phsc_new(Weight *weight, TermDocEnum **term_pos_enum,
+static Scorer *phsc_new(Weight *weight,
+                        TermDocEnum **term_pos_enum,
                         PhrasePosition *positions, int pos_cnt,
-                        Similarity *similarity, uchar *norms)
+                        Similarity *similarity,
+                        uchar *norms,
+                        int slop)
 {
     int i;
     Scorer *self                = scorer_new(PhraseScorer, similarity);
+    HashSet *term_set           = NULL;
+
 
     PhSc(self)->weight          = weight;
@@ -304 +310 @@
     PhSc(self)->pp_first_idx    = 0;
     PhSc(self)->pp_cnt          = pos_cnt;
-    PhSc(self)->slop            = 0;
+    PhSc(self)->slop            = slop;
     PhSc(self)->first_time      = true;
     PhSc(self)->more            = true;
-
+    PhSc(self)->check_repeats   = false;
+    
+    if (slop) {
+        term_set = hs_new_str((free_ft)NULL);
+    }
     for (i = 0; i < pos_cnt; i++) {
+        /* check for repeats */
+        if (slop && !PhSc(self)->check_repeats) {
+            char **terms = positions[i].terms;
+            const int t_cnt = ary_size(terms);
+            int j;
+            for (j = 0; j < t_cnt; j++) {
+                if (hs_add(term_set, terms[j])) {
+                    PhSc(self)->check_repeats = true;
+                    goto repeat_check_done;
+                }
+            }
+        }
+repeat_check_done:
         PhSc(self)->phrase_pos[i] = pp_new(term_pos_enum[i], positions[i].pos);
+    }
+
+    if (slop) {
+        hs_destroy(term_set);
     }
 
@@ -372 +399 @@
                                        Similarity *similarity, uchar *norms)
 {
-    Scorer *self =
-        phsc_new(weight, term_pos_enum, positions, pp_cnt, similarity, norms);
+    Scorer *self = phsc_new(weight,
+                            term_pos_enum,
+                            positions,
+                            pp_cnt,
+                            similarity,
+                            norms,
+                            0);
 
     PhSc(self)->phrase_freq = &ephsc_phrase_freq;
@@ -382 +414 @@
  * SloppyPhraseScorer
  ***************************************************************************/
+
+static bool sphsc_check_repeats(PhPos *pp,
+                                PhPos **positions,
+                                const int p_cnt)
+{
+    int j;
+    for (j = 0; j < p_cnt; j++) {
+        PhPos *ppj = positions[j];
+        /* If offsets are equal, either we are at the current PhPos +pp+ or
+         * +pp+ and +ppj+ are supposed to match in the same position in which
+         * case we don't need to check. */
+        if (ppj->offset == pp->offset) {
+            continue;
+        }
+        /* the two phrase positions are matching on the same term
+         * which we want to avoid */
+        if ((ppj->position + ppj->offset) == (pp->position + pp->offset)) {
+            if (!pp_next_position(pp)) {
+                /* We have no matches for this document */
+                return false;
+            }
+            /* we changed the position so we need to start check again */
+            j = -1;
+        }
+    }
+    return true;
+}
 
 static float sphsc_phrase_freq(Scorer *self)
@@ -392 +451 @@
     int last_pos = 0, pos, next_pos, start, match_length, i;
     bool done = false;
+    bool check_repeats = phsc->check_repeats;
     float freq = 0.0;
 
     for (i = 0; i < pp_cnt; i++) {
         pp = phsc->phrase_pos[i];
-        pp_first_position(pp);
+        /* we should always have at least one position or this functions
+         * shouldn't have been called. */
+        assert(pp_first_position(pp));
+        if (check_repeats && i > 0) {
+            if (!sphsc_check_repeats(pp, phsc->phrase_pos, i - 1)) {
+                goto return_freq;
+            }
+        }
         if (pp->position > last_pos) {
             last_pos = pp->position;
@@ -409 +476 @@
         while (pos <= next_pos) {
             start = pos;        /* advance pp to min window */
-            if (!pp_next_position(pp)) {
-                done = true;    /* ran out of a positions for a term - done */
+            if (!pp_next_position(pp)
+                || (check_repeats
+                    && !sphsc_check_repeats(pp, phsc->phrase_pos, pp_cnt))) {
+                done = true;
                 break;
             }
@@ -427 +496 @@
         pq_push(pq, pp);        /* restore pq */
     } while (!done);
+
+return_freq:
 
     pq_destroy(pq);
@@ -438 +509 @@
                                         int slop, uchar *norms)
 {
-    Scorer *self =
-        phsc_new(weight, term_pos_enum, positions, pp_cnt, similarity, norms);
-
-    PhSc(self)->slop        = slop;
+    Scorer *self = phsc_new(weight,
+                            term_pos_enum,
+                            positions,
+                            pp_cnt,
+                            similarity,
+                            norms,
+                            slop);
+
     PhSc(self)->phrase_freq = &sphsc_phrase_freq;
     return self;
@@ -1121 +1196 @@
     }
 }
+
+void frt_phq_set_slop(FrtQuery *self, int slop)
+{
+    PhQ(self)->slop = slop;
+}

c/test/test.c

@@ -456 +456 @@
         return true;
     }
+    fprintf(stderr, "diff = %g\n", diff);
 
     tc->failed = true;

c/test/test_search.c

@@ -164 +164 @@
     {"20051001", "word1 word2 the quick brown fox the quick brown fox",
         "cat1/sub1",            "0.954"},
-    {"20051002", "word1 word3",
+    {"20051002", "word1 word3 one two one",
         "cat1/sub1/subsub1",    "908.123434"},
-    {"20051003", "word1 word3",
+    {"20051003", "word1 word3 one two",
         "cat1/sub2",            "3999"},
     {"20051004", "word1 word2",
         "cat1/sub2/subsub2",    "+.3413"},
-    {"20051005", "word1",
+    {"20051005", "word1 one two x x x x x one two",
         "cat2/sub1",            "-1.1298"},
     {"20051006", "word1 word3",
@@ -265 +265 @@
     TopDocs *top_docs
         = searcher_search(searcher, query, 0, total_hits + 1, NULL, NULL, NULL);
-    if (!Aiequal(total_hits, top_docs->total_hits)) {
+    if (!tc->failed && !Aiequal(total_hits, top_docs->total_hits)) {
         int i;
         Tmsg_nf("\texpected;\n\t    ");
@@ -297 +297 @@
         /* only check the explanation if we got the correct docs. Obviously we
          * might want to remove this to visually check the explanations */
-        if (total_hits == top_docs->total_hits) {
+        if (!tc->failed && total_hits == top_docs->total_hits) {
             Explanation *e = searcher_explain(searcher, query, hit->doc);
             if (! Afequal(hit->score, e->value)) {
@@ -314 +314 @@
     }
     td_destroy(top_docs);
+
+    /* test search_unscored method */
     qsort(num_array, total_hits, sizeof(int), &icmp_risky);
     count = searcher_search_unscored(searcher, query,
@@ -525 +527 @@
     check_hits(tc, searcher, phq, "1", 1);
 
-    ((PhraseQuery *)phq)->slop = 4;
+    phq_set_slop(phq, 4);
     check_hits(tc, searcher, phq, "1, 16, 17", 17);
     q_deref(phq);
@@ -536 +538 @@
     check_hits(tc, searcher, phq, "1, 11, 14", 14);
 
-    ((PhraseQuery *)phq)->slop = 1;
+    phq_set_slop(phq, 1);
     check_hits(tc, searcher, phq, "1, 11, 14, 16", 14);
 
-    ((PhraseQuery *)phq)->slop = 4;
+    phq_set_slop(phq, 4);
     check_hits(tc, searcher, phq, "1, 11, 14, 16, 17", 14);
     phq_add_term(phq, "red", -1);
@@ -568 +570 @@
     q_deref(phq);
 
+    /* test repeating terms check */
+    phq = phq_new(field);
+    phq_add_term(phq, "one", 0);
+    phq_add_term(phq, "two", 1);
+    phq_add_term(phq, "one", 1);
+    check_hits(tc, searcher, phq, "2", 2);
+    phq_set_slop(phq, 2);
+    check_hits(tc, searcher, phq, "2", 2);
+    q_deref(phq);
+
     phq = phq_new(I("not a field"));
     phq_add_term(phq, "the", 0);
@@ -603 +615 @@
     Assert(q_eq(q1, q2), "Queries should be equal");
 
-    ((PhraseQuery *)q2)->slop = 5;
+    phq_set_slop(q2, 5);
     Assert(q_hash(q1) != q_hash(q2), "Queries should not be equal");
     Assert(!q_eq(q1, q2), "Queries should not be equal");
@@ -657 +669 @@
     check_hits(tc, searcher, phq, "1, 8, 11, 14", -1);
 
-    ((PhraseQuery *)phq)->slop = 4;
+    phq_set_slop(phq, 4);
     check_hits(tc, searcher, phq, "1, 8, 11, 14, 16, 17", -1);
     check_to_s(tc, phq, NULL, "field:\"quick|fast brown|red|hairy fox\"~4");
@@ -674 +686 @@
     q_deref(phq);
 
+    /* test repeating terms check */
+    phq = phq_new(field);
+    phq_add_term(phq, "WORD3", 0);
+    phq_append_multi_term(phq, "x");
+    phq_add_term(phq, "one", 0);
+    phq_add_term(phq, "two", 1);
+    phq_add_term(phq, "one", 1);
+    check_hits(tc, searcher, phq, "2", -1);
+    check_to_s(tc, phq, NULL, "field:\"WORD3|x&one two one\"");
+
+    phq_set_slop(phq, 4);
+    check_hits(tc, searcher, phq, "2", -1);
+    check_to_s(tc, phq, NULL, "field:\"WORD3|x&one two one\"~4");
+    q_deref(phq);
+
+    /* test phrase query on non-existing field doesn't break anything */
     phq = phq_new(I("not a field"));
     phq_add_term(phq, "the", 0);
@@ -717 +745 @@
     Assert(q_eq(q1, q2), "Queries should be equal");
 
-    ((PhraseQuery *)q2)->slop = 5;
+    phq_set_slop(q2, 5);
     Assert(q_hash(q1) != q_hash(q2), "Queries should not be equal");
     Assert(!q_eq(q1, q2), "Queries should not be equal");