SimilarityMeasures.h

Go to the documentation of this file.

// Contents: Classes implementing similarity measures for strings

//
// Principal Author:Copyright (2005)  Alexei Miasnikov
//
// Status:
//
// Revision History:
//

#ifndef STRING_SIMILARITY_H
#define STRING_SIMILARITY_H


#include "Word.h"
#include <vector>
//#include "MotivePatternWrapper.h"



double getLeftTaleConfidenceValue(const vector<double>& dist, double p);

class StringSimilarityMeasure;



class WordPairComparison
{
 public:

  WordPairComparison( int rank,  const StringSimilarityMeasure* sm): theRank( rank ), pSSM( sm ) {}
  

  vector<double> distrEstimate(int minLen, int maxLen, int nSamples = 1000)const;
  

  double comparePair( const Word& w1, const Word& w2, const vector<double>& measureDistr)const;


  double comparePair( const Word& w1, const Word& w2)const;
 private:
  WordPairComparison( const WordPairComparison& );
  WordPairComparison& operator = (const WordPairComparison&);
  const StringSimilarityMeasure* pSSM;
  int theRank;
};

//
// MEASURE ABSTRACT CLASS
//

class StringSimilarityMeasure
{
public:

  virtual double measure(const Word& w1, const Word& w2)const  = 0;
};


//
// HAMMING DISTANCE
//


class HammingDistance : public StringSimilarityMeasure
{
public:
  HammingDistance() {}
  

  double measure(const Word& w1, const Word& w2) const;
};

class HammingDistanceCyclic : public StringSimilarityMeasure
{
public:
  HammingDistanceCyclic() {}

  double measure(const Word& w1, const Word& w2) const;
};


class SubwordHammingDistanceCyclic : public StringSimilarityMeasure
{
 public:
  SubwordHammingDistanceCyclic() {}

  double measure(const Word& w1, const Word& w2) const;
};


//
// EDITING DISTANCE
//

class EditingDistance : public StringSimilarityMeasure
{
public:
  EditingDistance() {}
  

  double measure(const Word& w1, const Word& w2) const;
};


class SubwordEditingDistanceCyclic : public StringSimilarityMeasure
{
 public:
  SubwordEditingDistanceCyclic() {}

 double measure(const Word& w1, const Word& w2) const;
};




//
// WHITEHEAD GRAPH
//
                                     /*
class WhiteheadGraphSimilarity : public StringSimilarityMeasure
{
public:
  WhiteheadGraphSimilarity( const FreeGroup& F): theGroup( F ) {}
  double measure(const Word&, const Word&) const;
private:
  FreeGroup theGroup;
};
                                     */
//
// MOTIVES
//
                                 /*
class MotiveSimilarity : public StringSimilarityMeasure
{
public:
  MotiveSimilarity( const FreeGroup& F): theGroup( F ) {}
  double measure(const Word&, const Word&) const;
private:
  FreeGroup theGroup;
};
                                 */


#endif