readme.txt

来自「Build an optimal binary search tree usin」· 文本 代码 · 共 28 行

********************************************************************************************

compiler: g++
programing language:c++

********************************************************************************************

our design:
--------read the file Dictionary.txt,get the words and the frequency.
--------calculate the probability of every word,using the frequency.
--------compute q[i] correspond to the dummy key d[i]. q[i] is inversely proportional to the number of common prefix characters of k[i] and k[i+1],where A is a constant.we choose A=0.001 because we find that when A is smaller, the expected search cost is smaller too.But if A is too small,A^n will save as 0,we can't get the right result.  
--------using dynamic programming according section 15.5,we get the optimal binary search tree.
--------using the result get from Optimal-BSD,we get heights of every node in the OBST.using the heights of every node multiply the probability corresponding to it,we get the cost of searching every phrase in the OBSD.e[1,n] is just the average search cost,get from Optimal-BSD. 
--------save the information get above  in the file named "output.out"********************************************************************************************

some notes:
-------The program is encoded by the programing language C++, and its compiler is g++.
-------The program have been compiled successfuly.
-------Because the words are too many,we just use the previous 10000 words to build an optimal binary search tree,and we get the average search cost is 8.87763.

********************************************************************************************

thanks for your reading and checking!

********************************************************************************************