[C++] Run Length Encoding geeft teveel slashes bij decoderen

[laurenssie]

(dit is een huiswerktopic)
Hallo allen,

In het volgende C++ programmeerwerkje was het de bedoeling om bestanden dmv Run Length Encoding te compressen. Voor degenen die er niet mee bekend zijn, dit houdt in dat een string als aaaaabbbbbb87324 naar het volgende wordt gecomprimeerd: a5b6\8\7\3\2\4

Dus vijf a'tjes wordt vervangen door a5, zes b'tjes wordt b6 en voor alle getallen en backslashes komt een backslash te staan om het zodoende te kunnen onderscheiden. Voor het gemak heeft onze leraar nog bedacht dat het wel leuk was om die getallen om te keren, dus aaaaaaaaaaaa wordt a21 in plaats van a12.

Nu werkt ons coderen perfect, maar bij het decoderen (line 121-176) gaat het mis zodra er slashes in het spel komen. Wat er gebeurt is het volgende:

- Er wordt bijvoorbeeld een string als a7959dddd gecomprimeerd. Dit geeft als resultaat a\7\9\5\9d4.
- Als we dan weer gaan decoderen, denkt het programma dat \7 betekent dat er 7 slashes moeten komen, waardoor het bestand overspoeld wordt met backslashes

Dit zal ongetwijfeld een klein, dom foutje zijn, maar we komen er niet meer uit (eerstejaars studenten he )

We hebben hier in ons werkcollege uren mee zitten stoeien, Rosetta heeft ons niet geholpen (die gebruikt een of andere rare library) en ook de student-assistent wist niet precies hoe hij dit nou op kon lossen. We hebben al vooruitgang geboekt, eerst bleef het programma namelijk zevens uitspugen als het een \7 tegenkwam..

Als er iemand is die tijd en zin heeft om een kijkje te nemen en ons een stapje in de goede richting kan helpen (tenslotte moeten we dit wel zelf bedenken op het tentamen), zijn we al heel gelukkig

Alvast bedankt!


Decodeer-functie:

C++:

void decodeer(ifstream &invoer, ofstream &uitvoer){
   char prevkar = '$'; //vorige karakter (voor vergelijking); $ = default
   char kar; //huidig karakter
   int n = 0; // teller voor hoe vaak een karakter nog uitgevoerd moet worden
   int aantalTekensUit = 0; //teller voor grootte outputbestand
   int tellertje = 0; //teller voor voorloopnullen
   char onthoudLetter = '@'; //als een letter onthouden moet worden gebruiken we deze
   bool dubbelebackslash = false; //bool voor dubbele backslashes
   int aantalslash = 0; //aantal slashes dat de decodeerder tegenkomt

   kar = invoer.get();
   while (!invoer.eof())
   {      
      if (kar == '0')       
         tellertje++;      

      if (kar == '\\')
         aantalslash++;
       
      else if (prevkar != '\\')
         aantalslash = 0;
        
      if (isGetal(kar) && (prevkar != '\\' || dubbelebackslash))
             n = 10*n + kar-'0';
                               
      else {
         n = omgekeerdDecodeer(n, tellertje);
         tellertje = 0;
         
         while (n > 1){       
            uitvoer << onthoudLetter;
            n--;
            cout << "ik zit in de while" << endl;
         }//while
      
         n = 0;
         onthoudLetter = kar;
         
         if (aantalslash != 1)
            uitvoer.put(kar);

      }//else
      
      if (aantalslash == 2)
          dubbelebackslash = true;
      else
          dubbelebackslash = false;     
    
      aantalTekensUit++;
      prevkar = kar;  
      kar = invoer.get();   
            
   }//while
}

omgekeerd-decodeerfunctie

C++:

int omgekeerdDecodeer(int getal, int nullen){
   int omkeerhulpje = 0; //zorgt voor afhandeling voorloopnullen
      
   while (getal > 0){
      omkeerhulpje *= 10; 
      omkeerhulpje += laatsteCijfer(getal);
      getal /= 10;
   }//while
  
   while (nullen > 0){
      omkeerhulpje *= 10;
      nullen--;
   }//while 
   
   return omkeerhulpje;
}// omgekeerdDecodeer

[ Voor 39% gewijzigd door laurenssie op 15-10-2012 16:05 ]

[kutagh]

Wat mij opvalt is dat je decodeert door een huidige karakter, vorige karakter en eventueel een onthouden letter te bewaren.
Misschien kun je het programma een stuk duidelijker maken door dit aanpak te nemen:

- Lees een stuk van invoer in en bewaar de invoer totdat je bij een nieuwe karakter komt om te printen (dus "a\7\9\5\9d4" splits je uiteindelijk op in "a" "\7" "\9" "\5" "\9" "d4"). Kijk goed naar hoe je weet wanneer er een nieuwe karakter komt.
- Controleer of de eerste karakter een letter is of iets anders.
* Bij een letter pas je het decoderen van de aantal herhalingen toe (het decoderen kan simpeler hierdoor) en print je de juiste aantal letters.
* Bij een andere karakter verwijder je de beginnende backslash.

[BtM909]

Als er iemand is die tijd en zin heeft om een kijkje te nemen en ons een stapje in de goede richting kan helpen (tenslotte moeten we dit wel zelf bedenken op het tentamen), zijn we al heel gelukkig

Ik kan me niet voorstellen dat je 210 regels code nodig hebt om je PoC hier weer te geven. Je mag gerust een huiswerkvraag stellen, maar simpelweg je code dumpen is niet de bedoeling. Ik geef je een kans om je code aan te passen en alleen de relevante code weer te geven. Aan te geven waar je denkt dat de fout ontstaat, aangeven waarop je hebt gezocht en iets van blijk geven dat je snapt wat met dit topiconderdeel wordt bedoeld: Programming FAQ - Algemeen#debuggen

[lauwsa]

Waarom zetten jullie overal neer wat je afsluit, bvb:

code:

while (XXXX)
{ 
    XXXX
}//while

Ik snap wel dat je zo snel kan zien wat je afsluit, maar als je met je muis op de } gaat staan zie je ook waar hij geopend word ( als je een beetje IDE hebt ). Wat hebben jullie eigelijk al gedebuged? Kan je dus laten zien waar het presies mis gaat?

Edit:
Waarom noem je eigelijk een variable kar, met als aantekening dat het over het huidige karakter gaat. Noem hem dan meteen "huidigKarakter". Dan weet je meteen waar je het over hebt en heb je geen aantekening nodig.

Lang niks meer in C++ gedaan, maar doet dit wel het genen wat je wilt:

code:

n = 10*n + kar-'0';

'0' is namelijk hier 48 (ascii char naar int)

[ Voor 37% gewijzigd door lauwsa op 15-10-2012 16:25 ]

[laurenssie]

BtM909 schreef op maandag 15 oktober 2012 @ 16:01:
[...]


Ik kan me niet voorstellen dat je 210 regels code nodig hebt om je PoC hier weer te geven. Je mag gerust een huiswerkvraag stellen, maar simpelweg je code dumpen is niet de bedoeling. Ik geef je een kans om je code aan te passen en alleen de relevante code weer te geven. Aan te geven waar je denkt dat de fout ontstaat, aangeven waarop je hebt gezocht en iets van blijk geven dat je snapt wat met dit topiconderdeel wordt bedoeld: Programming FAQ - Algemeen#debuggen

Aangepast.

Voor wat betreft het debuggen: ik switch even naar m'n linux en dan zoek ik dat spul op.

[kzin]

Er wordt bijvoorbeeld een string als a7959dddd gecomprimeerd. Dit geeft als resultaat a\7\9\5\9d4

Ik kan me vergissen, maar volgens de methode die je gebruikt, zou a7959dddd als resultaat moeten geven:
\a\7\9\5\9d4
Dan ben je tenminste consequent, en gaat het decoderen ook goed.

[Anoniem: 273048]

Zorg eerst dat het decoderen werkt zonder backslashes in de invoer. Maak vervolgens een boolean variabele, die je op true zet als je een backslash tegenkomt die dient om het volgende karakter te 'escapen'. In dit geval ook gelijk invoer.get() doen om het karakter dat wordt 'geescaped' in te lezen. Dit karakter dan hetzelfde behandelen als een 'a' of een 'b'. Moeilijker dan dit is het niet.

[ Voor 13% gewijzigd door Anoniem: 273048 op 15-10-2012 16:21 ]

[laurenssie]

Ik heb zojuist het volgende stukje toegevoegd:

C++:

if (prevkar = '\\' && isGetal(kar)){
   uitvoer << kar; 
}

Nu komen er geen overbodige slashes meer, maar krijg je bij iets als \2 in de uitvoer \22, dus het programma doet nog steeds wat met die \. Dit is in ieder geval een stuk vooruitgang, ik stoei nog even verder

Anoniem: 273048 schreef op maandag 15 oktober 2012 @ 16:14:
Zorg eerst dat het decoderen werkt zonder backslashes in de invoer. Maak vervolgens een boolean variabele, die je op true zet als je een backslash tegenkomt die dient om het volgende karakter te 'escapen'. In dit geval ook gelijk invoer.get() doen om het karakter dat wordt 'geescaped' in te lezen. Dit karakter dan hetzelfde behandelen als een 'a' of een 'b'. Moeilijker dan dit is het niet.

Hoe 'escape' je een karakter? Gewoon niet outputten?

[Anoniem: 273048]

Met escapen bedoelde ik dat je er bij het coderen een backslash voorzet

[laurenssie]

Yeehaa, het is gelukt. Sleutel tot de oplossing: kijken of het vorige karakter een \ is en het karakter erna een getal. Dan nog een simpele isLetter functie maken, als het huidige karakter slechts 1 letter is sowieso outputten.

Thanks voor het meedenken allemaal!

Werkende code

[ Voor 6% gewijzigd door laurenssie op 15-10-2012 17:12 ]

[Anoniem: 273048]

Werkt bijvoorbeeld "\\\8" ook? Moet worden "\8"

[Soultaker]

Cases als "\\\\7" zijn ook interessant met de implementatie van de TS.