(Mathe) "Komprimierung" von Matrizen

[Boron]

Hier mal eine Frage an alle, bei denen Mathe nicht mit "zwei Dosen Bier ohne Pfand = 80 Cent" aufhört.

In einem noch zu schreibenden Computerprogramm werde ich eine Tabelle (Array) haben.
Das wird dann in etwa so aussehen:

  |1 [b]2[/b] 3 4 5
 -----------
 [b]a[/b]|  [b]m[/b]
 b|n       o
 c|p   q
 d|  r

Die Tabelle bedeutet in etwa das hier:
- Wenn eine bestimmte Variable den Wert a hat, und eine andere Variable den Wert 2 hat, dann soll erste Variable den Wert b annehmen.
Ich habe das mal hervorgehoben.

Jetzt seht ihr im Beispiel, dass die Tabelle nicht voll besetzt ist. Mathematiker nennen dies dünn besetzte Matrix.

Meine Matrix wird viel mehr Zeilen und Spalten haben.
Bsp. 100 Zeilen und 100 Spalten, in denen jeweils ein 4 Byte Wert gespeichert ist. Das ergibt als notwendiger Speicher 100*100*4 Bytes = 40.000 Bytes = ca. 39 KB.

Das System auf dem das Programm laufen soll ist ein sogenanntes "Embedded System". Da gibt es extrem wenig Speicher.
Ich muss also unbedingt Speicher sparen!

Jetzt endlich zur eigentlichen Frage:
Ich weiß, dass es Algorithmen gibt um Matrizen zu komprimieren, also den Speicherverbrauch zu verkleinern.

Kennt ich irgend jemand hier sich mit so etwas aus?
Hat jemand einen Bekannten, der sich mit so etwas auskennt?
Welche Algorithmen gibt es?
Kenn jemand passende Literatur?
Wie nennt sich denn die "mathematische Disziplin", in die das Thema reinfällt?

 

[7H3 N4C3R]

Hmmm.... was ich Dir sagen kann ist, Du solltest Dich mal nach "Sparse"-Matrizen umschauen. Würde mich wundern, wenn es für sowas nicht auch schon fertige Klassen im Netz gibt.

Btw, was willst Du da eigentlich bauen? Einen Zustandsautomaten?

 

[Loopo]

  |1 [b]2[/b] 3 4 5
 -----------
 [b]a[/b]|  [b]m[/b]
 b|n       o
 c|p   q
 d|  r

ich weiß ja nicht, ob das jetzt nur schematische Ungenauigkeit ist, oder ob es tatsächlich so aussieht: gibt es die Werte m, n, o, p, q, r jeweils nur einmal? dann könntest du nicht das Array in der Form Array[m] = { a, 2 }, ... aufbauen?

ansonsten gibt's noch die Möglichkeit:
Array[0] = { a, 2, m }
Array[1] = { b, 1, n }
...

 

[Boron]

@7H3 N4C3R (was zum bedeutet das eigentlich?
Ganz recht, das eine von vielen Möglichkeiten einen Zustandsautomaten zu implementieren.
Die Methode ist ja schnell (finden der nachsten Transition und ndes nächsten Zustands) und auch sehr einfach zu implementieren.

Großer Nachteil bleibt aber der Speicherverbrauch der Tabelle.
Lass so etwas mal auf einem System mit 512KB ROM und 24 KB RAM laufen.

Ich habe bewusst auf den Ausdruck "Sparse Matrix" verzeichtet, weil er ja eigentlich nur die Übersetzung von "dünn besetzte Matrix" ist.
Ich werde aber trotzdem mal intensiver das Wort bei der Suche benutzen.

@Loopo
Gut beobachtet.
Die Werte m bis r können auch mehrmals in der Tabelle auftreten.


Ich habe da mal noch was gefunden, das sich Row Displacement Scheme (RDS) nennt.
Blos noch keine Algo dazu.

 

[Toaster]

http://www.cs.ucsb.edu/labs/oocsb/papers/TRCS95-05.pdf

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol21/issue1/spe003cc.pdf

hoffe das hilft dir weiter

Gruß

Toaster

 

[LeChris]

Ich würde von dem Array weg gehen. Wobei noch die Frage ist, ob die Tabelle dynamisch ist...

Aber prinzipiell wäre es möglich, die Indizes und den dazu gehörigen Wert linear zu Speichern. Für diesen Fall zb:

a2mb1n5oc1p3qd2r

Wbei die Indizes natürlich jeweils erstmal nur maximal ein Byte benötigen. Dann braucht man noch einen Suchpointer, der dann die Werte liefert. Bei Fehlschlag liefert der dann 0 oder was-auch-immer.

Es ist dann nur nicht so einfach, noch Werte hinzuzufügen o.ä.. Aber mal so als Denkanstoß...