LCOV - code coverage report
Current view: top level - diversify - diversify.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 4ba52dacf4fb Lines: 102 114 89.5 %
Date: 2019-05-20 14:58:19 Functions: 10 10 100.0 %
Branches: 99 182 54.4 %

           Branch data     Line data    Source code
       1                 :            : /** @file diversify.cc
       2                 :            :  *  @brief Diversification API
       3                 :            :  */
       4                 :            : /* Copyright (C) 2018 Uppinder Chugh
       5                 :            :  *
       6                 :            :  * This program is free software; you can redistribute it and/or
       7                 :            :  * modify it under the terms of the GNU General Public License as
       8                 :            :  * published by the Free Software Foundation; either version 2 of the
       9                 :            :  * License, or (at your option) any later version.
      10                 :            :  *
      11                 :            :  * This program is distributed in the hope that it will be useful,
      12                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            :  * GNU General Public License for more details.
      15                 :            :  *
      16                 :            :  * You should have received a copy of the GNU General Public License
      17                 :            :  * along with this program; if not, write to the Free Software
      18                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
      19                 :            :  * USA
      20                 :            :  */
      21                 :            : 
      22                 :            : #include <config.h>
      23                 :            : 
      24                 :            : #include "xapian/diversify.h"
      25                 :            : #include "xapian/error.h"
      26                 :            : 
      27                 :            : #include "debuglog.h"
      28                 :            : #include "diversify/diversifyinternal.h"
      29                 :            : 
      30                 :            : #include <algorithm>
      31                 :            : #include <cmath>
      32                 :            : #include <limits>
      33                 :            : #include <vector>
      34                 :            : 
      35                 :            : using namespace Xapian;
      36                 :            : using namespace std;
      37                 :            : 
      38                 :            : Diversify::Diversify(const Diversify&) = default;
      39                 :            : 
      40                 :            : Diversify&
      41                 :            : Diversify::operator=(const Diversify&) = default;
      42                 :            : 
      43                 :            : Diversify::Diversify(Diversify&&) = default;
      44                 :            : 
      45                 :            : Diversify&
      46                 :            : Diversify::operator=(Diversify&&) = default;
      47                 :            : 
      48                 :          4 : Diversify::Diversify(Xapian::doccount k_,
      49                 :            :                      Xapian::doccount r_,
      50                 :            :                      double lambda_,
      51                 :            :                      double b_,
      52                 :            :                      double sigma_sqr_)
      53         [ +  - ]:          4 :     : internal(new Xapian::Diversify::Internal(k_, r_, lambda_, b_, sigma_sqr_))
      54                 :            : {
      55                 :            :     LOGCALL_CTOR(API, "Diversify", k_ | r_ | lambda_ | b_ | sigma_sqr_);
      56         [ -  + ]:          4 :     if (r_ == 0)
      57 [ #  # ][ #  # ]:          0 :         throw InvalidArgumentError("Value of r should be greater than zero.");
                 [ #  # ]
      58                 :          4 : }
      59                 :            : 
      60                 :         12 : Diversify::~Diversify()
      61                 :            : {
      62                 :            :     LOGCALL_DTOR(API, "Diversify");
      63                 :          6 : }
      64                 :            : 
      65                 :            : string
      66                 :          5 : Diversify::get_description() const
      67                 :            : {
      68         [ +  - ]:          5 :     return "Diversify()";
      69                 :            : }
      70                 :            : 
      71                 :            : DocumentSet
      72                 :          3 : Diversify::get_dmset(const MSet& mset)
      73                 :            : {
      74                 :            :     LOGCALL(API, MSet, "Diversify::get_dmset", mset);
      75                 :          3 :     return internal->get_dmset(mset);
      76                 :            : }
      77                 :            : 
      78                 :            : void
      79                 :          3 : Diversify::Internal::initialise_points(const MSet& source)
      80                 :            : {
      81                 :          3 :     unsigned int count = 0;
      82         [ +  - ]:          3 :     TermListGroup tlg(source);
      83 [ +  - ][ +  - ]:         24 :     for (MSetIterator it = source.begin(); it != source.end(); ++it) {
                 [ +  + ]
      84 [ +  - ][ +  - ]:         21 :         points.emplace(*it, Xapian::Point(tlg, it.get_document()));
         [ +  - ][ +  - ]
      85 [ +  - ][ +  - ]:         21 :         scores[*it] = it.get_weight();
                 [ +  - ]
      86                 :            :         // Initial top-k diversified documents
      87         [ +  + ]:         21 :         if (count < k) {
      88 [ +  - ][ +  - ]:         12 :             main_dmset.push_back(*it);
      89                 :         12 :             ++count;
      90                 :            :         }
      91                 :          3 :     }
      92                 :          3 : }
      93                 :            : 
      94                 :            : pair<Xapian::docid, unsigned int>
      95                 :        916 : Diversify::Internal::get_key(Xapian::docid doc_id, unsigned int centroid_id)
      96                 :            : {
      97                 :        916 :     return make_pair(doc_id, centroid_id);
      98                 :            : }
      99                 :            : 
     100                 :            : void
     101                 :          3 : Diversify::Internal::compute_similarities(const Xapian::ClusterSet& cset)
     102                 :            : {
     103                 :          3 :     Xapian::CosineDistance d;
     104 [ +  - ][ +  + ]:         24 :     for (auto p : points) {
     105                 :         21 :         Xapian::docid point_id = p.first;
     106         [ +  - ]:         42 :         Xapian::Point point = p.second;
     107 [ +  - ][ +  + ]:        105 :         for (unsigned int c = 0; c < cset.size(); ++c) {
     108 [ +  - ][ +  - ]:         84 :             double dist = d.similarity(point, cset[c].get_centroid());
                 [ +  - ]
     109                 :         84 :             auto key = get_key(point_id, c);
     110         [ +  - ]:         84 :             pairwise_sim[key] = dist;
     111                 :            :         }
     112                 :         24 :     }
     113                 :          3 : }
     114                 :            : 
     115                 :            : vector<Xapian::docid>
     116                 :          3 : Diversify::Internal::compute_diff_dmset(const vector<Xapian::docid>& dmset)
     117                 :            : {
     118                 :          3 :     vector<Xapian::docid> diff_dmset;
     119 [ +  - ][ +  + ]:         24 :     for (auto point : points) {
     120                 :         21 :         Xapian::docid point_id = point.first;
     121                 :         21 :         bool found_point = false;
     122         [ +  + ]:         75 :         for (auto doc_id : dmset) {
     123         [ +  + ]:         66 :             if (point_id == doc_id) {
     124                 :         12 :                 found_point = true;
     125                 :         12 :                 break;
     126                 :            :             }
     127                 :            :         }
     128                 :            : 
     129         [ +  + ]:         21 :         if (!found_point) {
     130         [ +  - ]:          9 :             diff_dmset.push_back(point_id);
     131                 :            :         }
     132                 :         21 :     }
     133                 :            : 
     134                 :          3 :     return diff_dmset;
     135                 :            : }
     136                 :            : 
     137                 :            : double
     138                 :         52 : Diversify::Internal::evaluate_dmset(const vector<Xapian::docid>& dmset,
     139                 :            :                                     const Xapian::ClusterSet& cset)
     140                 :            : {
     141                 :         52 :     double score_1 = 0, score_2 = 0;
     142                 :            : 
     143         [ +  + ]:        260 :     for (auto doc_id : dmset)
     144         [ +  - ]:        208 :         score_1 += scores[doc_id];
     145                 :            : 
     146         [ +  + ]:        260 :     for (unsigned int c = 0; c < cset.size(); ++c) {
     147                 :        208 :         double min_dist = numeric_limits<double>::max();
     148                 :        208 :         unsigned int pos = 1;
     149         [ +  + ]:       1040 :         for (auto doc_id : dmset) {
     150                 :        832 :             auto key = get_key(doc_id, c);
     151         [ +  - ]:        832 :             double sim = pairwise_sim[key];
     152                 :        832 :             double weight = 2 * b * sigma_sqr / log(1 + pos) * (1 - sim);
     153                 :        832 :             min_dist = min(min_dist, weight);
     154                 :        832 :             ++pos;
     155                 :            :         }
     156                 :        208 :         score_2 += min_dist;
     157                 :            :     }
     158                 :            : 
     159                 :         52 :     return -lambda * score_1 + (1 - lambda) * score_2;
     160                 :            : }
     161                 :            : 
     162                 :            : DocumentSet
     163                 :          3 : Diversify::Internal::get_dmset(const MSet& mset)
     164                 :            : {
     165                 :            :     // Return original mset if no need to diversify
     166 [ +  - ][ +  - ]:          3 :     if (k == 0 || mset.size() <= 2) {
         [ -  + ][ -  + ]
     167         [ #  # ]:          0 :         DocumentSet dmset;
     168 [ #  # ][ #  # ]:          0 :         for (MSetIterator it = mset.begin(); it != mset.end(); ++it)
                 [ #  # ]
     169 [ #  # ][ #  # ]:          0 :             dmset.add_document(it.get_document());
     170         [ #  # ]:          0 :         return dmset;
     171                 :            :     }
     172                 :            : 
     173                 :          3 :     unsigned int k_ = k;
     174 [ +  - ][ -  + ]:          3 :     if (k_ > mset.size())
     175         [ #  # ]:          0 :         k_ = mset.size();
     176                 :            : 
     177         [ +  - ]:          3 :     initialise_points(mset);
     178                 :            : 
     179                 :            :     // Cluster the given mset into k clusters
     180         [ +  - ]:          3 :     Xapian::LCDClusterer lc(k_);
     181         [ +  - ]:          6 :     Xapian::ClusterSet cset = lc.cluster(mset);
     182         [ +  - ]:          3 :     compute_similarities(cset);
     183                 :            : 
     184                 :            :     // topC contains union of top-r relevant documents of each cluster
     185                 :          6 :     vector<Xapian::docid> topc;
     186                 :            : 
     187                 :            :     // Build topC
     188 [ +  - ][ +  + ]:         15 :     for (unsigned int c = 0; c < cset.size(); ++c) {
     189 [ +  - ][ +  - ]:         12 :         auto documents = cset[c].get_documents();
     190 [ +  + ][ +  - ]:         33 :         for (unsigned int d = 0; d < r && d < documents.size(); ++d) {
         [ +  + ][ +  + ]
     191 [ +  - ][ +  - ]:         21 :             auto doc_id = documents[d].get_docid();
     192         [ +  - ]:         21 :             topc.push_back(doc_id);
     193                 :            :         }
     194                 :         12 :     }
     195                 :            : 
     196         [ +  - ]:          6 :     vector<Xapian::docid> curr_dmset = main_dmset;
     197                 :            : 
     198                 :            :     while (true) {
     199                 :          3 :         bool found_better_dmset = false;
     200         [ +  + ]:         15 :         for (unsigned int i = 0; i < main_dmset.size(); ++i) {
     201                 :         12 :             auto curr_doc = main_dmset[i];
     202         [ +  - ]:         12 :             double best_score = evaluate_dmset(curr_dmset, cset);
     203                 :         12 :             bool found_better_doc = false;
     204                 :            : 
     205         [ +  + ]:         96 :             for (unsigned int j = 0; j < topc.size(); ++j) {
     206                 :            :                 // Continue if candidate document from topC already
     207                 :            :                 // exists in curr_dmset
     208                 :            :                 auto candidate_doc = find(curr_dmset.begin(), curr_dmset.end(),
     209         [ +  - ]:         84 :                                           topc[j]);
     210         [ +  + ]:         84 :                 if (candidate_doc != curr_dmset.end()) {
     211                 :         44 :                     continue;
     212                 :            :                 }
     213                 :            : 
     214                 :         40 :                 auto temp_doc = curr_dmset[i];
     215                 :         40 :                 curr_dmset[i] = topc[j];
     216         [ +  - ]:         40 :                 double score = evaluate_dmset(curr_dmset, cset);
     217                 :            : 
     218         [ -  + ]:         40 :                 if (score < best_score) {
     219                 :          0 :                     curr_doc = curr_dmset[i];
     220                 :          0 :                     best_score = score;
     221                 :          0 :                     found_better_doc = true;
     222                 :            :                 }
     223                 :            : 
     224                 :         40 :                 curr_dmset[i] = temp_doc;
     225                 :            :             }
     226         [ -  + ]:         12 :             if (found_better_doc) {
     227                 :          0 :                 curr_dmset[i] = curr_doc;
     228                 :          0 :                 found_better_dmset = true;
     229                 :            :             }
     230                 :            :         }
     231                 :            : 
     232                 :            :         // Terminate algorithm when there's no change in current
     233                 :            :         // document matchset
     234         [ +  - ]:          3 :         if (!found_better_dmset)
     235                 :          3 :             break;
     236                 :            : 
     237         [ #  # ]:          0 :         main_dmset = curr_dmset;
     238                 :            :     }
     239                 :            : 
     240                 :            :     // Merge main_dmset and diff_dmset into final dmset
     241         [ +  - ]:          6 :     DocumentSet dmset;
     242         [ +  + ]:         15 :     for (auto doc_id : main_dmset)
     243 [ +  - ][ +  - ]:         12 :         dmset.add_document(points.at(doc_id).get_document());
                 [ +  - ]
     244                 :            : 
     245         [ +  - ]:          6 :     vector<Xapian::docid> diff_dmset = compute_diff_dmset(main_dmset);
     246         [ +  + ]:         12 :     for (auto doc_id : diff_dmset)
     247 [ +  - ][ +  - ]:          9 :         dmset.add_document(points.at(doc_id).get_document());
                 [ +  - ]
     248                 :            : 
     249         [ +  - ]:          6 :     return dmset;
     250                 :            : }

Generated by: LCOV version 1.11