Thema: [C#] Huffman

  1. #1

    Registriert seit
    09.11.2011
    Beiträge
    121
    Thanked 129 Times in 46 Posts

    Standard [C#] Huffman

    Nachdem SeBi Huffman in C# (mit einem selten auftretenden Fehler) gepostet hat:

    Hier meine Version - habe es auf meiner Festplatte entdeckt, ist irgendwann aus 2018.

    2 Klassen: KHuffman & BitStream

    KHuffman.cs V1 (mit Baum als String):
    Spoiler:


    using System;
    using System.Collections.Generic;
    using System.Text;

    namespace DeinTollesProjekt
    {
    class KHuffman
    {
    private readonly BinaryNode DecRoot;
    private String _16BitChar;
    private int _16BitCharPath;
    private int _16BitCharPathLen;
    private readonly char[] CharBuffer;
    private Dictionary<char, Pair<Path, Object>> EncMap;
    private readonly String Tree = KHuffman.DecodeForObfuscatorBug("\by\u00ef|/serverpp \"\u001ett\tD!ea\"ud\u000f\u0083\u0011\u0437\u0012\u00da\u0012\u00de\u0010\u20ac\u000f\u203e\u000f\u0085!\u00fcr\f\u00c85Ste5eck\u001f06_Mafia\"67\"NI\"lb\"ou\u0006#\u0005\n\u0004°\u001fsi4pla\u001fti4for\b\f5boy\u000b\r5man!Kl\"97\"ub5urg5kte OK ue\bb op!ev!Ob6per!Ko Mo]_°>_h\bm\u001fdi\u001fra\u000bj\u000f\u0082\u0012\u03ca\u0012\u00d9\u0011\u00c6\u0010\u0161\u000f¹\u0010\u25ac\u0011\u00c9\u0011\u00f8\"53\"lh\u000e\u2022\u000e`\u001fpy\u001e13\u001enn\u0007\u00e3 rc\u00c8_nicklist_ ef5bra\u001fee5ten nc4?d= Wo\"77\r\u00fa!944ing\u000b\u000e 02\u001fDe\u001fau!Ru\"oy\"km5eig Es!ks!Ol\b5\tE\u001fii\u000b\u0016\"mf\"Fo\"sk\u0010²\u0011\u255d\u0011\u009e\u0012\ufb7c\u0012\ufea1\u0012\ufea6\u0012\u2019\u0011\u0119\u0012\ufb8e\u0012\ufef6\u000e\u0015 Er6use!On ol!89\"k\u00f6\"Ze4art\u001fri\bw co\u000e\u0019\u000e\u00c4\"Ct!va\u001fbi4lin hr id do nk xx\"wb\u000e\u0018\u0010\u043a\u0010\u00cd\u000f\u008b\"ph\"fw5noc we4yer\u001ffe ko ht\u001fmi5100 31\u00073\u0007l\nW\u001ffc\"k\u00fc\u000f\u0432\u0010\u00f9\u0012\u0493\u0012\u2122\u0011\u0430\u000e´!iz 09\u001fBN\u001eim\t\u0001\u00012\u00010p\u00010!Kr\"Oo\"eg5Pun yl eh Ro Su!xe6hel5hlt\u001fet\u001fsm\nM pa 38\tz!Fl!48 uf5Knu Ni hi\"lz\r\u00dc6her So\"S\u00fc\"uh\u000f\u2192\u000f\u2591\u000e\u043d\"r\u00fc\u001eFh4Min\u001fba\u001fpl^0,0,0\u001e17\u001e 5bin!Gl!NusMafia2\u001fda!Rh6ken Sl\nI\u0089knuddel Fb\u001fBo!To\"za\u0010\u0192\u0011µ\u0011\u2593\u000f\u0086\u000e\u0438!Go!565ois ce\nN 03!rb!hn5rie!Je!Dr\b45Fu\u00df!Ju\"ny\"Yo\u001f365hei\"58\"ov\f$\u001fBB\b&^Bingo5lie!by!Ig4ste\n\u0011\u00072\nG ic6kle\u0012\ufefb\u0012\u042f\u0011\u0452\u0010\u00e0\u0010\u06d7\u0012\u0435\u0012\u00c1\u0012\u00d5\u0012\u2502\u0011\u00ee\u0011\u2554\u0010\u007f\u000f\u00d6\"64\u001fse\u001f23\u001fng wa!D\u00fc!fl\u001far rs Bi\u0084\u00010p\u00010B\u00010-\u00010\u0007\u00f5\u0007,\b\u00c24ute\u001fve\n@!sl!ac He\u0007B\u001d20 Wi\"cl\"M\u00f6!dm\u001fMa\u001ele\u0007i ot\"sc\"uu\f\t\nS5geb Me\u00ff\u0010\u000bfemale.b.my_4.gif tl\u001e164cht\"l\u00e4\"pu\"sb\"515Fif 905erh4255\nK\u001fig\b|\u001ema 29\"Am\u000f\u266b\u0010\u203a\u0011\u009d\u0011 \u0011\u00fe\u0011\u2190\u0011\u0099\u0011\u0141\u000f\u043c!K\u00f65von Ki\"\u00e4u\"Ce\"78\"Gi nu4gen du6Mar!ru!vo!ju\r\u2113\"bs6uhp\u00dbFotoContest Cp6tor6rea ziJkann\u001ell\t?\b\u00fb\b¾ mp!ln6Spi\u001fus\u001est!rf\r\u0006\r\u008f ff sh!44!Ic4hat ja6.w_\f\u0014\bg 27\"Ar\r\u0454!\u00fcb\u001fie\u001e106Und6ies!91\u000e¶\u000f\u00e9\u0010\u00d8\u0012\u014b\u0012\u2580\u0011\u00e7\"II go!ob\f'\u00dbknuddels.de\bx\n[5nge!lt\"88\"Zi Na Fa\n]\b¼\n\u00e45ausJsichHicon\t6\f\u2588!Gr po\u001f30\u0007>4Sch6par!ey!Ga6Nor]mafia\u001e12!Ja!s\u00fc\u000f¸\u000f\u008a\u000f\u001b\u000f\u0087\"\u00f6n6mag4ver Ge\u000b¤\u001f22!ag\"72\u000e\u0090\u000f\u00f4\u000f\u00885hal\u001f21 ro!Ps\"59\"Fu\u001fla 60\u000bP5Stu!mu\"Aa\"62\u0007n\u0007: dt6ONL!92^|/go \u0088Channel5bei Hi\t\u0002\t8\tf4200\"fo\"hm6ros gl\b0!496ens 346swh!bt\"HP\u0012\u00d3\u0012\u2592\u0012\u00c7\u0012\u00d1\u0011\u221a\u0011\u2193\u000f\u00e2\u0010±\u0010\u039e\u000f\u00846Bad\u001fed\f\u000f6tdeJ.png\td!mb!kn Da ir6GirK2009\u001d005Pri6Bre!Te\"Ve\"54!Sh5Who!ft!Ne Xx^James Cl mo6ang\f\u00cc!Wu!04\t9J0065\"CH\"ci!gh\u001fke!ur!ak!ia!wu^pics/4den Lo5sta\"GB7sbu\"oh\"qu Sa\u001fli\ta\nO!Fe\"xy\u0012£\u0012\u043e\u0011\u009a\u0010©\u0011\u00f7\u0011\u2557\u0012\u2500\u0012\u201c\u0012\u00ad\u0012½\u000f«\u0011\u255a\u0012\u00cb\u0012\u00f2\u0011¥\u0011\u00f3Jnich6bes!tc\f¬\f\u26655men St4bur\u001frt!93!Wa!Ti!07 ga!ds\"99\"Mu3sch!Jo6Her\"gg\"vb!ib5ent\"87\"ya!lf or!eb!aw\u000b\u0012 tz\u001dch!rl\u009f.shadow_ sp!to!oo\u000b*\u001e15\to\"nf\"86!956INE!SiJFoto!ys\"96\u000f\u001a\u000f\u001f\u000f\u0098\u0010\u00e1\u0011\u00d4\u0012\u0457\u0012\u00ec\u0007r4ist6Lad6Mom!Th6Pro ka Ch\u001fni\u001essI.my_ vi6Mon!pi!Qf\"oc\"sg\"Ta\"tw\"if\"zz\u001fna!Au!ai\u009eKnuddels\nXG°>_h#ug#My\"Pe\"ex\"No Ka no\"xt\"hp\"kr\"Pu\u001e18\tR5Sin An\"Ri7sel6bea!Vo\"ah\"Qu\u0007+\nc!ts!Tr We\nL\u00f1icon_gender_\u001fme5.h_6www\"yo\"hu\u00ff\f\n|/fotowhois \"5mit so\b\u000b4Fre6max6reg!Va6wer\nu6wieuicons/!En\u000f\u2550\u0010\u0095\u0010\u00d7\u000e\u009f\"jo\u0007%\u00dc255,255,255 ei!dr!ip Du\"kf\"57!Pl\u001flo5Sta\u000e\u03b1\u000f\u001d\u0011\u03c4\u0011\u00d2\u0010\u0091\"ER!ku ls6act!Fr\n\\\u00ff\u0013\u000bfotos/knuddels.de?n=\u000bH2 !Lu6dem5end#B\u00fc#ap\"746chl5gle\u001e40\t!\u001e324ein5sei!Ke\f\u00df fg5bal\u001fta\u001e194nde6Men6Lie ad\u001fSf\n§\u001ein#ec\u000f\u001e\u0010\u2039\u0011\u00dd\u0012¦\u0012\u00ea\u000e\u03b9#H\u00fc!os rnJ.mx_5wei\u001e..6ler!rk\u000bq\"tf\"Un!Po5Ver\tp\u0007/\f}#dw\u000f\u0455\u0010\u0092\u0010\u00eb\"az!lu!Fi!kl!wo 80\u00ff \t\u00010p\u00010B\u00010pics/icon_fullChannel.gif\u00010-\u00010\u001eel\u001fty6Neu\"52\"lm 01q|/w \"<´.quadcut_#69#d\u00e4\"tu6fre\"ih#ez#98\u001fte5gir5cnt\u009e.border_ it\u000bY\u00ff\u000e\u000bfullChannel.gif\"zo\"kc\"Ab\u000f\u03c5\u0012\u25aa\u0013\u2569\u0013\u212e\u0011\u00ca\u0010\u008d#82 33\u001fnd\nF Sp\u000b^6ach!uc ki4ich7fel#83\u000f¿\u000f\u00db!br6Fri6dor\u001fde\u001f50!aa\"gb\"lc6f\u00fcr!75 th5Ber6Bal!70!45\"Sw\"41 il6hfl\"Ih\r~\u00ff\u000e\npics/female.gif5htt\u0010\u266a\u0012¡\u0012\u00e8\u0012\u0131\u0013\u2014>\\\\\\\u0014\u04d9\u000f·#At#LE#SkK2010G.gifJfoto6Lan\r\u0013\"ik\u00c7°>gt.gif<° Ho\"dy\"Pi6alt 28J.jpg\u0007e\bs El6mer\u00ff\u000e\fmale.b.my_3.gif\u0088\u00010Flirt \u000e\u044f#76\"nb!La ns!rg!08 Be\u000bv\"ml#cd#73!Bu tr wi\u001fmm!sf6Die nt ly!em6tmu\"od\"sd6Kis\"DD\u0010\u0097\u0011¨\u0011\u00ce\u000f\u03b7#68\fQ\u001fge#84#FC\"gs!Ra!su\"iv#hh#Pr\u0007<\u001fha\u001fon\nT4che\bh\u0007\"\u00ff\r\fcloudsblue.gif\"Ci\r\u00037lig\u000e\u0017\u0010\u008e\u0010\u0096\u0012\u00f1\u0012\u00fd\u0012®\u0012\u0443\u0013\u03ae\u0013\u0130\u0013\u0142\u0013\u0144\u0011\u03c1!bb5ber Li!Di\r¯\"lg!Al6Out 24 un 397urt#Is#Rf!71!hl!Bl Ba5ear6ech\"Us\"476ipi\f; ze\u0007.\t7\u001fat\"w\u00e4#Hu\u000f\u2202\u0010º\u0011\u00f0\u0011\ufef9!\u00dfe!ut!fuI>--<\u001fan Le sa\r\u0004\"gt!je5pwd Re he ho\"om\"ok!554war5hen\"pe#ek#LL!bu\u001fre\"w\u00fc\"66!Se\u000bZ!\u00fcc\"Cr\"gu zu\fJ\"m\u00e4\"42!bo!Ca\u001fes6Tag#RR#ry\r\u0005 26\"rr\"of6Dor5res5cgi!dd\u00ff9\f|http://www3.knuddels.de:8080/txtl/click?d=knuddels.de&id=!Sm\"43\"af5ine!Co\u0012ª\u0012³\u0011\u03a3\u0010\u0089\u000f»#CE\"lk am pp!sw#63#my#pf\u0011\u009c\u0011\u00e6\u0010\u008c\u000f\u001c6fhe\r\b\"Vi5ter\n\u00ff\u001f11!fa#sr#Mf\r\u0010`°>sm_6Anz\nA as#NR#lr#NT#61!nz!ab!gi6dpg!gr\t(\u00ff\f\npics/male.gif pg#Cu\u0013\u03b4\u0013\u03c2\u0013\u06da\u0013\u2194\u0012\u0456\u0012\u25ba\u0011\u06d6\u0013\u0111\u0013\u0127\u0013\u01a7\u0013\u06d9\u0012\u03bd\u0012\u0441\u0011\u00cf\u0011\u00ed\u0012\u25cf\u0012\u201d\"Os!ow\u001fck\u000b\u00e5 Ha#gd#It\"kt6len!Ei\r\u0007\"fr\nC\t)6min6Sie\f{\"65\"M\u00fc\u000b\u00f6#N\u00fc#Do\"io!Pf6das\fV_Flirt\u000b\u00fc\"rz#Gu#fm6Ham\bt\u001den\u001der\u0004\u000104der!Cc6Alt5Mix#As#tp7nen!ld 05\u001fis\u000b\u00c3\"L\u00fc\u000f\u06d8\u000f\u06e1\u000f\u06e2\u000f¢6Ges6auf6and6blg!pr4und\u001fal\"In\"W\u00fc6hie6ges\"\u00f6\u00df\"ps\u001fbe 256140#hs\u0010\u03c9\u0010\u00ef\u0010\u0093\u0010\u03c3\"46\n\u0080\u001f14 35!Em6ger\u001fcg\nk\u0006-\"wh#rp\u0011\u0094\u0012\u039b\u0012\u009b\u0010\u2551\u0010\u0081\u0011\u00d0\u0013\u011f\u0013\u018f\u0013\u25a0\u0013\u25c4!Pa\u000bU bl!ca6vat!37\"eu\"ms!Mi!cs5die!ay!fi\n\u00c0 um5sen\t=!Br\"ul\"fy5vor!Wl6tsc rd\u001fne\"Ku\u000f\u03b5\u000f\u0442#R\u00fc6Par#85#wc\"cr!rm\b1\u0006_\u0004 ");

    public KHuffman()
    {
    this.DecRoot = new BinaryNode();
    this.CharBuffer = new char[65535];
    this.EncMap = new Dictionary<char, Pair<Path, Object>>();
    this.CreateTree();
    }

    private static String DecodeForObfuscatorBug(String s)
    {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.Length; ++i)
    {
    char c = s[i];
    if (c == '\u0001')
    {
    ++i;
    c = s[i];
    if (c == '0')
    {
    sb.Append('\0');
    continue;
    }
    }
    sb.Append(c);
    }
    return sb.ToString();
    }

    private void CreateTree()
    {
    int m = 1;
    int n = -33;
    int strLen;
    for (int i = 0; i < this.Tree.Length; i += strLen)
    {
    int temp = this.Tree[i++];
    int pathLen;
    if (temp == 255)
    {
    strLen = this.Tree[i++] + '\u0001';
    pathLen = this.Tree[i++];
    }
    else
    {
    strLen = temp / 21 + 1;
    pathLen = temp % 21;
    }
    if ((m & 0x1) == 0x0)
    {
    ++m;
    }
    else
    {
    while ((m & 0x1) == 0x1)
    {
    m >>= 1;
    --n;
    }
    ++m;
    }
    while (n < pathLen)
    {
    m <<= 1;
    ++n;
    }
    String str = this.Tree.Substring(i, strLen);
    int path = this.ReverseBits(m, pathLen);
    if (strLen == 3 && str.Equals("\\\\\\"))
    {
    this._16BitChar = str;
    this._16BitCharPath = path;
    this._16BitCharPathLen = pathLen;
    }
    this.AddString(str, path, pathLen);
    if (!this.Put(this.DecRoot, str, path, pathLen))
    {
    throw new Exception("error while creating tree (invalid path)");
    }
    }
    }

    private int ReverseBits(int x, int pathLen)
    {
    int rv = 0;
    for (int i = 0; i < pathLen; ++i, x >>= 1)
    {
    rv = (rv << 1 | (x & 0x1));
    }
    return rv;
    }

    private bool Put(BinaryNode node, String str, int path, int pathLen)
    {
    if (pathLen == 0)
    {
    node.SetData(str);
    return node.IsLeaf();
    }
    if (node.IsEmpty())
    {
    if (node.IsLeaf())
    {
    return false;
    }
    node.SetZero(new BinaryNode());
    node.SetOne(new BinaryNode());
    }
    return this.Put(((path & 0x1) == 0x0) ? node.GetZero() : node.GetOne(), str, path >> 1, pathLen - 1);
    }

    private void AddString(String str, int path, int pathLen)
    {
    Dictionary<char, Pair<Path, Object>> current = this.EncMap;
    for (int i = 0; i < str.Length; ++i)
    {
    char _char = str[i];
    char character = this.CharBuffer[_char];
    if (character == 0) // character == null
    {
    this.CharBuffer[_char] = _char;
    character = _char;
    }
    Pair<Path, Object> child = null;

    if (current.ContainsKey(character)) child = current[character];

    if (child == null)
    {
    Dictionary<char, Pair< Path, Object >> map = new Dictionary<char, Pair<Path, Object>>();
    current.Add(character, child = new Pair<Path, Object>(null, map));
    current = map;
    }
    else
    {
    current = (Dictionary<char, Pair<Path, Object>>)child.GetValue();
    }
    if (i == str.Length - 1)
    {
    child.SetKey(new Path(path, pathLen));
    }
    }
    }

    public String Decompress(byte[] data)
    {
    BitStream bitStream = new BitStream(data);
    BinaryNode tempNode = this.DecRoot;
    StringBuilder output = new StringBuilder();
    while (bitStream.HasNext())
    {
    tempNode = ((bitStream.NextBit() == 0) ? tempNode.GetZero() : tempNode.GetOne());
    if (!tempNode.IsLeaf())
    {
    continue;
    }
    if (tempNode.GetData().Equals(this._16BitChar))
    {
    int _char = 0;
    for (int k = 0; k < 16; ++k)
    {
    _char += bitStream.NextBit() << k;
    }
    output.Append((char)_char);
    }
    else
    {
    String str = tempNode.GetData();
    output.Append(str);
    }
    tempNode = this.DecRoot;
    }
    return output.ToString();
    }

    public byte[] Compress(String str)
    {
    BitStream output = new BitStream();
    Dictionary<char, Pair<Path, Object>> current = this.EncMap;
    int previous = -1;
    int previousLen = -1;
    int previousPos = -1;
    for (int i = 0; i < str.Length; ++i)
    {
    char _char = str[i];
    char character = this.CharBuffer[_char];
    if (character == 0) // character == null
    {
    this.CharBuffer[_char] = _char;
    character = _char;
    }
    Pair<Path, Object> temp = null;
    if (current.ContainsKey(character)) temp = current[character];

    if (temp == null)
    {
    if (previous == -1)
    {
    output.AddBits(this._16BitCharPath, this._16BitCharPathLen);
    output.AddBits(_char, 16);
    previousPos = i;
    }
    else
    {
    output.AddBits(previous, previousLen);
    }
    previous = -1;
    i = previousPos;
    current = this.EncMap;
    }
    else
    {
    if (temp.GetKey() != null)
    {
    previous = temp.GetKey().GetPath();
    previousLen = temp.GetKey().GetPathLen();
    previousPos = i;
    }
    if (temp.GetValue() != null)
    {
    current = (Dictionary<char, Pair<Path, Object>>)temp.GetValue();
    }
    }
    }
    if (previous >= 0)
    {
    output.AddBits(previous, previousLen);
    }
    return output.ToByteArray();
    }

    private class BinaryNode
    {
    private BinaryNode zero;
    private BinaryNode one;
    private String data;

    public bool IsLeaf()
    {
    return this.data != null && this.IsEmpty();
    }

    public bool IsEmpty()
    {
    return this.zero == null && this.one == null;
    }

    public void SetData(String data)
    {
    this.data = data;
    }

    public String GetData()
    {
    return this.data;
    }

    public BinaryNode GetZero()
    {
    return this.zero;
    }

    public void SetZero(BinaryNode left)
    {
    this.zero = left;
    }

    public BinaryNode GetOne()
    {
    return this.one;
    }

    public void SetOne(BinaryNode right)
    {
    this.one = right;
    }
    }

    private class Pair<K, V>
    {
    private K key;
    private V value;

    public Pair(K key, V value)
    {
    this.key = key;
    this.value = value;
    }

    public K GetKey()
    {
    return this.key;
    }

    public V GetValue()
    {
    return this.value;
    }

    public void SetKey(K key)
    {
    this.key = key;
    }
    }

    private class Path
    {
    private int path;
    private int pathLen;

    public Path(int path, int pathLen)
    {
    this.path = path;
    this.pathLen = pathLen;
    }

    public int GetPath()
    {
    return this.path;
    }

    public int GetPathLen()
    {
    return this.pathLen;
    }
    }
    }
    }



    KHuffman.cs V2 (mit Baum als char-array, weil das U-Labs-Plugin die Tree-Zeichenkette beim Kopieren verändert...):

    Spoiler:


    using System;
    using System.Collections.Generic;
    using System.Text;

    namespace DeinTollesProjekt
    {
    class KHuffman
    {
    private readonly BinaryNode DecRoot;
    private String _16BitChar;
    private int _16BitCharPath;
    private int _16BitCharPathLen;
    private readonly char[] CharBuffer;
    private Dictionary<char, Pair<Path, Object>> EncMap;
    private readonly String Tree = new string(new char[] { (char)8, (char)121, (char)239, (char)124, (char)47, (char)115, (char)101, (char)114, (char)118, (char)101, (char)114, (char)112, (char)112, (char)32, (char)34, (char)30, (char)116, (char)116, (char)9, (char)68, (char)33, (char)101, (char)97, (char)34, (char)117, (char)100, (char)15, (char)131, (char)17, (char)1079, (char)18, (char)218, (char)18, (char)222, (char)16, (char)8364, (char)15, (char)8254, (char)15, (char)133, (char)33, (char)252, (char)114, (char)12, (char)200, (char)53, (char)83, (char)116, (char)101, (char)53, (char)101, (char)99, (char)107, (char)31, (char)48, (char)54, (char)95, (char)77, (char)97, (char)102, (char)105, (char)97, (char)34, (char)54, (char)55, (char)34, (char)78, (char)73, (char)34, (char)108, (char)98, (char)34, (char)111, (char)117, (char)6, (char)35, (char)5, (char)10, (char)4, (char)176, (char)31, (char)115, (char)105, (char)52, (char)112, (char)108, (char)97, (char)31, (char)116, (char)105, (char)52, (char)102, (char)111, (char)114, (char)8, (char)12, (char)53, (char)98, (char)111, (char)121, (char)11, (char)13, (char)53, (char)109, (char)97, (char)110, (char)33, (char)75, (char)108, (char)34, (char)57, (char)55, (char)34, (char)117, (char)98, (char)53, (char)117, (char)114, (char)103, (char)53, (char)107, (char)116, (char)101, (char)32, (char)79, (char)75, (char)32, (char)117, (char)101, (char)8, (char)98, (char)32, (char)111, (char)112, (char)33, (char)101, (char)118, (char)33, (char)79, (char)98, (char)54, (char)112, (char)101, (char)114, (char)33, (char)75, (char)111, (char)32, (char)77, (char)111, (char)93, (char)95, (char)176, (char)62, (char)95, (char)104, (char)8, (char)109, (char)31, (char)100, (char)105, (char)31, (char)114, (char)97, (char)11, (char)106, (char)15, (char)130, (char)18, (char)970, (char)18, (char)217, (char)17, (char)198, (char)16, (char)353, (char)15, (char)185, (char)16, (char)9644, (char)17, (char)201, (char)17, (char)248, (char)34, (char)53, (char)51, (char)34, (char)108, (char)104, (char)14, (char)8226, (char)14, (char)96, (char)31, (char)112, (char)121, (char)30, (char)49, (char)51, (char)30, (char)110, (char)110, (char)7, (char)227, (char)32, (char)114, (char)99, (char)200, (char)95, (char)110, (char)105, (char)99, (char)107, (char)108, (char)105, (char)115, (char)116, (char)95, (char)32, (char)101, (char)102, (char)53, (char)98, (char)114, (char)97, (char)31, (char)101, (char)101, (char)53, (char)116, (char)101, (char)110, (char)32, (char)110, (char)99, (char)52, (char)63, (char)100, (char)61, (char)32, (char)87, (char)111, (char)34, (char)55, (char)55, (char)13, (char)250, (char)33, (char)57, (char)52, (char)52, (char)105, (char)110, (char)103, (char)11, (char)14, (char)32, (char)48, (char)50, (char)31, (char)68, (char)101, (char)31, (char)97, (char)117, (char)33, (char)82, (char)117, (char)34, (char)111, (char)121, (char)34, (char)107, (char)109, (char)53, (char)101, (char)105, (char)103, (char)32, (char)69, (char)115, (char)33, (char)107, (char)115, (char)33, (char)79, (char)108, (char)8, (char)53, (char)9, (char)69, (char)31, (char)105, (char)105, (char)11, (char)22, (char)34, (char)109, (char)102, (char)34, (char)70, (char)111, (char)34, (char)115, (char)107, (char)16, (char)178, (char)17, (char)9565, (char)17, (char)158, (char)18, (char)64380, (char)18, (char)65185, (char)18, (char)65190, (char)18, (char)8217, (char)17, (char)281, (char)18, (char)64398, (char)18, (char)65270, (char)14, (char)21, (char)32, (char)69, (char)114, (char)54, (char)117, (char)115, (char)101, (char)33, (char)79, (char)110, (char)32, (char)111, (char)108, (char)33, (char)56, (char)57, (char)34, (char)107, (char)246, (char)34, (char)90, (char)101, (char)52, (char)97, (char)114, (char)116, (char)31, (char)114, (char)105, (char)8, (char)119, (char)32, (char)99, (char)111, (char)14, (char)25, (char)14, (char)196, (char)34, (char)67, (char)116, (char)33, (char)118, (char)97, (char)31, (char)98, (char)105, (char)52, (char)108, (char)105, (char)110, (char)32, (char)104, (char)114, (char)32, (char)105, (char)100, (char)32, (char)100, (char)111, (char)32, (char)110, (char)107, (char)32, (char)120, (char)120, (char)34, (char)119, (char)98, (char)14, (char)24, (char)16, (char)1082, (char)16, (char)205, (char)15, (char)139, (char)34, (char)112, (char)104, (char)34, (char)102, (char)119, (char)53, (char)110, (char)111, (char)99, (char)32, (char)119, (char)101, (char)52, (char)121, (char)101, (char)114, (char)31, (char)102, (char)101, (char)32, (char)107, (char)111, (char)32, (char)104, (char)116, (char)31, (char)109, (char)105, (char)53, (char)49, (char)48, (char)48, (char)32, (char)51, (char)49, (char)7, (char)51, (char)7, (char)108, (char)10, (char)87, (char)31, (char)102, (char)99, (char)34, (char)107, (char)252, (char)15, (char)1074, (char)16, (char)249, (char)18, (char)1171, (char)18, (char)8482, (char)17, (char)1072, (char)14, (char)180, (char)33, (char)105, (char)122, (char)32, (char)48, (char)57, (char)31, (char)66, (char)78, (char)30, (char)105, (char)109, (char)9, (char)1, (char)50, (char)0, (char)112, (char)0, (char)33, (char)75, (char)114, (char)34, (char)79, (char)111, (char)34, (char)101, (char)103, (char)53, (char)80, (char)117, (char)110, (char)32, (char)121, (char)108, (char)32, (char)101, (char)104, (char)32, (char)82, (char)111, (char)32, (char)83, (char)117, (char)33, (char)120, (char)101, (char)54, (char)104, (char)101, (char)108, (char)53, (char)104, (char)108, (char)116, (char)31, (char)101, (char)116, (char)31, (char)115, (char)109, (char)10, (char)77, (char)32, (char)112, (char)97, (char)32, (char)51, (char)56, (char)9, (char)122, (char)33, (char)70, (char)108, (char)33, (char)52, (char)56, (char)32, (char)117, (char)102, (char)53, (char)75, (char)110, (char)117, (char)32, (char)78, (char)105, (char)32, (char)104, (char)105, (char)34, (char)108, (char)122, (char)13, (char)220, (char)54, (char)104, (char)101, (char)114, (char)32, (char)83, (char)111, (char)34, (char)83, (char)252, (char)34, (char)117, (char)104, (char)15, (char)8594, (char)15, (char)9617, (char)14, (char)1085, (char)34, (char)114, (char)252, (char)30, (char)70, (char)104, (char)52, (char)77, (char)105, (char)110, (char)31, (char)98, (char)97, (char)31, (char)112, (char)108, (char)94, (char)48, (char)44, (char)48, (char)44, (char)48, (char)30, (char)49, (char)55, (char)30, (char)32, (char)32, (char)53, (char)98, (char)105, (char)110, (char)33, (char)71, (char)108, (char)33, (char)78, (char)117, (char)115, (char)77, (char)97, (char)102, (char)105, (char)97, (char)50, (char)31, (char)100, (char)97, (char)33, (char)82, (char)104, (char)54, (char)107, (char)101, (char)110, (char)32, (char)83, (char)108, (char)10, (char)73, (char)137, (char)107, (char)110, (char)117, (char)100, (char)100, (char)101, (char)108, (char)32, (char)70, (char)98, (char)31, (char)66, (char)111, (char)33, (char)84, (char)111, (char)34, (char)122, (char)97, (char)16, (char)402, (char)17, (char)181, (char)17, (char)9619, (char)15, (char)134, (char)14, (char)1080, (char)33, (char)71, (char)111, (char)33, (char)53, (char)54, (char)53, (char)111, (char)105, (char)115, (char)32, (char)99, (char)101, (char)10, (char)78, (char)32, (char)48, (char)51, (char)33, (char)114, (char)98, (char)33, (char)104, (char)110, (char)53, (char)114, (char)105, (char)101, (char)33, (char)74, (char)101, (char)33, (char)68, (char)114, (char)8, (char)52, (char)53, (char)70, (char)117, (char)223, (char)33, (char)74, (char)117, (char)34, (char)110, (char)121, (char)34, (char)89, (char)111, (char)31, (char)51, (char)54, (char)53, (char)104, (char)101, (char)105, (char)34, (char)53, (char)56, (char)34, (char)111, (char)118, (char)12, (char)36, (char)31, (char)66, (char)66, (char)8, (char)38, (char)94, (char)66, (char)105, (char)110, (char)103, (char)111, (char)53, (char)108, (char)105, (char)101, (char)33, (char)98, (char)121, (char)33, (char)73, (char)103, (char)52, (char)115, (char)116, (char)101, (char)10, (char)17, (char)7, (char)50, (char)10, (char)71, (char)32, (char)105, (char)99, (char)54, (char)107, (char)108, (char)101, (char)18, (char)65275, (char)18, (char)1071, (char)17, (char)1106, (char)16, (char)224, (char)16, (char)1751, (char)18, (char)1077, (char)18, (char)193, (char)18, (char)213, (char)18, (char)9474, (char)17, (char)238, (char)17, (char)9556, (char)16, (char)127, (char)15, (char)214, (char)34, (char)54, (char)52, (char)31, (char)115, (char)101, (char)31, (char)50, (char)51, (char)31, (char)110, (char)103, (char)32, (char)119, (char)97, (char)33, (char)68, (char)252, (char)33, (char)102, (char)108, (char)31, (char)97, (char)114, (char)32, (char)114, (char)115, (char)32, (char)66, (char)105, (char)132, (char)0, (char)112, (char)0, (char)66, (char)0, (char)45, (char)0, (char)7, (char)245, (char)7, (char)44, (char)8, (char)194, (char)52, (char)117, (char)116, (char)101, (char)31, (char)118, (char)101, (char)10, (char)64, (char)33, (char)115, (char)108, (char)33, (char)97, (char)99, (char)32, (char)72, (char)101, (char)7, (char)66, (char)29, (char)50, (char)48, (char)32, (char)87, (char)105, (char)34, (char)99, (char)108, (char)34, (char)77, (char)246, (char)33, (char)100, (char)109, (char)31, (char)77, (char)97, (char)30, (char)108, (char)101, (char)7, (char)105, (char)32, (char)111, (char)116, (char)34, (char)115, (char)99, (char)34, (char)117, (char)117, (char)12, (char)9, (char)10, (char)83, (char)53, (char)103, (char)101, (char)98, (char)32, (char)77, (char)101, (char)255, (char)16, (char)11, (char)102, (char)101, (char)109, (char)97, (char)108, (char)101, (char)46, (char)98, (char)46, (char)109, (char)121, (char)95, (char)52, (char)46, (char)103, (char)105, (char)102, (char)32, (char)116, (char)108, (char)30, (char)49, (char)54, (char)52, (char)99, (char)104, (char)116, (char)34, (char)108, (char)228, (char)34, (char)112, (char)117, (char)34, (char)115, (char)98, (char)34, (char)53, (char)49, (char)53, (char)70, (char)105, (char)102, (char)32, (char)57, (char)48, (char)53, (char)101, (char)114, (char)104, (char)52, (char)50, (char)53, (char)53, (char)10, (char)75, (char)31, (char)105, (char)103, (char)8, (char)124, (char)30, (char)109, (char)97, (char)32, (char)50, (char)57, (char)34, (char)65, (char)109, (char)15, (char)9835, (char)16, (char)8250, (char)17, (char)157, (char)17, (char)160, (char)17, (char)254, (char)17, (char)8592, (char)17, (char)153, (char)17, (char)321, (char)15, (char)1084, (char)33, (char)75, (char)246, (char)53, (char)118, (char)111, (char)110, (char)32, (char)75, (char)105, (char)34, (char)228, (char)117, (char)34, (char)67, (char)101, (char)34, (char)55, (char)56, (char)34, (char)71, (char)105, (char)32, (char)110, (char)117, (char)52, (char)103, (char)101, (char)110, (char)32, (char)100, (char)117, (char)54, (char)77, (char)97, (char)114, (char)33, (char)114, (char)117, (char)33, (char)118, (char)111, (char)33, (char)106, (char)117, (char)13, (char)8467, (char)34, (char)98, (char)115, (char)54, (char)117, (char)104, (char)112, (char)219, (char)70, (char)111, (char)116, (char)111, (char)67, (char)111, (char)110, (char)116, (char)101, (char)115, (char)116, (char)32, (char)67, (char)112, (char)54, (char)116, (char)111, (char)114, (char)54, (char)114, (char)101, (char)97, (char)32, (char)122, (char)105, (char)74, (char)107, (char)97, (char)110, (char)110, (char)30, (char)108, (char)108, (char)9, (char)63, (char)8, (char)251, (char)8, (char)190, (char)32, (char)109, (char)112, (char)33, (char)108, (char)110, (char)54, (char)83, (char)112, (char)105, (char)31, (char)117, (char)115, (char)30, (char)115, (char)116, (char)33, (char)114, (char)102, (char)13, (char)6, (char)13, (char)143, (char)32, (char)102, (char)102, (char)32, (char)115, (char)104, (char)33, (char)52, (char)52, (char)33, (char)73, (char)99, (char)52, (char)104, (char)97, (char)116, (char)32, (char)106, (char)97, (char)54, (char)46, (char)119, (char)95, (char)12, (char)20, (char)8, (char)103, (char)32, (char)50, (char)55, (char)34, (char)65, (char)114, (char)13, (char)1108, (char)33, (char)252, (char)98, (char)31, (char)105, (char)101, (char)30, (char)49, (char)48, (char)54, (char)85, (char)110, (char)100, (char)54, (char)105, (char)101, (char)115, (char)33, (char)57, (char)49, (char)14, (char)182, (char)15, (char)233, (char)16, (char)216, (char)18, (char)331, (char)18, (char)9600, (char)17, (char)231, (char)34, (char)73, (char)73, (char)32, (char)103, (char)111, (char)33, (char)111, (char)98, (char)12, (char)39, (char)219, (char)107, (char)110, (char)117, (char)100, (char)100, (char)101, (char)108, (char)115, (char)46, (char)100, (char)101, (char)8, (char)120, (char)10, (char)91, (char)53, (char)110, (char)103, (char)101, (char)33, (char)108, (char)116, (char)34, (char)56, (char)56, (char)34, (char)90, (char)105, (char)32, (char)78, (char)97, (char)32, (char)70, (char)97, (char)10, (char)93, (char)8, (char)188, (char)10, (char)228, (char)53, (char)97, (char)117, (char)115, (char)74, (char)115, (char)105, (char)99, (char)104, (char)72, (char)105, (char)99, (char)111, (char)110, (char)9, (char)54, (char)12, (char)9608, (char)33, (char)71, (char)114, (char)32, (char)112, (char)111, (char)31, (char)51, (char)48, (char)7, (char)62, (char)52, (char)83, (char)99, (char)104, (char)54, (char)112, (char)97, (char)114, (char)33, (char)101, (char)121, (char)33, (char)71, (char)97, (char)54, (char)78, (char)111, (char)114, (char)93, (char)109, (char)97, (char)102, (char)105, (char)97, (char)30, (char)49, (char)50, (char)33, (char)74, (char)97, (char)33, (char)115, (char)252, (char)15, (char)184, (char)15, (char)138, (char)15, (char)27, (char)15, (char)135, (char)34, (char)246, (char)110, (char)54, (char)109, (char)97, (char)103, (char)52, (char)118, (char)101, (char)114, (char)32, (char)71, (char)101, (char)11, (char)164, (char)31, (char)50, (char)50, (char)33, (char)97, (char)103, (char)34, (char)55, (char)50, (char)14, (char)144, (char)15, (char)244, (char)15, (char)136, (char)53, (char)104, (char)97, (char)108, (char)31, (char)50, (char)49, (char)32, (char)114, (char)111, (char)33, (char)80, (char)115, (char)34, (char)53, (char)57, (char)34, (char)70, (char)117, (char)31, (char)108, (char)97, (char)32, (char)54, (char)48, (char)11, (char)80, (char)53, (char)83, (char)116, (char)117, (char)33, (char)109, (char)117, (char)34, (char)65, (char)97, (char)34, (char)54, (char)50, (char)7, (char)110, (char)7, (char)58, (char)32, (char)100, (char)116, (char)54, (char)79, (char)78, (char)76, (char)33, (char)57, (char)50, (char)94, (char)124, (char)47, (char)103, (char)111, (char)32, (char)136, (char)67, (char)104, (char)97, (char)110, (char)110, (char)101, (char)108, (char)53, (char)98, (char)101, (char)105, (char)32, (char)72, (char)105, (char)9, (char)2, (char)9, (char)56, (char)9, (char)102, (char)52, (char)50, (char)48, (char)48, (char)34, (char)102, (char)111, (char)34, (char)104, (char)109, (char)54, (char)114, (char)111, (char)115, (char)32, (char)103, (char)108, (char)8, (char)48, (char)33, (char)52, (char)57, (char)54, (char)101, (char)110, (char)115, (char)32, (char)51, (char)52, (char)54, (char)115, (char)119, (char)104, (char)33, (char)98, (char)116, (char)34, (char)72, (char)80, (char)18, (char)211, (char)18, (char)9618, (char)18, (char)199, (char)18, (char)209, (char)17, (char)8730, (char)17, (char)8595, (char)15, (char)226, (char)16, (char)177, (char)16, (char)926, (char)15, (char)132, (char)54, (char)66, (char)97, (char)100, (char)31, (char)101, (char)100, (char)12, (char)15, (char)54, (char)116, (char)100, (char)101, (char)74, (char)46, (char)112, (char)110, (char)103, (char)9, (char)100, (char)33, (char)109, (char)98, (char)33, (char)107, (char)110, (char)32, (char)68, (char)97, (char)32, (char)105, (char)114, (char)54, (char)71, (char)105, (char)114, (char)75, (char)50, (char)48, (char)48, (char)57, (char)29, (char)48, (char)48, (char)53, (char)80, (char)114, (char)105, (char)54, (char)66, (char)114, (char)101, (char)33, (char)84, (char)101, (char)34, (char)86, (char)101, (char)34, (char)53, (char)52, (char)33, (char)83, (char)104, (char)53, (char)87, (char)104, (char)111, (char)33, (char)102, (char)116, (char)33, (char)78, (char)101, (char)32, (char)88, (char)120, (char)94, (char)74, (char)97, (char)109, (char)101, (char)115, (char)32, (char)67, (char)108, (char)32, (char)109, (char)111, (char)54, (char)97, (char)110, (char)103, (char)12, (char)204, (char)33, (char)87, (char)117, (char)33, (char)48, (char)52, (char)9, (char)57, (char)74, (char)48, (char)48, (char)54, (char)53, (char)34, (char)67, (char)72, (char)34, (char)99, (char)105, (char)33, (char)103, (char)104, (char)31, (char)107, (char)101, (char)33, (char)117, (char)114, (char)33, (char)97, (char)107, (char)33, (char)105, (char)97, (char)33, (char)119, (char)117, (char)94, (char)112, (char)105, (char)99, (char)115, (char)47, (char)52, (char)100, (char)101, (char)110, (char)32, (char)76, (char)111, (char)53, (char)115, (char)116, (char)97, (char)34, (char)71, (char)66, (char)55, (char)115, (char)98, (char)117, (char)34, (char)111, (char)104, (char)34, (char)113, (char)117, (char)32, (char)83, (char)97, (char)31, (char)108, (char)105, (char)9, (char)97, (char)10, (char)79, (char)33, (char)70, (char)101, (char)34, (char)120, (char)121, (char)18, (char)163, (char)18, (char)1086, (char)17, (char)154, (char)16, (char)169, (char)17, (char)247, (char)17, (char)9559, (char)18, (char)9472, (char)18, (char)8220, (char)18, (char)173, (char)18, (char)189, (char)15, (char)171, (char)17, (char)9562, (char)18, (char)203, (char)18, (char)242, (char)17, (char)165, (char)17, (char)243, (char)74, (char)110, (char)105, (char)99, (char)104, (char)54, (char)98, (char)101, (char)115, (char)33, (char)116, (char)99, (char)12, (char)172, (char)12, (char)9829, (char)53, (char)109, (char)101, (char)110, (char)32, (char)83, (char)116, (char)52, (char)98, (char)117, (char)114, (char)31, (char)114, (char)116, (char)33, (char)57, (char)51, (char)33, (char)87, (char)97, (char)33, (char)84, (char)105, (char)33, (char)48, (char)55, (char)32, (char)103, (char)97, (char)33, (char)100, (char)115, (char)34, (char)57, (char)57, (char)34, (char)77, (char)117, (char)51, (char)115, (char)99, (char)104, (char)33, (char)74, (char)111, (char)54, (char)72, (char)101, (char)114, (char)34, (char)103, (char)103, (char)34, (char)118, (char)98, (char)33, (char)105, (char)98, (char)53, (char)101, (char)110, (char)116, (char)34, (char)56, (char)55, (char)34, (char)121, (char)97, (char)33, (char)108, (char)102, (char)32, (char)111, (char)114, (char)33, (char)101, (char)98, (char)33, (char)97, (char)119, (char)11, (char)18, (char)32, (char)116, (char)122, (char)29, (char)99, (char)104, (char)33, (char)114, (char)108, (char)159, (char)46, (char)115, (char)104, (char)97, (char)100, (char)111, (char)119, (char)95, (char)32, (char)115, (char)112, (char)33, (char)116, (char)111, (char)33, (char)111, (char)111, (char)11, (char)42, (char)30, (char)49, (char)53, (char)9, (char)111, (char)34, (char)110, (char)102, (char)34, (char)56, (char)54, (char)33, (char)57, (char)53, (char)54, (char)73, (char)78, (char)69, (char)33, (char)83, (char)105, (char)74, (char)70, (char)111, (char)116, (char)111, (char)33, (char)121, (char)115, (char)34, (char)57, (char)54, (char)15, (char)26, (char)15, (char)31, (char)15, (char)152, (char)16, (char)225, (char)17, (char)212, (char)18, (char)1111, (char)18, (char)236, (char)7, (char)114, (char)52, (char)105, (char)115, (char)116, (char)54, (char)76, (char)97, (char)100, (char)54, (char)77, (char)111, (char)109, (char)33, (char)84, (char)104, (char)54, (char)80, (char)114, (char)111, (char)32, (char)107, (char)97, (char)32, (char)67, (char)104, (char)31, (char)110, (char)105, (char)30, (char)115, (char)115, (char)73, (char)46, (char)109, (char)121, (char)95, (char)32, (char)118, (char)105, (char)54, (char)77, (char)111, (char)110, (char)33, (char)112, (char)105, (char)33, (char)81, (char)102, (char)34, (char)111, (char)99, (char)34, (char)115, (char)103, (char)34, (char)84, (char)97, (char)34, (char)116, (char)119, (char)34, (char)105, (char)102, (char)34, (char)122, (char)122, (char)31, (char)110, (char)97, (char)33, (char)65, (char)117, (char)33, (char)97, (char)105, (char)158, (char)75, (char)110, (char)117, (char)100, (char)100, (char)101, (char)108, (char)115, (char)10, (char)88, (char)71, (char)176, (char)62, (char)95, (char)104, (char)35, (char)117, (char)103, (char)35, (char)77, (char)121, (char)34, (char)80, (char)101, (char)34, (char)101, (char)120, (char)34, (char)78, (char)111, (char)32, (char)75, (char)97, (char)32, (char)110, (char)111, (char)34, (char)120, (char)116, (char)34, (char)104, (char)112, (char)34, (char)107, (char)114, (char)34, (char)80, (char)117, (char)30, (char)49, (char)56, (char)9, (char)82, (char)53, (char)83, (char)105, (char)110, (char)32, (char)65, (char)110, (char)34, (char)82, (char)105, (char)55, (char)115, (char)101, (char)108, (char)54, (char)98, (char)101, (char)97, (char)33, (char)86, (char)111, (char)34, (char)97, (char)104, (char)34, (char)81, (char)117, (char)7, (char)43, (char)10, (char)99, (char)33, (char)116, (char)115, (char)33, (char)84, (char)114, (char)32, (char)87, (char)101, (char)10, (char)76, (char)241, (char)105, (char)99, (char)111, (char)110, (char)95, (char)103, (char)101, (char)110, (char)100, (char)101, (char)114, (char)95, (char)31, (char)109, (char)101, (char)53, (char)46, (char)104, (char)95, (char)54, (char)119, (char)119, (char)119, (char)34, (char)121, (char)111, (char)34, (char)104, (char)117, (char)255, (char)12, (char)10, (char)124, (char)47, (char)102, (char)111, (char)116, (char)111, (char)119, (char)104, (char)111, (char)105, (char)115, (char)32, (char)34, (char)53, (char)109, (char)105, (char)116, (char)32, (char)115, (char)111, (char)8, (char)11, (char)52, (char)70, (char)114, (char)101, (char)54, (char)109, (char)97, (char)120, (char)54, (char)114, (char)101, (char)103, (char)33, (char)86, (char)97, (char)54, (char)119, (char)101, (char)114, (char)10, (char)117, (char)54, (char)119, (char)105, (char)101, (char)117, (char)105, (char)99, (char)111, (char)110, (char)115, (char)47, (char)33, (char)69, (char)110, (char)15, (char)9552, (char)16, (char)149, (char)16, (char)215, (char)14, (char)159, (char)34, (char)106, (char)111, (char)7, (char)37, (char)220, (char)50, (char)53, (char)53, (char)44, (char)50, (char)53, (char)53, (char)44, (char)50, (char)53, (char)53, (char)32, (char)101, (char)105, (char)33, (char)100, (char)114, (char)33, (char)105, (char)112, (char)32, (char)68, (char)117, (char)34, (char)107, (char)102, (char)34, (char)53, (char)55, (char)33, (char)80, (char)108, (char)31, (char)108, (char)111, (char)53, (char)83, (char)116, (char)97, (char)14, (char)945, (char)15, (char)29, (char)17, (char)964, (char)17, (char)210, (char)16, (char)145, (char)34, (char)69, (char)82, (char)33, (char)107, (char)117, (char)32, (char)108, (char)115, (char)54, (char)97, (char)99, (char)116, (char)33, (char)70, (char)114, (char)10, (char)92, (char)255, (char)19, (char)11, (char)102, (char)111, (char)116, (char)111, (char)115, (char)47, (char)107, (char)110, (char)117, (char)100, (char)100, (char)101, (char)108, (char)115, (char)46, (char)100, (char)101, (char)63, (char)110, (char)61, (char)11, (char)72, (char)50, (char)32, (char)32, (char)32, (char)33, (char)76, (char)117, (char)54, (char)100, (char)101, (char)109, (char)53, (char)101, (char)110, (char)100, (char)35, (char)66, (char)252, (char)35, (char)97, (char)112, (char)34, (char)55, (char)52, (char)54, (char)99, (char)104, (char)108, (char)53, (char)103, (char)108, (char)101, (char)30, (char)52, (char)48, (char)9, (char)33, (char)30, (char)51, (char)50, (char)52, (char)101, (char)105, (char)110, (char)53, (char)115, (char)101, (char)105, (char)33, (char)75, (char)101, (char)12, (char)223, (char)32, (char)102, (char)103, (char)53, (char)98, (char)97, (char)108, (char)31, (char)116, (char)97, (char)30, (char)49, (char)57, (char)52, (char)110, (char)100, (char)101, (char)54, (char)77, (char)101, (char)110, (char)54, (char)76, (char)105, (char)101, (char)32, (char)97, (char)100, (char)31, (char)83, (char)102, (char)10, (char)167, (char)30, (char)105, (char)110, (char)35, (char)101, (char)99, (char)15, (char)30, (char)16, (char)8249, (char)17, (char)221, (char)18, (char)166, (char)18, (char)234, (char)14, (char)953, (char)35, (char)72, (char)252, (char)33, (char)111, (char)115, (char)32, (char)114, (char)110, (char)74, (char)46, (char)109, (char)120, (char)95, (char)53, (char)119, (char)101, (char)105, (char)30, (char)46, (char)46, (char)54, (char)108, (char)101, (char)114, (char)33, (char)114, (char)107, (char)11, (char)113, (char)34, (char)116, (char)102, (char)34, (char)85, (char)110, (char)33, (char)80, (char)111, (char)53, (char)86, (char)101, (char)114, (char)9, (char)112, (char)7, (char)47, (char)12, (char)125, (char)35, (char)100, (char)119, (char)15, (char)1109, (char)16, (char)146, (char)16, (char)235, (char)34, (char)97, (char)122, (char)33, (char)108, (char)117, (char)33, (char)70, (char)105, (char)33, (char)107, (char)108, (char)33, (char)119, (char)111, (char)32, (char)56, (char)48, (char)255, (char)32, (char)9, (char)0, (char)112, (char)0, (char)66, (char)0, (char)112, (char)105, (char)99, (char)115, (char)47, (char)105, (char)99, (char)111, (char)110, (char)95, (char)102, (char)117, (char)108, (char)108, (char)67, (char)104, (char)97, (char)110, (char)110, (char)101, (char)108, (char)46, (char)103, (char)105, (char)102, (char)0, (char)45, (char)0, (char)30, (char)101, (char)108, (char)31, (char)116, (char)121, (char)54, (char)78, (char)101, (char)117, (char)34, (char)53, (char)50, (char)34, (char)108, (char)109, (char)32, (char)48, (char)49, (char)113, (char)124, (char)47, (char)119, (char)32, (char)34, (char)60, (char)180, (char)46, (char)113, (char)117, (char)97, (char)100, (char)99, (char)117, (char)116, (char)95, (char)35, (char)54, (char)57, (char)35, (char)100, (char)228, (char)34, (char)116, (char)117, (char)54, (char)102, (char)114, (char)101, (char)34, (char)105, (char)104, (char)35, (char)101, (char)122, (char)35, (char)57, (char)56, (char)31, (char)116, (char)101, (char)53, (char)103, (char)105, (char)114, (char)53, (char)99, (char)110, (char)116, (char)158, (char)46, (char)98, (char)111, (char)114, (char)100, (char)101, (char)114, (char)95, (char)32, (char)105, (char)116, (char)11, (char)89, (char)255, (char)14, (char)11, (char)102, (char)117, (char)108, (char)108, (char)67, (char)104, (char)97, (char)110, (char)110, (char)101, (char)108, (char)46, (char)103, (char)105, (char)102, (char)34, (char)122, (char)111, (char)34, (char)107, (char)99, (char)34, (char)65, (char)98, (char)15, (char)965, (char)18, (char)9642, (char)19, (char)9577, (char)19, (char)8494, (char)17, (char)202, (char)16, (char)141, (char)35, (char)56, (char)50, (char)32, (char)51, (char)51, (char)31, (char)110, (char)100, (char)10, (char)70, (char)32, (char)83, (char)112, (char)11, (char)94, (char)54, (char)97, (char)99, (char)104, (char)33, (char)117, (char)99, (char)32, (char)107, (char)105, (char)52, (char)105, (char)99, (char)104, (char)55, (char)102, (char)101, (char)108, (char)35, (char)56, (char)51, (char)15, (char)191, (char)15, (char)219, (char)33, (char)98, (char)114, (char)54, (char)70, (char)114, (char)105, (char)54, (char)100, (char)111, (char)114, (char)31, (char)100, (char)101, (char)31, (char)53, (char)48, (char)33, (char)97, (char)97, (char)34, (char)103, (char)98, (char)34, (char)108, (char)99, (char)54, (char)102, (char)252, (char)114, (char)33, (char)55, (char)53, (char)32, (char)116, (char)104, (char)53, (char)66, (char)101, (char)114, (char)54, (char)66, (char)97, (char)108, (char)33, (char)55, (char)48, (char)33, (char)52, (char)53, (char)34, (char)83, (char)119, (char)34, (char)52, (char)49, (char)32, (char)105, (char)108, (char)54, (char)104, (char)102, (char)108, (char)34, (char)73, (char)104, (char)13, (char)126, (char)255, (char)14, (char)10, (char)112, (char)105, (char)99, (char)115, (char)47, (char)102, (char)101, (char)109, (char)97, (char)108, (char)101, (char)46, (char)103, (char)105, (char)102, (char)53, (char)104, (char)116, (char)116, (char)16, (char)9834, (char)18, (char)161, (char)18, (char)232, (char)18, (char)305, (char)19, (char)8212, (char)62, (char)92, (char)92, (char)92, (char)20, (char)1241, (char)15, (char)183, (char)35, (char)65, (char)116, (char)35, (char)76, (char)69, (char)35, (char)83, (char)107, (char)75, (char)50, (char)48, (char)49, (char)48, (char)71, (char)46, (char)103, (char)105, (char)102, (char)74, (char)102, (char)111, (char)116, (char)111, (char)54, (char)76, (char)97, (char)110, (char)13, (char)19, (char)34, (char)105, (char)107, (char)199, (char)176, (char)62, (char)103, (char)116, (char)46, (char)103, (char)105, (char)102, (char)60, (char)176, (char)32, (char)72, (char)111, (char)34, (char)100, (char)121, (char)34, (char)80, (char)105, (char)54, (char)97, (char)108, (char)116, (char)32, (char)50, (char)56, (char)74, (char)46, (char)106, (char)112, (char)103, (char)7, (char)101, (char)8, (char)115, (char)32, (char)69, (char)108, (char)54, (char)109, (char)101, (char)114, (char)255, (char)14, (char)12, (char)109, (char)97, (char)108, (char)101, (char)46, (char)98, (char)46, (char)109, (char)121, (char)95, (char)51, (char)46, (char)103, (char)105, (char)102, (char)136, (char)0, (char)70, (char)108, (char)105, (char)114, (char)116, (char)32, (char)14, (char)1103, (char)35, (char)55, (char)54, (char)34, (char)110, (char)98, (char)33, (char)76, (char)97, (char)32, (char)110, (char)115, (char)33, (char)114, (char)103, (char)33, (char)48, (char)56, (char)32, (char)66, (char)101, (char)11, (char)118, (char)34, (char)109, (char)108, (char)35, (char)99, (char)100, (char)35, (char)55, (char)51, (char)33, (char)66, (char)117, (char)32, (char)116, (char)114, (char)32, (char)119, (char)105, (char)31, (char)109, (char)109, (char)33, (char)115, (char)102, (char)54, (char)68, (char)105, (char)101, (char)32, (char)110, (char)116, (char)32, (char)108, (char)121, (char)33, (char)101, (char)109, (char)54, (char)116, (char)109, (char)117, (char)34, (char)111, (char)100, (char)34, (char)115, (char)100, (char)54, (char)75, (char)105, (char)115, (char)34, (char)68, (char)68, (char)16, (char)151, (char)17, (char)168, (char)17, (char)206, (char)15, (char)951, (char)35, (char)54, (char)56, (char)12, (char)81, (char)31, (char)103, (char)101, (char)35, (char)56, (char)52, (char)35, (char)70, (char)67, (char)34, (char)103, (char)115, (char)33, (char)82, (char)97, (char)33, (char)115, (char)117, (char)34, (char)105, (char)118, (char)35, (char)104, (char)104, (char)35, (char)80, (char)114, (char)7, (char)60, (char)31, (char)104, (char)97, (char)31, (char)111, (char)110, (char)10, (char)84, (char)52, (char)99, (char)104, (char)101, (char)8, (char)104, (char)7, (char)34, (char)255, (char)13, (char)12, (char)99, (char)108, (char)111, (char)117, (char)100, (char)115, (char)98, (char)108, (char)117, (char)101, (char)46, (char)103, (char)105, (char)102, (char)34, (char)67, (char)105, (char)13, (char)3, (char)55, (char)108, (char)105, (char)103, (char)14, (char)23, (char)16, (char)142, (char)16, (char)150, (char)18, (char)241, (char)18, (char)253, (char)18, (char)174, (char)18, (char)1091, (char)19, (char)942, (char)19, (char)304, (char)19, (char)322, (char)19, (char)324, (char)17, (char)961, (char)33, (char)98, (char)98, (char)53, (char)98, (char)101, (char)114, (char)32, (char)76, (char)105, (char)33, (char)68, (char)105, (char)13, (char)175, (char)34, (char)108, (char)103, (char)33, (char)65, (char)108, (char)54, (char)79, (char)117, (char)116, (char)32, (char)50, (char)52, (char)32, (char)117, (char)110, (char)32, (char)51, (char)57, (char)55, (char)117, (char)114, (char)116, (char)35, (char)73, (char)115, (char)35, (char)82, (char)102, (char)33, (char)55, (char)49, (char)33, (char)104, (char)108, (char)33, (char)66, (char)108, (char)32, (char)66, (char)97, (char)53, (char)101, (char)97, (char)114, (char)54, (char)101, (char)99, (char)104, (char)34, (char)85, (char)115, (char)34, (char)52, (char)55, (char)54, (char)105, (char)112, (char)105, (char)12, (char)59, (char)32, (char)122, (char)101, (char)7, (char)46, (char)9, (char)55, (char)31, (char)97, (char)116, (char)34, (char)119, (char)228, (char)35, (char)72, (char)117, (char)15, (char)8706, (char)16, (char)186, (char)17, (char)240, (char)17, (char)65273, (char)33, (char)223, (char)101, (char)33, (char)117, (char)116, (char)33, (char)102, (char)117, (char)73, (char)62, (char)45, (char)45, (char)60, (char)31, (char)97, (char)110, (char)32, (char)76, (char)101, (char)32, (char)115, (char)97, (char)13, (char)4, (char)34, (char)103, (char)116, (char)33, (char)106, (char)101, (char)53, (char)112, (char)119, (char)100, (char)32, (char)82, (char)101, (char)32, (char)104, (char)101, (char)32, (char)104, (char)111, (char)34, (char)111, (char)109, (char)34, (char)111, (char)107, (char)33, (char)53, (char)53, (char)52, (char)119, (char)97, (char)114, (char)53, (char)104, (char)101, (char)110, (char)34, (char)112, (char)101, (char)35, (char)101, (char)107, (char)35, (char)76, (char)76, (char)33, (char)98, (char)117, (char)31, (char)114, (char)101, (char)34, (char)119, (char)252, (char)34, (char)54, (char)54, (char)33, (char)83, (char)101, (char)11, (char)90, (char)33, (char)252, (char)99, (char)34, (char)67, (char)114, (char)34, (char)103, (char)117, (char)32, (char)122, (char)117, (char)12, (char)74, (char)34, (char)109, (char)228, (char)34, (char)52, (char)50, (char)33, (char)98, (char)111, (char)33, (char)67, (char)97, (char)31, (char)101, (char)115, (char)54, (char)84, (char)97, (char)103, (char)35, (char)82, (char)82, (char)35, (char)114, (char)121, (char)13, (char)5, (char)32, (char)50, (char)54, (char)34, (char)114, (char)114, (char)34, (char)111, (char)102, (char)54, (char)68, (char)111, (char)114, (char)53, (char)114, (char)101, (char)115, (char)53, (char)99, (char)103, (char)105, (char)33, (char)100, (char)100, (char)255, (char)57, (char)12, (char)124, (char)104, (char)116, (char)116, (char)112, (char)58, (char)47, (char)47, (char)119, (char)119, (char)119, (char)51, (char)46, (char)107, (char)110, (char)117, (char)100, (char)100, (char)101, (char)108, (char)115, (char)46, (char)100, (char)101, (char)58, (char)56, (char)48, (char)56, (char)48, (char)47, (char)116, (char)120, (char)116, (char)108, (char)47, (char)99, (char)108, (char)105, (char)99, (char)107, (char)63, (char)100, (char)61, (char)107, (char)110, (char)117, (char)100, (char)100, (char)101, (char)108, (char)115, (char)46, (char)100, (char)101, (char)38, (char)105, (char)100, (char)61, (char)33, (char)83, (char)109, (char)34, (char)52, (char)51, (char)34, (char)97, (char)102, (char)53, (char)105, (char)110, (char)101, (char)33, (char)67, (char)111, (char)18, (char)170, (char)18, (char)179, (char)17, (char)931, (char)16, (char)137, (char)15, (char)187, (char)35, (char)67, (char)69, (char)34, (char)108, (char)107, (char)32, (char)97, (char)109, (char)32, (char)112, (char)112, (char)33, (char)115, (char)119, (char)35, (char)54, (char)51, (char)35, (char)109, (char)121, (char)35, (char)112, (char)102, (char)17, (char)156, (char)17, (char)230, (char)16, (char)140, (char)15, (char)28, (char)54, (char)102, (char)104, (char)101, (char)13, (char)8, (char)34, (char)86, (char)105, (char)53, (char)116, (char)101, (char)114, (char)10, (char)255, (char)31, (char)49, (char)49, (char)33, (char)102, (char)97, (char)35, (char)115, (char)114, (char)35, (char)77, (char)102, (char)13, (char)16, (char)96, (char)176, (char)62, (char)115, (char)109, (char)95, (char)54, (char)65, (char)110, (char)122, (char)10, (char)65, (char)32, (char)97, (char)115, (char)35, (char)78, (char)82, (char)35, (char)108, (char)114, (char)35, (char)78, (char)84, (char)35, (char)54, (char)49, (char)33, (char)110, (char)122, (char)33, (char)97, (char)98, (char)33, (char)103, (char)105, (char)54, (char)100, (char)112, (char)103, (char)33, (char)103, (char)114, (char)9, (char)40, (char)255, (char)12, (char)10, (char)112, (char)105, (char)99, (char)115, (char)47, (char)109, (char)97, (char)108, (char)101, (char)46, (char)103, (char)105, (char)102, (char)32, (char)112, (char)103, (char)35, (char)67, (char)117, (char)19, (char)948, (char)19, (char)962, (char)19, (char)1754, (char)19, (char)8596, (char)18, (char)1110, (char)18, (char)9658, (char)17, (char)1750, (char)19, (char)273, (char)19, (char)295, (char)19, (char)423, (char)19, (char)1753, (char)18, (char)957, (char)18, (char)1089, (char)17, (char)207, (char)17, (char)237, (char)18, (char)9679, (char)18, (char)8221, (char)34, (char)79, (char)115, (char)33, (char)111, (char)119, (char)31, (char)99, (char)107, (char)11, (char)229, (char)32, (char)72, (char)97, (char)35, (char)103, (char)100, (char)35, (char)73, (char)116, (char)34, (char)107, (char)116, (char)54, (char)108, (char)101, (char)110, (char)33, (char)69, (char)105, (char)13, (char)7, (char)34, (char)102, (char)114, (char)10, (char)67, (char)9, (char)41, (char)54, (char)109, (char)105, (char)110, (char)54, (char)83, (char)105, (char)101, (char)12, (char)123, (char)34, (char)54, (char)53, (char)34, (char)77, (char)252, (char)11, (char)246, (char)35, (char)78, (char)252, (char)35, (char)68, (char)111, (char)34, (char)105, (char)111, (char)33, (char)80, (char)102, (char)54, (char)100, (char)97, (char)115, (char)12, (char)86, (char)95, (char)70, (char)108, (char)105, (char)114, (char)116, (char)11, (char)252, (char)34, (char)114, (char)122, (char)35, (char)71, (char)117, (char)35, (char)102, (char)109, (char)54, (char)72, (char)97, (char)109, (char)8, (char)116, (char)29, (char)101, (char)110, (char)29, (char)101, (char)114, (char)4, (char)0, (char)52, (char)100, (char)101, (char)114, (char)33, (char)67, (char)99, (char)54, (char)65, (char)108, (char)116, (char)53, (char)77, (char)105, (char)120, (char)35, (char)65, (char)115, (char)35, (char)116, (char)112, (char)55, (char)110, (char)101, (char)110, (char)33, (char)108, (char)100, (char)32, (char)48, (char)53, (char)31, (char)105, (char)115, (char)11, (char)195, (char)34, (char)76, (char)252, (char)15, (char)1752, (char)15, (char)1761, (char)15, (char)1762, (char)15, (char)162, (char)54, (char)71, (char)101, (char)115, (char)54, (char)97, (char)117, (char)102, (char)54, (char)97, (char)110, (char)100, (char)54, (char)98, (char)108, (char)103, (char)33, (char)112, (char)114, (char)52, (char)117, (char)110, (char)100, (char)31, (char)97, (char)108, (char)34, (char)73, (char)110, (char)34, (char)87, (char)252, (char)54, (char)104, (char)105, (char)101, (char)54, (char)103, (char)101, (char)115, (char)34, (char)246, (char)223, (char)34, (char)112, (char)115, (char)31, (char)98, (char)101, (char)32, (char)50, (char)53, (char)54, (char)49, (char)52, (char)48, (char)35, (char)104, (char)115, (char)16, (char)969, (char)16, (char)239, (char)16, (char)147, (char)16, (char)963, (char)34, (char)52, (char)54, (char)10, (char)128, (char)31, (char)49, (char)52, (char)32, (char)51, (char)53, (char)33, (char)69, (char)109, (char)54, (char)103, (char)101, (char)114, (char)31, (char)99, (char)103, (char)10, (char)107, (char)6, (char)45, (char)34, (char)119, (char)104, (char)35, (char)114, (char)112, (char)17, (char)148, (char)18, (char)923, (char)18, (char)155, (char)16, (char)9553, (char)16, (char)129, (char)17, (char)208, (char)19, (char)287, (char)19, (char)399, (char)19, (char)9632, (char)19, (char)9668, (char)33, (char)80, (char)97, (char)11, (char)85, (char)32, (char)98, (char)108, (char)33, (char)99, (char)97, (char)54, (char)118, (char)97, (char)116, (char)33, (char)51, (char)55, (char)34, (char)101, (char)117, (char)34, (char)109, (char)115, (char)33, (char)77, (char)105, (char)33, (char)99, (char)115, (char)53, (char)100, (char)105, (char)101, (char)33, (char)97, (char)121, (char)33, (char)102, (char)105, (char)10, (char)192, (char)32, (char)117, (char)109, (char)53, (char)115, (char)101, (char)110, (char)9, (char)61, (char)33, (char)66, (char)114, (char)34, (char)117, (char)108, (char)34, (char)102, (char)121, (char)53, (char)118, (char)111, (char)114, (char)33, (char)87, (char)108, (char)54, (char)116, (char)115, (char)99, (char)32, (char)114, (char)100, (char)31, (char)110, (char)101, (char)34, (char)75, (char)117, (char)15, (char)949, (char)15, (char)1090, (char)35, (char)82, (char)252, (char)54, (char)80, (char)97, (char)114, (char)35, (char)56, (char)53, (char)35, (char)119, (char)99, (char)34, (char)99, (char)114, (char)33, (char)114, (char)109, (char)8, (char)49, (char)6, (char)95, (char)4, (char)32 });

    public KHuffman()
    {
    this.DecRoot = new BinaryNode();
    this.CharBuffer = new char[65535];
    this.EncMap = new Dictionary<char, Pair<Path, Object>>();
    this.CreateTree();
    }

    private void CreateTree()
    {
    int m = 1;
    int n = -33;
    int strLen;
    for (int i = 0; i < this.Tree.Length; i += strLen)
    {
    int temp = this.Tree[i++];
    int pathLen;
    if (temp == 255)
    {
    strLen = this.Tree[i++] + '\u0001';
    pathLen = this.Tree[i++];
    }
    else
    {
    strLen = temp / 21 + 1;
    pathLen = temp % 21;
    }
    if ((m & 0x1) == 0x0)
    {
    ++m;
    }
    else
    {
    while ((m & 0x1) == 0x1)
    {
    m >>= 1;
    --n;
    }
    ++m;
    }
    while (n < pathLen)
    {
    m <<= 1;
    ++n;
    }
    String str = this.Tree.Substring(i, strLen);
    int path = this.ReverseBits(m, pathLen);
    if (strLen == 3 && str.Equals("\\\\\\"))
    {
    this._16BitChar = str;
    this._16BitCharPath = path;
    this._16BitCharPathLen = pathLen;
    }
    this.AddString(str, path, pathLen);
    if (!this.Put(this.DecRoot, str, path, pathLen))
    {
    throw new Exception("error while creating tree (invalid path)");
    }
    }
    }

    private int ReverseBits(int x, int pathLen)
    {
    int rv = 0;
    for (int i = 0; i < pathLen; ++i, x >>= 1)
    {
    rv = (rv << 1 | (x & 0x1));
    }
    return rv;
    }

    private bool Put(BinaryNode node, String str, int path, int pathLen)
    {
    if (pathLen == 0)
    {
    node.SetData(str);
    return node.IsLeaf();
    }
    if (node.IsEmpty())
    {
    if (node.IsLeaf())
    {
    return false;
    }
    node.SetZero(new BinaryNode());
    node.SetOne(new BinaryNode());
    }
    return this.Put(((path & 0x1) == 0x0) ? node.GetZero() : node.GetOne(), str, path >> 1, pathLen - 1);
    }

    private void AddString(String str, int path, int pathLen)
    {
    Dictionary<char, Pair<Path, Object>> current = this.EncMap;
    for (int i = 0; i < str.Length; ++i)
    {
    char _char = str[i];
    char character = this.CharBuffer[_char];
    if (character == 0) // character == null
    {
    this.CharBuffer[_char] = _char;
    character = _char;
    }
    Pair<Path, Object> child = null;

    if (current.ContainsKey(character)) child = current[character];

    if (child == null)
    {
    Dictionary<char, Pair< Path, Object >> map = new Dictionary<char, Pair<Path, Object>>();
    current.Add(character, child = new Pair<Path, Object>(null, map));
    current = map;
    }
    else
    {
    current = (Dictionary<char, Pair<Path, Object>>)child.GetValue();
    }
    if (i == str.Length - 1)
    {
    child.SetKey(new Path(path, pathLen));
    }
    }
    }

    public String Decompress(byte[] data)
    {
    BitStream bitStream = new BitStream(data);
    BinaryNode tempNode = this.DecRoot;
    StringBuilder output = new StringBuilder();
    while (bitStream.HasNext())
    {
    tempNode = ((bitStream.NextBit() == 0) ? tempNode.GetZero() : tempNode.GetOne());
    if (!tempNode.IsLeaf())
    {
    continue;
    }
    if (tempNode.GetData().Equals(this._16BitChar))
    {
    int _char = 0;
    for (int k = 0; k < 16; ++k)
    {
    _char += bitStream.NextBit() << k;
    }
    output.Append((char)_char);
    }
    else
    {
    String str = tempNode.GetData();
    output.Append(str);
    }
    tempNode = this.DecRoot;
    }
    return output.ToString();
    }

    public byte[] Compress(String str)
    {
    BitStream output = new BitStream();
    Dictionary<char, Pair<Path, Object>> current = this.EncMap;
    int previous = -1;
    int previousLen = -1;
    int previousPos = -1;
    for (int i = 0; i < str.Length; ++i)
    {
    char _char = str[i];
    char character = this.CharBuffer[_char];
    if (character == 0) // character == null
    {
    this.CharBuffer[_char] = _char;
    character = _char;
    }
    Pair<Path, Object> temp = null;
    if (current.ContainsKey(character)) temp = current[character];

    if (temp == null)
    {
    if (previous == -1)
    {
    output.AddBits(this._16BitCharPath, this._16BitCharPathLen);
    output.AddBits(_char, 16);
    previousPos = i;
    }
    else
    {
    output.AddBits(previous, previousLen);
    }
    previous = -1;
    i = previousPos;
    current = this.EncMap;
    }
    else
    {
    if (temp.GetKey() != null)
    {
    previous = temp.GetKey().GetPath();
    previousLen = temp.GetKey().GetPathLen();
    previousPos = i;
    }
    if (temp.GetValue() != null)
    {
    current = (Dictionary<char, Pair<Path, Object>>)temp.GetValue();
    }
    }
    }
    if (previous >= 0)
    {
    output.AddBits(previous, previousLen);
    }
    return output.ToByteArray();
    }

    private class BinaryNode
    {
    private BinaryNode zero;
    private BinaryNode one;
    private String data;

    public bool IsLeaf()
    {
    return this.data != null && this.IsEmpty();
    }

    public bool IsEmpty()
    {
    return this.zero == null && this.one == null;
    }

    public void SetData(String data)
    {
    this.data = data;
    }

    public String GetData()
    {
    return this.data;
    }

    public BinaryNode GetZero()
    {
    return this.zero;
    }

    public void SetZero(BinaryNode left)
    {
    this.zero = left;
    }

    public BinaryNode GetOne()
    {
    return this.one;
    }

    public void SetOne(BinaryNode right)
    {
    this.one = right;
    }
    }

    private class Pair<K, V>
    {
    private K key;
    private V value;

    public Pair(K key, V value)
    {
    this.key = key;
    this.value = value;
    }

    public K GetKey()
    {
    return this.key;
    }

    public V GetValue()
    {
    return this.value;
    }

    public void SetKey(K key)
    {
    this.key = key;
    }
    }

    private class Path
    {
    private int path;
    private int pathLen;

    public Path(int path, int pathLen)
    {
    this.path = path;
    this.pathLen = pathLen;
    }

    public int GetPath()
    {
    return this.path;
    }

    public int GetPathLen()
    {
    return this.pathLen;
    }
    }
    }
    }



    BitStream.cs:
    Spoiler:


    using System;
    using System.Collections.Generic;

    namespace DeinTollesProjekt
    {
    class BitStream
    {
    private List<Byte> Stream;
    private int StreamPosition;
    private int BytePosition;

    public BitStream()
    {
    this.StreamPosition = 0;
    this.BytePosition = 0;
    this.Stream = new List<Byte>();
    }

    public BitStream(byte[] data) : this()
    {
    foreach (byte b in data)
    {
    this.Stream.Add(b);
    }
    }

    public byte[] ToByteArray()
    {
    byte[] temp = new byte[this.Stream.Count];
    for (int i = 0; i < temp.Length; temp[i] = this.Stream[i++]) { }
    return temp;
    }

    public void AddBit(int bit)
    {
    if (this.BytePosition == 8)
    {
    this.BytePosition = 0;
    ++this.StreamPosition;
    }
    if (this.Stream.Count == this.StreamPosition)
    {
    this.Stream.Add((byte)0);
    }
    byte temp = (byte)(this.Stream[this.StreamPosition] | bit << this.BytePosition++);
    this.Stream[this.StreamPosition] = temp;
    }

    public void AddBits(int i, int len)
    {
    for (int j = 0; j < len; ++j)
    {
    this.AddBit(i >> j & 0x1);
    }
    }

    public int NextBit()
    {
    int temp = this.Stream[this.StreamPosition] >> this.BytePosition & 0x1;
    if (++this.BytePosition == 8)
    {
    this.BytePosition = 0;
    ++this.StreamPosition;
    }
    return temp;
    }

    public bool HasNext()
    {
    return this.StreamPosition != this.Stream.Count || this.BytePosition != 0;
    }
    }
    }



    Aufruf:


    KHuffman huffman = new KHuffman();
    byte[] compressed = huffman.Compress("...");
    string decompressed = huffman.Decompress(compressed);
    Geändert von Brainy (24.05.2020 um 11:09 Uhr) Grund: 2. Version von KHuffman.cs hinzugefügt (andere Baumdarstellung)

  2. The Following 2 Users Say Thank You to Brainy For This Useful Post:

    Bubble Gum (20.05.2020), Realer Name (20.05.2020)

  3. #2

    Registriert seit
    09.11.2011
    Beiträge
    121
    Thanked 129 Times in 46 Posts

    Standard AW: [C#] Huffman

    (c) by KrT (habe ich vor Jahren mal aus KInspect (geschrieben in Java) extrahiert, wie ich soeben beim Durchstöbern festgestellt habe)

    Ich habe außerdem noch eine PHP-Version (by Duncan / 3LiT) von Huffman mit einem statischen Tree als Dictionary/Array gefunden (auch nach .NET portiert), aber die Performance von KrT kann das im Leben nicht toppen. Die Kompression ist nicht gut umgesetzt worden (zwei for-Schleifen, welche den gesamten Input (durch Substring) rückwärts zerlegen usw.).
    Geändert von Brainy (27.05.2020 um 09:36 Uhr)

  4. #3

    Registriert seit
    28.10.2011
    Beiträge
    625
    Thanked 279 Times in 168 Posts

    Standard AW: [C#] Huffman

    Die PHP-Version findet man auf Diebspiel.info.

    Edit: Okay, dass ist kein wirklicher Huffman encoder/decoder, sondern einfach ein simples Replacement.

    Ich weiß jetzt nicht, ob der Tree jemals verändert wurde, dann würde das ganze dann wohl nicht mehr funktionieren.

    Könnte später das ganze auch nach PHP portieren, mir würde da aber keinen Sinn erschließen, warum man das ganze in PHP nutzen sollte. Immerhin sind die normalen PHP-Versionen nicht Threadsafe, vorallem, weil PHP nicht für ein 24/7 running ausgelegt ist. Hierzu müsste man PHP mit ZTS selfcompilen.
    Geändert von Bubble Gum (27.05.2020 um 10:04 Uhr)

Ähnliche Themen

  1. [C#] Huffman
    Von SeBi im Forum Sourcecode
    Antworten: 8
    Letzter Beitrag: 27.05.2020, 11:19
  2. [Release] Huffman (Java Library)
    Von Flav im Forum Protokoll
    Antworten: 2
    Letzter Beitrag: 05.07.2013, 15:17
  3. [Java] Huffman
    Von Flav im Forum Sourcecode
    Antworten: 2
    Letzter Beitrag: 14.04.2012, 10:27
Diese Seite nutzt Cookies, um das Nutzererlebnis zu verbessern. Klicken Sie hier, um das Cookie-Tracking zu deaktivieren.