Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

ХаффманV2

85K
10 марта 2019 года
rzjanin
5 / / 09.03.2019
Код:
#include <bits/stdc++.h>
using namespace std;
  string basik;
string c( int value, int bts)
{
    bool found = false;
        string res;
    const int bits = bts;
    bool sk = false;
    for (int cb = bits - 1; cb  >= 0; cb--)
    {
        if ((value & (1 << cb )) != 0)
        {
            if (!found)
                found = true;
            res += '1';
        }
        else
        {
                res += '0';
        }
    }

    return res;
}
void printImage(string s) {
    int k = 1;
for (int i = 0; i < s.size(); i++) {

    cout << s[i];
    if (k%100 == 0 && k !=5100)
        cout << endl;
    k++;
  }

}
void getImage() {
    for (int i = 0; i < 51; i++){
        string x;
        cin >> x;
        basik+=x;
   }
}

class Node
{
    public:
     int a;
     string c;
     Node *left, *right;
     Node(){left=right=NULL;}
     Node(Node *L, Node *R)
     {  left =  L;
        right = R;
        a = L->a + R->a;  }
};
struct oversort
{
    bool operator()(const Node* l, const Node* r) const { return l->a < r->a; }
};
vector<bool> code;
int bistrtoint(char *x) {
    int ans = (int)strtol(x, NULL, 2);
    return ans;
}
map<string,vector<bool> > table;
void build(Node *rt)
{
    if (rt->left!=NULL)
                      { code.push_back(0);
                      build(rt->left);}
    if (rt->right!=NULL)
                       { code.push_back(1);
                       build(rt->right);}
    if (rt->left==NULL && rt->right==NULL) table[rt->c]=code;
    code.pop_back();
}
string dec(string &str, map<vector<bool>, string> &table1)
{
    string out = "";
    vector<bool> code;
    for (int i = 0; i < str.length(); i++)
    {
        code.push_back(str[i] == '0' ? false : true);
        if (table1.count(code))
        {
            out += table1[code];
            code.clear();
        }
    }
    return out;
}
string er (string x, int n) {
  x.erase(x.begin(),x.end()-x.size()+n);
  return x;
}
string strght(string s) {
     while (s.size()!=5100) {
        s.erase(s.begin() + s.size()-1, s.end());
   }
   return s;
}
int main() {
  int mode;
  cin >> mode;
  if (!mode) {
  int minsize = 1e9;
  string best;
  getImage();
  int bestval = 0;
    for (int val = 4; val <=20; val++) {
 string  s=basik;
  while (s.size()%val!=0)
    s+='0';
  vector<string> strvallist;
 map<string,int>often;
   for (int i = 0; i < s.size(); i+=val) {
    string c;
    for (int j = i; j< i+val;j++)
        c+=s[j];
    strvallist.push_back(c);
    often[c]++;
   }
   list<Node*> t;
   map<string,int>::iterator itr;
   for( itr=often.begin(); itr!=often.end(); ++itr)
   {
      Node *p = new Node;
      p->c = itr->first;
      p->a = itr->second;
      t.push_back(p);
      }
     bool manychar = true;
     if (t.size()==1)
       manychar = false;
while (t.size()!=1)
  {
     t.sort(oversort());
     Node *SonL = t.front();
     t.pop_front();
     Node *SonR = t.front();
     t.pop_front();
     Node *parent = new Node(SonL,SonR);
     t.push_back(parent);

  }
if (manychar){
  Node *root = t.front();
   build(root);
} else {
   vector<bool> tempc;
   tempc.push_back(0);
   table[strvallist[0]] = tempc;
}
   map<string, vector<bool> >::iterator it;
 vector<bool>::iterator ii;
 string tablecode = "";
 int sizetablecode = 0;
 for (it = table.begin(); it != table.end(); it++)
 {
     sizetablecode++;
  tablecode += it->first;
  string temp = "";
  int kount = 0;
  for (ii = table[it->first].begin(); ii != table[it->first].end(); ii++) {
   int t = (*ii);
   kount++;
   temp += t+'0';
  }
  tablecode += c(kount,4);
  tablecode += temp;
 }

  map<string, vector<bool> >::iterator iii;
  map<string,int>::iterator iof = often.begin();
  cout << endl << endl << val << endl;
  for (iii = table.begin(); iii != table.end(); iii++) {
    cout << iii->first << " : ";
     vector<bool>::iterator i;
   for (i = table[iii->first].begin(); i != table[iii->first].end(); i++)
     cout << *i;
   cout << " : " << iof->second;
   iof ++;
    cout << endl;
  }
 cout << endl << endl << endl;

 tablecode = c(val,5) + c(sizetablecode,12) + tablecode;
   string out = "";
    for (int i = 0; i < strvallist.size(); i++)
        for (int j = 0; j < table[strvallist[i]].size(); j++)
        {
            out += table[strvallist[i]][j] + '0';
        }
    string encodeds = out;
    int siz = out.size();
   map<vector<bool>, string> inverse;
    for (map<string, vector<bool> >::iterator i = table.begin(); i != table.end(); i++)
        inverse[i->second] = i->first;
    out = dec(out, inverse);
    string result = tablecode + encodeds;
table.clear();
if (result.size() < minsize) {
    minsize = result.size();
    best = result;
    bestval = val;
}
cout << endl << val << " " <<  often.size() << " " << siz << " " << tablecode.size() << endl;
code.clear();
    }
    cout << best;
    cout << endl << endl << endl << best.size() << " " << bestval  << endl;
  }
  else {
  string s;
  cin >> s;
  map<vector<bool>, string> vocabulary;
  char sizevalstring[8];
  string tempstr;
   for (int i = 0; i < 5; i++)  {
    tempstr+= s[i];
   }
   for (int i = 0; i < 5; i++)
    sizevalstring[i] = tempstr[i];
     int sizeval = bistrtoint(sizevalstring);
  s = er(s,5);
   char sizetabs[12];
   for (int i = 0; i < 12; i++)  {
    sizetabs[i] = s[i];
   }
   int sizetab = bistrtoint(sizetabs);
   s.erase(s.begin(), s.end()-s.size() + 12 );
  int j = 0;
  while (j < sizetab) {
    j++;
    string val = "";
     for (int i = 0; i < sizeval; i++)
       val += s[i];
    s = er(s, sizeval);
    char keysizes[9];
    for (int i = 0; i < 4; i++)  {
      keysizes[i] = s[i];
    }
    int keysize = bistrtoint(keysizes);
    s = er(s,4);
    string key = "";
    for (int i = 0; i < keysize; i++)
        key+=s[i];
    s = er(s,keysize);
    vector<bool> cod;
    for (int i = 0; i < key.size();i++){
        cod.push_back(key[i]-'0');
    }
    vocabulary[cod] = val;
  }
    s = dec(s, vocabulary);
    int k = 1;
  s = strght(s);
  printImage(s);
  }
    return 0;
}
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог