cluster.h

Go to the documentation of this file.

 
/* Copyright (C) 2010 Richard Boulton
 * Copyright (C) 2016 Richhiey Thomas
 * Copyright (C) 2018 Uppinder Chugh
 * Copyright (C) 2024,2026 Olly Betts
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see
 * <https://www.gnu.org/licenses/>.
 */
 
#ifndef XAPIAN_INCLUDED_CLUSTER_H
#define XAPIAN_INCLUDED_CLUSTER_H
 
#if !defined XAPIAN_IN_XAPIAN_H && !defined XAPIAN_LIB_BUILD
#error Never use <xapian/cluster.h> directly; include <xapian.h> instead.
#endif
 
#include <xapian/attributes.h>
#include <xapian/mset.h>
#include <xapian/queryparser.h>
#include <xapian/types.h>
#include <xapian/visibility.h>
 
#include <string_view>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
namespace Xapian {
 
class XAPIAN_VISIBILITY_DEFAULT StemStopper : public Xapian::Stopper {
  public:
    typedef enum {
        STEM_NONE, STEM_SOME, STEM_ALL, STEM_ALL_Z, STEM_SOME_FULL_POS
    } stem_strategy;
 
    explicit StemStopper(const Xapian::Stem &stemmer, stem_strategy strategy = STEM_SOME);
 
    std::string get_description() const override;
 
    bool operator()(const std::string& term) const override {
        return stop_words.find(term) != stop_words.end();
    }
 
    void add(std::string_view term);
 
  private:
    stem_strategy stem_action;
    std::unordered_set<std::string> stop_words;
    Xapian::Stem stemmer;
};
 
class XAPIAN_VISIBILITY_DEFAULT DocumentSet {
  public:
    class Internal;
    Xapian::Internal::intrusive_ptr_nonnull<Internal> internal;
 
    DocumentSet(const DocumentSet &other);
 
    DocumentSet & operator=(const DocumentSet &other);
 
    DocumentSet(DocumentSet && other);
 
    DocumentSet & operator=(DocumentSet && other);
 
    DocumentSet();
 
    ~DocumentSet();
 
    Xapian::doccount size() const;
 
    const Xapian::Document& operator[](Xapian::doccount i) const;
 
    void add_document(const Document &document);
};
 
class XAPIAN_VISIBILITY_DEFAULT FreqSource
    : public Xapian::Internal::opt_intrusive_base {
    void operator=(const FreqSource &) = delete;
 
    FreqSource(const FreqSource &) = delete;
 
  public:
    FreqSource() {}
 
    virtual ~FreqSource();
 
    virtual doccount get_termfreq(const std::string& term) const = 0;
 
    virtual doccount get_doccount() const = 0;
 
    FreqSource * release() {
        opt_intrusive_base::release();
        return this;
    }
 
    const FreqSource * release() const {
        opt_intrusive_base::release();
        return this;
    }
};
 
class XAPIAN_VISIBILITY_DEFAULT TermListGroup : public FreqSource {
    std::unordered_map<std::string, doccount> termfreq;
 
    doccount num_of_documents;
 
    void add_document(const Document &document, const Stopper *stopper = NULL);
 
  public:
    explicit TermListGroup(const MSet &docs, const Stopper *stopper = NULL);
 
    doccount get_termfreq(const std::string& term) const override;
 
    doccount get_doccount() const override;
};
 
class XAPIAN_VISIBILITY_DEFAULT PointType
    : public Xapian::Internal::opt_intrusive_base {
  protected:
    std::unordered_map<std::string, double> weights;
 
    double magnitude = 0.0;
 
    void set_weight(std::string_view term, double weight) {
        weights[std::string(term)] = weight;
    }
 
  public:
    PointType() {}
 
    TermIterator termlist_begin() const;
 
    TermIterator termlist_end() const noexcept {
        return TermIterator(NULL);
    }
 
    bool contains(std::string_view term) const {
        return weights.find(std::string(term)) != weights.end();
    }
 
    double get_weight(std::string_view term) const {
        auto it = weights.find(std::string(term));
        return (it == weights.end()) ? 0.0 : it->second;
    }
 
    void add_weight(std::string_view term, double weight) {
        weights[std::string(term)] += weight;
    }
 
    double get_magnitude() const { return magnitude; }
 
    Xapian::termcount termlist_size() const {
        return Xapian::termcount(weights.size());
    }
 
    PointType * release() {
        opt_intrusive_base::release();
        return this;
    }
 
    const PointType * release() const {
        opt_intrusive_base::release();
        return this;
    }
};
 
class XAPIAN_VISIBILITY_DEFAULT Point : public PointType {
    Document document;
 
  public:
    Point(const FreqSource& freqsource, const Document& document);
 
    Document get_document() const { return document; }
};
 
class XAPIAN_VISIBILITY_DEFAULT Centroid : public PointType {
  public:
    Centroid() { }
 
    explicit Centroid(const Point &point);
 
    void divide(double cluster_size);
 
    void clear() { weights.clear(); }
};
 
class XAPIAN_VISIBILITY_DEFAULT Cluster {
  public:
    class Internal;
    Xapian::Internal::intrusive_ptr_nonnull<Internal> internal;
 
    Cluster(const Cluster &other);
 
    Cluster& operator=(const Cluster &other);
 
    Cluster(Cluster && other);
 
    Cluster & operator=(Cluster && other);
 
    explicit Cluster(const Centroid &centroid);
 
    Cluster();
 
    ~Cluster();
 
    Xapian::doccount size() const;
 
    void add_point(const Point &point);
 
    void clear();
 
    const Point& operator[](Xapian::doccount i) const;
 
    DocumentSet get_documents() const;
 
    const Centroid& get_centroid() const;
 
    void set_centroid(const Centroid &centroid);
 
    void recalculate();
};
 
class XAPIAN_VISIBILITY_DEFAULT ClusterSet {
  public:
    class Internal;
    Xapian::Internal::intrusive_ptr_nonnull<Internal> internal;
 
    ClusterSet(const ClusterSet &other);
 
    ClusterSet& operator=(const ClusterSet &other);
 
    ClusterSet(ClusterSet && other);
 
    ClusterSet & operator=(ClusterSet && other);
 
    ClusterSet();
 
    ~ClusterSet();
 
    void add_cluster(const Cluster &cluster);
 
    void add_to_cluster(const Point &point, unsigned int index);
 
    Xapian::doccount size() const;
 
    const Cluster& operator[](Xapian::doccount i) const;
 
    void clear_clusters();
 
    void recalculate_centroids();
};
 
class XAPIAN_VISIBILITY_DEFAULT Similarity {
  public:
    virtual ~Similarity();
 
    virtual double similarity(const PointType &a, const PointType &b) const = 0;
 
    virtual std::string get_description() const = 0;
};
 
class XAPIAN_VISIBILITY_DEFAULT CosineDistance : public Similarity {
  public:
    double similarity(const PointType& a, const PointType& b) const override;
 
    std::string get_description() const override;
};
 
class XAPIAN_VISIBILITY_DEFAULT Clusterer
    : public Xapian::Internal::opt_intrusive_base {
  public:
    virtual ~Clusterer();
 
    virtual ClusterSet cluster(const MSet &mset) = 0;
 
    virtual std::string get_description() const = 0;
 
    Clusterer * release() {
        opt_intrusive_base::release();
        return this;
    }
 
    const Clusterer * release() const {
        opt_intrusive_base::release();
        return this;
    }
};
 
class XAPIAN_VISIBILITY_DEFAULT KMeans : public Clusterer {
    std::vector<Point> points;
 
    unsigned int k;
 
    unsigned int max_iters;
 
    Xapian::Internal::opt_intrusive_ptr<const Xapian::Stopper> stopper;
 
    void initialise_clusters(ClusterSet &cset, Xapian::doccount num_of_points);
 
    void initialise_points(const MSet &source);
 
  public:
    explicit KMeans(unsigned int k_, unsigned int max_iters_ = 0);
 
    ClusterSet cluster(const MSet &mset) override;
 
    void set_stopper(const Xapian::Stopper* stop = NULL) { stopper = stop; }
 
    std::string get_description() const override;
};
 
class XAPIAN_VISIBILITY_DEFAULT LCDClusterer : public Clusterer {
    unsigned int k;
 
  public:
    explicit LCDClusterer(unsigned int k_);
 
    ClusterSet cluster(const MSet &mset) override;
 
    std::string get_description() const override;
};
}
#endif // XAPIAN_INCLUDED_CLUSTER_H