Løsningsforslag - oppgaver i Avsnitt 7.2.3


Oppgave 3

  public static Map<String,Integer> komprimer(String melding)
  {
    . . . . . . .
    . . . . . . .

    return ordbok;
  }

Dette kan brukes f.eks. på denne måten:

  Map<String,Integer> ordbok = LZW.komprimer("ABBABABAC");

  for (String ord : ordbok.keySet())
    System.out.print(ord + "-" + ordbok.get(ord) + " ");

Obs: Hvis vi bruker en TreeMap, kommer ordene i sortert rekkefølge. I samme rekkefølge som ordene ble lagt inn hvis vi bruker en LinkedHashMap.

HashMap: BB-257 ABA-259 AB-256 ABAC-260 BA-258
TreeMap: AB-256 ABA-259 ABAC-260 BA-258 BB-257
LinkedHashMap: AB-256 BB-257 BA-258 ABA-259 ABAC-260

Oppgave 4

  public static List<Integer> komprimer2(String melding)
  {
    char c = melding.charAt(0);     // første tegn i meldingen
    String s = String.valueOf(c);   // tegnstrengen med c som innhold
    int kode = c;                   // tallkoden til c
    int nestekode = 256;            // første ledige tallkode

    String format = "%2d%4s  %-12s  %-7s%5s%5s%5s\n";  // utskriftsformat

    System.out.printf(format, 0, c, "", s, "", kode, nestekode);

    Map<String,Integer> ordbok = new HashMap<>();  // en ordbok
    List<Integer> resultat = new ArrayList<>(); // resultatliste

    for (int i = 1; i < melding.length(); i++)     // resten av meldingen
    {
      c = melding.charAt(i);                       // neste tegn i meldingen

      Integer ordkode = ordbok.get(s + c);         // søker etter s + c

      if (ordkode == null)                         // s + c er ikke i ordboken
      {
        ordbok.put(s + c, nestekode++);              // legger s + c i ordboken

        String ut = (s + c) + "-" + nestekode;
        System.out.printf(format, i, c, ut, "" + c, kode, (int)c, nestekode + 1);
        resultat.add(kode);

        s = String.valueOf(c);                     // s får c som innhold
        kode = c;                                  // kode = tallverdien til c
      }
      else                                         // s + c er i ordboken
      {
        kode = ordkode;                            // kode = ordkoden til s + c
        s += c;                                    // setter s = s + c
        System.out.printf(format, i, c, "", s, "", kode, "");
      }
    }

    // alle tegnene i meldingen er behandlet, deretter siste utskrift
    System.out.printf(format, melding.length(), "", "", "", kode, "", "");
    resultat.add(kode);

    return resultat;
  } 

Denne metoden kan brukes slik:

  LZW.komprimer2("ABBABABAC");
Utskrift:
 0   A                A              65  256
 1   B  AB-256        B         65   66  257
 2   B  BB-257        B         66   66  258
 3   A  BA-258        A         66   65  259
 4   B                AB            256
 5   A  ABA-259       A        256   65  260
 6   B                AB            256
 7   A                ABA           259
 8   C  ABAC-260      C        259   67  261
 9                              67