project3.cpp

Build an optimal binary search tree using dynamic programming.

#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <string>
#include <math.h>
#include <locale>
#include <limits>

#define A 0.0001
#define SUM_P 0.99
using namespace std;

int NUM=10000;

void read(string *words,float *prob); //read words
void GetPro(float *prob); //Get the probility of every node
short int **Optimal_BST(float *p,float *q,short int n,float **e);//BST algorithm
void QuizeLevel(short int **root,short int *level,short int k_level,short int start,short int end); //get the heights of every node
void GetLevelCost(short int *level,float *cost,float *p,short int **root,short int n);//get the heights and the cost
void Getq(float *q,string *words);//calculate the value of q
void   output(string *words,float **e,short int *level,float *cost,int n);//out put the result

 int main()
{
  
  short int i,j;
  string *words=new string [NUM+1];
  float *prob=new float [NUM+1];
  read(words,prob);  //read words
  GetPro(prob);      //Get the probility of every node
  cout<<"Getp OK!"<<endl;
  short int n=NUM;
  float **e;
  e=new float * [n+2];   //get e space
  for(i=1;i<n+2;i++)
    {
      
      e[i]=new float [n+1];
    }
  
  float *p=prob;
  float *q=new float[NUM+1];
  Getq(q,words); //Get the probility of every node
  cout<<"Getq OK!"<<endl;
  //for(i=0;i<=n;i++)
  //  q[i]=0.01/(n+1);
  short int **root;  
  root=Optimal_BST(p,q,n,e);//BST algorithm
  cout<<"BST OK!"<<endl;
  cout<<"Searth Cost: "<<e[1][n]<<endl;
     
  float *cost=new float[n+1];
  short int *level=new short int[n+1];
  GetLevelCost(level,cost,p,root, n);//get the heights and the cost
  output(words,e,level,cost,n);//out put the result
  for(i=1;i<n+2;i++)// delete
    {
      
      delete e[i];
    }
  delete e;
  for(i=1;i<n+1;i++)
    {
        delete root[i];
    }
  delete root;
  delete prob;
  delete q;
  delete cost;
  delete level;
 return 0;
}
void   output(string *words,float **e,short int *level,float *cost,int n)//out put the result
{
  ofstream out("result.out");
  int i;
  out<<" number "<<setw(10)<<" heights "<<" cost "<<"           words  "<<endl;
  for(i=1;i<=n;i++)
    out<<setw(6)<<i<<"    "<<setw(4)<<level[i]<<"     "<<left<<setw(12)<<cost[i]<<"    "<<words[i]<<endl<<right;
  out<<"The average search cost is: "<<e[1][n]<<endl;
}


void read(string *words,float *prob) //读文件
{    
       string ifileku;
       ifileku ="Dictionary.txt";
       ifstream infileb( ifileku.c_str() );
       if ( ! infileb)
	 {
	   cerr << "error :  1 " <<ifileku <<endl;
	   
	 }
       
       float dtemp;
       string stemp;
       short int k=0;
       for(short int i=1;i<=NUM;i++)
	 {
	   infileb>>dtemp;
	   infileb>>stemp;
	   words[i]=stemp;
	   prob[i]=dtemp;
	  
	 }
       	  
}
void GetPro(float *prob) //Get the probility of every node
{
  short int i;
  float s=0;
  for(i=1;i<=NUM;i++)
    s+=prob[i];
  s/=SUM_P;
  for(i=1;i<=NUM;i++)
    prob[i]=prob[i]/s;
}
      


short int **Optimal_BST(float *p,float *q,short int n,float **e)//BST algorithm
{
  short int i;
  
  float **w;
  w=new float *  [n+2];   //get w space
  for(i=1;i<n+2;i++)
    {
      w[i]=new float [n+1];
    }
  short int **root;            //get root space
  root=new short int * [n+1];
  for(i=1;i<n+1;i++)
    {
      root[i]=new short int [n+1];
    }
  
  for(i=1;i<=n+1;i++)
    {
      e[i][i-1]=q[i-1];
      w[i][i-1]=q[i-1];
    }
  short int j,l,r;
  float t;
  short int start,end;
  for(l=1;l<=n;l++)
    {
      for(i=1;i<=n-l+1;i++)
	{
	  j=i+l-1;
	  e[i][j]=numeric_limits<float>::max();
	  w[i][j]=w[i][j-1]+p[j]+q[j];
	  if(j>i)
	    {
	      start=root[i][j-1];
	      
	    }
	  else
	    start=i;
	  if(j>i)
	    end=root[i+1][j];
	  else
	    end=j;
	  //cout<<start<<" "<<end<<endl; 
	  for(r=start;r<=end;r++)
	    {
	      t=e[i][r-1]+e[r+1][j]+w[i][j];
	      if(t<e[i][j])
		{
		  e[i][j]=t;
		  root[i][j]=r;
		}
	    }
	}
    }
  for(i=1;i<n+2;i++)
    {
      delete w[i];
    }
  delete w;
  return root;
}

void QuizeLevel(short int **root,short int *level,short int k_level,short int start,short int end) //get the heights of every node
{
  if(start<=end)
    {
      level[root[start][end]]=k_level++;
      QuizeLevel(root,level,k_level,start,root[start][end]-1);
      QuizeLevel(root,level,k_level,root[start][end]+1,end);
    }
}
void GetLevelCost(short int *level,float *cost,float *p,short int **root,short int n)//get the heights and the cost
{
  short int start=1,end=n;
  short int i,j;
  short int k_level=1;
  QuizeLevel(root,level,k_level,start,end);
  for(i=1;i<=n;i++)    //the cost of searching a phrase
    cost[i]=p[i]*level[i];
  
      
}
  
void Getq(float *q,string *words)//calculate the value of q
{
  
  short int   i,n,len;
  float   s=0;
  for(i=1;i<NUM;i++)
    {
      n=0;
      len=min(words[i].length(),words[i+1].length());
      while(n<len&&words[i][n]==words[i+1][n])
	n++;
      //cout<<n<<endl;
      
      q[i]=1/pow(A,n/2);
      s+=q[i];
    }
  q[0]=q[1];
  q[NUM]=q[NUM-1]; 
  s+=q[0];
  s+=q[NUM];
  s/=1-SUM_P;
  for(i=0;i<=NUM;i++)
    q[i]/=s;
  
}