Ideenfindung Datenkompression

Jump to last post
Eine 1 ist je nach Zeichensatz ja auch schon wieder codiert und braucht zumindest bei ascii 2 zahlen. Die häufigsten *Wörter*/ Schnipsel würde ich daher durch binäre Zeichen ersetzen (hattest du aber glaube ich eh mal überlegt?) Also muss man rechnen evtl 3 oder 4 Stellen 1111 als the z.b also einen eigenen Zeichensatz definierten der nur benötigte Zeichen beinhaltet
 
Leicht OT: was passiert mit dem Geld, wenn "wir" signifikant unter 15 MB kommen? ;)
 
  • Thread Starter Thread Starter
  • #23
You do not have permission to view link please Anmelden or Registrieren


Wenn du Binär in ein Zeichen umwandelst, kommt zwingend auch ein 1 Byte langes Zeichen daraus hervor, bzw. nach Encoding, wie du selbst sagst 2 oder 4 Byte*
Wenn etwas jetzt nur 1 Bit benötigen würde, kann es, wenn ich alles richtig verstanden habe, mit nichts kleinerem als einem 1 Byte großem Zeichen abgespeichert werden.

Die Beiträge von Jester gehen ja mit dem 7 bit Packing auch darauf ein:
Klick 1 und Klick 2

und dieser Post von mir hier, quote mich mal selbst ;)

theSplit schrieb:
[...] für mich ist halt nur logisch das die kleinste Einheit ein Byte - zum Beispiel aus dem 8 bit ASCII Zeichenvorrat ist, worunter neben dem Alphabet auch die Zahlen 0-9 fallen und Steuerzeichen, also alles was man als "char" in C abbilden kann. Soweit richtig?

Ich könnte jetzt Binär intern ausgeben lassen und müßte diese 7 bits dann wie du sagst mit einem Folgebit füllen und hätte dann ein Byte, das Zeichen X das ich nun speichern als Byte speichern kann.
Also wenn die 7 bit folgende Abbildung sind 0101011 sind und das nächste Bit des nächsten Datenstroms wäre 1, ergibt sich 01010111 (ich hab das jetzt mal in einem
You do not have permission to view link please Anmelden or Registrieren
konvertiert) - es wäre das Zeichen "W".
Zum Vergrößern anklicken....

Was Jester ja freundlicherweise bestätigt hat.

Also "Bits" schreiben geht so nicht direkt, man kann aber scheinbar mit Bits soweit arbeiten, das sich diese nicht als "einzelne Bit" speichern lassen, man jedoch mit 7 Bit, laut Jester, alle ASCII Zeichen abbilden kann. Und ein Bit könnte aus dem Folgenden Byte herausgezogen und "angeheftet" werden usw.


-------------

Ein ganz anderes Problem auf das Seedy mich gebracht hat, das Encoding - in der 100 MB Datei sind definitiv arabische, chinesische, kyrillische Schriftzeichen enthalten...
Aber das ist mal eine ganz andere Baustelle und da bin ich auch überfragt weil ich mich zu wenig in der Thematik auskenne. Also auch definitiv etwas was man irgendwie noch beachten können sollte.
 
Zuletzt bearbeitet:
You do not have permission to view link please Anmelden or Registrieren

Garnicht so ein Problem:
Alle Zeichen in dem Dokument sind 8Bit codiert.
Wenn du statt den Zeichen, dich um die Bits kümmerst umgehst du das Problem komplett
 
auch keine blöde Idee Seedy,
8,16,24,32 usw. bit Blöcke bilden und zählen >> schauen bei welcher "wortlänge" die meisten dopplungen enstehen
 
  • Thread Starter Thread Starter
  • #26
Also ich bin gerade etwas verwirrt. So mit den ganzen Bits und Bytes und so und dem Encoding und und ;)

Seedy, warum komplett umgehen? Das Kürzen kann doch ein Step von X Steps werden. Ist ja nicht damit das Ende erreicht. :unknown:

Ich glaube wenn ich, jemand von uns, diese ganzen Ideen und Vorschläge umsetzen soll brauchen wir 5 Wochen Urlaub, weil
hier kommen die Ideen so schnell, da kommt ja kein Mensch mit implementieren hinterher ;)

Ich bin so weit:
Lasse gerade immer noch die Datei auslesen (Zeichenweise) um die Worttabelle aufstellen zu lassen, um danach damit anzufangen die Vorkommnisse ermitteln zu lassen (Computer arbeite schneller!), selbst Step 1 dauert (nicht nur gefühlte) 3 Stunden stelle ich gerade fest, hab echt gedacht das wäre schneller, nun ja... :o
 
Zuletzt bearbeitet:
Das Dokument hat
100.000.000Byte auf 99.621.832 Zeichen auf 1128024 Zeilen

Leerzeichen und Zeilenumbrüche eingerechnet. Tabs sind 2 Leerzeichen.
Jedes Zeichen nimmt 8 Bit weg.

Ich schau mir mal ein bischen die Textstruktur an, eventuell finde ich irgendwo nennenswertes Einsparpotential, dass nicht schwer zu erreichen ist.
Ich denke da eher an daran 1000 mal 2 Bit zu sparen, statt 2 Mal 20 bit :D
 
Zuletzt bearbeitet:
  • Thread Starter Thread Starter
  • #28
Seedy, ich nehm dir etwas Arbeit ab und vielleicht auch anderen, habe jetzt knapp etwas mehr als 77 tausend Wörter identifiziert und ausgearbeitet..

Hier die Liste: Anhang anzeigen tmpfile big.txt

PS: Warum ich mir die Arbeit mache, ich denke es ist nicht verkehrt das Datenvolumen so zu reduzieren, bevor man etwas mit Bits machen würde. Aber ist jetzt nur mein Gedanke dazu ;)
 
Zuletzt bearbeitet:
Seedy schrieb:
Ich schau mir mal ein bischen die Textstruktur an, eventuell finde ich irgendwo nennenswertes Einsparpotential, dass nicht schwer zu erreichen ist.
Ich denke da eher an daran 1000 mal 2 Bit zu sparen, statt 2 Mal 20 bit :D
Zum Vergrößern anklicken....

Wikisyntax wäre da einer von vielen Ansatzen.
''''[[
Zum Vergrößern anklicken....
und '
''']]
Zum Vergrößern anklicken....
und Tabellenformatierung (|..., ||, || leerzeichen...) und diverse andere Dinge aus der Baustelle* und so Dinge kann man prima einkürzen und/oder weglöschen (|leer=| usw.). Visuelle Code-analyse. Es gibt da reichlich Dinge, die man kaputtmachen kann.
Wobei ich mir mit meinen mangelnden Englischkenntnissen nicht so einig bin, was die Aufgabe genau hergibt. "Komprimiere das Beispiel-File" oder entwickle einen allgemeinen Algo für _ähnliche Files_
Des Weiteren: geht es um Komprimierung der Information oder der Datei? Meiner bescheidenen Meinung nach kann (bzw MUSS) man alle "align=irgendwas" auch wegwerfen. genauso wie style=, <div*, id= usw. Weiter gehts mit<tag attribut="*">Hallo welt</tag> und dergleichen. Braucht kein Mensch. Wer solchen Dreck schreibt, muss sich nicht wundern, wenn das auf irgendwelchen Endgeräten "kaputt" ist.

*   zuzüglich Kombinationen sind in aller Regel überflüssig.
 
You do not have permission to view link please Anmelden or Registrieren

Es muss nur auf das Beispiel file funktionieren.
Es muss Lossless sein, (auch wenn du vollkommen recht mit dem Müll hast :D)
 
You do not have permission to view link please Anmelden or Registrieren

Hi Split,

wenn Dir das nicht zu trocken und mathematisch ist,
You do not have permission to view link please Anmelden or Registrieren
.

Inkl. Calgary-Corpus und Herangehensweise mit Huffman-Codierung/-kompression.

Damit ist das Thema aber sicher noch nicht durch ^^

Ich bin recht sicher, dass mit lediglich dieser Herangehensweise kein Benchmark erreicht werden kann (intelligentes und kontextbezogenes Multi-Pass Packing als Notwendigkeit für extreme Effizienz), für den Wettbewerb dürfte "intelligent" das Keyword sein, wobei sich das auf die Art, Struktur und den Inhalt des Wikipedia-Dumps bezieht.

Gruß, J.

Ps: wenn wir von einem Overhead an Text-Rohdaten sprechen - mal so ins Blaue geschossen - was wäre denn mit einem zusätzlich grammatikalischen Ansatz? Also Speicherung als Subjekt, Objekt und Prädikat, in einer Baumstruktur mit variabler Bitlänge (!), Tokenisierung und/oder Wörterbuch-/Wiederholungskompression?

Wie gesagt, nur ins Blaue geschossen.
 
Ich habe im Editor gesehen, daß da einzelne Worte fast 30.000 x vorkommen.

Jetzt habe ich mal spaßeshalber alle Wörter, die mehr als 4 Zeichen haben und mehr als 1000 mal vorkommen durch |00x ersetzen lassen und vorne das Mapping angehängt. Sind über 600 Wörter und über 6MB, die da wegfallen
 
Seedy schrieb:
es muss Lossless sein, (auch wenn du vollkommen recht mit dem Müll hast :D)
Zum Vergrößern anklicken....
Also das ge- und entpackte File muss identisch sein zum Original. Man berichtige mich, wenn ich das falsch verstehe.

Gehört nicht direkt zum Thema, aber bzgl. Müll mal noch präzisiert; würde es der Wikisoftware gut stehen, redundantes (wie oben beschrieben) Markup jeweils auf eine (möglichst einfache) Variante einzudampfen. Dann wäre mit einer 08/15-Standardkompression auch schon einiges erreicht.

Zum Thema:
KaPiTN schrieb:
Jetzt habe ich mal spaßeshalber alle Wörter, die mehr als 4 Zeichen haben und mehr als 1000 mal vorkommen durch |00x ersetzen lassen und vorne das Mapping angehängt. Sind über 600 Wörter und über 6MB, die da wegfallen
Zum Vergrößern anklicken....
Kannst Du da noch 10-50 Favoriten bringen? Hast Du da nur Worte, oder auch Zeichenkombis? (wie bspw. [src=php]''']][/src])
 
You do not have permission to view link please Anmelden or Registrieren
Ich habe nach whitespace getrennt. Die Wörter waren dann folgende:

671=<TD><FONT
671=<TD><FONT
670=Charles
669=speed
668=feature
667=season
666=est.)
665=England
664=space
663=football
662=Irish
661=players
660=Japanese
659=radio
658=aircraft
657=External
656=player
655=computer
654=video
653=Church
652=design
651=Australian
650=program
649=rules
648=African
647=species
646=performed
645=Jewish
644=status
643=[[Roman
642=Republic
641=reached
640=water
639=[[European
638=approximately
637=sound
636=model
635=additional
634=that,
633=Canadian
632=Soviet
631=films
630=*''[[The
629=<td
628=produce
627=primarily
626=designed
625=basic
624=contain
623=contains
622=special
621=energy
620=Catholic
619=title
618=[[University
617=function
616=operating
615=except
614=scientific
613=knowledge
612=&ndash;
611=George
610=&nbsp;
609=[[Charles
608=added
607=writer
606=actor
605=future
604=previous
603=(such
602=record
601=[[South
600=release
599=battle
598=quickly
597=likely
596=appointed
595=system.
594=shows
593=again
592=attack
591=[[Battle
590=position
589=southern
588=process
587=actual
586=Central
585=proposed
584=original
583=[[James
582=science
581=allowed
580=eventually
579=World
578=House
577=style
576=time.
575=account
574=member
573=legal
572=Court
571=larger
570=church
569=south
568=beginning
567=forces
566=states
565=March
564=President
563=frequently
562=relationship
561=married
560=story
559=women
558=court
557=object
556=games
555=remains
554=provided
553=returned
552=entire
551=provides
550=killed
549=becomes
548=forced
547=named
546=death
545=young
544=father
543=names
542=latter
541=lines
540=ancient
539=required
538=television
537=*[[List
536=North
535=College]]
534=University]]
533=country
532=mostly
531=region
530=national
529=Party
528=During
527=placed
526=Union
525=State
524=*/</comment>
523=/>
522=military
521=album
520=derived
519=international
518=intended
517=|518s
516=standard
515=below
514=element
513=League
512=Latin
511=languages
510=Roman
509=consists
508=served
507=align="center"
506=started
505=movie
504=female
503=South
502=double
501=January
500=released
499=Despite
498=British
497=president
496=replaced
495=growth
494=continued
493=century,
492=history
491=located
490=western
489=island
488=north
487=image
486=black
485=direct
484=commercial
483=heavy
482=whole
481=result
480=basis
479=building
478=built
477=cities
476=northern
475=Great
474=color
473=white
472=greater
471=appears
470=effect
469=highest
468=across
467=average
466=surface
465=field
464={{cite
463=characters
462=evidence
461=discovered
460=longer
459=period
458=character
457=services
456=independent
455=addition
454=simple
453=Minister
452=[[British
451=local
450=available
449=numerous
448=letter
447=community
446=light
445=actually
444=effects
443=research
442=University
441=claimed
440=study
439=largely
438=matter
437=family
436=cases
435=public
434=types
433=produced
432=former
431=probably
430=service
429=currently
428=enough
427=nearly
426=methods
425=parts
424=complex
423=total
422=definition
421=increase
420=lower
419=source
418=shown
417=allows
416=material
415=better
414=world
413=Because
412=become
411=extremely
410=change
409=older
408=little
407=relatively
406=cannot
405=sense
404=strong
403=earlier
402=features
401=events
400=given
399=remain
398=points
397=passed
396=level
395=problems
394=increased
393=them.
392=changes
391=having
390=seems
389=above
388=ability
387=playing
386=company
385=appear
384=months
383=things
382=either
381=order
380=quite
379=great
378=generally
377=instead
376=majority
375=years.
374=originally
373=almost
372=meaning
371=introduced
370=Greek
369=current
368=children
367=three
366=language
365=several
364=series
363=second
362=already
361=gives
360=States]]
359=among
358=seven
357=while
356=results
355=subject
354=short
353=includes
352=links==
351===External
350===References==
349=&
348=books
347=also==
346===See
345=[[United
344=following
343=civil
342=third
341=making
340=reference
339=influence
338=personal
337=behind
336=recent
335=perhaps
334=[[January
333=population
332=specific
331=least
330=others
329=possible
328=There
327=[[George
326=because
325=foreign
324=makes
323=information
322=-->
321=<!--
320=These
319=software
318=music
317=systems
316=(which
315=different
314=[[World
313=carried
312=attempt
311=separate
310=living
309=[[National
308=created
307=existence
306=cultural
305=create
304=caused
303=business
302=according
301=applied
300=referred
299=article
298=small
297=under
296=degree
295=range
294=however,
293=classical
292=refer
291=issue
290=single
289=traditional
288=itself
287=numbers
286=examples
285=throughout
284=&mdash;
283=[[John
282=world.
281=usually
280=return
279=Another
278=takes
277=particular
276=action
275=taking
274=countries
273=whether
272=version
271=these
270=German
269="The
268=David
267=concept
266=terms
265=various
264=highly
263=always
262=school
261=consider
260=therefore
259=years,
258=problem
257=along
256=typically
255=example
254=structure
253=certain
252=''[[The
251=author
250=Christian
249=official
248=established
247=higher
246=historical
245=culture
244=physical
243=directly
242=worked
241=Germany
240=Since
239=appeared
238=areas
237=large
236=control
235=changed
234=popular
233=divided
232=close
231=practice
230=government
229=another
228=Italian
227=common
226=difficult
225=States
224=[[North
223=Their
222=forms
221=group
220=towards
219=themselves
218=began
217=France
216=parties
215=success
214=resulting
213=policy
212=those
211=American
210=central
209=development
208=Russian
207=general
206=outside
205=claims
204=today
203=largest
202=smaller
201=National
200=played
199=million
198=successful
197=allow
196=support
195=members
194=founded
193=remained
192=significant
191=writing
190=formed
189=After
188=though
187=primary
186=state
185=associated
184=notable
183=whose
182=individual
181=time,
180=force
179=method
178=people
177=further
176=example,
175=Spanish
174=include
173=nature
172=important
171=person
170=production
169=moved
168=[[List
167=often
166=power
165=party
164=around
163=between
162=after
161=Council
160=General
159=elected
158=leading
157=start
156=links
155=European
154=[[International
153=followed
152=First
151=included
150=Other
149=value
148=received
147=without
146=system
145=Press,
144=believed
143=right
142=market
141=theory
140=variety
139=English
138=widely
137=became
136=noted
135=wrote
134=years
133=[[New
132=[[Robert
131=thought
130=himself
129=never
128=through
127=comes
126=simply
125=interest
124="the
123=natural
122=accepted
121=''The
120=works
119=number
118=developed
117=active
116=class
115=French
114=within
113=provide
112=together
111=would
110=working
109=amount
108=using
107=trade
106=could
105=groups
104=involved
103=capital
102=limited
101=called
100=supported
099=cause
098=their
097=rights
096=complete
095=famous
094=claim
093=adopted
092=until
091=commonly
090=elements
089=mainly
088=known
087=point
086=major
085=later
084=Although
083=published
082=[[William
081=Indian
080=leader
079=being
078=private
077=which
076=United
075=described
074=where
073=other
072=something
071=Civil
070=during
069=movement
068=present
067=times
066=every
065=since
064=Western
063=modern
062=religious
061=considered
060=sometimes
059=Europe
058=century
057=written
056=According
055=similar
054=found
053=Chinese
052=[[History
051=[[The
050=access
049=equal
048=human
047=recorded
046=before
045=brought
044=especially
043=might
042=about
041=However,
040=believe
039=defined
038=While
037=based
036=relations
035=social
034=economic
033=political
032=regarded
031=place
030=rather
029=particularly
028=related
027=refers
026=there
025=although
024=should
023=taken
022=final
021=International
020=History
019=means
018=describe
017=still
016=including
015=early
014=against
013=first
012=<comment>/*
011=programming
010=[[American
009=<minor
008=</page>
007=</revision>
006=xml:space="preserve">#REDIRECT
005=<text
004=</contributor>
003=<contributor>
002=<revision>
001=<page>
 
Kurzer Denkanstoss:
Kompression bedeutet Redundanzen zu entfernen.
Die Nachricht also auf ihren Informationsgehalt zu reduzieren.

Nachdem ich die Seite von der Ausschreibung nochmal durchforstet habe, bin ich an zwei Quotes hängen geblieben:
Enwik8 is about 75% clean text and 25% "artificial" data of various forms (tables, hypertext links, XML, etc).
Zum Vergrößern anklicken....

Das heißt, eventuell zwei verschiedene Ansätze. Also die Markups gesondert komprimieren.

One can prove that the better you can compress, the better you can predict; and being able to predict [the environment] well is key for being able to act well. Consider the sequence of 1000 digits "14159...[990 more digits]...01989". If it looks random to you, you can neither compress it nor can you predict the 1001st digit. If you realize that they are the first 1000 digits of pi, you can compress the sequence and predict the next digit.
Zum Vergrößern anklicken....

Einmal durch das Affenhirn gedreht:
Die menschlichen Sprachen sind von sich aus redundant bis zum geht nicht mehr.
Man könnte also eine Semantikanalyse schreiben, die fehlende Worte ergänzt, wenn es anders kein Sinn macht.

Die Redundanz aus der Sprache entfernen, bevor man die Redundanz aus der Datei entfernt.
 
You do not have permission to view link please Anmelden or Registrieren
Semantikanalyse? wirklich? Wörter und Zahlen und kryptische Zeichen filtern usw. ist gut und schön, aber jetzt noch Semantik einer Sprache implementieren und entfernen/ersetzten... Naja mir geht das zu weit.

Ich komme derzeit mit einem "schlechten" Wörterbuch auf <78 % der Originalgröße. Da sind noch einige Prozente Verbesserungspotential drin. Einziges Manko derzeit: Die Laufzeit meines Compressors steigt überproportional stark zur Datei-Größe. 1MB ca. 60 Sekunden. 8 MB ca. 12min 100MB über 12h (noch nicht durchgelaufen). Dafür benutze ich allerdings nur Dateigröße*2 + 10MB an RAM. Das würde vermutlich auch noch ein wenig schneller gehen, wenn ich nicht Python nutzen würde ...
 
You do not have permission to view link please Anmelden or Registrieren

Das klingt schwieriger als es in Wirklichkeit ist.

Im Bezug auf Sprache:
Vieles in der Sprache ist redundant und mit einfachen Prozessen zu minimieren:

Eines der einfachsten Beispiele ist "a" und "an":
Wenn "a" alleine steht UND das nachfolgende Wort mit A,E,I,O,U beginnt.
Ersetze "a" durch "an" bzw. hänge "n" an "a".
damit hast du grob überschlagen schon 0,04MB gespart.
Das sind in Python ~ 10 Zeilen?

Edit: Wow, 10 Zeilen, gut geschätzt :D
Seit gnädig, ist ne weile her, seit dem ich mal was programmiert hab. :confused:

[src=python]
text=input()
l = list(text)
i=0
while i<len(l):
if (l == "a") and (l[i-1] == " ") and (l[i+1] == " ") and (l[i+2] == "a" or "e" or "i" or "o" or "u"):
l.insert(i+1,"n")
else: pass
i=i+1
m = "".join(l)
print m
[/src]

macht aus:
adds a item to list
adds an item to list

So einfach geht Syntax Redundanz entfernen :p
 
Zuletzt bearbeitet:
You do not have permission to view link please Anmelden or Registrieren
Da hast du aber teils das Problem, dass es sprachliche Ausnahmen gibt, die du nicht auf normalem Wege berechnen kannst - so gilt die Vokalregel nicht immer, weil Worte, die sich mit "a" einfacher aussprechen lassen, trotz Vokal kein "an" bekommen (z. B. "a user"). Mit der Kompression hättest du also schon eine unumkehrbare Veränderung.

Generell machen die ganzen Ausnahmen etc. Semantikanalysen sehr schwer.
 
  • Thread Starter Thread Starter
  • #39
Hi, also ich hab eure Diskussion soweit verfolgt und schön dass sich alle so Ihre Köpfe zermartern und auch Code so wie Ergebnisse von Analysen und Co posten :T

Weil @dexter das mit dem XML anspricht, schaut mal auf exomos Beitrag hier, er schlug vor das man Markup, Markdown, gesondert behandeln lassen könnte.

Ich hab mich ja auch schon mit XML beschäftigt und wenn man sagt das ein Wort durch einen Token wiederholt und ein Tag geschlossen werden (Status 0-9) muß sofort oder nach X Elementen einer Aufzählung, braucht man den Closing Tag auch nicht mehr ins System aufzunehmen. Speziell für den Dekompressor der dann sagt, wenn alle Wörter verarbeitet sind, schließe mit dem ersten Wort den XML Tag in der Form: "</"+Anfangswort+">".

Die Trennung nach Whitespace mache ich auch gerade. Aber idealerweise kann der Kompressor Markup Parsen (spezielle Optimierungen sind Okay laut den Regeln, der Kompressor kann speziell für diesen Fall programmiert worden sein!) oder auch Markdown.

-------------

PS: Bei der 100 MB Datei komme ich auf:
1.440.450 Wörter, kommt das hin oder hat jemand andere Werte? Zeichenweise nur mit Space als Wordbreak.
 
Zuletzt bearbeitet:
theSplit schrieb:
Bei der 100 MB Datei komme ich auf:
1.440.450 Wörter, kommt das hin oder hat jemand andere Werte? Zeichenweise nur mit Space als Wordbreak.
Zum Vergrößern anklicken....
Ich komme auf ein paar Wörter mehr, allerdings suche ich auch beispielsweise zwei Wörter nebeneinander, die mehrfach vorkommen. (of the) oder so, die dann ebenfalls ersetzt werden.

EDIT:
Ich suche ja am Anfang erstmal Zeichen, die in der Datei nicht in der Form [Zeichen + HEX-ZAHL) vorkommen.
Ich habe mir gedacht, dass ich mir 3 Zeichen für Leerzeichen und z.B. Capital-Flags nutze. Als Zusatz habe ich mir jetzt noch gedacht, dass man sich ein Wörterbuch aufbaut und dieses dann in mehrere kleine zerlegt, sodass die Zahlen kleiner sind, die man zum Ersetzen nutzen kann. So spart man sich bei zB. 3 kleinen Wörterbüchern bei der großen Datei noch mal zusätzlich >2MB
Zudem kann man nach dem ersten Wörterbuch anwenden, erneut ein Wörterbuch erstellen. Aus zB. 819kB werden dann 814kb, zumindest wenn man lediglich Wörter setzt und noch keine Zeichenstrukturen oder Tags oder so.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben