Oppgave 1

  public static void dekomprimer(String fraUrl, String tilFil) throws IOException
  {
    BitInputStream inn =
            new BitInputStream((new URL(fraUrl)).openStream());  // åpner filen

    int k = inn.readBits(3);                  // antall biter i lengdene
    int[] lengder = new int[256];             // 256 mulige tegn

    for (int i = 0; i < lengder.length; i++)
    {
      if (inn.readBit() == 1)
      {
        lengder[i] = inn.readBits(k);
      }
    }

    int vaktpost = Tabell.maks(lengder);      // tegnet med størst lengde

    int s = inn.readBits(5);       // antall siffer i vaktpostens frekvens
    int vaktpostfrekvens = inn.readBits(s) + 1;

    int n = lengder[vaktpost];                // lengden til vaktposten
    int[] blader = new int[n + 1];            // n er nederste nivå

    for (int lengde : lengder)
    {
      if (lengde > 0)
      {
        blader[lengde]++;       // finner antallet på hvert nivå
      }
    }
    int[] bitkoder = finnBitkoder(lengder);   // finner bitkodene

    int m = (n + 1) / 2;                      // det midterste nivået i treet
    byte[] tegntabell = new byte[1 << m];   // en byte-tabell

    int[] høyder = treHøyde(blader, m);     // de indre nodene på nivå m
    int grense = høyder.length;             // skiller indre noder og blader

    for (int i = 0; i < grense; i++)
    {
      tegntabell[i] = (byte) høyder[i];        // høydene først i tegntabellen
    }

    int[] tilbake = new int[lengder.length];  // for tilbakelegging

    byte[][] tegntabeller = new byte[grense][];    // en to-dimensjonal tabell

    for (int i = 0; i < grense; i++)
    {
      tegntabeller[i] = new byte[1 << høyder[i]];  // størrelse 1 << høyder[i]
    }

    for (int i = 0; i < lengder.length; i++)    // går gjennom alle lengdene
    {
      int lengde = lengder[i];                  // hjelpevariabel

      if (lengde > 0)                           // tegnet i skal være med
      {
        if (lengde <= m)                        // den store tabellen
        {
          int d = m - lengde;                   // lengdeforskjellen
          tilbake[i] = d;                       // antall tilbake

          int fra = bitkoder[i] << d;           // starten på tegn nr. i
          int til = fra + (1 << d);             // slutten på tegn nr. i

          for (int j = fra; j < til; j++)
          {
            tegntabell[j] = (byte) i;  // fyller ut
          }
        }
        else                                    // de små tabellene
        {
          int kode = bitkoder[i];        // bitkoden til tegnet med i som asciiverdi
          int d1 = lengde - m;           // differensen mellom lengde og m

          int kode1 = kode >> d1;               // de m første bitene i kode
          int kode2 = kode & ((1 << d1) - 1);   // de d1 siste bitene i kode

          byte[] b = tegntabeller[kode1];       // finner rett tabell

          int d2 = tegntabell[kode1] - d1;      // differensen mellom høyden og k
          tilbake[i] = d2;                      // antall tilbake

          int fra = kode2 << d2;                // starten på tegn i
          int til = fra + (1 << d2);            // slutten på tegn i

          for (int j = fra; j < til; j++)
          {
            b[j] = (byte) i;  // fyller ut
          }
        }
      }
    }

    BitOutputStream ut = new BitOutputStream(tilFil);  // for utskrift
    int frekvens = 0;   // forekomster av vaktposttegnet

    for (;;)
    {
      int lest = inn.readBits(m);               // leser m biter
      int tall = tegntabell[lest] & 255;        // slår opp i tegntabellen

      if (lest < grense)                        // lest gir en indre node
      {
        byte[] b = tegntabeller[lest];          // finner rett tabell
        lest = inn.readBits(tall);              // leser flere biter
        tall = b[lest] & 255;                   // slår opp i tabellen
      }

      // tall er nå ascii-verdien til et tegn

      if (tall == vaktpost)
      {
        if (++frekvens == vaktpostfrekvens)
        {
          break;
        }
      }

      ut.write(tall);                           // skriver ut tegnet

      inn.unreadBits(tilbake[tall]);            // legger biter tilbake
    }

    ut.close();    // lukker ut-filen
    inn.close();
  }