Lineairiseren van een tabel

[Alain]

Ik wil een programma maken om de inhoud van tabellen te minimaliseren. Ik wil hiervoor een algoritme programmeren die de waarden in de tabel lineairiseert, uiteraard met zo weinig mogelijk verliezen aan nauwkeurigheid. De tabel geeft het inhoud van een tank weer, afhankelijk de de vloeistofhoogte en de hoek waaronder de tank zich op dat moment bevindt. De data wordt ingelezen (en gecached) door een PLC en dat gaat niet bepaald snel, hierdoor wil ik de in te lezen data minimaliseren.

De tabel bouw ik als volgt op:

code:

    -1.5    -1  -0.5    0   0.5 1.5
0   0   1   2   3   4   5
10  1   2   3   4   5   6.1
20  2   3   4   5   6   7
30  3   4   5   6   7   8
80  4   5   6   7   8   9

De eerste regel geeft de hoek weer (muv de eerste kolom). Daarna is de eerste kolom de hoogte in mm en de waarden die erna staan de inhoud in m³. Ik wil een tabel overhouden met zo weinig mogelijk rijen en kolommen, met een zo groot mogelijke nauwkeurigheid. Aangezien in de PLC ruimte is voor 1000 rijen wil ik dit als maximum aanhouden en wil ik de nauwkeurigheid instelbaar maken. Meestal heeft een tabel minder dan 1000 rijen en speelt nauwkeurigheid een rol.

Om het eenvoudig te houden wil ik eerst het algoritme toepassen op een enkele kolom. In het voorbeeld zou dit voor de eerste kolom 3 records opleveren ({0, 0}, {30, 3}, {80. 4}) en voor de zesde kolom 5 records ({0, 5}, {10, 6.1}, {20, 7}, {30, 8}, {80, 9}) bij 0% afwijking. De tabel die uiteindelijk gelineairiseerd moet worden is uiteraard veel groter en complexer.

Mijn eerste gedachte was om stappen te zoeken met de meeste regels en met de kleinste afwijking. Ik voorzie hier het probleem dat de afwijking zich in het meest lineaire gedeelte van de tabel gaat concentreren en niet verdeeld wordt over de totale inhoud. Dit lijkt in eerste instantie de bedoeling, maar het zou beter zijn als een ander lineair gebied ook een deel van de afwijking voor zijn rekening zou nemen.

De volgende gedachte was om een stap te berekenen met de laagste afwijking. Er zal een nieuwe maximale afwijking voor de stap bijgehouden worden en als er een stap is met een kleinere afwijking, zal deze gekozen worden. Probleem is dat de maximale afwijking niet gelijk hoeft te zijn aan de werkelijke afwijking.

Een derde gedachte is om elke stap met een soort brute force/backtracking aloritme door te rekenen om de maximale nauwkeurigheid te behalen.

Zijn hier misschien slimmere algoritme's voor?

[H!GHGuY]

Zeker weten!

Kijk even opzij naar wat er in MPEG gebeurd. Daar heb je typisch een tabel van volgende aard:

code:

158 130 75 50 31 15 3 0 0 0
125 114 59 36 23  9 0 0 0 0
 98  63 42 27 18  6 0 0 0 0
 64  47 32 15  7  0 0 0 0 0
... en nog wat rijen

wat nu gebeurt is een herordening van de tabel als volgt:
158 130 125 98 114 75 50 59 63 64 ...
Ze zigzaggen dus letterlijk door de tabel.

Op die manier creer je waarden die opeenvolgend dicht bij elkaar liggen. Dit kan je vervolgens met minder bits proberen weergeven + run-length coding op toepassen. Voor de details verwijs ik je echter door naar google want die zitten me helemaal niet fris meer in het geheugen

[Alain]

Ik denk dat ik snap wat je bedoeld, maar volgens mij gaat dat in mijn geval niet werken. Ik behoud dan namelijk evenveel informatie. Voor de PLC maakt het niet (veel) uit hoe gecomprimeerd de data opgeslagen is, maar hoeveel waarden de tabel heeft. Ik moet juist rijen schrappen, zodat ik de cache niet zo vaak hoef te verversen.

Ik wil het volgende eens proberen:

1. Bepaal afwijking bij het lineairiseren van rij 2 tot en met n - 1 voor alle kolommen, neem de grootste afwijking. Totale afwijking = 0%.
2. Sorteer op afwijking van klein naar groot.
3. Begin met de kleinste afwijking (rij x)
4. Als (Totale afwijking + afwijking rij x) > Maximale afwijking? einde; anders lineairiseer rij x.
5. Totale afwijking += afwijking rij x
6. Bereken de afwijking voor alle gelineairiseerde rijen uit de originele tabel tussen rij x - 1 en rij x + 1 uit de nieuwe tabel en voor alle kolommen, neem de grootste afwijking en bewaar deze voor rij x + 1.
7. Ga naar 2

Ik ben alleen bang dat het wel een traag geheel gaat worden, maar op zich is snelheid geen issue.

Eerst java maar weer eens een beetje leren. Het leek me wel weer eens leuk om java te gebruiken, maar ik merk dat we op school niet veel leerden.

[H!GHGuY]

Sla de tabel lineair op zoals ik aangeef.
Pas daarop run-length coding toe, eventueel sla je enkel de diff op.

Zoek het verband tussen x,y -> z

Door je run-length coding kun je sneller zoeken:

code:

z = calc(x,y)

index = 0
current = total = table[index]
while (index < z)
{
  value, number = runlengthdecode(table[index]);
  if (number > z - index)
    total = (current + value) * number
    index += number
  else
     total = (current + value) * z - index
     index = z;
  current = current + value;
}

of iets in die trend

[Alain]

Volgens mij snap ik nog steeds wat je bedoeld. Ik snap alleen niet hoe dit in mijn geval zou werken. Zoals ik het begrijp worden er nog steeds geen rijen geschrapt, maar wordt de tabel compacter opgeslagen. Daarnaast mag de PLC absoluut geen decode werk verichten, en moet de PLC de data zo makkelijk mogelijk uit het bestand kunnen halen. (Deze hele actie is immers bedoeld om de PLC te ontlasten en omdat ik in een PLC bij voorbaat het geheugengebruik moet definieren).

De grootte van het bestand is (tot op zekere hoogte) niet van belang, het mag alleen niet meer dan 1000 rijen hebben.

[H!GHGuY]

Tjah, het is de eeuwenoude trade-off tussen performantie en opslag.
Daarpas vertel je nog dat snelheid geen issue is, nu mag je plots geen decode werk verrichten?
Misschien is je het nog niet opgevallen maar omzetten van x,y -> z is helemaal geen complexe stap
en die run-length coding maak je zo simpel/moeilijk als je het zelf wil. Bovendien kan je gerust je tabel partitioneren (per rij/kolom toepassen) om de performance hit te minimaliseren.

Kijk even naar Wikipedia: Self-information en huiver, want veel mensen zijn je al voorgegaan. Als je dingen wil schrappen, doe je aan compressie. Wil je aan compressie doen dan moet je even opzij gaan naar kansen/informatie-theorie en van daaruit, toegepast op jouw probleem, de juiste oplossing zoeken. Analyseer je data:
- je ziet bvb dat de waarde in [x,y] weinig verschilt van max(x-1, y-1). Kun je over je tabel itereren en telkens deze waarde aftrekken van de waarde in de tabel? Misschien hou je dan informatie over die maar half zoveel bits in beslag neemt en kun je dus 4 maal zoveel data op dezelfde plaats duwen.
- je ziet ook dat de increments beperkt zijn. Kun je delta-coding doen?
- Is floating point echt een noodzakelijkheid? Kun je met fixed point of zelfs integers iets (door bvb cm³ ipv dm³ en dus alle waarden*1000)?

Je vergeet misschien ook dat je nog informatie moet toevoegen die aanduidt wat er met de verdwenen rij is gebeurd? Op welke magische wijze haal je anders je data terug? Hoe bepaal je dat je rijen moet schrappen; het is misschien efficienter om kolommen te schrappen of misschien zelfs een arbitraire volgorde van kolommen en rijen. Welk algoritme ga je dan gebruiken om je originele tabel te reconstrueren, want uiteindelijk betekent een waarde uit je tabel halen evenveel als de tabel (of een stuk ervan) te reconstrueren.
En dit is nu net wat jij decoderen noemt...

Over jouw algoritme:
Je spreekt over afwijkingen maar vertelt niet wat er tov wat afwijkt. Bedoel je delta's tussen opeenvolgende waardes? Leg eerst even jou algoritme glashelder uit, want zoals je het nu vertelt kan geen mens er een touw aan vast knopen.

[Alain]

Allereerst, ik ben misschien niet helemaal duidelijk in het uitleggen van wat ik wil. Mijn excuses hiervoor. Ik heb er wel veel aandacht aan besteed, maar vind het erg moeilijk om het goed te omschrijven.

H!GHGuY schreef op dinsdag 13 januari 2009 @ 20:36:
Daarpas vertel je nog dat snelheid geen issue is, nu mag je plots geen decode werk verrichten?

Ik bedoelde dat snelheid geen issue is voor de PC die het algoritme uit gaat voeren en de tabel gereed maakt voor de PLC. De PLC daarentegen moet zo weinig mogelijk werk doen.

Misschien is je het nog niet opgevallen maar omzetten van x,y -> z is helemaal geen complexe stap
en die run-length coding maak je zo simpel/moeilijk als je het zelf wil. Bovendien kan je gerust je tabel partitioneren (per rij/kolom toepassen) om de performance hit te minimaliseren.

Kijk even naar Wikipedia: Self-information en huiver, want veel mensen zijn je al voorgegaan.

Het is ook niet zo complex om te implementeren op een PC met hogere programmeer talen. Ik moet de tabel uiteindelijk uitlezen met een PLC en deze beschikt niet over veel mogelijkheden.

Als je dingen wil schrappen, doe je aan compressie. Wil je aan compressie doen dan moet je even opzij gaan naar kansen/informatie-theorie en van daaruit, toegepast op jouw probleem, de juiste oplossing zoeken.

Dat is inderdaad het doel.

Analyseer je data:
- je ziet bvb dat de waarde in [x,y] weinig verschilt van max(x-1, y-1). Kun je over je tabel itereren en telkens deze waarde aftrekken van de waarde in de tabel? Misschien hou je dan informatie over die maar half zoveel bits in beslag neemt en kun je dus 4 maal zoveel data op dezelfde plaats duwen.

De waarden onderling kunnen veel verschillen, maar perfect lineair zijn. Daar waar de waarden weinig verschillen is het waarschijnlijker dat de waarden niet lineair zijn. (Een tank op een schip heeft aan de onderkant vaak de vorm van het schip. Aangezien er aan de onderkant weinig oppervlakte is, verschilt de inhoud weinig ten opzichte van de vorige inhoud, maar deze is niet lineair. Het bovenste deel van de tank is vaak het lineaire gedeelte waarbij het verschil relatief groot is, maar constant.)

- je ziet ook dat de increments beperkt zijn. Kun je delta-coding doen?

Ik heb nog geen idee wat het is, maar ik zal me inlezen.

- Is floating point echt een noodzakelijkheid? Kun je met fixed point of zelfs integers iets (door bvb cm³ ipv dm³ en dus alle waarden*1000)?

Mja, dat is een afweging. fixed point is niet mogelijk omdat de PLC hier niet mee om kan gaan. Als ik er zelf iets voor zou schrijven kunnen de apparaten die de data moeten visualiseren hier niet mee omgaan. Integers zou mogelijk zijn (dan moet ik er een DINT van maken, want een INT in de PLC is 16 bits).

De keuze voor floating point is omdat ik moet interpoleren tussen de waarden in de tabel en de integer deling dan niet voldoet.

Je vergeet misschien ook dat je nog informatie moet toevoegen die aanduidt wat er met de verdwenen rij is gebeurd? Op welke magische wijze haal je anders je data terug?

Heel simpel, niet. De tabel die aangeleverd wordt is vaak een tabel die gegenereerd wordt uit een 3d model. Deze heeft rijen met een gelijk vloeistofhoogte verschil. Als de tank op een gegeven moment een lineaire toename heeft qua volume blijft de tabel dezelfde vloeistofhoogteverschillen hanteren.

Om een lang verhaal kort te maken: Veel rijen in de tabel zijn overbodig en kunnen met een kleine afwijking geschrapt worden.

Over jouw algoritme:
Je spreekt over afwijkingen maar vertelt niet wat er tov wat afwijkt. Bedoel je delta's tussen opeenvolgende waardes?

Met afwijking bedoel ik de afwijking die je krijgt als je een rij schrapt. Dus ik bereken de waarde van de originele rij in de nieuwe situatie. Ik bepaal het verschil met de waarde in de originele situatie en deel het door de waarde in de originele situatie. Dit is dus een procentuele afwijking t.o.v. de originele waarde.

Overigens heb ik net een mini framework af zodat ik kan testen.

[Alain]

Ik heb mijn algoritme eens geprobeerd en stap 5 is niet goed. Stap 5 klopt niet omdat de totale afwijking na het lineairiseren van een rij niet groter hoeft te worden. Ik heb dit nu opgelost door de maximale afwijking van de gelineairiseerde rijen in de originele tabel telkens opnieuw te berekenen en deze aan te merken als maximale afwijking. Dit is best duur en er valt nog te optimaliseren.

Het werkt vooral langzaam voor lineaire tabellen en bij een grote maximale afwijking. In de praktijk komt dat niet voor, maar dat ga ik nog verbeteren.

[Alain]

Ik zit nu nog met 1 klein probleempje. Als ik een zuiver lineaire tabel invoer van bijvoorbeeld 2000 regels. Ik wil 0% afwijking, dus ik verwacht 2 regels; de eerste en laatste regel. Op een geven moment treed er een kleine afwijking op in de berekening door afrondingsfouten. Order van grootte: 1,1 * 10E-14. Het is compleet verklaarbaar dat deze afwijking optreed, maar ik wil dit tegengaan.

Ik denk er zelf aan om 0.0% als userinput te interpreteren als < 0.05% en 0.01% als < 0.015%. Wat is eigenlijk een normale werkwijze bij dit soort afwijkingen?

[Alain]

Mijn algoritme brengt een echte (wing tank) tabel naar 25% van de originele grootte bij 0,1% afwijking.Bij 2000 regels staat er bijna direct een antwoord, dus ik ga niet verder optimaliseren. Bij 5000 regels is het algoritme vrij traag, maar dat komt nooit voor.

[kdekker]

AlainS schreef op zaterdag 17 januari 2009 @ 19:03:
Ik zit nu nog met 1 klein probleempje. .... Op een geven moment treed er een kleine afwijking op in de berekening door afrondingsfouten. Order van grootte: 1,1 * 10E-14. Het is compleet verklaarbaar dat deze afwijking optreed, maar ik wil dit tegengaan.

Ik weet niet precies hoe je zit te rekenen, maar floating points hebben een eindige precisie (ergens tot de 14e decimaal gaat wel goed, maar verder niet). Oplossing: vermenigvuldig de boel met bij 100 of 1000, en ga met integers werken. Dan heb je geen last van de rekenkundige precisie (en representatie intern) van floating points. Wel moet je opletten dat je niet over de bovengrenzen van je datatype heenvalt (bijv (2^16 - 1) / 1000 voor 16 bits unsigned int en een vermenigvuldigingsfactor van 1000). Welke vermenigvuldigingsfactor je wilt hangt af van de verhouding max/min waarde van je metingen.

[Alain]

kdekker schreef op maandag 02 februari 2009 @ 22:05:
[...]


Ik weet niet precies hoe je zit te rekenen, maar floating points hebben een eindige precisie (ergens tot de 14e decimaal gaat wel goed, maar verder niet).

Probeer 0,2 eens als float te schrijven. Dat gaat je met 32 bits waarschijnlijk niet lukken.

Ik reken niet door met resultaten uit berekeningen en daardoor blijft de afwijking controleerbaar.