ARST第二周(2/521)
Algorithm:
第二周LeetCode
Review:(为了学习英文)
Consider how our digital content consumption works today. Some people consume free music and TV shows daily via pirated files, illegal streams. Some consume digital content via legal, publicly-funded radio and TV station streams. Others pay for the privilege to access highly curated and secure services like Spotify, Pandora, Netflix, Hulu, and others. AR clouds will be no different.So how will we choose? I think the answer is security and convenience.
我也认为将来全面上云之后盗版资源的安全隐患会变得极其巨大，所以必须做好安全防范，最好购买服务，但是同时也最好要照顾世界上的弱势群体
Don’t Be Evil！
The Future of the AR Cloud — a Thousand Walled Gardens Bloom
Tip:(主要是为了总结和归纳你在是常工作中所遇到的知识点)
安装VMware15Pro，在上面安装CentOS7，并设置NAT联网(以及kexue就不说了，自行学习)
安装VMware15Pro
VMware15上安装CentOS7
设置NAT联网
Share：
1.基于上下文的自适应算术编码代码实现
设信源可能输出的符号是a, b, c 三个字母，构成一个二阶Markov信源，且各阶条件概率如下，试编写程序可以对任意字母序列（如abbcabcb）进行基于上下文的自适应算术编码，并进行相应的译码。
思路:建立合适的映射表，然后对一个字符和两个字符的时候进行特殊讨论.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
|
// 设信源可能输出的符号是a, b, c 三个字母，构成一个二阶Markov信源，且各阶条件概率如下，
// 试编写程序可以对任意字母序列（如abbcabcb）进行基于上下文的自适应算术编码，并进行相应的译码。
/*
// 经过研究发现，长度变长的时候会出现不相等的情况，分析得知，是因为算法本身的概率选取的调整问题double tp = 0.01*be + 0.99*end;
// 选取时应该把tp调整到大区间段(个人猜测，不会证明，但可以写一个循环自动化调参训练...当在某个长度(input)上面达到某个精度的时候输出参数)
// input : length 先建立 length 长的全 a 序列, length重循环 最后一个从 a+0到+1到+2(最内层),每个外层一变化都要变化一次,O(3^length)指数爆炸
for(double i=0.01;i<1.00;i+=0.01){
for()// length重for3循环，后面计算 sumOf((s<t)||(s>t)) / 3^length 错误率...维护错误率min的i值 看i为多少的时候l错误率最低
}
发现还有是精度问题，如果p后面变得很小的时候，那判断的时候很可能去掉几位判断
最近这几天事情比较多，所以就不写高精度的小数计算了
*/
#include<bits/stdc++.h>
using namespace std;
string s,ans,t;
double table[4][4][4];// eg: c/ab [1][2][3] c/a [1][3][0] a [1][0][0]
int sl;// s 的长度
int l; // 码符号长度
void Init(){
for(int i=1;i<=3;i++){
table[i][0][0] = 1/3.0;
}
for(int i=1;i<4;i++){
for(int j=1;j<4;j++){
if(i==j) table[i][j][0]=0.5;
else table[i][j][0]=0.25;
}
}
// 有点机械，还好sublime有多点编辑
table[1][1][1]=3/5.0; table[1][1][2]=1/5.0; table[1][1][3]=1/5.0;
table[1][2][1]=1/4.0; table[1][2][2]=1/4.0; table[1][2][3]=1/2.0;
table[1][3][1]=1/4.0; table[1][3][2]=1/4.0; table[1][3][3]=1/2.0;
table[2][1][1]=1/2.0; table[2][1][2]=1/4.0; table[2][1][3]=1/4.0;
table[2][2][1]=1/5.0; table[2][2][2]=3/5.0; table[2][2][3]=1/5.0;
table[2][3][1]=1/4.0; table[2][3][2]=1/4.0; table[2][3][3]=1/2.0;
table[3][1][1]=1/2.0; table[3][1][2]=1/4.0; table[3][1][3]=1/4.0;
table[3][2][1]=1/2.0; table[3][2][2]=1/4.0; table[3][2][3]=1/4.0;
table[3][3][1]=1/5.0; table[3][3][2]=1/5.0; table[3][3][3]=3/5.0;
}
void encord(){// 老师用be end 算 len (概率长度) ,我觉得用p (概率长度) 算前后更方便
// 维护 p ,be , end , 之后用be ，end算出概率，p算出编码长度,之后便可以编码
cout<<"编码开始"<<endl;
int n = int(s.length());
double be = 0.0,end = 1.0;
double p = 1.0;
int k = s[0] - 'a' + 1;
int kp=0,kpp=0;
for(int i=0;i<n;i++){
if(i==0){
if(k==1){end = 1/3.0;}
else if(k==2){ be = 1/3.0; end = 2/3.0;}
else be = 2/3.0;
p = 1/3.0;
}
else if(i==1){
// kp = s[i-1] - 'a' + 1;/// 我也是醉了，昨天状态不佳的时候写了多少bug，我以后再在状态不好时写代码我是狗
kp = k;
k = s[i] - 'a' + 1;
if(k==1){
p *= table[kp][k][0];
end = be + p;
}
else if(k==2){
be += p*table[kp][k-1][0];
p *= table[kp][k][0];
// p *= table[kp][k][0]; // 昨天写的bug 真牛逼..
// be += table[kp][k-1][0];
end = be + p;
}
else{
p *= table[kp][k][0];
be = end - p;
}
}
else{
kpp = kp;
kp = k;
// kp = s[i-1] - 'a' + 1;// 昨天的bug
// kpp = s[i-2] - 'a' + 1;
k = s[i] - 'a' + 1;
if(k==1){
p *= table[kpp][kp][k];
end = be + p;
}
else if(k==2){
// p *= table[kpp][kp][k];
// be += table[kpp][kp][k-1];// 这里有bug
// end = be + p;
be += p*table[kpp][kp][k-1];// 原来的长度*第一段
p *= table[kpp][kp][k];
end = be + p;
}
else{
p *= table[kpp][kp][k];
be = end - p;
}
}
// cout<<"s[i]"<<s[i]<<endl;
// cout<<"kpp:"<<kpp<<" kp:"<<kp<<" k:"<<k<<endl;
// cout<<"p监控:"<<p<<endl;
// cout<<"be: "<<be<<endl;
// cout<<"end: "<<end<<endl;
}
l = ceil(log(1/p)/log(2));
// cout<<"be:"<<be<<"end:"<<end<<endl;
// double tp = 0.5*be + 0.5*end;
double tp = 0.01*be + 0.99*end;
int tp2;
ans.resize(0);
for(int i=0;i<l;i++){
tp *= 2;
tp2 = (int)tp;
tp -= tp2;
ans += char(tp2+'0');
}
cout<<"编码长度为: "<<l<<endl;
cout<<"编码结果为: "<<ans<<endl;
sl = int(s.length());
}
void decord(){
cout<<"\n译码: "<<endl;
double res = 0.0;double w = 0.5;
for(int i=0;i<l;i++,w*=0.5){
res += w*(ans[i]-'0');
}
cout<<"译码选取的数字为:"<<res<<endl;
int a=0,b=0; // 用a,b,c来记录下一个概率分布数组
double p = 1; //还是需要记录一个p(概率长度),因为这里的table是通用映射表，需要加约束
t.resize(0);
double be = 0;
for(int i=0;i<sl;i++){
// 2019年4月27日20:52:03 发现还是不能仅跟长度对比啊，没有be，end不行
if(i==0){// 记住左闭右开
if(res<1/3.0){t+='a';a = 1;be = 0.0;}
else if(res<2/3.0){t+='b'; a = 2; be = 1/3.0;}
else {t+='c';a = 3; be = 2/3.0;}
p = 1/3.0;
}
else if(i==1){
if(res < be + p*table[a][1][0]){//be 不变
t += 'a'; b = 1;
p *= table[a][1][0];
}
else if(res < be + p*(table[a][2][0]+table[a][1][0])){
t += 'b'; b = 2;
be += p*(table[a][1][0]);
// be += p*table[a][2][0]; // 2019年4月27日21:49:18今天的bug也很抠脚
p *= table[a][2][0];
}
else{
t += 'c'; b = 3;
be += p*(table[a][1][0]+table[a][2][0]);
p *= table[a][3][0];
}
}
else{// eg: c/ab [1][2][3] c/a [1][3][0] a [1][0][0]自己开始的假设碰巧有一致性，下次还是要打草稿
// 要先p*=table[a][b][1]再更新a,b
if(res < be + p*table[a][b][1]){
t += 'a';
p*=table[a][b][1];// 更新a,b的值
a = b; b = 1;
}
else if(res < be + p*(table[a][b][2]+table[a][b][1])){
t += 'b';
be += p*table[a][b][1];
p*=table[a][b][2];
a = b; b = 2;
}
else{
t += 'c';
be += p*(table[a][b][2]+table[a][b][1]);
p*=table[a][b][3];
a = b; b = 3;
}
}
}
cout<<"译码结果为:"<<t<<endl;
}
int main(int argc, char const *argv[]){
ios::sync_with_stdio(false);
Init();
cout<<"请输入需要编码的字符序列(编码符号为a,b,c):"<<endl;
// cout<<table[1][1][1]<<endl;
while(cin>>s&&s[0]!='#'){
encord();
decord();
string tstr;
tstr += ((s<t)||(s>t)) == 0 ? "恭喜你,译码和源码完全一样哦":"Sorry,可能长度超出了默认精度范围了哦,有空试试高精度吧";
cout<<tstr<<" 此时源码长度为: "<<sl<<endl;
cout<<"\n是否验证下一个字符序列,是则输入,否则输入#:"<<endl;
}
return 0;
}
|
2.完全统计模型的算术编码代码实现
设信源可能输出的符号是26个字母，且每个字母出现的概率未知，试编写程序可以对任意字母序列（如presentation）进行完全统计模型的算术编码，并与香农编码进行码长比较（比值）。
思路:对输入的整个串做分析，然后生成特定串的概率映射表，从而可以开始用最基础的Algorithm Code做题了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
/*
设信源可能输出的符号是26个字母，且每个字母出现的概率未知，试编写程序可以对任意字母序列
（如presentation）进行完全统计模型的算术编码，并与香农编码进行码长比较（比值）。
2019年4月28日19:44:50 总算找完了bug，发现真的有精度问题，如果p后面变得很小的时候，那判断的时候很可能去掉几位判断
最近这几天事情比较多，所以就不写高精度的小数计算了
*/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define x first
#define y second
string s, ans, t;
int num[26];
int Myhash[26];
char Myhash2[26];
int XNlen;
typedef pair<double, pair<double, double>> Node;
vector<Node> p;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cout<<"请输入需要编码的字符序列(编码符号为小写哦):"<<endl;
while (cin >> s&&s[0]!='#')
{
XNlen = 0;
p.clear();
memset(num, 0, sizeof(num));
memset(Myhash, 0, sizeof(Myhash));
memset(Myhash2, 0, sizeof(Myhash2));
int n = (int)s.length();
for (int i = 0; i < n; i++)
{
num[s[i] - 'a']++;
}
// Init
// 先建立通用的概率，然后再进行讨论
// pair<possibility,<be,end>> + hash[char] = order
double be = 0, end = 0;
int k = 0;
double temd;
for (int i = 0; i < 26; i++)
{
if (num[i])
{ // 不为0说明有值的
be = end;
temd = (double)num[i] / n;
end = be + temd;
XNlen += ceil(log(1 / temd) / log(2)) * num[i];
p.pb({temd, {be, end}});
Myhash[i] = k;
Myhash2[k] = 'a' + i;
//在vscode debug结果令人震惊的时候还是得手动
// cout<<"be: "<<be<<" end: "<<end<<endl;
k++;
}
}
// p的构建好像出了问题，2019年4月28日12:34:18 来测试一下 最后发现没有出错...
// for (int i = 0; i < (int)p.size();i++){
// cout << "p[i].x:" << p[i].x << " p[i].y.x:" << p[i].y.x << " p[i].y.y:" << p[i].y.y << endl;
// }
// encode
double pos = 1;
be = 0, end = 0;
for (int i = 0; i < n; i++){
int tem = Myhash[s[i] - 'a'];
be += pos * p[tem].y.x;
// end += pos * p[tem].y.y; 昨天的bug 今天又错了，就是不能这样操作因为可能第一次就有end = 1，可以不维护end,可以的
pos *= p[tem].x;
// cout << "tem:" << tem << " p[tem].y.x" << p[tem].y.x << " p[tem].y.y:" <<p[tem].y.y << endl;
// cout << "be:" << be << " end:" << end << endl;
// cout << "pos监控: " << pos << endl;
}
end = be + pos;
// cout << "be:" << be << " end:" << end << endl;
// cout << "pos监控: " << pos << endl;
int l = ceil(log(1 / pos) / log(2));
double tp = 0.01 * be + 0.99 * end;
int tp2;
ans.resize(0);
for (int i = 0; i < l; i++)
{
tp *= 2;
tp2 = (int)tp;
tp -= tp2;
ans += char(tp2 + '0');
}
cout << "编码长度为: " << l << " 香农编码长度为:" << XNlen << endl;
if (l < XNlen)
{
cout << "WOW,Algorithm Code 果然名不虚传！" << endl;
}
cout << "编码结果为: " << ans << endl;
int sl = int(s.length());
// 译码
cout << "\n译码: " << endl;
double res = 0.0;
double w = 0.5;
for (int i = 0; i < l; i++, w *= 0.5)
{
res += w * (ans[i] - '0');
}
cout << "译码选取的数字为:" << res << endl;
pos = 1;
t.resize(0);
be = 0;
for (int i = 0; i < sl; i++)
{
for (int j = 0; j < k; j++)
{
// cout << "p[j].y.x:" << pos*p[j].y.x << "p[j].y.y" << pos*p[j].y.y << endl;
// if (res >= pos * p[j].y.x && res < pos * p[j].y.y) // mdzz,这个p值会越来越小，所以根本不能用 这样的比较，必须还是要和be和end比较 1. 没有借鉴昨天的后果 2. 没有思考清楚参考系的结果
if (res >= be + pos * p[j].y.x && res < be + pos * p[j].y.y)
{
t += Myhash2[j]; // 这里应该是j对应的反hash
be += pos * p[j].y.x;
pos *= p[j].x;
break;// 不跳出可能再二次迭代出错
}
}
}
cout << "译码结果为: \n" << t << endl;
string tstr;
tstr += ((s<t)||(s>t)) == 0 ? "恭喜你,译码和源码完全一样哦":"Sorry,可能长度超出了默认精度范围了哦,有空试试高精度吧";
cout<<tstr<<" 此时源码长度为: "<<sl<<endl;
cout<<"\n是否验证下一个字符序列,是则输入,否则输入#:"<<endl;
}
return 0;
}
|
3.完全统计模型的算术编码代码实现–无限长不报错版
思路：上面的代码在长度达到20多位的时候就可能会报错了，所以也就是说在10位以内绝对不会报错，所以我们可以把源码分成8个一串的批次处理，这样就可以使的整个过程完成没有错误了
- 这种方法只要不溢出string的内存,理论上来说是可以实现无限长编码的
- 网上查了一下，发现string最大4G
- 4GB是单个程序内存寻址的极限，因此也是CString的极限。
- 绝对够你用了(所以一个2K电影的话就分两个string吧,23333)
- 1.自己昨天没有分成函数模块写，导致了自己改代码改的有点难受，于是花了2个小时改代码(然后还是没有改成函数版，因为这几天太忙了，所以就不改了，读者见谅)(小编不会说自己因为写这个分享错过了晚饭时间，所以不想改成模块化了可能主要是想早点分享给你们(lan
bu yao jiao bian))
- 2.对于tp的取值思考::::取[ ]最终区段的左边会因为迭代操作而一直左偏，所以精度不行，所以选最右边的样子exp积累:
- 1、 以后一定要函数化模块
- 2、 昨天想到的只是精度问题，只是想着暴力处理扩大精度，却没有思考的扩大精度的本质其实就是分块操作
- (所以分布式+集群真是大道至简，积累成就无限的可能)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define x first
#define y second
string source, ans, t;
int num[26];
int Myhash[26];
char Myhash2[26];
int XNlen;
typedef pair<double, pair<double, double>> Node;
vector<Node> p;
int l;
void solve(){
int len = int(source.length());
int last = 0,binlast=0;// 一开始没有想到binlast!
while(len){
int slen = len >= 8? 8 : len;
string s = source.substr(last,slen);
// last += slen;
// len -= slen; // 这两个要在最最最后才搞，否则出错
// string s = source.substr(last,slen);// mdzz 写在这
cout<<"s:"<<s<<endl;
p.clear();
memset(num, 0, sizeof(num));
memset(Myhash, 0, sizeof(Myhash));
memset(Myhash2, 0, sizeof(Myhash2));
int n = (int)s.length();
for (int i = 0; i < n; i++)
{
num[s[i] - 'a']++;
}
// Init
// 先建立通用的概率，然后再进行讨论
// pair<possibility,<be,end>> + hash[char] = order
double be = 0, end = 0;
int k = 0;
double temd;
for (int i = 0; i < 26; i++)
{
if (num[i])
{ // 不为0说明有值的
be = end;
temd = (double)num[i] / n;
end = be + temd;
XNlen += ceil(log(1 / temd) / log(2)) * num[i];
p.pb({temd, {be, end}});
Myhash[i] = k;
Myhash2[k] = 'a' + i;
k++;
}
}
// p的构建好像出了问题，2019年4月28日12:34:18 来测试一下 最后发现没有出错...
// for (int i = 0; i < (int)p.size();i++){
// cout << "p[i].x:" << p[i].x << " p[i].y.x:" << p[i].y.x << " p[i].y.y:" << p[i].y.y << endl;
// }
// encode
double pos = 1;
be = 0, end = 0;
for (int i = 0; i < n; i++){
int tem = Myhash[s[i] - 'a'];
be += pos * p[tem].y.x;
// end += pos * p[tem].y.y; 昨天的bug 今天又错了，就是不能这样操作因为可能第一次就有end = 1，可以不维护end,可以的
pos *= p[tem].x;
// cout << "tem:" << tem << " p[tem].y.x" << p[tem].y.x << " p[tem].y.y:" <<p[tem].y.y << endl;
// cout << "be:" << be << " end:" << end << endl;
// cout << "pos监控: " << pos << endl;
}
end = be + pos;
// cout << "be:" << be << " end:" << end << endl;
// cout << "pos监控: " << pos << endl;
l = ceil(log(1 / pos) / log(2));
double tp = 0.01 * be + 0.99 * end;
int tp2;
// ans.resize(0);
for (int i = 0; i < l; i++)
{
tp *= 2;
tp2 = (int)tp;
tp -= tp2;
ans += char(tp2 + '0');
}
cout << "编码结果为: " << ans << endl;
int sl = int(s.length());
cout<<"当前串长:"<<sl<<endl;
// 译码
cout << "\n译码: " << endl;
double res = 0.0;
double w = 0.5;
for (int i = binlast; i < binlast+ l ; i++, w *= 0.5) // 要用0 1 码长搞出来
{
res += w * (ans[i] - '0');
}
cout << "译码选取的数字为:" << res << endl;
pos = 1;
// t.resize(0);
be = 0;
for (int i = 0; i < sl; i++)
{
for (int j = 0; j < k; j++)
{
// cout << "p[j].y.x:" << pos*p[j].y.x << "p[j].y.y" << pos*p[j].y.y << endl;
// if (res >= pos * p[j].y.x && res < pos * p[j].y.y) // mdzz,这个p值会越来越小，所以根本不能用 这样的比较，必须还是要和be和end比较 1. 没有借鉴昨天的后果 2. 没有思考清楚参考系的结果
if (res >= be + pos * p[j].y.x && res < be + pos * p[j].y.y)
{
t += Myhash2[j]; // 这里应该是j对应的反hash
be += pos * p[j].y.x;
pos *= p[j].x;
break;// 不跳出可能再二次迭代出错
}
}
}
cout<<"中间源码为："<<s<<endl;
cout<<"中间译码为："<<t.substr(last,slen)<<endl;
last += slen;
len -= slen;
binlast += l;
}
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cout<<"请输入需要编码的字符序列(编码符号为小写哦):"<<endl;
while(cin>>source&&source[0]!='#') {
XNlen = 0;
t.resize(0);
ans.resize(0);
solve();
cout<<"编码为："<<ans<<"\n编码长度是："<<ans.length()<<endl;
cout<<"译码为:"<<t<<endl;
// 与香农比较
cout << "编码长度为: " << l << " 香农编码长度为:" << XNlen << endl;
if (l < XNlen)
{
cout << "WOW,Algorithm Code 果然名不虚传！" << endl;
}
string tstr;
tstr += ((source<t)||(source>t)) == 0 ? "恭喜你,译码和源码完全一样哦":"Sorry,可能长度超出了默认精度范围了哦,有空试试高精度吧";
cout<<tstr<<" 此时源码长度为: "<<int(source.length())<<endl;
cout<<"\n是否验证下一个字符序列,是则输入,否则输入#:"<<endl;
}
return 0;
}
|
更新
2019年10月11日19:42:24 更新了文章,发现主分类不用写updated时间也会由插件记录更新时间,但是我不知道记录在哪了,所以写一下比较好