Inforeferat

[Fehlersucher]

Hallo,

ich soll in Info ein Referat (mit freier Themenwahl) halten.

Nun wollte ich ein Thema nehmen, welches man auch gut implementieren kann.
Es sollte also (mehr oder weniger) spannend und für die anderen auch leicht verständlich sein.

Ich dachte zuerst an Komprimierung, jedoch scheint mir die Implementation davon recht schwierig zu sein.

Hat jemand vielleicht Anregungen für andere Themen?

[Furtbichler]

Komprimierung: Geht eigentlich

RLE ist sehr leicht erklärt,
LZW ist nur ein wenig schwerer.
Huffman/Shannon-Fano geht auch noch.

Von der Implementierung her sind die drei Verfahren auch nicht soo schwer.

Die anderen sind imho stärkerer Tobak (LZ77/78/SS, BZIP, Markov usw.)

Aber das ist auch eine Frage der Erfahrung.

Im 'schlimmsten' Fall verwende Sortierverfahren und/oder die lineare bzw. binäre Suche.

[DeddyH]

Steganografie ist auch ein beliebtes Thema AFAIK.

[implementation]

Du koenntest auch einfache Kryptographie machen, wie Vigenere oder so. Aber sei dir dann im Klaren, dass das nicht sicher ist.

[BUG]

Afaik sind die Prinzipien der an Deflate beteiligten Algorithmen relativ einfach zu zu verstehen, insbesondere wenn man nicht großartig optimieren will.
Schön bei der Komprimierung ist, das man was an der Tafel vorführen kann (evtl. auch "interaktiv" mit den Mitschülern).

[Fehlersucher]

Also,

Kryptographie und Steganographie hatten wir schon so im Unterricht und fallen damit weg.
Der DEFLATE-Algorithmus scheint mir schwieriger als die von Furtbichler genannten Algorithmen zu sein.

@ Furtbichler

Die drei von dir genanten Algorithmen sehen sehr interessant aus. Ich werde wahrscheinlich RLE nehmen.

Jedoch hätte ich ein Problem:

Die Implementierung wäre ja beispielsweise mit Strings relativ einfach.
Aber was ist, wenn ich zeigen möchte, wie ein Bild komprimiert wird?
Dann arbeite ich ja nicht wie bei Strings mit einzelnen Charactern sodern mit Bytes.

Und wie komme ich bei Dateien (z.B. Bildern) an diese Bytes dran?
Wie kann man mit den Bytes arbeiten? Speichert man die irgendwie als Variable?

Ist es auch noch im Bereich des Machbaren den ersten Algorithmus für richtige Dateien zu implementieren?

Gruß

[Bummi]

Wenn Du bei einem Bitmap die reinen "Pixeldaten" meinst dann kannst Du mal nach Scanline suchen. Ansonsten könntest Du gleich das ganze File verwenden.

[Furtbichler]

Zitat:

Zitat von BUG (Beitrag 1198788)

Afaik sind die Prinzipien ... relativ einfach zu zu verstehen

Also entweder *verstehst* Du es, oder nicht. Nix mit 'afaik' (afaik="Soweit ich das weiß" => "Ich glaube").

Zitat:

Zitat von Fehlersucher (Beitrag 1198803)

Und wie komme ich bei Dateien (z.B. Bildern) an diese Bytes dran?
Wie kann man mit den Bytes arbeiten? Speichert man die irgendwie als Variable?

Du scheinst noch nicht so gut programmieren zu können. Dann ist das vielleicht eine Nummer zu hoch, oder (wenn Du ergeizig bist), fängst Du einfach an und holst Dir Hilfe hier im Forum.

[BUG]

Zitat:

Zitat von Furtbichler (Beitrag 1198813)

Zitat:

Zitat von BUG (Beitrag 1198788)

Afaik sind die Prinzipien ... relativ einfach zu zu verstehen

Also entweder *verstehst* Du es, oder nicht. Nix mit 'afaik' (afaik="Soweit ich das weiß" => "Ich glaube").

Aber ich weiß nicht ob andere das verstehen, also kann ich nur von den Leuten ausgehen, die ich kenne (im Zweifelsfall nur ich), und dann verallgemeinern :mrgreen:

[Fehlersucher]

Zitat:

Zitat von Bummi (Beitrag 1198811)

Wenn Du bei einem Bitmap die reinen "Pixeldaten" meinst dann kannst Du mal nach Scanline suchen. Ansonsten könntest Du gleich das ganze File verwenden.

Wie macht man das mit dem ganzen File?

Zitat:

Zitat von Furtbichler (Beitrag 1198813)

Zitat:

Zitat von BUG (Beitrag 1198788)

Afaik sind die Prinzipien ... relativ einfach zu zu verstehen

Also entweder *verstehst* Du es, oder nicht. Nix mit 'afaik' (afaik="Soweit ich das weiß" => "Ich glaube").

Zitat:

Zitat von Fehlersucher (Beitrag 1198803)

Und wie komme ich bei Dateien (z.B. Bildern) an diese Bytes dran?
Wie kann man mit den Bytes arbeiten? Speichert man die irgendwie als Variable?

Du scheinst noch nicht so gut programmieren zu können. Dann ist das vielleicht eine Nummer zu hoch, oder (wenn Du ergeizig bist), fängst Du einfach an und holst Dir Hilfe hier im Forum.

Nun, ich habe seit etwa 3 Jahren Info. Wir haben aber nie über Bytes gesprochen, geschweige denn, wie man diese aus Dateien herausquetscht.

Wie bekommt man jetzt die Bytes aus einer beliebigen Datei? Kann man die Bytefolge dann in einen String schreiben und mit dem String den RLE-Algorithmus füttern?

Gruß

[Bummi]

Eine Bytefolge gehört nicht in einen String sondern in einen Stream,
eine Array of Byte oder ähnliches.
Ich war gedanklich allerdings bei LZW hängengeblieben, sorry.
Für RLE macht es natürlich Sinn nur auf die Bilddaten zuzugreifen. Da würde dann wieder der Verweis auf Scanline greifen, die Triple/QuadArrays lesen, mit letzt gelesenem vergleichen und Zähler und Array direkt wieder in einen Stream schreiben.
Falls es doch in Richtung LZW gehen sollte:
Lesen kannst Du so eine Datei z.B. in einen MemoryStream und über MemoryStream.Memory wahlfrei zugreifen. Du könntest aber auch einfach per FileStream Byte für Byte einlesen.
Für die Generierung der Tabellen wirst Du Verwaltungsstrukturen, gegf. in Form von Arrays benötigen.

[p80286]

3 Jahre und kein Byte?
Das klint für mich als hättest Du zuerst die binomischen Formeln gelernt ohne das kleine 1x1 zu kennen.
Ein Byte ist die kleinste Informationseinheit. Sie wird mit 8 Bit dargestellt. Ein Bit hat den Wert 0 oder Eins. Ein Byte kann somit Werte von 0 bis 2^8 -1 annehmen.
ird das höchste Bit als Vorzeichen interpretiert, dan reicht der Wertebereich von -127 bis 127. Ein Byte kann auch als (Ansi-)Char interpretiert werden. Davon dan mehrere hintereinander sind ein string oder ein Array of Char.

Gruß
K-H

[Valle]

Ich glaube du interpretierst da etwas zu viel in die Aussage rein.

Ich hatte auch knapp drei Jahre Informatik und wir haben überhaupt nichts sinnvolles gelernt. Streams oder byteweiser Zugriff auf Dateien? Nä. Wir fangen jetzt an "HTML zu programmieren". Erwarte nicht zu viel von Informatik in der Schule. Bei manchen Themen wäre es sogar besser gewesen, wenn wir sie gar nicht erst behandelt hätten...

Liebe Grüße,
Valentin

[p80286]

Du willst mich veräppeln??

Gruß
K-H

[Valle]

Zitat:

Zitat von p80286 (Beitrag 1198841)

Du willst mich veräppeln??

Ähm, nein? Mein Post war (zur Ausnahme ;-) ) völlig frei von Ironie oder ähnlichem.

Ist dir irgendwas davon jetzt wirklich neu? Ich dachte mittlerweile hätte sich sowas hier rumgesprochen.

Liebe Grüße,
Valentin

[Furtbichler]

Ich glaube, es geht nicht um die Güte des Informatik-Unterrichts in Schulen, sondern um das Referat.

Ich würde das auch nicht auf eine Datei anwenden, denn es geht im Referat nicht unbedingt um den Zugriff auf Dateien. Natürlich wäre es schick, als Essenz des Referates ein kleines Komprimierungsprogramm vorzuweisen, aber imho wäre das ein wenig viel für den Anfang.

Du kannst auf verschiedene Arten auf eine byteweise auf eine Datei zugreifen. Hier mal die Stichwörter: TFileStream (modern) per 'File Of Byte (Uralt, Einzige Möglichkeit des Ur-Pascal)' oder per 'File/BlockRead (alte Methode)'. Google mal nach diesen Stichwörtern.

[sx2008]

Zitat:

Zitat von Fehlersucher (Beitrag 1198803)

Kryptographie und Steganographie hatten wir schon so im Unterricht und fallen damit weg.

Na dann würde ich doch eher eine Simulation programmieren.
Zum Beispiel eine Wärmesimulation.
http://www.youtube.com/watch?v=TvlIfSlLB0c
Ein Array aus 100 * 100 Kacheln wobei jede Kachel eine Temperatur hat die durch die Farbe angezeigt wird.
Per Mausklick werden ein oder mehrere Kacheln erhitzt und das Programm errechnet wie sich die Wärme verteilt.
Die Berechnung ist eigentlich ziemlich einfach.

Delphi-Quellcode:

Temp_neu := Temp_alt + Summe(Temperaturdifferenz zum Nachbarn) * Faktor;

Jede Kachel hat max 8 Nachbarn.
Man kann die Berechnung noch verfeinern, indem die diagonalen Nachbarn einen kleineren Faktor bekommen als die horizontalen und vertikalen Nachbarn.
Man benötigt zwei Arrays, die man jeweils im Wechsel für die alten und neuen Temperaturen benützt.

[Fehlersucher]

Zitat:

Zitat von sx2008 (Beitrag 1198859)

Zitat:

Zitat von Fehlersucher (Beitrag 1198803)

Kryptographie und Steganographie hatten wir schon so im Unterricht und fallen damit weg.

Na dann würde ich doch eher eine Simulation programmieren.
Zum Beispiel eine Wärmesimulation.
http://www.youtube.com/watch?v=TvlIfSlLB0c
Ein Array aus 100 * 100 Kacheln wobei jede Kachel eine Temperatur hat die durch die Farbe angezeigt wird.
Per Mausklick werden ein oder mehrere Kacheln erhitzt und das Programm errechnet wie sich die Wärme verteilt.
Die Berechnung ist eigentlich ziemlich einfach.

Delphi-Quellcode:

Temp_neu := Temp_alt + Summe(Temperaturdifferenz zum Nachbarn) * Faktor;

Jede Kachel hat max 8 Nachbarn.
Man kann die Berechnung noch verfeinern, indem die diagonalen Nachbarn einen kleineren Faktor bekommen als die horizontalen und vertikalen Nachbarn.
Man benötigt zwei Arrays, die man jeweils im Wechsel für die alten und neuen Temperaturen benützt.

Auch ein interessantes Thema.
Würdest du die Kacheln durch ein StringGrid darstellen und dann die Berechnung bei dem OnClick setzen?
Wie würdest du den Temperaturen die Farben (flüssig) zuweisen?

Noch einmal zu RLE:
RLE lohnt sich doch soweit ich weiß nicht nur für Bilder, sondern auch für Text.

Hat jemand von euch einen Ansatz für eine Routine, welche die Bytes einer beliebigen Datei in einen Stream schreibt?

[DeddyH]

TMemoryStream.LoadFromFile

[Sir Rufo]

Mal eine ganz doofe Frage:

Zitat:

Zitat von Fehlersucher (Beitrag 1198803)

Steganographie hatten wir schon so im Unterricht

Zitat:

Zitat von Fehlersucher (Beitrag 1198822)

Wir haben aber nie über Bytes gesprochen, geschweige denn, wie man diese aus Dateien herausquetscht.

Kann man Steganographie behandeln ohne mit den Bytes in Berührung zu kommen? :gruebel:

[Aphton]

Oberflächlich; ist aber ned so interessant

[Medium]

Zitat:

Zitat von Fehlersucher (Beitrag 1198871)

Würdest du die Kacheln durch ein StringGrid darstellen und dann die Berechnung bei dem OnClick setzen?
Wie würdest du den Temperaturen die Farben (flüssig) zuweisen?

Ich würde das eher in einer 100x100 Pixel großen TPaintBox zeichnen. Bei den Farben kommt es ein wenig darauf an, was du als maximale und minimale Teperatur definieren möchtest:
Grundlage: Farben werden (in der Regel) als RGB-Tripel angegeben - (R)ot, (G)rün und (B)lau Anteil, wobei jeder davon von 0 (von dieser Farbe nix) bis 255 (volle Kanne diese Farbe) sein kann. Einem Pixel eine Farbe zuweisen könnte man (langsam aber dafür recht einfach) z.B. mittels

Delphi-Quellcode:

TPaintBox.Canvas.Pixels[x, y] := RGB(RotAnteil, GruenAnteil, BlauAnteil);

Angenommen deine tiefste Teperatur ist 0, und die höchste ist 100, und du willst Farben von Blau bis Rot haben, müssten die 3 Anteile wiefolgt berechnet werden:
RotAnteil = Round((Temperatur/100)*255)
GruenAnteil = 0
BlauAnteil = Round((1-(Temperatur/100))*255)
Damit gäbe es dann einen linearen Verlauf zwischen den Temepraturen von 0 bis 100.

Zitat:

Noch einmal zu RLE:
RLE lohnt sich doch soweit ich weiß nicht nur für Bilder, sondern auch für Text.

Nur, wenn die Texte viele aufeinanderfolgende Zeichen enthalten. Beim vorigen Satz z.B. wäre es völlig ineffizient, bei "Haaaaalllloooooooooo DDDDeeeeeelllllllphiiiiii Freeeeuuuuuunnnnddddd!!!!!!!!!!!" hingegen schon ganz gut ;)
Bei Bildern ist es eben auch so eine Sache: Wenn im Bild viele große exakt einfarbige Flächen sind, ist RLE prima. Also Comics oder Screenshots einer normalen Arbeitsumgebung und dergleichen. Bei Fotos wird es ohne weitere Tricks und Kniffe fast genau so wertlos wie für Texte.
Das heisst jedoch nicht, dass RLE grundsätzlich schlecht ist. Bei JPEG wird es z.B. sehr effizient eingesetzt, jedoch werden die Bilder dort nicht als Pixel mit Farbtripeln genommen, sondern vor der RLE-Kompression noch recht kompliziert umgewandelt, aufbereitet, eingestampft und umsortiert. All dieses Verhackstückeln wird aber letztlich auch deswegen gemacht, damit gerade die RLE-Kompression möglichst effiziente Ergebnisse bringt. Daher: RLE einzeln für sich betrachtet mag anfangs wenig sinnvoll erscheinen, es ist aber dennoch an vielen Stellen ein ganz wichtiger Schlüsselpart in vielen Belangen. Nur eben nicht auf Rohdaten, sondern eben auf solche, die darauf abgerichtet sind für RLE geeignet zu sein. Die Abrichtung dort hin ist jedoch eher Stoff für 3.-4. Semester Info Studium, und hat eher mit Signalverarbeitung und Mathe zu tun, weniger mit Informatik an sich.

[Aphton]

[QUOTE=Medium;1198936]

Zitat:

Zitat von Fehlersucher (Beitrag 1198871)

Nur, wenn die Texte viele aufeinanderfolgende Zeichen enthalten. Beim vorigen Satz z.B. wäre es völlig ineffizient, bei "Haaaaalllloooooooooo DDDDeeeeeelllllllphiiiiii Freeeeuuuuuunnnnddddd!!!!!!!!!!!" hingegen schon ganz gut ;)
Bei Bildern ist es eben auch so eine Sache: Wenn im Bild viele große exakt einfarbige Flächen sind, ist RLE prima. Also Comics oder Screenshots einer normalen Arbeitsumgebung und dergleichen. Bei Fotos wird es ohne weitere Tricks und Kniffe fast genau so wertlos wie für Texte.

Einer dieser Tricks ist es, die Entropie zu senken - bei Bildern geht das einfach, indem man ein Differenz-Bild erzeugt. Da die Differenzen zweier benachbarten Pixel meistens sehr gering ist, kommt es dadurch zu einer Senkung der Entropie, da nur noch mehr eben diese Differenzen gespeichert werden und diese meistens voneinander nicht allzu stark varieren.
Kommt übrigens bei PNG zum Einsatz!