3. LZW Codierung

LZW Codierung

  • K

    Aufgabenstellung

    Implementieren Sie die LZW-Codierung. Verwenden Sie für die Codierung jedes Zeichens 2 Bytes, wobei die zusammengesetzten Symbole bei 256 beginnen.
    Lesen Sie wiederum ein ASCII-Textbeispiel ein und geben Sie die erweiterte Codetabelle und die Codierung des Textes als Folge von int-Zahlen aus. Bei längeren Texten (über 64K) kann es sein, dass die freien Symbole aufgebraucht sind. In diesem Fall werden die ersten Symbole wieder
    überschrieben.

    ein Beispiel in Wikipedia zur LZW Codierung: https://de.wikipedia.org/wiki/Lempel-Ziv-Welch-Algorithmus

    Die Verwendung von map oder vector ist leider nicht erlaubt.

    Ich habe bereits ein Programm geschrieben aber er gibt nicht die richtigen Werte aus, jedoch kann ich meinen Fehler nicht finden.
    Ich hoffe mir kann jemand helfen 😕 🙂

    #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <math.h>
using namespace std;

int main()
{

	int dictSize = 256;
	char dictionary[512];
    for(int i = 0; i < dictSize; i++) {
        dictionary[i] = i;
    }

    	string input;
		cout << "user input: ";
		cin >> input;
		int next = 1;

		for (int j = 0; j < input.length(); j++)
		{
			for(int k = 0; k < sizeof(dictionary); k++) {

				if (dictionary[k] == input[j] + input[next]){
					cout << int(dictionary[k]);
					next++;
				}

				else if (dictionary[k] == input[j]){
					dictionary[k] = input[j] + input[next];
					cout << int(dictionary[k]) << " ";

				}

			}

		}

	return 0;

	}
    0
  • C

    Dieser Thread wurde von Moderator/in SeppJ aus dem Forum Mathematik und Physik in das Forum C++ (alle ISO-Standards) verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • Mod

    Wie man seinen Beitrag lesbar formatiert

    Nun, da man es lesen kann (Danke, Arcoth!): Du kannst nicht einfach raten, wie eine Syntax in C++ wohl aussehen könnte. Und noch viel weniger durch ausprobieren herausfinden. char ist ein Datentyp für genau ein Zeichen. Die Summe von zwei char ist wieder ein char (und zwar ein char, dessen Position in der internen Zeichentabelle der Summer der Positionen der beiden Summanden entspricht), keine Folge von zwei chars!

    Außerdem solltest du aufpassen, wie groß dein Wörterbuch aktuell ist.

    0
  • Mod

    Ich hatte zu viel Zeit:
    Wörterbuchklasse:

    class Dictionary
{
  std::array<std::string, 65536> data_;  // Die ersten 256 könnte man sich sparen. Aber wenn wir schon ohne vector auskommen sollen und daher alles im Voraus reservieren, dann machen 256 weitere Beiträge auch nicht mehr viel aus.
  std::size_t size_;

public:
  Dictionary(): size_(256)
  {
    for (int i = 0; i < 256; ++i)
      data_[i] += i; 
  }

  int find(const std::string& string) const
  {
    if (string.size() == 1)
      return string[0];

    for (std::size_t index = 256; index < size_; ++index)
      if (data_[index] == string)
        return index;

    return -129;
  }

  void add(const std::string& string)
  {
    data_[size_++] = string;
  }

  void print_extended_table(std::ostream &out)
  {
    for (std::size_t index = 256; index < size_; ++index)
      out << std::hex << index << ":\t" << data_[index] << '\n';
  }

  std::string get_string(std::size_t index) const
  {
    return data_[index];
  }

  std::size_t size() const
  {
    return size_;
  }
};

    Codierung und Ausgabe des erweiterten Wörterbuchs:

    Dictionary dictionary;

  std::string last_string;
  int last_encoding;
  char next_character;
  while(std::cin.get(next_character))
    {
      std::string next_string = last_string + next_character;  // Zu einem String kann man tatsächlich ein Zeichen addieren und bekommt dann einen String mit diesem Zeichen angehängt.

      int next_encoding = dictionary.find(next_string);
      if (next_encoding > -129)
        {
          last_string = next_string;
          last_encoding = next_encoding;
        }
      else
        {
          dictionary.add(next_string);
          std::cout << std::hex << last_encoding << '\t';
          last_string = next_character;
          last_encoding = (unsigned char) next_character;
        }
    }
   if (last_string.size())
     std::cout << std::hex << last_encoding << '\n';

   dictionary.print_extended_table(std::cout);

    Decodierung:

    Dictionary dictionary;

  std::size_t last_code;
  if (std::cin >> std::hex >> last_code)
    std::cout << dictionary.get_string(last_code);

  std::size_t next_code;
  while (std::cin >> std::hex >> next_code)
    {
      if (dictionary.size() > next_code)
        {
          dictionary.add(dictionary.get_string(last_code) + dictionary.get_string(next_code)[0]);          
        }
      else
        {
          dictionary.add(dictionary.get_string(last_code) + dictionary.get_string(last_code)[0]);           
        }
      std::cout << dictionary.get_string(next_code);
      last_code = next_code;
    }

    Ausdrücklich nicht beachtet:
    -Die Klausel "Bei längeren Texten (über 64K) kann es sein, dass die freien Symbole aufgebraucht sind. In diesem Fall werden die ersten Symbole wieder überschrieben." kam mir komisch vor. Du darfst dir eine sinnvolle Behandlung ausdenken oder aber deiner Vorgabe folgen. Derzeit tut das Programm einfach so, als könne der Fall nicht vorkommen 🕶
    -Die Integrität des zu decodierenden Streams wird nicht geprüft. Musst du noch machen.

    0
Anmelden zum Antworten