String.replace für (sehr) großen Text

Status
Nicht offen für weitere Antworten.

eyeless

Mitglied
Servus!

Folgendes: ich möchte einen Text, ca 300 seiten, ergo ca. 490000 zeichen kodieren, nur monogramme.
das alphabet wurde kodiert und steht bereit.
nun wollte ich die einzelnen zeichen im Text mittels String.replace mit deren kodierungen ersetzen.
das so:
Code:
for(int i=0;i<code.length;i++) {
            key =  ((ArrayList<Entry<String,Double>>) list.get(1)).get(i).getKey();
            codeTxt = codeTxt.replace(((CharSequence) key).toString(),code[i]);
        }
wobei in code das kodierte ABC ind in codeTxt zuanfangs der orignatext steht.
überschlagen ergibt der fertig codierte text (textlänge * mittlereKodewortLänge(=4,758231988319831) =) 2333456 zeichen .. sind aber auch nur ca. 4.45 mb (bei 2byt/zeichen, string halt) .

das Problem: es dauert exponentiell länger .. is klar, weil der text exponentiell anwäxt, aber das ist verkraftbar
das wirkliche problem: trotz -Xmx256m bekomme ich bei ca. 80% nen outofmemoryerror: java heap size .. der speicher ist bei ca 40% noch bei 13mb, dann expo mehr .. wiso das???
wenn ich-Xmx512m mache, bleibt alles einfach irgendwann stehen

kann mir da jemand helfen und sagen, wiso String.replace so schnell speicher anhäuft?
gibt es eine schnelle alternative, meine (
Code:
StringBuffer sb=new StringBuffer(origTxt);
oi=0;
while(sb.indexOf(key,oi) > -1) {
                sb = sb.replace(sb.indexOf(key,oi),sb.indexOf(key,oi)+key.length(),code[i]);
                oi = oi + code[i].length();
            }
) ist kotzlangsam, verständlich.

help!

mfg, eyeless
 

Wildcard

Top Contributor
Welchen grund hast du diese riesen Datenmenge auf einmal in den Speicher zu packen?
Nimm einen PipedStream oder sowas.
 

eyeless

Mitglied
der grund ist, dass ich später auch noch bigramme, trigramme bis septogramme berücksichtigen und ersetzen muss, in wenn ich den text aufteile, kann es sein, dass ich ihne genau an einem sehr oft vorkommendem n-gramm trenne, das dann nicht alssolchen koderit werden kann.

sorry, hat ich vergessen, zu erwähnen

mfg, eyeless
 

Marco13

Top Contributor
Soweit ich weiß verwenden die Matching-Algortihmen häufig Backtracking - und das IST nunmal langsam (exponentielle Laufzeit). Warum der Text selbst exponentiell länger werden soll, hab ich aber nicht gerafft....
länge = textlänge * mittlereKodewortLänge
ist erstmal nicht exponentiell, außer, wenn die Kodierten Worte wieder die Keys enhalten können (!?)

Falls ich da jetzt nicht irgendwas falsch verstanden habe, könnte man das ja auch ohne Regex machen. Sinngemäß sowas wie
Code:
String input = ....
String output = ""; //(eigentlich StringBuffer...)
int currentIndex = 0;
while (...)
{
    int occurance = input.indexOf(key, currentIndex);
    output += input.substring(currentIndex, occurance);
    output += codeFor(key);
    currentIndex += key.length();
}
Also den String von vorne nach hinten nach dem Auftreten der keys durchsuchen. Jedes mal, wenn man einen Key gefunden hat, hängt man den Teil, der den Key NICHT enthielt, unverändert an den output, hängt dann den code für den jeweiligen Key dazu, und sucht dann nach dem nächsten Auftreten eines Keys.

Hm. Bin aber nicht 100% sicher, ob damit das geht, was du vorhast. Spätestens bei n-grammen mit n>1 könnte das etwas komplizierter werden. Jedenfalls würde man sich das (extem aufwändige) Pattern matching damit sparen...
 

Marco13

Top Contributor
Äh - *nochmaldrüberguck* ja, das ist "eigentlich" ziemlich genau das, was du in deiner "kotzlangsamen" Methode machst. Aber ohne sb.replace. Wenn in einem StringBuffer das erste Zeichen durch einen 2 Zeichen langen String ersetzt werden muß, muss der gesamte Buffer umkopiert werden. Das kann man sich ersparen, wenn man einfach den "neuen" String in einen NEUEN StingBuffer schreibt....
 

eyeless

Mitglied
@Marco13: danke für deine Antwort. du meinst also ungefähr so:
Code:
StringBuffer sb = new StringBuffer(codeTxt);
StringBuffer tb;
for(int i=0;i<code.length;i++) {
            key =  ((ArrayList<Entry<String,Double>>) list.get(1)).get(i).getKey();
            oi = 0;
            while(sb.indexOf(key,oi) > -1) {
                tb = sb.replace(sb.indexOf(key,oi),sb.indexOf(key,oi)+key.length(),code[i]);
                sb = tb;
                tb = null;
                oi = oi + code[i].length();
            }
        }

hab ich auch schon dran gedacht, hat aber nichts gebracht.

ABER: mein verdacht: es liegt am (String/StringBuffer).indexOf(..) .. denn wenn ich die Schleife nur mit
Code:
 while(sb.indexOf(key,oi) > -1) {
               //nix
            }
durchlaufen lasse, dauert es auch ewiglich ...

komik!

mfg, eyeless
 

Marco13

Top Contributor
Dass du davon ausgehst, dass das indexOf lange dauert, und es trotzdem DREI mal machst, obwohl es nur einmal gemacht werden muss, wundert mich etwas. Was du da mit dem tb machst, wundert mich auch, weil ich ja extra gesagt hatte, dass man es OHNE sb.replace machen kann/sollte. Dass es mit
Code:
while(sb.indexOf(key,oi) > -1) {
               //nix
            }
"ewiglich" dauert, wundert mich aber NICHT, weil das in diesem Fall (solange 'oi' nicht geändert wird) wohl eine Endlosschleife ist :wink:

Was ich eigentlich meinte war wohl etwa sowas
Code:
String sb = codeTxt;
char input[] = sb.toCharArray(); // vermeidet die vielen "substring"-Aufrufe!
StringBuffer tb = new StringBuffer(codeTxt.length() * 5); // Gleich genug Speicher reservieren - erspart das Umkopieren!
for(int i=0;i<code.length;i++) 
{
    key =  ((ArrayList<Entry<String,Double>>) list.get(1)).get(i).getKey();
    oi = 0;
    int index = sb.indexOf(key,oi); 
    while(index > -1) 
    {
        tb.append(input, oi, index-oi);
        tb.append(code[i]);
        oi += key.length();
        index = sb.indexOf(key,oi);
    }
    tb.append(input, oi, input.length-oi);
}

Ist jetzt noch ungetestet. Wenn es immernoch Probleme gibt, sag bescheid, dann kann ich es heute abend oder morgen mal richtig testen.
 

eyeless

Mitglied
@Maro13: mit ein paar änderungen funktioniert das so jezt ganz gut, danke für deine Hilfe.
hier das resultat:
Code:
        char[] input = new char[Math.round(codeTxt.length() * (float) mWL) + 1];
        StringBuilder tb = new StringBuilder(Math.round(codeTxt.length() * (float) mWL) + 1);
        int oi;
        for(int i=0;i<code.length;i++) {
            key =  ((ArrayList<Entry<String,Double>>) list.get(1)).get(i).getKey();
            oi = 0;
            input = codeTxt.toCharArray();
            index = codeTxt.indexOf(key,oi);
            tb.delete(0,tb.length());
            while(index > -1) {
                tb.append(input,oi,index-oi);
                tb.append(code[i]);
                oi = key.length() + index;
                index = codeTxt.indexOf(key,oi);
            }
            tb.append(input,oi,input.length-oi);
            codeTxt = tb.toString();
        }

PS: noch eine ganz andere Frage: gibt es eine einfache möglichkeit, diesen, nun nur aus bits bestehenden kodierten text nun auch bitweise in eine Datei zu schreiben oder muss ich immer 8 bit zu einem Byte zusammenfassen? und was mach ich dann mit den letzen meist < 8 bits? kann ich ja in kein byte packen.. ?

mfg, eyeless
 

Marco13

Top Contributor
Höm - was genau du meinst, ist mir nicht ganz klar. Es gibt eigentlich keine einzlenen Bits. Ein byte ist eigentlich das mindeste. Man kann den Text binär rausschreiben, oder menschenlesbar (ASCII), aber bin nicht sicher, ob du das meintest...

EDIT: Das folgende ist falsch....


Übrigens sollte es reichen, statt
Code:
char[] input = new char[Math.round(codeTxt.length() * (float) mWL) + 1];
...
        for(int i=0;i<code.length;i++) {
...
            input = codeTxt.toCharArray();
den input nur EIN mal zu holen
Code:
char[] input = codeTxt.toCharArray(); // Das nur EIN mal machen!
...
        for(int i=0;i<code.length;i++) {
            ...
            key =  ((ArrayList<Entry<String,Double>>) list.get(1)).get(i).getKey();

... weil die Schleife ja mit "codeTxt = tb.toString()" endet - aber muss sie das wirklich???
 

eyeless

Mitglied
ja, das muss sie wirklich, da ich ja sonst bei den näxten durchläufen wieder nur den originaltext kodiere, und nicht schon den teilweise kodierten text, der ja aufgrund der tatsache, dass die kodierten zeichen länger sein können/müssten also die orignalzeichen, auch länger ist und somit die indexOf geschichte nich mehr so hinhaut .. hab ich leidlig erfahren ^^

die sache mit dem bit in datei hat sich auch erledigt .. bin ebenfalls zu der eigentlich klaren erkenntnis gekommen, das man nur bytes schreiben kann und habe mir inzwischen ne BitOutStream ud ne BitInStream klasse zusammen gestammelt, die das so leidlig erledigt.

somit hat sich dieses thema soweit erledigt. vielen.
(es sei denn, jemand kann mit sagen, wie ich rauskriege, ob es sich lohn, ein bestimmtes n-gramm mit in die kodierung aufzunehmen oder nicht, abe das ist eher ein mathematisches problem, da werd ich noch drann nagen ^^)

mfg, eyeless
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
P String.replace() funktioniert nicht? Allgemeine Java-Themen 3
Xge Replace x Zeichen aus String Allgemeine Java-Themen 2
K String.replace funktioniert nicht Allgemeine Java-Themen 3
L String Replace mit Regulärem Ausdruck Allgemeine Java-Themen 2
E String replace java 1.4 Allgemeine Java-Themen 4
G Mehrmals replace() auf langem String, zu speicherintensiv Allgemeine Java-Themen 10
C Problem mit String.replace(CharSequence, CharSequence) Allgemeine Java-Themen 3
C String replace Allgemeine Java-Themen 8
OnDemand Java String in Hashmap als Key NULL Allgemeine Java-Themen 27
JAnruVA Datentypen Berechneten String-Wert in Double umwandeln um weiter zu rechnen Allgemeine Java-Themen 7
M String Allgemeine Java-Themen 10
M Suche nach String mit unbekannten characters Allgemeine Java-Themen 53
kodela String kann nicht zu Pfad konvertiert werden Allgemeine Java-Themen 16
melaniemueller Einzelne Zeile aus einer txt Datei in einem String speichern Allgemeine Java-Themen 12
E Objekte in einen String packen und wieder laden Allgemeine Java-Themen 5
M Map<String,String>funktioniert nicht richtig Allgemeine Java-Themen 4
O String in Long Hexerdezimal umwandel Allgemeine Java-Themen 14
N String vergleichen. Allgemeine Java-Themen 27
SaschaMeyer Arbeitet String.split falsch? Allgemeine Java-Themen 4
M Switches ohne String Allgemeine Java-Themen 18
AmsananKING String Iteration Allgemeine Java-Themen 5
S Shuffle String aus if-clause Allgemeine Java-Themen 11
Besset Variablen Ist String = "" + int inordnung? Allgemeine Java-Themen 6
M Map <Long, String> zu Map<String, Long> Allgemeine Java-Themen 9
S String Encoding Verständnisproblem Allgemeine Java-Themen 22
N Prüfen, ob ein String 2x das selbe Zeichen hat Allgemeine Java-Themen 10
SaftigMelo Bug Fixen von String-spliten Allgemeine Java-Themen 8
Monokuma String List nach Zahlen und Worten sortieren Allgemeine Java-Themen 9
Kingamadeus2000 Alle mehrfach vorkommenden Buchstaben rekursiv aus einem String entfernen. Allgemeine Java-Themen 6
YohnsonM String - Aufteilung und Nutzung einzelner Chars Allgemeine Java-Themen 7
O Formatierte String ausgabe bei vier Variablen in einer Zeile Allgemeine Java-Themen 1
S String umbenennen: wie? Allgemeine Java-Themen 4
x46 String Format Fehler Allgemeine Java-Themen 2
S ISO 8601 -> getter / setter String Allgemeine Java-Themen 3
L String zu repräsentativen Wert Allgemeine Java-Themen 0
H Array mit dem Datentype String[] initializieren Allgemeine Java-Themen 7
L ArrayList mit String Arrays in ein Array umwandeln Allgemeine Java-Themen 1
L regex ganzer string? Allgemeine Java-Themen 2
L Ist ein string ein erlaubter variabel name? Allgemeine Java-Themen 2
Z JNA Cpp-DLL String Verwendung Allgemeine Java-Themen 2
A String auf Zahlen überprüfen Allgemeine Java-Themen 5
N String Array Eingabe Allgemeine Java-Themen 6
MiMa Datum von String zu LocalDateTime Allgemeine Java-Themen 8
W String -> byte[] -> String - Sieht jemand was ich nicht sehe? Allgemeine Java-Themen 10
R char aus String entfernen Allgemeine Java-Themen 10
LimDul Mittels Streams aus Strings A B C den String A, B und C machen Allgemeine Java-Themen 12
M Programm erkennt String aus .txt Datei nicht Allgemeine Java-Themen 3
P einen public <Optinal String> in einer anderen Klasse mit einem Int vergleichen Allgemeine Java-Themen 2
S Ini Text aus String parsen Allgemeine Java-Themen 1
T String-Manipulation beim Ablauf in Eclipse und als JAR-File Allgemeine Java-Themen 8
M String lässt sich nicht Zusammenfügen Allgemeine Java-Themen 10
Drachenbauer Wie kann ich das Wort "concrete" in einem String durch ein anderes Wort ersetzen lassen? Allgemeine Java-Themen 5
R Schlüsselworte "Throw new exception" gibt nicht den String als Fehlermeldung aus Allgemeine Java-Themen 2
R Variablen String mit split-Funktion aufteilen Allgemeine Java-Themen 7
F Datei in String-Array einlesen Allgemeine Java-Themen 8
S Marker aus String ermitteln Allgemeine Java-Themen 5
T Objekt mit String und Int aus TxT Datei erstellen Allgemeine Java-Themen 23
M Bei String.format ein Komma statt einem Punkt ausgeben lassen Allgemeine Java-Themen 1
S MSSQL Exception & Connection String Allgemeine Java-Themen 19
B Bei Email: FW / AW... - Hilfe bei String suche Allgemeine Java-Themen 21
J String - Vergleiche Allgemeine Java-Themen 7
K Aus String zwei Jahreszahlen auslesen Allgemeine Java-Themen 18
Drachenbauer Wie kann eine vorgegebene Farbe über einen String erkannt werden? Allgemeine Java-Themen 11
G CSV in String Allgemeine Java-Themen 7
P String-Verschlüsselung - Frage zur Sicherheit Allgemeine Java-Themen 21
K Methodenaufruf mit String / String zu Objekt konvertieren Allgemeine Java-Themen 8
D Erste Schritte Fehler mit negativen und 0 Zahlen im String Allgemeine Java-Themen 6
coolian warum bekomme ich ein string index out of bounds exception Allgemeine Java-Themen 17
F In String 2 Buchstaben vertauschen Allgemeine Java-Themen 2
J Class Decompile als String (Procyon) Allgemeine Java-Themen 2
I Datentypen String in class sicher verwahren Allgemeine Java-Themen 17
J Falls der String ein "X" beinhaltet Allgemeine Java-Themen 2
T String mehrere Worte Allgemeine Java-Themen 2
D String Groß-/Kleinschreibung Allgemeine Java-Themen 2
D String und Klassenvariable Allgemeine Java-Themen 6
Aruetiise Funktion(y = mx+n) in String speichern und berechnen Allgemeine Java-Themen 9
C String in Objektnamen umwandeln Allgemeine Java-Themen 3
E Variablen Aus .txt ausgelesener string mit if() überprüfen? Allgemeine Java-Themen 2
L String-Schema-Aufspaltung Allgemeine Java-Themen 2
E String in Zahl umwandeln, ohne Befehl Integer.parseInt Allgemeine Java-Themen 3
L String splitten und multiplizeren Allgemeine Java-Themen 10
G String mit umbekannter länge splitten. Allgemeine Java-Themen 2
S Einzigartigen String in Datenbank finden und löschen Allgemeine Java-Themen 23
A Byte zu String Allgemeine Java-Themen 4
B Von String zu <Objekt> ||Speichern/Laden Allgemeine Java-Themen 17
T Komplexitätsoptimierung String vergleich Allgemeine Java-Themen 4
heinz ketchup String im JLabel ausgeben und erneuern Allgemeine Java-Themen 6
S Input/Output Beste Möglichkeit einen String in einen Datei zu Schreiben Allgemeine Java-Themen 2
V Eingegeben String Splitten und in Integer umwandeln Allgemeine Java-Themen 2
L Decrypt String Allgemeine Java-Themen 1
X Variablen AtmicLong größer als String ? Allgemeine Java-Themen 4
S String literal und Referenzvariablen Allgemeine Java-Themen 6
J Datentypen Absätze mit String im Word Dokument Allgemeine Java-Themen 3
D "Paste" String doppelt Allgemeine Java-Themen 14
E String Frage Allgemeine Java-Themen 9
T String aus While Schleife für ganze Klasse sichtbar machen Allgemeine Java-Themen 5
D JSON to String Allgemeine Java-Themen 31
M String automatisch in nächste Zeile umbrechen (Graphics) Allgemeine Java-Themen 6
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
T Swing Font String Pixellänge Allgemeine Java-Themen 1

Ähnliche Java Themen

Neue Themen


Oben