xapian-core/cluster/cluster.cc

   1 /** @file
   2  *  @brief Cluster API
   3  */
   4 /* Copyright (C) 2010 Richard Boulton
   5  * Copyright (C) 2016 Richhiey Thomas
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License as
   9  * published by the Free Software Foundation; either version 2 of the
  10  * License, or (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
  20  * USA
  21  */
  22
  23 #include <config.h>
  24
  25 #include "xapian/cluster.h"
  26
  27 #include "cluster/clusterinternal.h"
  28 #include "xapian/error.h"
  29 #include "api/termlist.h"
  30 #include "debuglog.h"
  31 #include "omassert.h"
  32
  33 #include <cmath>
  34 #include <unordered_map>
  35 #include <vector>
  36
  37 using namespace Xapian;
  38 using namespace std;
  39
  40 FreqSource::~FreqSource()
  41 {
  42     LOGCALL_DTOR(API, "FreqSource");
  43 }
  44
  45 Similarity::~Similarity()
  46 {
  47     LOGCALL_DTOR(API, "Similarity");
  48 }
  49
  50 Clusterer::~Clusterer()
  51 {
  52     LOGCALL_DTOR(API, "Clusterer");
  53 }
  54
  55 TermListGroup::TermListGroup(const MSet& docs, const Stopper* stopper)
  56 {
  57     LOGCALL_CTOR(API, "TermListGroup", docs | stopper);
  58     for (MSetIterator it = docs.begin(); it != docs.end(); ++it)
  59         add_document(it.get_document(), stopper);
  60     num_of_documents = docs.size();
  61 }
  62
  63 void
  64 TermListGroup::add_document(const Document& document, const Stopper* stopper)
  65 {
  66     LOGCALL_VOID(API, "TermListGroup::add_document", document | stopper);
  67
  68     TermIterator titer(document.termlist_begin());
  69
  70     for (; titer != document.termlist_end(); ++titer) {
  71         const string& term = *titer;
  72
  73         // Remove stopwords by using the Xapian::Stopper object
  74         if (stopper && (*stopper)(term))
  75             continue;
  76
  77         // Remove unstemmed terms since document vector should
  78         // contain only stemmed terms
  79         if (term[0] != 'Z')
  80             continue;
  81
  82         unordered_map<string, doccount>::iterator i;
  83         i = termfreq.find(term);
  84         if (i == termfreq.end())
  85             termfreq[term] = 1;
  86         else
  87             ++i->second;
  88     }
  89 }
  90
  91 doccount
  92 TermListGroup::get_doccount() const
  93 {
  94     LOGCALL(API, doccount, "TermListGroup::get_doccount", NO_ARGS);
  95     return num_of_documents;
  96 }
  97
  98 doccount
  99 TermListGroup::get_termfreq(const string& tname) const
 100 {
 101     LOGCALL(API, doccount, "TermListGroup::get_termfreq", tname);
 102     unordered_map<string, doccount>::const_iterator it = termfreq.find(tname);
 103     if (it != termfreq.end())
 104         return it->second;
 105     else
 106         return 0;
 107 }
 108
 109 DocumentSet::DocumentSet(const DocumentSet&) = default;
 110
 111 DocumentSet&
 112 DocumentSet::operator=(const DocumentSet&) = default;
 113
 114 DocumentSet::DocumentSet(DocumentSet&&) = default;
 115
 116 DocumentSet&
 117 DocumentSet::operator=(DocumentSet&&) = default;
 118
 119 DocumentSet::DocumentSet()
 120     : internal(new Xapian::DocumentSet::Internal)
 121 {
 122 }
 123
 124 doccount
 125 DocumentSet::size() const
 126 {
 127     LOGCALL(API, doccount, "DocumentSet::size", NO_ARGS);
 128     return internal->size();
 129 }
 130
 131 doccount
 132 DocumentSet::Internal::size() const
 133 {
 134     return documents.size();
 135 }
 136
 137 void
 138 DocumentSet::add_document(const Document& document)
 139 {
 140     LOGCALL_VOID(API, "DocumentSet::add_document", document);
 141     internal->add_document(document);
 142 }
 143
 144 void
 145 DocumentSet::Internal::add_document(const Document& document)
 146 {
 147     documents.push_back(document);
 148 }
 149
 150 Document&
 151 DocumentSet::operator[](doccount i)
 152 {
 153     return internal->get_document(i);
 154 }
 155
 156 Document&
 157 DocumentSet::Internal::get_document(doccount i)
 158 {
 159     return documents[i];
 160 }
 161
 162 const Document&
 163 DocumentSet::operator[](doccount i) const
 164 {
 165     return internal->get_document(i);
 166 }
 167
 168 const Document&
 169 DocumentSet::Internal::get_document(doccount i) const
 170 {
 171     return documents[i];
 172 }
 173
 174 DocumentSet::~DocumentSet()
 175 {
 176     LOGCALL_DTOR(API, "DocumentSet");
 177 }
 178
 179 class PointTermIterator : public TermIterator::Internal {
 180     unordered_map<string, double>::const_iterator i;
 181     unordered_map<string, double>::const_iterator end;
 182     termcount size;
 183     bool started;
 184   public:
 185     PointTermIterator(const unordered_map<string, double>& termlist)
 186         : i(termlist.begin()), end(termlist.end()),
 187           size(termlist.size()), started(false)
 188     {}
 189     termcount get_approx_size() const { return size; }
 190     termcount get_wdf() const {
 191         throw UnimplementedError("PointIterator doesn't support get_wdf()");
 192     }
 193     string get_termname() const { return i->first; }
 194     doccount get_termfreq() const {
 195         throw UnimplementedError("PointIterator doesn't support "
 196                                  "get_termfreq()");
 197     }
 198     Internal* next();
 199     termcount positionlist_count() const {
 200         throw UnimplementedError("PointTermIterator doesn't support "
 201                                  "positionlist_count()");
 202     }
 203     bool at_end() const;
 204     PositionList* positionlist_begin() const {
 205         throw UnimplementedError("PointTermIterator doesn't support "
 206                                  "positionlist_begin()");
 207     }
 208     Internal* skip_to(const string&) {
 209         throw UnimplementedError("PointTermIterator doesn't support skip_to()");
 210     }
 211 };
 212
 213 TermIterator::Internal*
 214 PointTermIterator::next()
 215 {
 216     if (!started) {
 217         started = true;
 218         return NULL;
 219     }
 220     Assert(i != end);
 221     ++i;
 222     return NULL;
 223 }
 224
 225 bool
 226 PointTermIterator::at_end() const
 227 {
 228     if (!started) return false;
 229     return i == end;
 230 }
 231
 232 TermIterator
 233 PointType::termlist_begin() const
 234 {
 235     LOGCALL(API, TermIterator, "PointType::termlist_begin", NO_ARGS);
 236     return TermIterator(new PointTermIterator(weights));
 237 }
 238
 239 bool
 240 PointType::contains(const string& term) const
 241 {
 242     LOGCALL(API, bool, "PointType::contains", term);
 243     return weights.find(term) != weights.end();
 244 }
 245
 246 double
 247 PointType::get_weight(const string& term) const
 248 {
 249     LOGCALL(API, double, "PointType::get_weight", term);
 250     unordered_map<string, double>::const_iterator it = weights.find(term);
 251     return (it == weights.end()) ? 0.0 : it->second;
 252 }
 253
 254 double
 255 PointType::get_magnitude() const {
 256     LOGCALL(API, double, "PointType::get_magnitude", NO_ARGS);
 257     return magnitude;
 258 }
 259
 260 void
 261 PointType::add_weight(const string& term, double weight)
 262 {
 263     LOGCALL_VOID(API, "PointType::add_weight", term | weight);
 264     unordered_map<string, double>::iterator it;
 265     it = weights.find(term);
 266     if (it != weights.end())
 267         it->second += weight;
 268     else
 269         weights[term] = weight;
 270 }
 271
 272 void
 273 PointType::set_weight(const string& term, double weight)
 274 {
 275     LOGCALL_VOID(API, "PointType::set_weight", term | weight);
 276     weights[term] = weight;
 277 }
 278
 279 termcount
 280 PointType::termlist_size() const
 281 {
 282     LOGCALL(API, termcount, "PointType::termlist_size", NO_ARGS);
 283     return weights.size();
 284 }
 285
 286 Document
 287 Point::get_document() const
 288 {
 289     LOGCALL(API, Document, "Point::get_document", NO_ARGS);
 290     return document;
 291 }
 292
 293 Point::Point(const FreqSource& freqsource, const Document& document_)
 294 {
 295     LOGCALL_CTOR(API, "Point::initialize", freqsource | document_);
 296     doccount size = freqsource.get_doccount();
 297     document = document_;
 298     for (TermIterator it = document.termlist_begin();
 299          it != document.termlist_end();
 300          ++it) {
 301         doccount wdf = it.get_wdf();
 302         string term = *it;
 303         double termfreq = freqsource.get_termfreq(term);
 304
 305         // If the term exists in only one document, or if it exists in
 306         // every document within the MSet, or if it is a filter term, then
 307         // these terms are not used for document vector calculations
 308         if (wdf < 1 || termfreq <= 1 || size == termfreq)
 309             continue;
 310
 311         double tf = 1 + log(double(wdf));
 312         double idf = log(size / termfreq);
 313         double wt = tf * idf;
 314
 315         weights[term] = wt;
 316         magnitude += wt * wt;
 317     }
 318 }
 319
 320 Centroid::Centroid(const Point& point)
 321 {
 322     LOGCALL_CTOR(API, "Centroid", point);
 323     for (TermIterator it = point.termlist_begin();
 324          it != point.termlist_end();
 325          ++it) {
 326         weights[*it] = point.get_weight(*it);
 327     }
 328     magnitude = point.get_magnitude();
 329 }
 330
 331 void
 332 Centroid::divide(double cluster_size)
 333 {
 334     LOGCALL_VOID(API, "Centroid::divide", cluster_size);
 335     magnitude = 0;
 336     unordered_map<string, double>::iterator it;
 337     for (it = weights.begin(); it != weights.end(); ++it) {
 338         double new_weight = it->second / cluster_size;
 339         it->second = new_weight;
 340         magnitude += new_weight * new_weight;
 341     }
 342 }
 343
 344 void
 345 Centroid::clear()
 346 {
 347     LOGCALL_VOID(API, "Centroid::clear", NO_ARGS);
 348     weights.clear();
 349 }
 350
 351 Cluster&
 352 Cluster::operator=(const Cluster&) = default;
 353
 354 Cluster::Cluster(const Cluster&) = default;
 355
 356 Cluster::Cluster(Cluster&&) = default;
 357
 358 Cluster&
 359 Cluster::operator=(Cluster&&) = default;
 360
 361 Cluster::Cluster() : internal(new Xapian::Cluster::Internal)
 362 {
 363     LOGCALL_CTOR(API, "Cluster", NO_ARGS);
 364 }
 365
 366 Cluster::Cluster(const Centroid& centroid)
 367     : internal(new Xapian::Cluster::Internal(centroid))
 368 {
 369     LOGCALL_CTOR(API, "Cluster", centroid);
 370 }
 371
 372 Cluster::~Cluster()
 373 {
 374     LOGCALL_DTOR(API, "Cluster");
 375 }
 376
 377 Centroid::Centroid()
 378 {
 379     LOGCALL_CTOR(API, "Centroid", NO_ARGS);
 380 }
 381
 382 DocumentSet
 383 Cluster::get_documents() const
 384 {
 385     LOGCALL(API, DocumentSet, "Cluster::get_documents", NO_ARGS);
 386     return internal->get_documents();
 387 }
 388
 389 DocumentSet
 390 Cluster::Internal::get_documents() const
 391 {
 392     DocumentSet docs;
 393     for (auto&& point : cluster_docs)
 394         docs.add_document(point.get_document());
 395     return docs;
 396 }
 397
 398 Point&
 399 Cluster::operator[](Xapian::doccount i)
 400 {
 401     return internal->get_point(i);
 402 }
 403
 404 Point&
 405 Cluster::Internal::get_point(Xapian::doccount i)
 406 {
 407     return cluster_docs[i];
 408 }
 409
 410 const Point&
 411 Cluster::operator[](Xapian::doccount i) const
 412 {
 413     return internal->get_point(i);
 414 }
 415
 416 const Point&
 417 Cluster::Internal::get_point(Xapian::doccount i) const
 418 {
 419     return cluster_docs[i];
 420 }
 421
 422 ClusterSet&
 423 ClusterSet::operator=(const ClusterSet&) = default;
 424
 425 ClusterSet::ClusterSet(const ClusterSet&) = default;
 426
 427 ClusterSet&
 428 ClusterSet::operator=(ClusterSet&&) = default;
 429
 430 ClusterSet::ClusterSet(ClusterSet&&) = default;
 431
 432 ClusterSet::ClusterSet() : internal(new Xapian::ClusterSet::Internal)
 433 {
 434 }
 435
 436 ClusterSet::~ClusterSet()
 437 {
 438 }
 439
 440 doccount
 441 ClusterSet::Internal::size() const
 442 {
 443     return clusters.size();
 444 }
 445
 446 doccount
 447 ClusterSet::size() const
 448 {
 449     LOGCALL(API, doccount, "ClusterSet::size", NO_ARGS);
 450     return internal->size();
 451 }
 452
 453 void
 454 ClusterSet::Internal::add_cluster(const Cluster& cluster)
 455 {
 456     clusters.push_back(cluster);
 457 }
 458
 459 void
 460 ClusterSet::add_cluster(const Cluster& cluster)
 461 {
 462     LOGCALL_VOID(API, "ClusterSet::add_cluster", cluster);
 463     internal->add_cluster(cluster);
 464 }
 465
 466 Cluster&
 467 ClusterSet::Internal::get_cluster(doccount i)
 468 {
 469     return clusters[i];
 470 }
 471
 472 Cluster&
 473 ClusterSet::operator[](doccount i)
 474 {
 475     return internal->get_cluster(i);
 476 }
 477
 478 const Cluster&
 479 ClusterSet::Internal::get_cluster(doccount i) const
 480 {
 481     return clusters[i];
 482 }
 483
 484 const Cluster&
 485 ClusterSet::operator[](doccount i) const
 486 {
 487     return internal->get_cluster(i);
 488 }
 489
 490 void
 491 ClusterSet::Internal::add_to_cluster(const Point& point, unsigned int index)
 492 {
 493     clusters[index].add_point(point);
 494 }
 495
 496 void
 497 ClusterSet::add_to_cluster(const Point& point, unsigned int index)
 498 {
 499     LOGCALL_VOID(API, "ClusterSet::add_to_cluster", point | index);
 500     internal->add_to_cluster(point, index);
 501 }
 502
 503 void
 504 ClusterSet::Internal::recalculate_centroids()
 505 {
 506     for (auto&& cluster : clusters)
 507         cluster.recalculate();
 508 }
 509
 510 void
 511 ClusterSet::recalculate_centroids()
 512 {
 513     LOGCALL_VOID(API, "ClusterSet::recalculate_centroids", NO_ARGS);
 514     internal->recalculate_centroids();
 515 }
 516
 517 void
 518 ClusterSet::clear_clusters()
 519 {
 520     LOGCALL_VOID(API, "ClusterSet::clear_clusters", NO_ARGS);
 521     internal->clear_clusters();
 522 }
 523
 524 void
 525 ClusterSet::Internal::clear_clusters()
 526 {
 527     for (auto&& cluster : clusters)
 528         cluster.clear();
 529 }
 530
 531 doccount
 532 Cluster::size() const
 533 {
 534     LOGCALL(API, doccount, "Cluster::size", NO_ARGS);
 535     return internal->size();
 536 }
 537
 538 doccount
 539 Cluster::Internal::size() const
 540 {
 541     return (cluster_docs.size());
 542 }
 543
 544 void
 545 Cluster::add_point(const Point& point)
 546 {
 547     LOGCALL_VOID(API, "Cluster::add_point", point);
 548     internal->add_point(point);
 549 }
 550
 551 void
 552 Cluster::Internal::add_point(const Point& point)
 553 {
 554     cluster_docs.push_back(point);
 555 }
 556
 557 void
 558 Cluster::clear()
 559 {
 560     LOGCALL_VOID(API, "Cluster::clear", NO_ARGS);
 561     internal->clear();
 562 }
 563
 564 void
 565 Cluster::Internal::clear()
 566 {
 567     cluster_docs.clear();
 568 }
 569
 570 const Centroid&
 571 Cluster::get_centroid() const
 572 {
 573     LOGCALL(API, Centroid, "Cluster::get_centroid", NO_ARGS);
 574     return internal->get_centroid();
 575 }
 576
 577 const Centroid&
 578 Cluster::Internal::get_centroid() const
 579 {
 580     return centroid;
 581 }
 582
 583 void
 584 Cluster::set_centroid(const Centroid& centroid_)
 585 {
 586     LOGCALL_VOID(API, "Cluster::set_centroid", centroid_);
 587     internal->set_centroid(centroid_);
 588 }
 589
 590 void
 591 Cluster::Internal::set_centroid(const Centroid& centroid_)
 592 {
 593     centroid = centroid_;
 594 }
 595
 596 void
 597 Cluster::recalculate()
 598 {
 599     LOGCALL_VOID(API, "Cluster::recalculate", NO_ARGS);
 600     internal->recalculate();
 601 }
 602
 603 void
 604 Cluster::Internal::recalculate()
 605 {
 606     centroid.clear();
 607     for (const Point& temp : cluster_docs) {
 608         for (TermIterator titer = temp.termlist_begin();
 609              titer != temp.termlist_end();
 610              ++titer) {
 611             centroid.add_weight(*titer, temp.get_weight(*titer));
 612         }
 613     }
 614     centroid.divide(size());
 615 }
 616
 617 StemStopper::StemStopper(const Stem& stemmer_, stem_strategy strategy)
 618     : stem_action(strategy), stemmer(stemmer_)
 619 {
 620     LOGCALL_CTOR(API, "StemStopper", stemmer_ | strategy);
 621 }
 622
 623 string
 624 StemStopper::get_description() const
 625 {
 626     string desc("Xapian::StemStopper(");
 627     unordered_set<string>::const_iterator i;
 628     for (i = stop_words.begin(); i != stop_words.end(); ++i) {
 629         if (i != stop_words.begin()) desc += ' ';
 630         desc += *i;
 631     }
 632     desc += ')';
 633     return desc;
 634 }
 635
 636 void
 637 StemStopper::add(const string& term)
 638 {
 639     LOGCALL_VOID(API, "StemStopper::add", term);
 640     switch (stem_action) {
 641         case STEM_NONE:
 642             stop_words.insert(term);
 643             break;
 644         case STEM_ALL_Z:
 645             stop_words.insert('Z' + stemmer(term));
 646             break;
 647         case STEM_ALL:
 648             stop_words.insert(stemmer(term));
 649             break;
 650         case STEM_SOME:
 651         case STEM_SOME_FULL_POS:
 652             stop_words.insert(term);
 653             stop_words.insert('Z' + stemmer(term));
 654             break;
 655     }
 656 }