00001 #ifndef moses_DynSuffixArray_h
00002 #define moses_DynSuffixArray_h
00003
00004 #include <vector>
00005 #include <set>
00006 #include <algorithm>
00007 #include <utility>
00008 #include "moses/Util.h"
00009 #include "moses/File.h"
00010 #include "moses/TranslationModel/DynSAInclude/types.h"
00011
00012 namespace Moses
00013 {
00014
00015 typedef std::vector<unsigned> vuint_t;
00016
00017
00020
00021 class ComparePosition
00022 {
00023 vuint_t const& m_crp;
00024 vuint_t const& m_sfa;
00025
00026 public:
00027 ComparePosition(vuint_t const& crp, vuint_t const& sfa);
00028 bool operator()(unsigned const& i, std::vector<wordID_t> const& phrase) const;
00029 bool operator()(std::vector<wordID_t> const& phrase, unsigned const& i) const;
00030 };
00031
00032
00035 class DynSuffixArray
00036 {
00037
00038 public:
00039 DynSuffixArray();
00040 DynSuffixArray(vuint_t*);
00041 ~DynSuffixArray();
00042 bool GetCorpusIndex(const vuint_t*, vuint_t*);
00043 void Load(FILE*);
00044 void Save(FILE*);
00045 void Insert(vuint_t*, unsigned);
00046 void Delete(unsigned, unsigned);
00047 void Substitute(vuint_t*, unsigned);
00048
00049 size_t GetCount(vuint_t const& phrase) const;
00050
00051 private:
00052 vuint_t* m_SA;
00053 vuint_t* m_ISA;
00054 vuint_t* m_F;
00055 vuint_t* m_L;
00056 vuint_t* m_corpus;
00057 void BuildAuxArrays();
00058 void Qsort(int* array, int begin, int end);
00059 int Compare(int, int, int);
00060 void Reorder(unsigned, unsigned);
00061 int LastFirstFunc(unsigned);
00062 int Rank(unsigned, unsigned);
00063 int F_firstIdx(unsigned);
00064 void PrintAuxArrays() {
00065 std::cerr << "SA\tISA\tF\tL\n";
00066 for(size_t i=0; i < m_SA->size(); ++i)
00067 std::cerr << m_SA->at(i) << "\t" << m_ISA->at(i) << "\t"
00068 << m_F->at(i) << "\t" << m_L->at(i) << std::endl;
00069 }
00070 };
00071 }
00072
00073 #endif