Witboek DNA - Basic (NL)

Witboek DNA - Basic (NL)

Berichtdoor SDSC » vr 02 dec 2011, 11:55




Verander taal: Nederlands


Witboek DNA versie 2.x



Index

1. INLEIDING................................................................................................................2
1.1 Bedoeling van dit document......................................................................................2
1.2 Over DNA...............................................................................................................2
1.3 Geschiendenis........................................................................................................2

2. BASIS PRINCIPES...................................................................................................3
2.1 Het idee achter DNA................................................................................................3
2.2 Codering / decodering..............................................................................................3
2.3 De algoritmes.........................................................................................................3

3. TEST-RESULTATEN.................................................................................................4
3.1 De eerste test-resultaten..........................................................................................4
3.2 Referentietabel grootte versus input...........................................................................6
3.3 Sleutelcode grootte versus iteraties...........................................................................6

4. SAMENVATTING.......................................................................................................8
4.1 Verder onderzoek.....................................................................................................8
4.2 Aantekening van de auteur........................................................................................8

5. AANHANGSEL..........................................................................................................9
5.1 Stroomdiagram codering...........................................................................................9
5.2 Sleutelcode diagram van bestand in screenshot 1 en 2...............................................10







© 2012 door SDSC document versie 1.0
Pagina 1


Witboek DNA versie 2.x



1. INLEIDING


1.1 Bedoeling van dit document

Dit document is bedoeld om de basis principes van DNA te beschrijven en de focus te
leggen op het codeer gedeelte. Het bevat geen gedetailleerde informatie van de DNA
algoritmes of hoe de algoritmes samenwerken. Deze informatie inclusief de intellectuele
rechten behoren toe aan de auteur en worden niet gepubliceerd.


1.2 Over DNA

DNA is een combinatie van algoritmes die het mogelijk maakt om van ieder bestandstype
zoals exe, bin, mp3, mpeg, wav etc., een sleutelcode te berekenen die kleiner of gelijk is
aan 256 bytes. Met behulp van een referentie tabel kan DNA middels deze sleutelcode weer
het originele bestand reconstrueren. DNA is een geheel andere manier van verliesvrije data-
opslag die geen gebruik maakt van bekende compressie technieken. De naam DNA is geko-
zen vanwege de algoritmes. Zoals DNA in de genetica, gebruikt ook DNA unieke reeksen om
de informatie voor de originele gegevens terug te halen. DNA is niet de vervanger voor de
huidige compressie technieken maar is een aanvulling daarop en beide technieken kunnen
goed met elkaar samenwerken.


1.3 Geschiedenis

Sinds de jaren '90 houdt de gedachte me bezig dat gegevens efficiënter opgeslagen zouden
moeten kunnen worden dan we eigenlijk nu doen. De bedoeling was om te kijken als er een
manier bestaat om tekst- en foto- bestanden op een effectievere manier op te slaan zodat de
opslagcapaciteit optimaal gebruikt wordt.

Gebruik een compressie programma zou je vermoedelijk nu zeggen!

Met die gedachte is niets mis en het zou de makkelijkste weg zijn ware het niet dat mijn
gevoel me afvroeg "Hee, bestaat er dan geen betere en efficiëntere manier ?". Ik moest
me aan dat gevoel toegeven wat het begin was van die zoektocht. Na vele pogingen en
zonder positieve resultaten te behalen, leerde ik veel over compressie en uiteindelijk ont-
stonden de DNA algoritmes. Om mijn ideën en de inzet van de algoritmes aan te tonen en
tevens te bewijzen werd Versie 2 van DNA ontworpen, die daadwerkelijk dat bewijs leverde!
Er is nog een lange weg te gaan maar de basis is er. DNA is een hobby project en ondanks
de hoeveelheid onderzoek die nog steeds gaande is, kent DNA nu al reeds vele mogelijkheden
zoals bijvoorbeeld gegevenscodering!


© 2012 door SDSC document versie 1.0
Pagina 2


Witboek DNA versie 2.x



2. BASIS PRINCIPES


2.1 Het idee achter DNA

Het belangrijkste idee achter DNA is om gemeenschappelijke gebruikte gegevens slechts
één keer op te slaan! Het is een eenvoudig idee maar is makkelijker gezegd dan gedaan.
Een bestand is niets meer of minder dan een reeks getallen ongeacht het type. Om van
gegevensblokken unieke (DNA) reeksen te maken, die hetzelfde zijn voor elk bestand,
moest het mogelijk zijn deze blokken te vervangen voor een kortere verwijzing. Dit bied
tevens de mogelijkheid om iteraties (herhalingen) te gebruiken die de uiteindelijke
grootte tot een minimum kan reduceren (bij DNA is dat <= 256 bytes). Een paar jaar ge-
leden stuitte ik op het verhaal van Jan Sloot. Hat was een nederlandse uitvinder die een
revolutionair dataopslag systeem had ontwikkeld. Na het lezen van het boek "De Broncode"
herkende ik veel waar ik op zoek naar was en om eerlijk te zijn, het duwde me de goede
richting op. In de resultaten zijn ook enkele opmerkelijke gelijkenissen te zien.


2.2 Codering / Decodering

De basis van het codeer proces is zichtbaar gemaakt in het stroomdiagram in bijlage 5.1.
Het proces begint met het openen van een bestand die het in unieke gegevensblokken
verdeeld. DNA berekent voor iedere blok een (DNA) patroon. Hierna kijkt DNA als dit
patroon reeds in de referentie tabel aanwezig is. Zo niet, dan wordt dit patroon aan
het tabel toegevoegd en ontvangt hij een verwijzing. Maar als het patroon reeds in het
tabel bevind dan wordt er niets toegevoegd en gebruikt hij enkel de verwijzing daarvan.
De gegevensblok wordt dan vervangen door die kleinere verwijzing en de totale grootte
wordt gecontroleerd. Is de omvang nog steeds groter dan de gewenste omvang, <= 256
is het minimum en elke grotere waarde kan gebruikt worden, dan gaat het proces zolang
door totdat de gewenste grootte is bereikt. Als het totale proces afgerond is wordt het
resultaat opgeslagen als een sleutelcode (DNA code). Het decoderen gebeurd op dezelfde
manier maar dan andersom.


2.3 De algoritmes

Versie 2.x van DNA gebruikt 5 algoritmes (Jan Sloot?). Deze algoritmes werken samen en
het compleet proces wordt uitgevoerd door DNA wat allemaal wiskundig bewezen is. De
eerste bedoeling van DNA was om de gegevensopslag op lokale apparaten te verbeteren.
Dat is ook de reden waarom gekozen is voor een dynamisch referentie tabel. Sla niet meer
op dan noodzakelijk is! Als de sleutelcodes bedoeld waren om tussen systemen te kunnen
uitwisselen, dan zou het referentie tabel in deze testversie van DNA ongeveer een grootte
bezitten van 9,3652456509479766941447916893795e+145 bytes. Voor tests met deze ver-
sie was dat niet relevant en bovendien is zulk enorm groot tabel onmogelijk te beheren.
Tevens zouden biljoenen patronen in het tabel staan die vermoedelijk nooit gebruikt
zouden worden.



© 2012 door SDSC document versie 1.0
Pagina 3


Witboek DNA versie 2.x



3. TEST-RESULTATEN


3.1 De eerste test-resultaten

De getoonde test is van DNA versie 2.6. Er is begonnen met versie 3 maar tussendoor
ontstonden nieuwe ideeën die makkelijker verwezenlijkt en getest konden worden in
versie 2.4 en hoger.

Laten we beginnen met een leeg referentie tabel en een screenshot van versie 2.6 met de
resultaten van een gecodeerd bestand.



Screenshot 1

In dit geval heeft het gebruikte bestand een omvang van 544606 bytes en de uiteindelijke
sleutelcode is ingesteld op <= 256 bytes. Zoals u kunt zien zijn er 42 iteraties voor nodig
om dit te bereiken. Belangrijk zijn de 'encoder in' en de 'encoder out' waardes! Door het
gebruik van iteraties is de hoeveelheid gegevens die de encoder verwerkt een stuk groter
dan de orginele bestandsomvang! Dit is afhankelijk van het aantal iteraties die noodzake-
lijk zijn om de ingestelde grootte van de sleutelcode te bereiken. De 'encoder in' geeft de
hoeveelheid aan die de encoder verwerkt en de 'encoder out' geeft de hoeveelheid weer
die in totaal aan het referentie tabel zijn toegevoegd (alles in bytes).

Ik hoor u nu denken!

Encoder out = 473839 en de omvang van het bestand = 544606, dat is een reductie van 12.99%,
elk compressie software levert een betere prestatie!


© 2012 door SDSC document versie 1.0
Pagina 4


Witboek DNA versie 2.x


Laten we eerlijk zijn, het zou niet sportief zijn om DNA op deze enkele berekening te
gaan beoordelen, want er is meer.

Compressie programma's zouden op dit enkel bestand beter presteren omdat deze
speciaal ontworpen zijn met de wetenschap hoe ze een enkel bestand optimaal kunnen
comprimeren op basis van het type bestand en passen hun strategie daarop aan. DNA
daarentegen kijkt in zijn geheel niet naar het type bestand en behandelt ze als gelijk,
gewoon als een reeks van getallen! Dat is tevens de reden waarom er iteraties mogelijk
zijn. Probeer eens een gecomprimeerd bestand te comprimeren en u zult zien dat het
niet verder te comprimeren valt omdat alle redundantie in de eerste fase is verwijderd.
De algoritmes bereiken het einde van hun capaciteit wat resulteert in een bestand die
weer steeds groter wordt (negatieve compressie!).

Laten we eens kijken naar enkele test resutaten.

Op de eerste plaats de 'encoder out' versus de hoeveelheid gegevens die door de encoder
verwerkt wordt. Het gebruikte bestand heeft een omvang van 544606 bytes. Om de inge-
stelde sleutelcode te bereiken heeft hij enkele iteraties nodig. Deze iteraties zorgen ervoor
dat de hoeveelheid gegevens wat door de encoder gaat een stuk groter is als het aangeboden
bestand. In dit geval moet de encoder 2271608 bytes verwerken om uiteindelijk een omvang
van 473839 bytes hiervan te maken. In feite moet de werkelijke gegevens reductie percentage
van deze waardes berekend worden. Dit is (2271608 – 473839)/(2271608 / 100) = 79,14% en
niet te vergeten, dat bij een start met een leeg referentie tabel. Dat was al het eerste bewijs
dat de algoritmes functioneren en precies deden wat ervan verwacht werd.

Waarom?

Vergeet eventjes het gebruikt bestand. We kijken nu naar de aantal bytes die door de en-
coder verwerkt zijn, 2271608 bytes in en 473839 bytes uit. Onthoud het basis idee van DNA,
unieke (DNA) patronen maken van gegevensblokken die voor elk bestandstype gelijk zijn.
Een ander belangrijke waarde is de 'Table extent' die 8855 is (zie Screenshot 1). Deze waarde
geeft aan hoeveel (DNA) patronen in het tabel zijn toegevoegd. We zijn gestart met een
leeg referentie tabel omdat het noodzakelijk is om een goede indruk te krijgen wat de algo-
ritmes genereren en doen. Van de totale gegevensstroom van 2271608 bytes berekenen de
algoritmes 8855 verwijzingen met een totale omvang van 473839 bytes. Dit geeft aan dat
de algorimes al gelijke patronen heeft gevonden en dat de totale gegevensstroom van
2271608 bytes uit deze 8855 verwijzingen met een omvang van 473839 bytes teruggehaald
kan worden!

Houd in gedachte dat dit het eerste bestand is wat door de algoritmes verwerkt is met
een tabel zonder verwijzingen. Zodra er meer bestanden door DNA verwerkt worden, zullen
het aantal gelijke patronen oplopen wat natuurlijk resulteert in minder toevoegingen
van patronen in het tabel. Let op dat het totaal aantal bytes die zijn toegevoegd aan
het referentie tabel kleiner is dan de omvang van het gebruikt bestand.


© 2012 door SDSC document versie 1.0
Page 5


Witboek DNA versie 2.x


3.2 Referentietabel grootte versus input

Het volgend diagram laat ons zien dat de grootte van de referentie tabel groeit
naarmate het aantal bestanden die door DNA verwerkt worden oploopt.


Diagram 1

Dit was precies zoals verwacht werd en u kunt zien, des te meer bestanden verwerkt worden
des te minder gegevens toegevoegd worden aan het tabel en des te effectiever DNA wordt.
Dit diagram laat tevens zien dat DNA met een dynamisch tabel geen vervanging is voor de
huidige compressie software. In dit geval laat DNA zien dat het meer bestanden/gegevens
nodig heeft om effectiever te worden (het moet leren ;-)). Voor enkele bestanden is het
gebruik van compressie software een betere optie.


3.3 Sleutelcode grootte versus iteraties

Een ander belangrijk aspect is hoe de grootte van de sleutelcode zich gedraagt bij iedere
iteratie. Zoals eerder verteld maakt DNA geen gebruik van compressie algoritmes zoals
run time length encoding, Huffman trees etc. etc. Maar daarnaast is me iets merkwaar-
digs opgevallen in de eerste iterartie. Ik kom hier later op terug en laten we eerst kijken
naar diagram 2 die ons de grootte van de sleutelcode versus het aantal iteraties laat zien.
Voor dit bestand heb ik een klein bestand gebruikt van 2489 bytes maar grotere bestan-
den lieten hetzelfde gedrag zien. Dit bestand had 18 iteraties nodig voor het verkrijgen
van een sleutelcode van <=256 bytes. In aanhangsel 5.2 vind u de sleutelcode diagram
van het (groter) bestand die gebruikt werd voor screenshot 1 en 2.





© 2012 door SDSC document versie 1.0
Pagina 6


Witboek DNA versie 2.x



Diagram 2

Dit gedrag was een beetje vreemd voor mij omdat mijn verwachting was dat de grootte
van de sleutelcode bij iedere iteratie rond dezelfde hoeveelheid zou verkleinen, maar
vreemd genoeg deed hij dat niet! De reden hiervoor was te vinden in de eerste iteratie.
Zie de volgende screenshot.



Screenshot 2


© 2012 door SDSC document versie 1.0
Pagina 7


Witboek DNA versie 2.x


Ondanks dat de DNA algoritmes geen gebruik maken van compressie technieken schijnen
ze de meeste redundantie al in de eerste iteratie te verwijderen! Ik deed een test en com-
primeerde dezelfde bestand als in screenshot 2 middels win-zip en het gecomprimeerde
bestand werd 209409 bytes groot. Dat was toch kleiner dan het resultaat uit de eerste ite-
ratie. Ondanks dat deden de algoritmes goed hun werk, zonder te weten om welk type be-
stand het ging. Als u naar diagram 2 kijkt is er nog iets opmerkelijks. Tot aan de vijfde
iteratie reduceert de sleutelcode sterk maar daarna wordt het effect op de resterende
iteraties kleiner (dertien iteraties voor 750 bytes). Nu kijken we naar grootte van de
sleutelcode in de vijfde iteratie, ongeveer 1K (Jan Sloot?). Een ander leuke mogelijkheid
van iteraties is dat men zelf kan bepalen hoe groot de uiteindelijk output wordt (sleutel-
code). Ofschoon dat DNA een sleutelcode kan berekenen van <=256 bytes, wil dit nog niet
zeggen dat het altijd de beste keus is. Als bijvoorbeeld DNA wordt ingezet om het gebruik
van een harde schijf te optimaliseren dan is de beste uiteindelijk grootte <= sector grootte.
Dit reduceert het aantal iteraties en de hardeschijf capaciteit zou dan optimaal gebruikt
worden.


4. SAMENVATTING

4.1 Verder onderzoek

De test resultaten van versie 2 toonden aan dat de algoritmes functioneerden zoals
verwacht met zeer positieve resultaten waardoor het onderzoek verder kan doorgaan.
Het toonde nieuwe ruimte voor optimalisatie en ideeën evenals aandachtpunten waar-
onder bijvoorbeeld snelheid. Daarnaast ligt er een andere grote uitdaging zoals het
referentie tabel, kan deze kleiner of kunnen we het ook zonder ? Er is nog veel onder-
zoek te doen en het is een lange weg van test-versie tot aan een uiteindelijke toepas-
sing maar de resultaten gaven een stevige basis.


4.2 Aantekening van de auteur

Ik beweer niet dat ik de oplossing heb gevonden van de vermiste broncode van Jan Sloot
of een manier van eindeloze compressie bereikt te hebben. DNA is een hobby project en
het hoofddoel is een zoektocht naar alternatieve manieren van dataopslag. De video-
demo, forum en het witboek zijn bedoeld om de status van het project te tonen evenals
de verwezenlijkingen/resultaten tot nu toe. Ik zou heel graag meer over DNA willen ver-
tellen en laten zien maar helaas maken bepaalde omstandigheden dit onmogelijk. Voor
meer informatie over de status of voor eventuele vragen kunt u terecht op:
http://jansloot.telcomsoft.nl.


© 2012 door SDSC document versie 1.0
Pagina 8


Witboek DNA versie 2.x


5. AANHANGSEL

5.1 Stroomdiagram codering




© 2012 door SDSC document versie 1.0
Pagina 9


Witboek DNA versie 2.x


5.2 Sleutelcode diagram van bestand in screenshot 1 en 2
















© 2012 door SDSC document versie 1.0
Pagina 10



Met vriendelijke groet,

SDSC.




Bookmark and Share
The best way to slow down your compateters is to give them your source code!
Avatar gebruiker
SDSC
 
Berichten: 24
Geregistreerd: vr 01 okt 2010, 21:53

Keer terug naar Informatie over DNA (Relinks)