Advertisement
Guest User

Untitled

a guest
Jan 20th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.39 KB | None | 0 0
  1. #include<iostream>
  2. #include<string>
  3. #include<fstream>
  4. using namespace std;
  5. class cnode
  6. {
  7. public:
  8. int frequency;
  9. char name[256];
  10. string encryption;
  11. cnode *pnext;
  12. cnode *pleft = NULL;;
  13. cnode *pright = NULL;
  14. cnode *pdown = NULL;
  15. };
  16. class clist
  17. {
  18. public:
  19. cnode *phead;
  20. cnode *ptail;
  21.  
  22. clist()
  23. {
  24. phead = NULL;
  25. ptail = NULL;
  26. }
  27.  
  28. ~clist()
  29. {
  30. cnode *ptrav = phead;
  31. while (ptrav != NULL)
  32. {
  33. phead = phead->pnext;
  34. delete ptrav;
  35. ptrav = phead;
  36. }
  37. }
  38.  
  39. void Attach(cnode *pnn)
  40. {
  41. if (phead == NULL)
  42. {
  43. phead = pnn;
  44. ptail = pnn;
  45. }
  46. else
  47. {
  48. ptail->pnext = pnn;
  49. ptail = pnn;
  50. }
  51. }
  52.  
  53. void sortAttach(cnode *pnn)
  54. {
  55. cnode *pB = NULL;
  56. cnode *ptrav = phead;
  57. while (ptrav != NULL)
  58. {
  59. if (ptrav->frequency > pnn->frequency)
  60. {
  61. break;
  62. }
  63. pB = ptrav;
  64. ptrav = ptrav->pnext;
  65. }
  66. if (ptrav != NULL)
  67. {
  68. if (pB != NULL)
  69. {
  70. pB->pnext = pnn;
  71. pnn->pnext = ptrav;
  72. }
  73. else
  74. {
  75. pnn->pnext = ptrav;
  76. phead = pnn;
  77. }
  78. }
  79. else
  80. {
  81. pB->pnext = pnn;
  82. pnn->pnext = NULL;
  83. }
  84. }
  85.  
  86. void combine(cnode *pnn, cnode *ptrav)
  87. {
  88. cnode *pnn2;
  89. pnn2 = new cnode;
  90. cnode *tnext;
  91. cnode *tdown;
  92. tdown = new cnode;
  93. tnext = pnn->pnext;
  94. pnn2->frequency = pnn->frequency + tnext->frequency;
  95. int k = 0;
  96.  
  97. //copy name pnn
  98. for (int i = 0; i < 256; i++)
  99. {
  100. if (pnn->name[i] != '\0')
  101. {
  102. pnn2->name[k] = pnn->name[i];
  103. k++;
  104. }
  105. else
  106. {
  107. break;
  108. }
  109.  
  110. }
  111.  
  112. //copy name pnext
  113. for (int i = 0; i < 256; i++)
  114. {
  115. if (tnext->name[i] != '\0')
  116. {
  117. pnn2->name[k] = tnext->name[i];
  118. k++;
  119. }
  120. else
  121. {
  122. break;
  123. }
  124. }
  125.  
  126. //make rest of array null
  127. pnn2->name[k] = '\0';
  128.  
  129. //set tdown
  130. for (int i = 0; pnn2->name[i]!='\0'; i++)
  131. {
  132. tdown->name[i] = pnn2->name[i];
  133. }
  134. tdown->frequency = pnn2->frequency;
  135.  
  136.  
  137. //set tree
  138. //check pnn
  139. if (pnn->pdown != NULL)
  140. {
  141. tdown->pleft = pnn->pdown;
  142. }
  143. else
  144. {
  145. tdown->pleft = pnn;
  146. }
  147.  
  148. //check tnext
  149. if (tnext->pdown != NULL)
  150. {
  151. tdown->pright = tnext->pdown;
  152. }
  153. else
  154. {
  155. tdown->pright = tnext;
  156. }
  157.  
  158. pnn2->pdown = tdown;
  159.  
  160.  
  161.  
  162. //sortAttach
  163. cnode *pB = NULL;
  164. while (ptrav != NULL)
  165. {
  166. if (ptrav->frequency > pnn2->frequency)
  167. {
  168. break;
  169. }
  170. pB = ptrav;
  171. ptrav = ptrav->pnext;
  172. }
  173. if (ptrav != NULL)
  174. {
  175. pB->pnext = pnn2;
  176. pnn2->pnext = ptrav;
  177. }
  178. else
  179. {
  180. pB->pnext = pnn2;
  181. pnn2->pnext = ptrav;
  182. }
  183.  
  184. }
  185.  
  186. void binsearch(cnode *pnn)
  187. {
  188. cnode *ptrav;
  189. string bin;
  190. int flag = 0;
  191. ptrav = pnn;
  192. cout << "input binary" << endl;
  193. cin >> bin;
  194. for (int i = 0; i < bin.length(); i++)
  195. {
  196. if (ptrav != NULL)
  197. {
  198. if (bin[i] == '0')
  199. {
  200. ptrav = ptrav->pleft;
  201. }
  202. else
  203. {
  204. if (bin[i] == '1')
  205. {
  206. ptrav = ptrav->pright;
  207. }
  208. else
  209. {
  210. flag = 1;
  211. break;
  212. }
  213. }
  214. }
  215. else
  216. {
  217. break;
  218. }
  219. }
  220. cout << endl << "-------------------------------" << endl;
  221. if (ptrav != NULL && flag==0)
  222. {
  223. for (int i = 0; i < 256; i++)
  224. {
  225. if (ptrav->name[i] != ' ')
  226. {
  227. cout << ptrav->name[i];
  228. }
  229. else
  230. {
  231. break;
  232. }
  233. }
  234. cout << " : " << ptrav->frequency << endl;
  235. }
  236. else
  237. {
  238. cout << "node not found" << endl;
  239. }
  240.  
  241. }
  242.  
  243. void searchBin(cnode *pnn)
  244. {
  245. cnode *ptrav;
  246. ptrav = pnn;
  247. char code[1];
  248. int flag = 0;
  249. cin >> code[0];
  250. while (ptrav->pleft != NULL && ptrav->pright != NULL)
  251. {
  252. for (int i = 0; i < 256; i++)
  253. {
  254. if (ptrav->pleft->name[i] == code[0])
  255. {
  256. ptrav = ptrav->pleft;
  257. break;
  258. }
  259. if (ptrav->pright->name[i] == code[0])
  260. {
  261. ptrav = ptrav->pright;
  262. break;
  263. }
  264. }
  265.  
  266. }
  267. pnn = ptrav;
  268. for (int i = 0; i < 256; i++)
  269. {
  270. if (pnn->name[i] != ' ')
  271. {
  272. cout << pnn->name[i];
  273. }
  274. else
  275. {
  276. break;
  277. }
  278. }
  279. cout << " : " << pnn->frequency << endl;
  280. }
  281.  
  282. void searchEnc(cnode *pnn, cnode *pnn2)
  283. {
  284. cnode *ptrav;
  285. ptrav = pnn;
  286. string encryption;
  287. char code[1];
  288. int flag = 0;
  289. code[0] = pnn2->name[0];
  290. while (ptrav->pleft != NULL && ptrav->pright != NULL)
  291. {
  292. for (int i = 0; i < 256; i++)
  293. {
  294. if (ptrav->pleft->name[i] == code[0])
  295. {
  296. ptrav = ptrav->pleft;
  297. encryption += '0';
  298. break;
  299. }
  300. if (ptrav->pright->name[i] == code[0])
  301. {
  302. ptrav = ptrav->pright;
  303. encryption += '1';
  304. break;
  305. }
  306. }
  307. }
  308. pnn = ptrav;
  309. for (int i = 0; pnn->name[i] != '\0'; i++)
  310. {
  311. if (pnn->name[i] != '\0')
  312. {
  313. cout << pnn->name[i];
  314. }
  315. }
  316. pnn2->encryption = encryption;
  317. cout << " : " << pnn2->frequency << " : " << pnn2->encryption << endl;
  318. }
  319.  
  320. };
  321.  
  322. int main()
  323. {
  324. cnode *pnn;
  325. cnode *t, *t2;
  326. clist l, lcopy;
  327. int c = 0, flag = 0, n;
  328. //string p;
  329.  
  330. //getline(cin, p);
  331. ofstream fl2("decompressed.png", ofstream::binary);
  332. ifstream fl("2.png", ifstream::binary);
  333. fl.seekg(0, fl.end);
  334. int h = fl.tellg();
  335. cout << h << endl;
  336. fl.seekg(0, fl.beg);
  337. string p = "";
  338. char cpto = 0;
  339.  
  340. char ch = 0;
  341. for (int i = 0; i < h; i++)
  342. {
  343. fl.read(&ch, 1);
  344. p += ch;
  345. //fl2.write(&ch, 1);
  346. }
  347.  
  348. /*for (int i = 0; i < h; i++)
  349. {
  350. fl2.write(&word[i], 1);
  351. }*/
  352.  
  353. pnn = new cnode;
  354. pnn->name[0] = p[0];
  355. pnn->name[1] = '\0';
  356. pnn->frequency = 1;
  357. for (int i = 1; i < p.length(); i++)
  358. {
  359. if (p[i] == pnn->name[0])
  360. {
  361. pnn->frequency++;
  362. }
  363. }
  364. l.Attach(pnn);
  365. c++;
  366.  
  367. for (int i = c; i < p.length(); i++)
  368. {
  369. t = l.phead;
  370. while (t != NULL)
  371. {
  372. if (p[c] == t->name[0])
  373. {
  374. flag = 1;
  375. break;
  376. }
  377. t = t->pnext;
  378. }
  379. if (flag != 1)
  380. {
  381. pnn = new cnode;
  382. pnn->name[0] = p[c];
  383. pnn->name[1] = '\0';
  384. pnn->frequency = 0;
  385. for (int i = c; i < p.length(); i++)
  386. {
  387. if (p[i] == pnn->name[0])
  388. {
  389. pnn->frequency++;
  390. }
  391. }
  392. l.sortAttach(pnn);
  393. }
  394. flag = 0;
  395. c++;
  396.  
  397. }
  398.  
  399. t = l.phead;
  400. while (t != NULL)
  401. {
  402. cout << t->name[0] << " : " << t->frequency << endl;
  403. t = t->pnext;
  404. }
  405.  
  406.  
  407.  
  408. //show nodes
  409. cout << endl << "-------------------------------" << endl;
  410. t = l.phead;
  411. while (t != NULL)
  412. {
  413. for (int i = 0; i < 256; i++)
  414. {
  415. if (t->name[i] != '\0')
  416. {
  417. cout << t->name[i];
  418. }
  419. else
  420. {
  421. break;
  422. }
  423. }
  424. cout << " : " << t->frequency << endl;
  425. t = t->pnext;
  426. }
  427.  
  428.  
  429. t = l.phead;
  430. while (t->pnext != NULL)
  431. {
  432. t2 = l.phead;
  433. l.combine(t, t2);
  434. t = t->pnext;
  435. t = t->pnext;
  436. l.phead = t;
  437. }
  438.  
  439. //show first root
  440. t = l.phead;
  441. cout << endl << "-------------------------------" << endl << "First root : ";
  442. for (int i = 0; i < 256; i++)
  443. {
  444. if (t->name[i] != '\0')
  445. {
  446. cout << t->name[i];
  447. }
  448. else
  449. {
  450. break;
  451. }
  452. }
  453. cout << " : " << t->frequency << endl;
  454.  
  455. //functions
  456. cout << endl << "-------------------------------" << endl;
  457. t = l.phead->pdown;
  458.  
  459.  
  460. c = 0;
  461. pnn = new cnode;
  462. pnn->name[0] = p[0];
  463. pnn->name[1] = '\0';
  464. pnn->frequency = 1;
  465. for (int i = 1; i < p.length(); i++)
  466. {
  467. if (p[i] == pnn->name[0])
  468. {
  469. pnn->frequency++;
  470. }
  471. }
  472. lcopy.Attach(pnn);
  473. c++;
  474. for (int i = c; i < p.length(); i++)
  475. {
  476. t = lcopy.phead;
  477. while (t != NULL)
  478. {
  479. if (p[c] == t->name[0])
  480. {
  481. flag = 1;
  482. break;
  483. }
  484. t = t->pnext;
  485. }
  486. if (flag != 1)
  487. {
  488. pnn = new cnode;
  489. pnn->name[0] = p[c];
  490. pnn->name[1] = '\0';
  491. pnn->frequency = 0;
  492. for (int i = c; i < p.length(); i++)
  493. {
  494. if (p[i] == pnn->name[0])
  495. {
  496. pnn->frequency++;
  497. }
  498. }
  499. lcopy.sortAttach(pnn);
  500. }
  501. flag = 0;
  502. c++;
  503.  
  504. }
  505.  
  506.  
  507. t2 = lcopy.phead;
  508. while (t2 != NULL)
  509. {
  510. t = l.phead->pdown;
  511. l.searchEnc(t, t2);
  512. t2 = t2->pnext;
  513. }
  514.  
  515. clist lencypt;
  516. char m, stemp = 0, comp[500000];
  517. int iBit = 7;
  518. c = 0;
  519. for (int i = 0; i < h; i++)
  520. {
  521. t = lcopy.phead;
  522. while (t->name[0] != p[i])
  523. {
  524. t = t->pnext;
  525. }
  526. for (int k = 0; k < t->encryption.length(); k++)
  527. {
  528. if (iBit == -1)
  529. {
  530. comp[c] = stemp;
  531. c++;
  532. iBit = 7;
  533. stemp = 0;
  534. }
  535. if (t->encryption[k] == '0')
  536. {
  537. m = 0;
  538. }
  539. else
  540. {
  541. m = 1;
  542. }
  543. stemp = stemp | (m << iBit);
  544. iBit--;
  545. }
  546. if ((i + 1) == h)
  547. {
  548. comp[c] = stemp;
  549. //comp[c + 1] = '\0';
  550. c++;
  551. }
  552. }
  553.  
  554. cout << endl << "-------------------------------" << endl;
  555. for (int i = 0; i<(c+1); i++)
  556. {
  557. cout << comp[i];
  558. }
  559. cout << endl << endl;
  560.  
  561. clist lcomp;
  562. char res, decomp[500000];
  563. string check, null;
  564. int cc = (c+1);
  565. c = 0;
  566. for (int i = 0; i<cc; i++)
  567. {
  568.  
  569. cout << i << endl;
  570. stemp = comp[i];
  571. iBit = 7;
  572. while (iBit != -1)
  573. {
  574. char res = stemp & (1 << iBit);
  575. if (res != 0)
  576. {
  577. pnn = new cnode;
  578. pnn->name[0] = '1';
  579. pnn->pnext = NULL;
  580. lcomp.Attach(pnn);
  581. }
  582. else
  583. {
  584. pnn = new cnode;
  585. pnn->name[0] = '0';
  586. pnn->pnext = NULL;
  587. lcomp.Attach(pnn);
  588. }
  589. t = lcopy.phead;
  590. t2 = lcomp.phead;
  591. check = null;
  592. while (t2 != NULL)
  593. {
  594. check += t2->name[0];
  595. t2 = t2->pnext;
  596. }
  597.  
  598. //check encry
  599. while (t != NULL)
  600. {
  601. if (check == t->encryption)
  602. {
  603. if (c != h)
  604. {
  605. decomp[c] = t->name[0];
  606. fl2.write(&t->name[0], 1);
  607. c++;
  608. lcomp.phead = NULL;
  609. }
  610. break;
  611. }
  612. t = t->pnext;
  613. }
  614. iBit--;
  615. }
  616. }
  617. cout << endl << endl;
  618.  
  619.  
  620. system("pause");
  621. return 0;
  622. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement