diff options
author | Anthony Wang | 2020-05-24 17:35:36 +0000 |
---|---|---|
committer | repl.it user | 2020-05-24 17:35:36 +0000 |
commit | 04ae85a14db30c6a0cb88a1909a5478d08a1a01a (patch) | |
tree | 479295485520cdf272945b2a35d86f8eaaf67b2d | |
parent | 177548da5419b187c14f5697208248ac9202ed2b (diff) |
update
-rw-r--r-- | out | bin | 0 -> 155896 bytes | |||
-rw-r--r-- | src/common.h | 2 | ||||
-rw-r--r-- | src/huffman.cpp | 38 | ||||
-rw-r--r-- | src/main.cpp | 53 |
4 files changed, 60 insertions, 33 deletions
Binary files differ diff --git a/src/common.h b/src/common.h index be30799..c295a6a 100644 --- a/src/common.h +++ b/src/common.h @@ -1,3 +1,5 @@ +// include this file at the top of every source file + #pragma once #include <bits/stdc++.h> using namespace std;
\ No newline at end of file diff --git a/src/huffman.cpp b/src/huffman.cpp index 006ff21..8a8e4c7 100644 --- a/src/huffman.cpp +++ b/src/huffman.cpp @@ -9,7 +9,7 @@ namespace huffman { struct comp { bool operator()(node * a, node * b) { return a->f > b->f; } }; node * root; vector<bool> path; - vector<vector<bool>> code(256); + vector<vector<bool>> code(128); void traverse(node * n) { if (n->l) { path.push_back(0); @@ -24,42 +24,42 @@ namespace huffman { if (n->c) code[n->c] = path; } - void get_tree(node * n, vector<bool> & v) { - if (n->l) { + void encode_tree(node * n, vector<bool> & v) { + if (n->c) { v.push_back(1); - get_tree(n->l, v); + for (int i = 0; i < 8; ++i) v.push_back(1 & (n->c >> i)); } else v.push_back(0); - if (n->r) { + if (n->l) { v.push_back(1); - get_tree(n->r, v); + encode_tree(n->l, v); } else v.push_back(0); - if (n->c) { + if (n->r) { v.push_back(1); - for (int i = 0; i < 8; ++i) v.push_back(1 & (n->c >> i)); + encode_tree(n->r, v); } else v.push_back(0); } int idx = 0; - void construct_tree(node * n, vector<bool> & v) { + void decode_tree(node * n, vector<bool> & v) { if (v[idx++] == 1) { - n->l = new node(0, 0); - construct_tree(n->l, v); + for (int i = 0; i < 8; ++i) n->c |= (1 << v[idx++]); } if (v[idx++] == 1) { - n->r = new node(0, 0); - construct_tree(n->r, v); + n->l = new node(0, 0); + decode_tree(n->l, v); } if (v[idx++] == 1) { - for (int i = 0; i < 8; ++i) n->c |= (1 << v[idx++]); + n->r = new node(0, 0); + decode_tree(n->r, v); } } void generate(vector<int> f) { priority_queue<node *, vector<node *>, comp> pq; - for (int c = 'a'; c <= 'z'; ++c) { + for (int c = 0; c < 128; ++c) { node * n = new node(c, f[c]); pq.push(n); } @@ -76,6 +76,8 @@ namespace huffman { void solve(node * n, vector<bool> & v, string & s) { if (n->c) { s += n->c; + cout << (int)n->c << '\n'; + if (idx > v.size()) return; solve(root, v, s); } else { @@ -85,12 +87,12 @@ namespace huffman { } vector<bool> encode(string s) { - vector<int> f(256); + vector<int> f(128, 0); for (auto& c : s) ++f[c]; generate(f); traverse(root); vector<bool> ret; - get_tree(root, ret); + encode_tree(root, ret); for (auto& c : s) { for (auto b : code[c]) ret.push_back(b); } @@ -99,8 +101,8 @@ namespace huffman { string decode(vector<bool> v) { root = new node(0, 0); + decode_tree(root, v); string ret; - construct_tree(root, v); solve(root, v, ret); return ret; } diff --git a/src/main.cpp b/src/main.cpp index 6d4a043..982b276 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2,9 +2,14 @@ #include "huffman.h" #define pb push_back + + int getweight(string s) { - return 0; + if(s[0]=='$') + return 1000; + else if(s=="Farmer"||s=="a"||s=="example")return 1; + else return 10; } struct clause { @@ -15,13 +20,18 @@ struct clause void parse() { string word=""; + bool iseq=false; for(int j=0;j<s.length();j++) { - if(s.at(j)!=' ')word+=s.at(j); + if(s.at(j)=='$') iseq=!iseq; + if(('a'<=s.at(j)&&s.at(j)<='z')||('A'<=s.at(j)&&s.at(j)<='Z')||('0'<=s.at(j)&&s.at(j)<='9')||(iseq&&s.at(j)=='$')))word+=s.at(j); else { - if(word!="")words.pb(word); - word=""; + if(!iseq) + { + if(word!="")words.pb(word); + word=""; + } } } if(word!="") words.pb(word); @@ -41,11 +51,11 @@ struct sentence void parse() { string cl=""; - //bool iseq=false; + bool iseq=false; for(int j=0;j<s.length();j++) { - //if(s.at(j)=='$') iseq=!iseq; - if(s.at(j)!=',') cl+=s.at(j); + if(s.at(j)=='$') iseq=!iseq; + if(s.at(j)!=','|| iseq) cl+=s.at(j); else { clause tmp; @@ -68,7 +78,11 @@ struct sentence void calcweight() { weight=-100000; - for(auto& c : clauses)if(c.weight>weight)weight=c.weight; + for(auto& c : clauses) + { + c.calcweight(); + if(c.weight>weight)weight=c.weight; + } } }; vector<sentence> text; @@ -80,12 +94,14 @@ void init() cin>>c; ifstream stin("soc1.txt"); string sentencefile=""; + bool iseq=false; while(getline(stin,line)) { for(int i=0;i<line.length();i++) { b++; - if(line.at(i)!='.')sentencefile+=line.at(i); + if(line.at(i)=='$') iseq=!iseq; + if((line.at(i)!='.'&&line.at(i)!='?'&&line.at(i)!='!')|| iseq)sentencefile+=line.at(i); else { sentence tmp;tmp.s=sentencefile;text.pb(tmp); @@ -95,16 +111,23 @@ void init() b++; sentencefile+=' '; } -} -void clsep() -{ for(auto& i:text)i.parse(); } int main() { init(); - clsep(); - /*vector<bool> test = huffman::encode("test"); + for(sentence& i:text) + { + for(clause& j:i.clauses) + { + for(auto k:j.words) + { + cout<<k<<endl; + } + } + } + + vector<bool> test = huffman::encode("test"); for (auto b : test) cout << b; string s = huffman::decode(test); - cout << s << '\n';*/ + cout << s << '\n'; }
\ No newline at end of file |