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



## eyeless (30. Sep 2007)

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:

```
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 (
	
	
	
	





```
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 (30. Sep 2007)

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


----------



## eyeless (30. Sep 2007)

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 (30. Sep 2007)

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

```
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 (30. Sep 2007)

Ä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 (30. Sep 2007)

@Marco13: danke für deine Antwort. du meinst also ungefähr so:

```
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 
	
	
	
	





```
while(sb.indexOf(key,oi) > -1) {
               //nix
            }
```
 durchlaufen lasse, dauert es auch ewiglich ...

komik!

mfg, eyeless


----------



## Marco13 (30. Sep 2007)

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

```
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

```
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 (1. Okt 2007)

@Maro13: mit ein paar änderungen funktioniert das so jezt ganz gut, danke für deine Hilfe.
hier das resultat: 
	
	
	
	





```
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 (1. Okt 2007)

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

```
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

```
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 (1. Okt 2007)

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


----------

