Ideenfindung Datenkompression

[theSplit]

Ich bin mit eine zeichenbasiertem Aufbau bei 25,3 kb... da ist dann aber schon etwas Code enthalten um die Daten in Datenstrukturen einzulesen.
Aber das meiste wird nur in die Konsole ausgegeben, damit ich erst sicherstellen kann das die Analyse der Daten korrekt funktioniert.

Momentan vergleiche ich "möglicherweise problematische Stellen" mit dem Konsolen-Output aus der Probedatei. Schon das ist eine Heidenarbeit und Kostet viel Zeit.

Eine ungefähre Einschätzung wie viel eingespart werden kann, kann man hier finden:
http://mattmahoney.net/dc/textdata.html

Dort findet man zum Beispiel folgende Analyse mit Replacement/Stripping und ähnlichem eines anderen Tools:
Links die Größe der Datei, rechts der Schritt der durchgeführt wird...

[src=text]enwik8 Step
----------- ------------
100,000,000 Original size
96,829,911 Discard all outside <text...> ... </text>
96,604,864 Discard #REDIRECT text
96,210,439 Discard XML tags (<text...> and </text>)
95,287,203 URL-decode < > and & to < > and &
95,087,290 Remove <ref> ... </ref> (citations)
93,645,338 Remove other XHTML tags
91,399,021 Replace [http:... anchor text] with [anchor text]
90,868,662 Replace [[Image:...|thumb|left/right|NNNpx|caption]] with caption
90,770,617 Replace [[category:text|title]] with [[text]]
88,385,654 Remove [[language:link]] (links to same page in other languages)
85,443,983 Replace [[Wiki link|anchor text]] with [[anchor text]]
83,420,173 Remove {{...}} (icons and special symbols)
80,943,967 Remove { ... } (tables)
77,732,609 Remove [ and ]
75,053,443 Replace &...; with space (URL-encoded chars)
70,007,945 Convert to lower case, replace all sequences not in a-z,0-9 with a single space
74,090,640 Spell digits, leaving a-z and unrepeated spaces[/src]

The conversion was done by the Perl program given in Appendix A. [....]

Indirekt gehe ich diese Schritte ja schon ein wenig ab, nur das der Inhalt nicht auf wichtige Information heruntergekürzt wird, aber etwas Boilerplate entfernt wird. Auf die 70 MB werde ich damit aber nicht kommen und ich vermute das der Gewinn wirklich um einiges geringer ausfällt. Man könnte sich auch Fragen ob es die Arbeit und investierte Zeit überhaupt wert sein wird...

Der Parser hilft aber zumindest dabei, die Inhalte in logische und bedeutungsvolle Einheiten zu überführen. Daraus erhoffe ich mir eigentlich die Chance Worte anders als WikiTags behandelt zu können oder HTML-Entities direkt umzuformatieren (eine Tabelle dafür habe ich nicht, aber die stehen zum Beispiel hier: https://en.wikipedia.org/wiki/List_of_XML_and_HTML_character_entity_references), letzteres sind in der oberen Liste ganze 2 MB - aber ich glaube das wäre dann die "größte" Optimierung der Rohdaten die man on-the-fly vornehmen kann.

Zu mal ein Wikitag ja nun doch andere Tags wie zum Beispiel Links oder Anchors beinhalten kann und diese bestehen soweit ich das einschätzen kann leider nicht alle nur aus einem Wort, sondern gern auch 2-3 Wörtern.

Ich habe aber auch schon feststellen müssen dass das Wiki-Markup auch zum Teil Fehler enthält, das verändert das Resultat ein wenig beim einlesen... zwar nicht optimal, aber ich vermute (ich konnte dies leider nicht mehr auf dem entsprechen Wikipedia Artikel feststellen) das es auch die Wikipedia Engine verunsichert hatte - schade das sich nicht mehr nachvollziehen lässt wie das Ergebnis online ausgesehen hat. Hätte ich mal gern verglichen!

Und dann irgendwann, wenn das einlesen funktioniert, versuche ich mal die hier genannten Algorithmen und Techniken anzuwenden und ich hoffe durch das etwaige minimieren von Corner Cases in Texten lässt sich dann etwas gescheites damit anstellen...

 

[Roin]

Ich denke, ich werde demnächst nochmal das schlichte Wörterbuch noch einmal neu umsetzten und gucken, was ich da für eine Kompressionsrate bei rausbekomme. Wäre ja mal interessant, wie gut die wirklich sein kann, wenn man das vernünftig ersetzt.
Ich denke, 60% sind damit schon zu erreichen (immerhin 400MB weniger...). Wenn man als erstes dein Code darüberjagt und anschließend ein Wörterbuch drauf ansetzt, könnte man vermutlich nochmal einige Prozent rauskitzeln.

Ich frage mich sowieso, wie der Typ auf so wenige Bytes am Ende kam... Ich könnte mir Vorstellen, dass er in seinem "Artikel"-Objekt gespeichert hat, wie lang der Text ist und wie die Überschrift heißt und dann entsprechendes Markup automatisch hinzugefügt hat, welches einem festen Muster folgt. Ist vielleicht noch etwas effizienter, als das komplett zu trennen.

Ich bleibe gespannt.

 

[theSplit]

Das du gespannt bist finde ich gut und auch das du Bock darauf hast noch bzw. wieder daran zu arbeiten.

Was du mit deiner Kompression erreicht hast war ja auch schon nicht schlecht. Und es würde mich auch motivieren mal jemand anderen hier schreiben zu sehen.

Schließlich balldowere ich damit schon lange, ohne das ein Fortschritt in harten Zahlen zu sehen ist. Ich weiß nämlich auch nicht wie gut die Idee/der Ansatz ist.

----

Ich werde es vermutlich so machen, bevor ich anfange etwas zu komprimieren, werde ich die Ausgabe in eine Datei umleiten um einfach sicherzustellen das ich alles so gut wie möglich erfasse. Defektes Markup (nicht XML aber Wiki-Markup) habe ich wie gesagt auch schon entdeckt und das wird ein Problem verursachen.

Aber so fern es nur die Formatierung ist und nicht der Inhalt, denke ich das man das noch verschmerzen kann, auch wenn dann natürlich nicht sichergestellt ist dass das was reinkommt auch wieder genau so herauskommt; was schade ist. Nun ja.....

 

[theSplit]

Bei mir gibt es etwas neues, wenn auch keine richtigen Fakten was eine Kompression betrifft....

Jetzt habe ich die Grundlagen: Das Einlesen von XML Knoten mit Attributen funktioniert, wie auch das Auslesen der Daten innerhalb eines Knotens.

Soweit so gut.

Das Problem das sich mir gerade stellt:
Die Größe des Speichers für die eingelesen Daten ist immens. So benötige ich für die große Testdatei 100 MB zwischen 620-720 MB.
Bei einem aktuellen Dump von Wikipedia mit ~635 MB sind es sage und schreibe von ~4,4-4,7 GB Speicher die beansprucht werden.

Ich habe unter anderem mit Valgrind Massif gemessen wie auch mit "top" in Linux, das ja von ein Prozessen den reservierten bzw. genutzten Speicher anzeigt.

Was ich in C versucht habe zu mangen:
Mit der Compiler-Direktive >#pragma pack(2)< habe ich auch schon versucht zu optimieren, die Performance ist für mich die selbe (kleine und grpße Datei), jedoch ist der Speicherverbrauch auch ein paar MB heruntergegangen.
Mit Struktur Packing habe ich auch versuch das Padding so gering wie möglich zu halten.

Was ich generell nicht verstehe:
Wie kann man sinnvoll eine Kompression durchführen wenn die Speicherbeschränkungen (Wettbewerb) bzw. die Speichernutzung generell so hoch ist, selbst für "kleine" Dateien eine aktuellen EN-Wikipedia Dump ist schon gepackt 14 GB groß und wahrscheinlich noch um ein vielfaches größer entpackt..., damit gehe ich mal vom "schlimmsten Fall" aus.

Ist der Ansatz die Daten strukturiert einzulesen überhaupt sinnvoll? (Details mit Zahlen unten)
Sllte man "on-the-fly" komprimieren?
Was wäre sinnvoll auf auszulagern um den Memory Footprint gering zu halten und wie praktikabel wäre das für die Performance über kurz? Oder ist der Ansatz auch nicht ganz korrekt?

-----

Zur Challenge/Thema:

Ich muss jetzt so langsam aber sicher zugeben, das Thema ist eine harte Nuss
Selbst wenn man den Testrechner für die Competition nicht mit in Betracht zieht....

Hab ich mir alles leichter vorgestellt und irgendwie gedacht dass man doch relativ schnell zu brauchbaren Ergebissen kommt; junge Naivität.

Aber unterm Strich hab ich auch schon einiges gelernt dabei und noch keine grauen Haare bekommen

Wer Interesse hat kann meinen Source Code im Anhang finden, zum ausprobieren, testen, bemängeln, herumfurwerkeln oder auch nur weil ich eine coole Socke bin...

-----

FÜR STATISTIK-NERDS:

Über kurz und lang, folgend auch eine Auswertung, von mir, wie die Datei (enwik8, 100 MB glatt) bestückt sein sollte (relativ genau).

[src=text][ INFO ] Starting parsing process on file "data/enwik8".
[STATUS] RUN TIME FOR PARSING PROCESS: 0h 0m 9s
[REPORT] PARSED LINES : 1128024 | FAILED ELEMENTS: 0
[REPORT] FILE STATISTICS
KEYS : 12372 [~ 0.106 MB]
VALUES : 12372 [~ 0.118 MB]
WORDS : 11835198 [~ 57.235 MB]
ENTITIES : 469686 [~ 2.207 MB]
WIKITAGS : 972128 [~ 16.664 MB]
WHITESPACE : 12885758 [~ 12.289 MB]
FORMATTING : [~ 1.068 MB]

TOTAL COLLECTED DATA : ~89.687 MB + (~ 1.068 MB pre whitespace + ~ 2.931 MB xml name and closing + ~ 1.275 MB newline char)
[/src]

Schlüssel, Werte, Wörter, Entities, WikiTags und Leerzeichen sind gezählt und die ungefähre Datengröße wird angezeigt für die jeweilige Datensammlung.
Formattiungszeichen (Formatting) werden gesondert behandelt, also >'< und >=< für Bold, Italic, Bold+Italic und Headings.

Dann wird die Gesamtgröße dieser Daten angezeigt.
Zu der Gesamtsumme kommen dann noch >preSpaces< also Einrückung der Daten XML, XML Name und XML Closing (sagt aber nicht das ein Tag zwingend geschlossen sein muß, desßhalb das Circa) und Newline >\n< Abschlusszeichen die auch enthalten sind.

 

[Roin]

@theSplit: Nur 9 Sekunden zum vollständigen einlesen und zuordnen? Das ist deutlich schneller als ich erwartet habe. Ich habe bereits für dein vernünftiges Aufschlüsseln, in die verschiedenen Markups und Wörter trennen usw. mit einer Laufzeit von ein oder zwei Minuten gerechnet...
Python ist aber in dem Bereich auch deutlich langsamer.
Du sagst, du kommst auf einen Speicherverbrauch von rund 4,5GB bei der Datei von 100MB. Woraus setzt sich der denn zusammen?
Also 100MB die Datei eingelesen. vielleicht 10MB das Programm inklusive Pakete im Hintergrund und so.
Dann erstellst du ja einige Objekte, wie du in den vorherigen Posts erläutert hast (um das Markup aufzuschlüsseln). Diese verbrauchen ja vermutlich den Hauptteil des Speichers. In Python gibt es da eine ganz geschickte Lösung, um solche Probleme zu umgehen. Man kann dort "Generatoren" verwenden (Schlüsselwort ist yield). Dies sind Funktionen, die (normalerweise) etwas ähnliches wie eine Liste erstellen. Allerdings speichern sie lediglich die Daten, auf die sie sich beziehen sollen (Referenzen sind da auch sehr sinnvoll) und den aktuellen Schritt zum erzeugen des nächsten Listenelements. So hast du nicht tausende Elemente im Speicher sondern lediglich einige Referenzen und die paar Programmzeilen, die dafür verantwortlich sind, diese Elemente zu erzeugen.
Vielleicht gibt es in C etwas ähnliches? Das könnte zumindest Anfangs einiges an Speicher einsparen. Diese eingelesenen Daten könnte man dann auf der Festplatte speichern und systematisch zusammenfassen. Ich denke allerdings auch, dass vielleicht deine Objekte einfach zu viel Overhead erzeugen. Ich vergleiche mal mit meiner (damaligen) Wörterbuch-Methode. Dort hatte ich nur ca. das 6-10 fache der Dateigröße an Speicherverbrauch...

---
Bis ich mich erneut daran begebe, muss ich erstmal einige Arbeiten für die Uni abschließen. Vorher habe ich da keinen Kopf für.

 

[theSplit]

Danke. Die Geschwindigkeit finde ich auch top - hängt vielleicht auch mit der Hardware zusammen - aber vermutlich eher an der Tatsache das noch nichts mit den Daten gemacht wird außer das die Datei eingelesen und Inhalte (strukturiert) in den Speicher geschoben werden.

Mit dem Speicherverbrauch hast du es gedreht, den 100 MB Dump (enwik8) benötigt zwischen 620-720 MB Speicher.
Eine 650 MB Eingabedatei (aus den Wikipedia Dumps) verbraucht bis zu 4,5 GB Speicher.

Gründe warum das so ist, vermutlich die vielen Datenstrukturen. In denen wird nicht nur ein String eingelesen, sondern auch noch anderen Attribute wie Position in der Zeile, Leerzeichenanzahl vor und nach dem Wort, ist ein Wort Formatiert, zu welcher Formatierungsgruppe (also wenn zwei Formatierungen aufeinander folgen, um diese zu trennen) gehört es, haben wir ein "Elternformat" und weiteres von dem ich denke das ich es nutzen muß.

Zusätzlich zu solchen Attributen kommen dann noch der Verwaltungsapparat, also (das könnten, ich weiß es nicht zu genau( Informationen darüber sein in welcher Speicheradresse was für ein Wert liegt und oder wo ein anderer Wert/String beginnt innerhalb eines Strukturblocks und vermutlich noch andere Faktoren - aber da habe ich ehrlich gesagt derzeit keine Ahnung wie das vom Betriebssystem / C gehandhabt wird.
In Massif wird zum Beispiel bei 600-700 MB angezeigt das 400 MB Daten sind und der Rest könnte "Housekeeping" sein damit man in den Daten "navigieren" kann. So in etwa

Aber es gibt noch andere Möglichkeiten, Wikipedia beschreibt das ganz kurz auf die Frage mit man mit den Wikidumps umgehen könnte.
https://en.wikipedia.org/wiki/Help:Export#Processing_XML_export

---

Ich gĺaube das was du mit Generatoren und Yield beschreibst zu verstehen, aber ich hab gerade keine Idee wie man das sinnvoll umsetzen kann in diesem Fall.

Im Grunde ist der Ansatz wohl schon viel zu komplex geworden... und vielleicht sollte man schon während des Einlesens anfangen die Wörter zu nummerieren und dann die Zahl anstelle des Worts und seiner Wiederholungen in dem RAM speichern, sowas ähnliches mache ich zum Beispeil schon für HTML-Entities, aber die Masse ist in diesem Fall wohl oder übel reiner Text mit zig Wiederholungen und (leichten) Verunreinigungen wie Punkt, Komma, Strich und so weiter...

 

[theSplit]

Ich habe das ganze jetzt mal etwas versucht zu überarbeiten und lasse die Daten nicht direkt in den Speicher kopieren, so komme ich jetzt auf:

276 MB bei der 100 MB Datei

[src=text]--------------------------------------------------------------------------------
Command: ./cp
Massif arguments: --time-unit=B
ms_print arguments: massif.out.9415
--------------------------------------------------------------------------------


MB
263.0^ #
| ::#:
| @@: #::@
| @@@@: #::@::
| @@@@@: #::@::@
| @@@@@@@: #::@::@::
| @@@ @@@@@: #::@::@:::@
| @@@@@ @@@@@: #::@::@:::@::
| @@@ @@@ @@@@@: #::@::@:::@::::
| ::@@@ @@@ @@@@@: #::@::@:::@::::::
| @@ @@@ @@@ @@@@@: #::@::@:::@:::::@:
| @@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@:::
| @@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@:::::
| @:@@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@::::::@
| @@:@@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@::::::@::
| @:@@:@@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@::::::@:::
| ::@:@@:@@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@::::::@:::::
| @::@:@@:@@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@::::::@:::::@:
| @@@::@:@@:@@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@::::::@:::::@:::
| @:@ @::@:@@:@@@@@@ @@@ @@@ @@@@@: #::@::@:::@:::::@::::::@:::::@:::::
0 +----------------------------------------------------------------------->MB
0 525.7

Number of snapshots: 87
Detailed snapshots: [1, 2, 5, 6, 9, 11, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 37 (peak), 41, 45, 49, 59, 69, 79]

[....]

--------------------------------------------------------------------------------
n time(B) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
36 267,609,480 267,609,480 260,891,420 6,718,060 0
37 275,817,792 275,817,792 268,881,272 6,936,520 0[/src]

Jetzt sind allerdings alle Daten auf der Festplatte, dabei sind Wörter und Wikitags getrennt gespeichert, die Laufzeit wurde nur marginal beeinflusst durch das Auslagern in eine Datei, so liegt diese bei 10-12 Sekunden.

Es ist auch so, der Parser macht auch folgendes mit den Wikitags:

Aus:
[src=text]{{main articles|[[International Workingmen's Association]], [[Anarchism and Marxism]]}}[/src]

Wird:

[ZIEL] main articles
[WIKITAG] International Workingmen's Association
[WORD] ,
[WIKITAG] Anarchism and Marxism

Oder aus:
[src=text][[Image:CNT_tu_votar_y_ellos_deciden.jpg|thumb|175px|CNT propaganda from April 2004. Reads: Don't let the politicians rule our lives/ You vote and they decide/ Don't allow it/ Unity, Action, Self-management.]][/src]

Wird :
[TARGET] CNT_tu_votar_y_ellos_deciden.jpg
[WORD] thumb
[WORD] 175px
[WORD] CNT
....

Ist dort ein WikiTag enthalten wird dieser entsprechend aufgeschlüsselt, wie auch dieser Wikitag, weil ich das Rekursiv mache.

Das [TARGET] bleibt dabei jedoch im ganzen, hier wied bisher der ganze String mit Leerzeichen eingelesen.


Jetzt müsste ich nur noch effizient über die Wörter in der Textdatei iterieren.... um mit einer eigentlichen Kompression bzw. dem Dictionary aufbau zu beginnen.
Ich glaube alle Wörter von der HD zu iterieren wird lange dauern, aber so bleibt zumindest der RAM-Speicherverbrauch gering.


Bei der 634 MB Testdatei sieht es allerdings doch noch etwas anders aus:

Spoiler

[src=txt]--------------------------------------------------------------------------------
Command: ./cp
Massif arguments: --time-unit=B
ms_print arguments: massif.out.9493
--------------------------------------------------------------------------------


GB
1.487^ ##
| :# :
| :::# ::
| @: :# ::::
| @@@@: :# ::::::
| @@ @@: :# ::::::::
| ::@@ @@: :# ::::::: ::
| @::@@ @@: :# ::::::: ::::
| @@@::@@ @@: :# ::::::: ::: ::
| @@ @::@@ @@: :# ::::::: ::: : ::
| @@@@@@ @::@@ @@: :# ::::::: ::: : : @
| @ @ @@ @::@@ @@: :# ::::::: ::: : : @::
| @@@@ @ @@ @::@@ @@: :# ::::::: ::: : : @::::
| :@@@ @ @ @@ @::@@ @@: :# ::::::: ::: : : @::: ::
| @:@@@ @ @ @@ @::@@ @@: :# ::::::: ::: : : @::: : :
| ::@@:@@@ @ @ @@ @::@@ @@: :# ::::::: ::: : : @::: : ::::
| :: @@:@@@ @ @ @@ @::@@ @@: :# ::::::: ::: : : @::: : ::: :
| ::: @@:@@@ @ @ @@ @::@@ @@: :# ::::::: ::: : : @::: : ::: :::
| @@::: @@:@@@ @ @ @@ @::@@ @@: :# ::::::: ::: : : @::: : ::: :::::
| :@@ ::: @@:@@@ @ @ @@ @::@@ @@: :# ::::::: ::: : : @::: : ::: :::::::
0 +----------------------------------------------------------------------->GB
0 2.998

Number of snapshots: 59
Detailed snapshots: [1, 3, 4, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 28 (peak), 41, 57]

[...]

--------------------------------------------------------------------------------
n time(B) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
26 1,473,413,720 1,473,413,720 1,443,108,837 30,304,883 0
27 1,533,261,776 1,533,261,776 1,501,756,076 31,505,700 0
28 1,597,082,616 1,597,082,616 1,564,276,633 32,805,983 0[/src]

Und die "Statistik" dazu:

[src=text][REPORT] PARSED LINES : 4755045 | FAILED ELEMENTS: 0
[REPORT] FILE STATISTICS
KEYS : 27161 [~ 0.215 MB]
VALUES : 27161 [~ 0.298 MB]
WORDS : 74683227 [~ 393.427 MB]
ENTITIES : 5714621 [~ 25.647 MB]
WIKITAGS : 4322020 [~ 82.914 MB]
WHITESPACE : 84455640 [~ 80.543 MB]
FORMATTING : [~ 4.378 MB]

TOTAL COLLECTED DATA : ~587.422 MB + (~ 3.483 MB pre whitespace + ~ 7.058 MB xml name and closing + ~ 5.352 MB newline char)[/src]


Aber halt auch keine 4,7 GB mehr! , sondern "nur" 1,6 GB.

 

[theSplit]

Ich habe jetzt noch weitere Speicheroptimierungen vorgenommen, so konnte anstelle der 276 MB der benötigte Speicher, bei gleichen gesammelten Daten, auf 226 MB reduziert werden für 100 MB Beispieleingabe.

Den Trick den ich angewandt habe: Für >formatType<, spacesCount und preSpacesCount anstelle anstelle von >short< bzw. >unsigned int< jeweils >char< bzw. >unsigned char< verwendet.
Ich gehe dabei davon aus das es nicht mehr als 125 Format-Typen gibt, es sind 8 an der Zahl die erkannt werden - und nicht mehr als 255 Leerzeichen nach oder vor einem Element kommen.

Desweiteren hat sich die Ausbeute für die Datei, nach einer Anpassung und einer Fehlerkorrektur etwas verbessert, so werden jetzt auch mehr Daten gesammelt - es scheint aber noch nicht 100% zu sein:

Vorher:
[src=text]REPORT] FILE STATISTICS
KEYS : 12372 [~ 0.106 MB]
VALUES : 12372 [~ 0.118 MB]
WORDS : 11835198 [~ 57.235 MB]
ENTITIES : 469686 [~ 2.207 MB]
WIKITAGS : 972128 [~ 16.664 MB]
WHITESPACE : 12885758 [~ 12.289 MB]
FORMATTING : [~ 1.068 MB]

TOTAL COLLECTED DATA : ~89.687 MB + (~ 1.068 MB pre whitespace + ~ 2.931 MB xml name and closing + ~ 1.275 MB newline char)[/src]

Nachher:
[src=text][REPORT] FILE STATISTICS
KEYS : 12372 [~ 0.106 MB]
VALUES : 12372 [~ 0.118 MB]
WORDS : 12190353 [~ 59.305 MB]
ENTITIES : 470196 [~ 2.209 MB]
WIKITAGS : 975611 [~ 16.733 MB]
WHITESPACE : 12902538 [~ 12.305 MB]
FORMATTING : [~ 1.068 MB]

TOTAL COLLECTED DATA : ~91.844 MB + (~ 1.068 MB pre whitespace + ~ 2.931 MB xml name and closing + ~ 1.275 MB newline char)[/src]

Wenn man die Daten mit Extra Daten hinzuzieht, kommt man auf circa 97.118 MB, es fehlen also circa noch 3-4 MB die nicht korrekt mitgezählt bzw. nicht korrekt erfasst werden, aber circa. 2 MB mehr Daten die erkannt worden sind.
Der Rest der fehlt, es kann daran liegen das Zeilen übergreifende Table-Tags derzeit nicht funktionieren (ich lese ja Zeilenweise ein), kann aber auch ein genereller Parsing Error sein oder im schlimmstem Fall, ich zähle manche Daten nicht korrekt mit.

Ich glaube das ist auch das nächste an dem ich arbeiten werde, das beim Zeileneinlesen Tables gesondert behandelt werden und ein "Newline" Zeichen ignoriert wird, so das die Zeilen komplett im Speicher landen und dann erst überprüft werden. Sollte auch für die Auswertung generell besser sein weil etwas mehr optimiert werden kann.

Bei der großen Datei liegt das Datenaufkommen bei 1.209 GB - anstelle von 1.473 GB. (plus minus ein paar MB für die Toleranz von ms_print/Massif).

 

[Roin]

@theSplit: Hast du schon mal versucht einfach alle Tags und Co., die du gefunden hast in der Datei durch "blanks" zu ersetzten, also einfach zu löschen?

Vielleicht siehst du dann sehr schnell, was nicht eingelesen wurde. Könnte ja sein, dass da ein Wiki-Tag fehlerhaft ist und somit nicht erkannt wird oder sowas. Solche Fälle müsstest du bestenfalls ja auch abfangen.

Die Optimierung des Speichers ist aber schon nicht zu verachten. Mal eben knapp 20% gespart - und das nur durch einen anderen Datentypen - bei der Menge an Daten kann man sowas leicht unterschätzen.

Zeit für etwaiges Ausprobieren habe ich nun wieder - jetzt muss ich mich nur dazu durchringen, mich da auch wirklich ranzusetzen ^^

 

[theSplit]

Roin, das mit den Leerzeichen ist eine sehr sehr gute Idee
Das sollte ich ins Auge fassen.

Müsste dann mal überlegen wie sich das am geschicktesten umsetzen lässt....

Ich hab eine aktuelle Variante jetzt auch auf Github geladen. - Und heute Nacht mal durchlaufen lassen wie lange die Erstellung eines Dictionaries bei der 100 MB Datei dauert wenn ich die Daten von der Platte immer einlesen lasse...

[STATUS] RUN TIME FOR PARSING PROCESS: 18h 24m 15s

Und das ist nur die Erstellung eine "unique" Dictionaries. Ist wohl nicht so mit Daten auslagern.... und dann damit werkeln...

------

Du kannst deinen Code ja auch mal irgendwo hochladen, vielleicht kann man dir auch ein paar Tips geben.

 

[theSplit]

Ich melde mich hier auch mal wieder zu Wort - es gibt eine neue Version des Parsers.

Kleiner Scherz am Rande: Vielleicht hätte ich den Threadtitel eher "Ich schreibe einen Wikipedia Dump Parser" nennen sollen.

Im Parser gibt es nur kleinere Korrekturen - zum Beispiel das Wörter, die von einem Wikitag ohne Leerzeichen gefolgt waren, anstelle als einzelnes Wort, in den Wikitag mit übernommen wurden. Behoben wurde auch ein Fehler, bei dem die letzten Worte einer Überschrift nicht mehr als solche deklariert waren. Behoben wurde ein Problem, nur optisch, das Wikitag Typen nicht mehr angezeigt worden sind in vielen Fällen, spürbar war dies besonders durch die Debug Ausgabe und wenn BEVERBOSE verwendet wird. Auch ist die Statistik nun etwas genauer, im Test findet der Parser, geschätzt, mehr Daten, als die Datei groß ist - was daran liegt das manche XML Tags mit Tag Namen geschlossen sind, andere nicht. Außerdem wird jetzt auch die Zeilennummer an die "addWord", "addWikitag" usw... Funktionen übergeben.

Außerdem wird die Ausgabe von Wörtern und WikiTags jetzt ungefiltert in die entsprechenden Textdateien in den "data" Ordner geschrieben und mit weiteren Informationen wie Zeilennummer, wikiTagType und Formatierung gepspeichert.

Neben diesen Fehlerkorrekturen und Verbesserungen habe ich auch den letzten Vorschlag von Roin aufgegriffen:
Es gibt nun ein "datachecker.py" Skript. Wenn mit Python 3 gestartet, wird der Inhalt der Quelldatei (enwik8_small) in den Speicher geladen. Dann werden alle Entities entfernt, dann die Wikitags aus der entsprechenden "wikitags.txt" und dann das gleiche mit den Worten.

Zweck des Tools ist, Daten die nicht erfasst worden sind übrig zu lassen.
Diese Funktionalität ist derzeit gegeben.

Es gibt lediglich ein Problem mit Wikitag-Closings, Pipes und Überschriften bei dieser Filterung, so das diese nicht gezielt und effizient mit einem String.replace() entfernt werden konnten, zumindest so wie ich es mir gedacht hatte.

Ein Beispiel, mit Suche nach : ' Zeichen
Ein Replace mit zwei '-Zeichen würde einem fünfer Block ' Formatierung entfernen, wenn das Wort vor dem Wikitag kommt (es werden ja Wikitags vor der Wortliste bearbeitet)

Auch sind WikiTags ein Problem die mehrere Parameter haben, so wird zum Beispiel das "]]" Closing eines beinhalteten Wikitags entfernt, anstelle des entsprechenden Tags...

Ich habe noch keine gute Lösung gefunden wie man dies verbessern kann.
Daher benutzt der datachecker auch eine "Cleanup" Routine die derartige Zeichen entfernt.

Als letzter Schritt wird Whitespace zusammengeschmolzen soweit sinnvoll.

Wenn alles richtig funktioniert hat man nur noch den XML Körper mit Schlüsseln und Werten innerhalb des XML Knotens, aber keine XML Tag Inhalt mehr. Die Zeilennummer bleiben identisch.
Heißt die Wörter/Wikitags sind erfolgreich verarbeitet worden wenn etwas leer bleibt.

Wollte das Feedback mal da lassen und zeigen das es weitergeht.

Wer interessiert ist kann sich das ganze bei Github ansehen bzw. auch testweise die Cleanup Routine und das Whitespace Merging auskommentieren.

 

[Roin]

Neben diesen Fehlerkorrekturen und Verbesserungen habe ich auch den letzten Vorschlag von Roin aufgegriffen:
Es gibt nun ein "datachecker.py" Skript. Wenn mit Python 3 gestartet, wird der Inhalt der Quelldatei (enwik8_small) in den Speicher geladen. Dann werden alle Entities entfernt, dann die Wikitags aus der entsprechenden "wikitags.txt" und dann das gleiche mit den Worten.

Schön, dass ich Input geben konnte

Es gibt lediglich ein Problem mit Wikitag-Closings, Pipes und Überschriften bei dieser Filterung, so das diese nicht gezielt und effizient mit einem String.replace() entfernt werden konnten, zumindest so wie ich es mir gedacht hatte.

Wie sieht es aus mit Regulären Ausdrücken, die du je nach Tag erstellen lässt? Damit solltest du doch die Probleme der "zuviel entfernten Zeichen" beheben können. Immerhin besitzt XML ja eine Syntax, die du in Regulären Ausdrücken beschreiben kannst.


Was jetzt noch für mich im Raum steht: Speicherst du bei den Wikitags, ob diese einen Closing-Tag haben oder nicht? Immerhin sollst du eine 1:1 Rekonstruktion schaffen.

Zudem, wie sieht es mit "fehlerhaftem" Tag-Baum aus? Wenn beispielsweise <i><b>Text</i></b> steht (kommt sowas vor?), wie speicherst du die Reihenfolge der "fehlerhaften" Closing-Tags? Du könntest natürlich eine "richtige" Version wiederherstellen, allerdings ist dies NICHT gewünscht - Fehler müssen ebenfalls rekonstruiert werden.

Ich habe es jetzt nicht nachgeguckt, aber wie fasst du die Whitespaces zusammen? Erneut durch ein "Wörterbuch"?
Da fällt mir nämlich eine Idee zu ein.
Whitespaces als erstes entfernen --> Man speichert in einer Datei die Zeichenposition und optional die Anzahl der Whitespaces. Dadurch schafft man bei optimaler Ausnutzung eine Beschreibung der Whitespaces in 2 Bytes (die Zeilen der Dateien müsstest du irgendwie in die Datei mit einbauen, wodurch die die Zeichenposition in einem Byte speichern können müsstest.
Ein weiterer Gedankengang: Wie sieht es aus, eventuell zuvor euonted-encoding (Wird bei Emails verwendet, um die Zeichen pro Zeile auf x Zeichen zu begrenzen) zu verwenden? Eine abgewandelte Form davon könnte den Speicherbedarf der Dateipositionen durch kürzere Zeilen / geringere Zeichenanzahl pro Zeile verringern.

 

[theSplit]

Wie sieht es aus mit Regulären Ausdrücken, die du je nach Tag erstellen lässt? Damit solltest du doch die Probleme der "zuviel entfernten Zeichen" beheben können. Immerhin besitzt XML ja eine Syntax, die du in Regulären Ausdrücken beschreiben kannst.

Das XML bzw. dessen Struktur zu erfassen ist eigentlich nicht schwer.

Problematisch ist das Wikimarkup wie zum Beispiel ein Wikitag vom Typ Image der wie folgt aussieht (enwik_8... Zeile 250)
[src=text][[Image:CNT-armoured-car-factory.jpg|right|thumb|270px|[[Spain]], [[1936]]. Members of the [[CNT]] construct [[armoured car]]s to fight against the [[fascist]]s in one of the [[collectivisation|collectivised]] factories.]][/src]

Die Daten werden wie folgt erfasst:
Daher, ich belasse nicht die gesamte Struktur, sondern eine Wikitag wird "aufgeschlüsselt".

[src=text]====================================================================
[DEBUG] START PARSING DATA => TAG: 'text' | READERPOS: 0 | LINE: 250
[DEBUG] LINE: 250 | SPACING: 0/0 | WTD: 0 | POS: 0 | READER: 221 | DATA: 212 | WIKITAG | DATA: "CNT-armoured-car-factory.jpg|right|thumb|270px|[[Spain]], [[1936]]. Members of the [[CNT]] construct [[armoured car]]s to fight against the [[fascist]]s in one of the [[collectivisation|collectivised]] factories." 'Image type'
[DEBUG] PARSING WIKITAG => "CNT-armoured-car-factory.jpg|right|thumb|270px|[[Spain]], [[1936]]. Members of the [[CNT]] construct [[armoured car]]s to fight against the [[fascist]]s in one of the [[collectivisation|collectivised]] factories." (Image type)
[DEBUG] TARGET => "CNT-armoured-car-factory.jpg"
[DEBUG] FOUND [ WORD ] => "right"
[DEBUG] FOUND [ WORD ] => "thumb"
[DEBUG] FOUND [ WORD ] => "270px"
[DEBUG] FOUND [ WIKITAG ] => "Spain" (Link)

[DEBUG] ADDING WIKITAG : "Spain" (Link)
[DEBUG] FOUND [ WORD ] => ","
[DEBUG] FOUND [ WIKITAG ] => "1936" (Link)

[DEBUG] ADDING WIKITAG : "1936" (Link)
[DEBUG] FOUND [ WORD ] => "."
[DEBUG] FOUND [ WORD ] => "Members"
[DEBUG] FOUND [ WORD ] => "of"
[DEBUG] FOUND [ WORD ] => "the"
[DEBUG] FOUND [ WIKITAG ] => "CNT" (Link)

[DEBUG] ADDING WIKITAG : "CNT" (Link)
[DEBUG] FOUND [ WORD ] => "construct"
[DEBUG] FOUND [ WIKITAG ] => "armoured car" (Link)

[DEBUG] ADDING WIKITAG : "armoured car" (Link)
[DEBUG] FOUND [ WORD ] => "s"
[DEBUG] FOUND [ WORD ] => "to"
[DEBUG] FOUND [ WORD ] => "fight"
[DEBUG] FOUND [ WORD ] => "against"
[DEBUG] FOUND [ WORD ] => "the"
[DEBUG] FOUND [ WIKITAG ] => "fascist" (Link)

[DEBUG] ADDING WIKITAG : "fascist" (Link)
[DEBUG] FOUND [ WORD ] => "s"
[DEBUG] FOUND [ WORD ] => "in"
[DEBUG] FOUND [ WORD ] => "one"
[DEBUG] FOUND [ WORD ] => "of"
[DEBUG] FOUND [ WORD ] => "the"
[DEBUG] FOUND [ WIKITAG ] => "collectivisation" (Link)

[DEBUG] ADDING WIKITAG : "collectivisation" (Link)
[DEBUG] FOUND [ WORD ] => "collectivised"
[DEBUG] FOUND [ WORD ] => "factories."[/src]

All diese Daten sind aus dem einem Wikitag ausgelesen worden und sind diesem intern zugeordnet.

In der Textdatei speichere ich allerdings nicht den gesamten Tag, sondern nur "Typ" und "Target"
Die Attribute wie Größe in Pixel, Ausrichtigung und Thumb sind alles Wörter.
Die Wikitags und Wörter die in diesem langen Imagetag auftauchen sind Kinder.

In der "wikitags.txt" speichere ich aktuell die Wikitags, also:

(Image) Target/Ziel:
CNT-armoured-car-factory.jpg

aber auch, alle Link-Tags auf unter Seiten:
Spain, 1936, CNT, amoured car....

aus den Daten.
Die Wörter kommen alle in die "words.txt".


Wenn wir uns jetzt nochmal die Originalzeile wie in enwik8_small ansehen:
[src=text][[Image:CNT-armoured-car-factory.jpg|right|thumb|270px|[[Spain]], [[1936]]. Members of the [[CNT]] construct [[armoured car]]s to fight against the [[fascist]]s in one of the [[collectivisation|collectivised]] factories.]][/src]

[[image: --- kann ersetzt werden (Info des Typs aus wikitag.txt) also "[[image:"
CNT-armoured-car-factory.jpg (Target, gespeichert in wikitag.txt)

|right|thumb|270px|
Die Pipes könnte man automatisch entfernen lassen wenn vor einem Wort. Der weiteren Attribute sind wie gesagt nur Wörter, schritt zwei.

[[Spain]]
Das ist ein Link-Wikitag innerhalb unserer Elternwikitags, und hier das Problem, die beiden linken eckigen Klammern am Ende: ]]


Der ganze Aufbau mit:
[[Image:.....|[[Spain]], [[1936]]. Members of the....]]

Ist das Problem, da kann ich nicht mit Regex greifen wenn ich nur nach [[ und ]] suche - da innerhalb dieser Struktur diese Begrenzungszeichen bereits enthalten sind durch Spain und 1936 usw... und ich auch nicht sagen ob ein Wikitag diese immer beinhaltet, viele tun dies zum Beispiel nicht.

---

Sorry für den vielen Text, aber so wird glaube ich klar was wie erfasst wird.

Was jetzt noch für mich im Raum steht: Speicherst du bei den Wikitags, ob diese einen Closing-Tag haben oder nicht? Immerhin sollst du eine 1:1 Rekonstruktion schaffen.

Die Tags werden in der Regel durch: "[[" oder "{|" oder "{{" geöffnet und mit "]]", "|}" oder "}}" geschlossen.

Wenn ein Tag defekt ist, wird er auch nicht als solcher behandelt und wird dann theoretisch mit in die Wörter aufgenommen.
Das ist zum Beispiel ein Problem wenn eine Formatiertung fehlerhaft ist, der Parser beendet die Formatierung erst, wenn diese auch beendet wurde bzw. in einer neuen Zeile.
Aber das ist auch fehlerhaftes Markup, dafür würde ich jetzt nicht extra versuchen Workarounds zu schreiben.

Zudem, wie sieht es mit "fehlerhaftem" Tag-Baum aus? Wenn beispielsweise <i><b>Text</i></b> steht (kommt sowas vor?), wie speicherst du die Reihenfolge der "fehlerhaften" Closing-Tags? Du könntest natürlich eine "richtige" Version wiederherstellen, allerdings ist dies NICHT gewünscht - Fehler müssen ebenfalls rekonstruiert werden

Der Fall kommt so nicht vor, es gibt mal stellen da ist zum Beispiel ein "}}}}" obwohl davor nur ein "{{" geöffnet wurde - dann werden die zweiten "}}" (was auch ein Wikitag wäre, ignoriert da wir fehlerhaftes Markup haben.

Anders sieht der Fall aus wenn zwei "[[[[" kommen und nur ein "]]" als Closing geliefert wird - hier würde der Parser aktuell wie folgt agieren:
Also: [[[[Test]] mehr Text Zeilenende

"[DEBUG] LINE: 40 | SPACING: 1/0 | WTD: 1 | POS: 2 | READER: 71 | DATA: 18 | WIKITAG | DATA: "[[Test]] mehr Text Zeilenende" 'Link'
[DEBUG] ADDING WIKITAG : "[[Test]] mehr Text Zeilenende" (Link)"

Das Beispiel gibt es so nicht, aber der Parser würde die Zeile komplett bis zum Ende einlesen, da hier kein logisches Ende erfolgt und dieses als Link vermerken, heißt bei der Rekonstruktion wäre schon ein Fehler, wir hätten dann statt:
[[[[Test]] mehr Text Zeilenende
das hier:
[[[[Test]] mehr Text Zeilenende]]

Weil der Text als ein Link erfasst wird.
Weil ich beim "rückbau" der Daten davon ausgehe, das der Input korrekt geformt ist.

Ich habe es jetzt nicht nachgeguckt, aber wie fasst du die Whitespaces zusammen? Erneut durch ein "Wörterbuch"?

Durch einen Regex mit Replace, aus:
r"[ ]{2,}" => " " (2 oder mehr Leerzeichen in einer Folgen, so viele wie möglich Matchen, auf ein Leerzeichen reduzieren.

Das ist aber keine Kompremierung! - Das ist nur im "Kontrolltext" die das "datachecker.py" Skript erstellt. Um Inhalte des XML zu finden das nicht korrekt eingelesen worde.

Da fällt mir nämlich eine Idee zu ein.
Whitespaces als erstes entfernen --> Man speichert in einer Datei die Zeichenposition und optional die Anzahl der Whitespaces. Dadurch schafft man bei optimaler Ausnutzung eine Beschreibung der Whitespaces in 2 Bytes (die Zeilen der Dateien müsstest du irgendwie in die Datei mit einbauen, wodurch die die Zeichenposition in einem Byte speichern können müsstest.

Irgendwie kann ich das nicht nachvollziehen, kannst du ein Beispiel geben?

Ein weiterer Gedankengang: Wie sieht es aus, eventuell zuvor euonted-encoding (Wird bei Emails verwendet, um die Zeichen pro Zeile auf x Zeichen zu begrenzen) zu verwenden? Eine abgewandelte Form davon könnte den Speicherbedarf der Dateipositionen durch kürzere Zeilen / geringere Zeichenanzahl pro Zeile verringern.

Nein, warum sollte die Zeichengröße kleiner werden nur weil die Zeilen kürzer sind?
Die Zeile stört es relativ wenig ob 200 oder 3000 Zeichen in ihr sind.

Es würde die Datei sogar aufblähen, weil du mehr "\n" (newline) Zeichen in deinem Text hättest um die Zeilenumbrüche zu generieren, jeweils ein Byte.

 

[Roin]

Da fällt mir nämlich eine Idee zu ein.
Whitespaces als erstes entfernen --> Man speichert in einer Datei die Zeichenposition und optional die Anzahl der Whitespaces. Dadurch schafft man bei optimaler Ausnutzung eine Beschreibung der Whitespaces in 2 Bytes (die Zeilen der Dateien müsstest du irgendwie in die Datei mit einbauen, wodurch die die Zeichenposition in einem Byte speichern können müsstest.

Irgendwie kann ich das nicht nachvollziehen, kannst du ein Beispiel geben?

Ein weiterer Gedankengang: Wie sieht es aus, eventuell zuvor euonted-encoding (Wird bei Emails verwendet, um die Zeichen pro Zeile auf x Zeichen zu begrenzen) zu verwenden? Eine abgewandelte Form davon könnte den Speicherbedarf der Dateipositionen durch kürzere Zeilen / geringere Zeichenanzahl pro Zeile verringern.

Nein, warum sollte die Zeichengröße kleiner werden nur weil die Zeilen kürzer sind?
Die Zeile stört es relativ wenig ob 200 oder 3000 Zeichen in ihr sind.

Das gehört alles zusammen.

Meine Idee war aus etwas wie [src=txt]
Hallo ich habe eben drei Leerzeichen geschrieben[/src] in einer Datei etwas wie [2] 6 3 speichere. Zeile 2, Zeichen 6, 3-maliges Vorkommen. Wenn man das nun auf 1024 Zeichen pro Zeile beschränkt, kannst du beispielsweise die Position des entsprechenden Leerzeichens in einem Byte speichern (Binäre Datei statt Textdatei verwenden). Findet man nun noch eine kluge Art, die Zeile der entsprechenden Datei zu finden, so kann man womöglich einiges an Speicherplatz für solche Komprimierungen sparen. In wie weit sich das lohnt, da ja neue Zeichen angefügt werden (durch das Quoted-Encoding), müsste man dann testen. So beschränkst du auch erneut den Zeichensatz, der für die Komprimierung erforderlich wäre.


Die Frage bezüglich der Closing-Tags ist also derzeit noch nicht vollständig geklärt. Du hast ja ein Beispiel gegeben, wo die Rekonstruktion nicht funktioniert. Erst wenn die Rekonstruktion der Datei einwandfrei funktioniert, lohnt sich der Versuch diese Daten zu reduzieren und anschließend zu komprimieren.

 

[theSplit]

Ich hab die Idee mit den Leerzeichen immer noch nicht verstanden

Kannst du mir mal irgendwie aufzeichnen nach welchem Muster das ablaufen soll?

Zur Rekonstruktion:

Ja das Problem ist, das wird auch Wikipedia haben - du öffnest einen Link Tag ("[[")und hast gleich darauf noch nen Link Tag "Opening" mit "[["- welcher zählt jetzt? Du hast aber nur "ein" oder gar kein Closing wie "]]"? - Was machst du jetzt?

Das ist eine Designentscheidung. Was ist zu bevorzungen, lassen wir die Link Tags flöten gehen, versuchen wir das beste "nach meinem Verständnis" zu machen, oder ignorieren wir dies komplett dann?

Btw. sind die Zeichen "[[", "{{" und "{|" reserviert - wenn diese auftauchen, "sollte" ein Tag folgen zu 100% - aber was machen wir dann, bis wohin einlesen, wann schließen.

Ich regele es mit Stufen: Jeder "[[" öffnet einen Wikitag (link). Also +1 Stufen.
Jedes "]]" das darauf folgt, setzt die Stufe um ein Level herab.

Sind wir bei 0 - ist der Tag geschlossen.

Wie würdest du es handhaben, in einer nicht perfekten Welt?

 

[Roin]

Ich hab die Idee mit den Leerzeichen immer noch nicht verstanden
Kannst du mir mal irgendwie aufzeichnen nach welchem Muster das ablaufen soll?

Nehmen wir das Beispiel von oben. In Zeile 2 stehen 3 Leerzeichen ab Position 6.
Du schreibst in eine Datei [2] (ob du die Zeile nun mit reinschreibst oder irgendwie anders zugehörig speicherst, müsste man ausprobieren) 6 3. Bedeutung: In Zeile Zwei sind ab Position 6 nicht ein Leerzeichen, sondern 3.

So könntest du einfach jedes Wort mit einem Leerzeichen trennen (oder entsprechend einem Satzzeichen) und falls in deiner "Whitespace"-Datei ein Eintrag zu der zugehörigen Position zu finden ist, fügst du beim Rekonstruieren weitere Leerzeichen hinzu.
Damit der Speicherbedarf auch gering ist, speicherst du die Zahlen in Binärer Form, schreibst also direkt die Bytes als 00000110 (6) ...
Damit das funktioniert, musst du die Anzahl der Zeichen in einer Zeile begrenzen - in einem Byte kannst du 1024 Werte speichern - also dürfen nicht mehr Zeichen in einer Zeile vorkommen. Ansonsten benötigst du für das Speichern der Position vermutlich mehr Speicher, als die Leerzeichen an sich benötigen.

Ob das wirklich was bringt, oder man das vielleicht auf etwas anderes anwendet, sei dahingestellt. Ich würde halt sagen, am Ende hast du ja eine Datei, die irgendwie auf die Wörterbucheinträge verweist und die Inhalte entsprechend korrekt wieder anordnen kann. Auf diese Datei könnte man dann beispielsweise dieses Whitespace-Extrahier-Verfahren anwenden - dabei kann man dann auch einzelne Whitespaces und Wörter, die durch andere Zeichen getrennt werden "ignorieren" und muss wirklich nur mehrfache Whitespaces zusammenfassen.

Ich hoffe, das war nun etwas verständlicher, wie ich mir da gedacht habe.

Wie würdest du es handhaben, in einer nicht perfekten Welt?

Ich vermute Wikimedia / Wikipedia haben da eine Regel eingeführt, dass zum Beispiel ein Link, der offensichtlich nicht geschlossen wird, nicht mehr als zwei Wörter / x Zeichen beinhalten kann usw.
Diese müsste man natürlich herausfinden (kann man vielleicht sogar irgendwo nachlesen...).
Aber sonst... Hoffen, dass man irgendwie ein Workaround findet, was das korrekt macht.

EDIT:
BTW, die Dateien, die du später irgendwie zusammen speichern möchtest, haben bestenfalls als Dateinamen nur noch ein Zeichen und keine Extension - dadurch verringerst du ja auch die Informationen, die du zum Beschreiben der Datei ebenfalls in dein entgültiges Archiv schreiben müsstest.

 

[theSplit]

Jetzt habe ich auch den Bogen bekommen.

Das wäre also eine Art "Run-length Encoding", also statt "xxxx" zu kürzen auf "4x", 50% gespart - also meinst du das wohl auch für Whitespaces.
Müsste man schauen in wie weit dafür ein nutzen wäre.

Ich hab es beim einlesen so gelöst, das vermerkt wird wie viel Whitespace sich hinter einem Wort/Wikitag befinden. Die Info wird allerdings nur in den Speicher geladen und findet bisher keine andere Anwendung.

Erst einmal wollte ich den Parser, wie du vorgeschlagen hast, kontrollieren. Also, werden alle Daten korrekt eingelesen oder fehlt etwas an Inhalten?
Zugegeben, das Säubern des datachecker.py von "Resten" ist nicht sonderlich sinnvoll, mal sollte ja sehen wenn etwas übrig bleibt, aber das ist echt schwer zu überprüfen.

Aber wichtig ist ja schon einmal, das die Inhalte sauber eingelesen werden.

Vielleicht wäre der nächste Schritt die Tags ohne Attribute wie Pixelbreite, Alignment oder innerem "Markup" zu überprüfen. Also zu testen, ob sich an einer Stelle ein Tag dieses Typs befindet oder vielleicht sogar besser - findet sich in einer Zeile ein Tag der so nicht erfasst wurde oder besitzt ein Wort eine Formatierung die nicht auftaucht?
Ich wüsste halt nicht anders wie ich sonst sicherstellen bzw. überprüfen könnte ob das Auslesen funktioniert, dafür ist selbst eine 1 MB Datei einfach viel zu Umfangreich um alle Wikitags und oder Worte mit Formaten (auch Wikitags können formatiert sein) zu überprüfen - um zu Beweisen das alles, unter der Berücksichtigung der Parserlogik bzw. Wikipedia-Regeln "korrekt" funktioniert.

 

[Roin]

Ich wüsste halt nicht anders wie ich sonst sicherstellen bzw. überprüfen könnte ob das Auslesen funktioniert [...]

Das ist halt eine sehr schwierige Frage, wie ich finde. Daher habe ich das Parsen der Einträge bereits sehr früh am Anfang erstmal verworfen, da mir die Tags und Co. einfach zu unsauber getrennt aufgebaut sind.
Allerdings liegt theoretisch nun bei dir größeres Komprimierungspotential - natürlich auf dieses Dumps spezialisiert.
Lass mich/uns wissen, wie du das gelöst hast!

 

[theSplit]

Also, heute noch mal etwas Arbeit in das Datachecker Skript gegeben, jetzt liefert das Teil auch nen Report wenn "Leftovers" gefunden werden.

Ich muß das nochmal überprüfen - aber scheinbar schlägt es schon bei einigem richtig an das Daten doch noch fehlen:


[src=text]=========================================================================
Reporting orphands
=========================================================================

Orphand symbols in line 477: [[zh-min-nan:Hui-thóng-tī-chú-gī]]</text>

Orphand symbols in line 695: ''''

Orphand symbols in line 968: [[zh:自閉症]]</text>

Orphand symbols in line 1187: [[uk:Альбедо]]</text>

Orphand symbols in line 1345: [[zh:阿布扎比]]</text>

Orphand symbols in line 2331: [[zh:A]]</text>

Orphand symbols in line 2808: [[zh:阿拉巴馬州]]</text>

Orphand symbols in line 2903: '' ''

Orphand symbols in line 2932: ''' '''

Orphand symbols in line 2961: '''' ''''

Orphand symbols in line 2965: ''''

Orphand symbols in line 2967: ''''

Orphand symbols in line 2969: ''''

Orphand symbols in line 2970: ''''

Orphand symbols in line 3030: [[zh:阿基琉斯]]</text>

Orphand symbols in line 3345: ''''

Orphand symbols in line 3358: '''' '''' ''''

Orphand symbols in line 3571: [[zh:亚伯拉罕·林肯]]</text>

Orphand symbols in line 3739: ''''

Orphand symbols in line 4011: [[zh:亚里士多德]]</text>

Orphand symbols in line 4039: [[sv:An American in Paris (symfonisk dikt)]]</text>

Orphand symbols in line 4378: [[zh:奥斯卡金像奖]]</text>

Orphand symbols in line 4466: [[sk:Živočíchy]]</text>

Orphand symbols in line 4533: [[svAI]]</text>

Orphand symbols in line 4730: [[sv:Altruism]]</text>

Orphand symbols in line 4743: <text xml:space="preserve">''''

Orphand symbols in line 4827: [[zh:李安]]</text>

Orphand symbols in line 5318: [[zh:艾茵·兰德]]</text>

Orphand symbols in line 5367: [[zh:阿兰·孔]]</text>

Orphand symbols in line 5478: [[de:Allan Dwan]]</text>

Orphand symbols in line 5605: [[ru:Экономика Алжира]]</text>

Orphand symbols in line 5690: :''See also :'' [[Algeria]]</text>

Orphand symbols in line 5773: ''''

Orphand symbols in line 6035: [[zh-min-nan:Algeria]]</text>

Orphand symbols in line 6200: [[Category:Lists of fictional characters|Atlas Shrugged characters]]</text>

Orphand symbols in line 6246: [[Category:Fictional technology|Atlas Shrugged]]</text>

Orphand symbols in line 6341: [[Category:Fictional companies|Atlas Shrugged]]</text>

Orphand symbols in line 6388: [[Category:Atlas Shrugged]]</text>

Orphand symbols in line 6474: ====

Orphand symbols in line 6562: ====

Orphand symbols in line 6572: ====

Orphand symbols in line 6591: [[Category:Lists of fictional things]]</text>

Orphand symbols in line 6671: [[Category:Atlas Shrugged]]</text>

Orphand symbols in line 6683: <text xml:space="preserve">'' ''

Orphand symbols in line 6789: [[zh:阿特拉斯摆脱重负]]</text>

Orphand symbols in line 7014: [[zh:人类学]]</text>

Orphand symbols in line 7047: '''' ''''

Orphand symbols in line 7281: [[zh:考古学]]</text>

Orphand symbols in line 7404: [[zh:农学]]</text>

Orphand symbols in line 7550: '' ''

Orphand symbols in line 7620: '' ''

Orphand symbols in line 7778: [[zh:炼金术]]</text>

Orphand symbols in line 7894: [[Category:Avionics]]</text>

Orphand symbols in line 8097: ''''''

Orphand symbols in line 8254: [[fiu-vro:Austria]]</text>

Orphand symbols in line 8329: ''''

Orphand symbols in line 8337: ''''

Orphand symbols in line 8394: ''''

Orphand symbols in line 8426: ''''

Orphand symbols in line 8572: [[zh:澳大利亚]]</text>

Orphand symbols in line 8838: [[zh:美屬薩摩亞]]</text>

Orphand symbols in line 8855: ''''

Orphand symbols in line 8856: ''''

Orphand symbols in line 8876: [[zh:外星人]]</text>

Orphand symbols in line 8976: [[zh:天文学家]]</text>

Orphand symbols in line 9005: <text xml:space="preserve"> (''Chaos''

Orphand symbols in line 9006: (''Ammonia''

Orphand symbols in line 9007: (''Actinophrys''

Orphand symbols in line 9030: [[pl:Ameby]]</text>

Orphand symbols in line 10047: [[zh-min-nan:ASCII]]</text>

Orphand symbols in line 10104: ''''

Orphand symbols in line 10131: [[tr:Amerika]]</text>

Orphand symbols in line 10192: '' ''

Orphand symbols in line 10264: ''''

Orphand symbols in line 10265: ''''

Orphand symbols in line 10266: ''''

Orphand symbols in line 10267: ''''

Orphand symbols in line 10956: [[so:Afrika]]</text>

Orphand symbols in line 11036: ''''

Orphand symbols in line 11037: ''''

Orphand symbols in line 11038: ''''

Orphand symbols in line 11051: [[sv:Austin]]</text>

Orphand symbols in line 11105: '' ''

Orphand symbols in line 11243: [[zh:动画]]</text>

Orphand symbols in line 11371: ''' '''

Orphand symbols in line 11396: '' ''

Orphand symbols in line 11464: '' ''

Orphand symbols in line 11551: [[zh:阿波罗]]</text>

Orphand symbols in line 12522: [[Category:List of Assyrians|Agassi, Andre]]</text>

Orphand symbols in line 12612: [[zh:南亚语系]]</text>

Orphand symbols in line 12643: <text xml:space="preserve">'' ''

Orphand symbols in line 12779: [[zh:闪含语系]]</text>

Orphand symbols in line 13032: [[fiu-vro:Andorra]]</text>[/src]


Wenn man mal von der Formatierung der '-Zeichen absieht, ganz klar das der Fall nicht abgedeckt ist, wenn Tags in einer Zeile mit einem XML Tag Closing liegen.

Zum Beispiel der letzte Output:
"Orphand symbols in line 13032: [[fiu-vro:Andorra]]</text>

Das </text> schließt das XML Element - aber die Tags werden dann nicht mehr korrekt hinzugefügt. Klassischer "Flüchtigkeits"-Fehler....

Wegen der Formatierung muß ich noch einmal genauer hinschauen, also '-Zeichen und die Gleichzeichen (Überschriften-Formatierung) sind auch nicht 100% bei dieser Prüfung, wenn die aktuelle Säuberung korrekt ist - aber ich würde fast mutmaßen das die Formatierung stimmt und nur der Datacheckers etwas falsch macht, lässt sich aber dank Debug Output und Zeilennummer, wie auch Rohdaten gut überprüfen....

Macht sich gerade bezahlt, die Arbeit, in ein extra "Testing"-Tool investiert zu haben...

*Nachtrag:

Noch etwas verbessert, jetzt auch mit ascii_letters Erkennung:
[src=text]=========================================================================
Reporting orphands
=========================================================================

Orphand symbols in line 477: [[zh-min-nan:Hui-thóng-tī-chú-gī]]</text>

Orphand symbols in line 695: ''''

Orphand symbols in line 968: [[zh:自閉症]]</text>

Orphand symbols in line 1187: [[uk:Альбедо]]</text>

Orphand symbols in line 1345: [[zh:阿布扎比]]</text>

Orphand symbols in line 2331: [[zh:A]]</text>

Orphand strings in line 2492: Areas/Sprawl

Orphand symbols in line 2808: [[zh:阿拉巴馬州]]</text>

Orphand symbols in line 2903: '' ''

Orphand symbols in line 2932: ''' '''

Orphand symbols in line 2961: '''' ''''

Orphand symbols in line 2965: ''''

Orphand symbols in line 2967: ''''

Orphand symbols in line 2969: ''''

Orphand symbols in line 2970: ''''

Orphand symbols in line 3030: [[zh:阿基琉斯]]</text>

Orphand symbols in line 3345: ''''

Orphand symbols in line 3358: '''' '''' ''''

Orphand symbols in line 3571: [[zh:亚伯拉罕·林肯]]</text>

Orphand symbols in line 3739: ''''

Orphand symbols in line 4011: [[zh:亚里士多德]]</text>

Orphand strings in line 4026: :a

Orphand symbols in line 4039: [[sv:An American in Paris (symfonisk dikt)]]</text>

Orphand strings in line 4239: a

Orphand symbols in line 4378: [[zh:奥斯卡金像奖]]</text>

Orphand symbols in line 4466: [[sk:Živočíchy]]</text>

Orphand strings in line 4495: sa

Orphand symbols in line 4533: [[svAI]]</text>

Orphand strings in line 4546: a

Orphand symbols in line 4730: [[sv:Altruism]]</text>

Orphand symbols in line 4743: ''''

Orphand symbols in line 4827: [[zh:李安]]</text>

Orphand symbols in line 5318: [[zh:艾茵·兰德]]</text>

Orphand strings in line 5330: ss a

Orphand symbols in line 5367: [[zh:阿兰·孔]]</text>

Orphand strings in line 5411: a

Orphand symbols in line 5478: [[de:Allan Dwan]]</text>

Orphand symbols in line 5605: [[ru:Экономика Алжира]]</text>

Orphand symbols in line 5690: :''See also :'' [[Algeria]]</text>

Orphand symbols in line 5773: ''''

Orphand symbols in line 6035: [[zh-min-nan:Algeria]]</text>

Orphand symbols in line 6200: [[Category:Lists of fictional characters|Atlas Shrugged characters]]</text>

Orphand strings in line 6214: a

Orphand symbols in line 6246: [[Category:Fictional technology|Atlas Shrugged]]</text>

Orphand symbols in line 6341: [[Category:Fictional companies|Atlas Shrugged]]</text>

Orphand symbols in line 6388: [[Category:Atlas Shrugged]]</text>

Orphand strings in line 6416: a

Orphand symbols in line 6474: ====

Orphand symbols in line 6562: ====

Orphand symbols in line 6572: ====

Orphand symbols in line 6591: [[Category:Lists of fictional things]]</text>

Orphand symbols in line 6671: [[Category:Atlas Shrugged]]</text>

Orphand symbols in line 6683: '' ''

Orphand symbols in line 6789: [[zh:阿特拉斯摆脱重负]]</text>

Orphand symbols in line 7014: [[zh:人类学]]</text>

Orphand symbols in line 7028: = s

Orphand symbols in line 7047: '''' ''''

Orphand symbols in line 7281: [[zh:考古学]]</text>

Orphand strings in line 7310: a

Orphand symbols in line 7404: [[zh:农学]]</text>

Orphand symbols in line 7550: '' ''

Orphand symbols in line 7620: '' ''

Orphand symbols in line 7778: [[zh:炼金术]]</text>

Orphand strings in line 7791: a

Orphand symbols in line 7894: [[Category:Avionics]]</text>

Orphand symbols in line 8097: ''''''

Orphand symbols in line 8254: [[fiu-vro:Austria]]</text>

Orphand symbols in line 8329: ''''

Orphand symbols in line 8337: ''''

Orphand symbols in line 8394: ''''

Orphand symbols in line 8426: ''''

Orphand symbols in line 8572: [[zh:澳大利亚]]</text>

Orphand symbols in line 8838: [[zh:美屬薩摩亞]]</text>

Orphand symbols in line 8855: ''''

Orphand symbols in line 8856: ''''

Orphand symbols in line 8876: [[zh:外星人]]</text>

Orphand strings in line 8891: a

Orphand symbols in line 8976: [[zh:天文学家]]</text>

Orphand symbols in line 9005: (''Chaos''

Orphand symbols in line 9006: (''Ammonia''

Orphand symbols in line 9007: (''Actinophrys''

Orphand symbols in line 9030: [[pl:Ameby]]</text>

Orphand symbols in line 10047: [[zh-min-nan:ASCII]]</text>

Orphand symbols in line 10104: ''''

Orphand symbols in line 10131: [[tr:Amerika]]</text>

Orphand symbols in line 10192: '' ''

Orphand symbols in line 10264: ''''

Orphand symbols in line 10265: ''''

Orphand symbols in line 10266: ''''

Orphand symbols in line 10267: ''''

Orphand symbols in line 10956: [[so:Afrika]]</text>

Orphand strings in line 10983: a

Orphand symbols in line 11036: ''''

Orphand symbols in line 11037: ''''

Orphand symbols in line 11038: ''''

Orphand symbols in line 11051: [[sv:Austin]]</text>

Orphand symbols in line 11105: '' ''

Orphand symbols in line 11243: [[zh:动画]]</text>

Orphand symbols in line 11371: ''' '''

Orphand symbols in line 11396: '' ''

Orphand symbols in line 11464: '' ''

Orphand symbols in line 11551: [[zh:阿波罗]]</text>

Orphand symbols in line 12522: [[Category:List of Assyrians|Agassi, Andre]]</text>

Orphand symbols in line 12612: [[zh:南亚语系]]</text>

Orphand symbols in line 12643: '' ''

Orphand symbols in line 12779: [[zh:闪含语系]]</text>

Orphand symbols in line 13032: [[fiu-vro:Andorra]]</text>[/src]

 

[Roin]

Ich wollte nur mal einwerfen: Wenn man vielleicht "sinnig" komprimieren will, sollte man sich mal dieses Video reinziehen.
Das könnte helfen.

https://youtu.be/JsTptu56GM8

Ich bin derzeit ja doch etwas ausgelastet aber vielleicht nehme ich mir dieses Problem ja in der Zukunft mal wieder vor.
Dann vermutlich in C++.