# Suchen in grosser Datei (100+ MB)



## VVeiler (9. Okt 2005)

Hallo,

möchte in einer (sortierten) ca. 100 MB Textfile, die pro Zeile ein Wort enthält, testen ob ein Wort schon drin steht (-> Binäre Suche). Leider kann ich die File nicht in einen Array, List, etc. einlesen weil ich dann eine 


```
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
```

bekomme. 
Kann mir jemand helfen wie ich das Suchen vielleicht "offline" hinbekomme ohne die ganze file zu laden.

Vielen Dank schonmal für die Antworten.

Michael


----------



## Bleiglanz (9. Okt 2005)

einfach zeilenweise lesen OHNE die Zeilen zu speichern?

das ist aber bestimmt keine "binäre Suche"...


----------



## VVeiler (9. Okt 2005)

Bleiglanz hat gesagt.:
			
		

> das ist aber bestimmt keine "binäre Suche"...


Nein das wuerde viel zu lange dauern (ca. 10 Mio worte in der file) und das ganze muss sehr sehr oft wiederholt werden (ca 10^6 mal).

Ops: Sehe gerade das ich in "Java 3d und co" gepostet habe... gehoert vielleicht nicht dahin, sorry.

Aber vielleicht kann mir ja trotzdem jem. eine Lösung vorschlagen.

thx Michael


----------



## Bleiglanz (9. Okt 2005)

hab ich das richtig verstanden

du hast eine 100MB Textdatei, mit ca. 10 Millionen Zeilen wobei in jeder Zeile ein Wort steht? Und die Zeilen sind nicht sortiert?

und jetzt willst du 10^6=eine Million mal da drin nach einem Wort suchen???

im Ernst? 

Wenn die 10^6 Suchwörter schon bekannt sind, dann würd ich die in den Speicher einlesen, dann zeilenweise durch das File gehen und jedes gefundene Wort aus der Liste streichen, die die übrig bleiben sind dann die nicht gefundenen


----------



## Beni (9. Okt 2005)

Wenn du dir sicher sein kannst, dass das File nicht noch grösser wird, versuch mal mit "-Xmx" den Speicher zu erhöhen.
z.B. "java -Xmx512m dasProgramm" um 512 MB zu erlauben.

Vielleicht lohnt sich ja auch eine Datenbank bei solch einer Menge von Daten.


----------



## VVeiler (9. Okt 2005)

Bleiglanz hat gesagt.:
			
		

> hab ich das richtig verstanden
> 
> du hast eine 100MB Textdatei, mit ca. 10 Millionen Zeilen wobei in jeder Zeile ein Wort steht? Und die Zeilen sind nicht sortiert?


Die datei ist bereits sortiert (siehe ersten Post von mir)



			
				Bleiglanz hat gesagt.:
			
		

> und jetzt willst du 10^6=eine Million mal da drin nach einem Wort suchen???
> 
> im Ernst?



Ja. Da die Datei ja schon sortiert ist läßt sich diese ja mit biärer suche in O(log n) durchsuchen, bei meinen 10Mio Worten wären das pro Suchlauf im worst case nur log2(10.000.000) < 24.



			
				Bleiglanz hat gesagt.:
			
		

> Wenn die 10^6 Suchwörter schon bekannt sind, dann würd ich die in den Speicher einlesen,


Geht nicht! Ist zu gross: 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Aber ich werde das das Beni vorgeschlagen hat mit *java -Xmx512m* ausprobieren.

Trotzdem danke.


----------



## Bleiglanz (9. Okt 2005)

das Problem ist die Ablage in einem File

da du keinen wahlfreien Zugriff hast (auch RandomAccessFile hilft nix, weil man die "Positionen" nicht kennt) bleibt dir wohl wirklich nichts anderes übrig als alles in den Speicher zu holen...

100 MB als Strings => dürfte 200MB RAM verbrauchen (wegen char...)


----------



## Mag1c (9. Okt 2005)

Hi,

- benutze den MappedByteBuffer. Das dürfte schneller sein, als alles auf herkömmlichen Weg in den Speicher zu laden.

- falls sich die Datei selten oder garnicht ändert, erstelle einen Index (1. oder 1.+2. Buchstabe oder so). Das dürfte die Suche erheblich beschleunigen.

Gruß
Mag1c


----------



## Bleiglanz (10. Okt 2005)

Mag1c hat gesagt.:
			
		

> Hi,
> - benutze den MappedByteBuffer. Das dürfte schneller sein, als alles auf herkömmlichen Weg in den Speicher zu laden.


Zeilenenden und das Encoding? Achtung!


----------



## kirdie (5. Nov 2009)

Ich habe das selbe Problem und werde in den nächsten Tagen mal daran arbeiten.
Wenn dabei was herauskommt, werde ich es hier posten.
Meine Idee bis jetzt:

- man braucht relativen low level - Zugriff auf die Datei, in dem man spezifizieren kann "lies ein paar bytes ab byte x"
(RandomAccessFile klingt ja ganz gut, dass seh ich mir mal an)

Der Algorithmus, den ich mir vorstelle:
- führe die binäre Suche nicht auf den Zeilennummern sondern auf der Dateigröße auf
1. setze pos = mitte der datei
2. lese solange bytes/zeichen ein, bis ein zeilenumbruch kommt
3. vergleiche das Wort mit dem Zielwort, bestimme daraus die neue Position oder gebe gefunden zurück bei Übereinstimmung
4. gehe zu 1., falls der Suchbereich noch >0 ist
5. Ende

P.S.:
Später kann man da ja noch Spielereien wie einen Index Zeilennummer->Position für jede n-te Zeile benutzen, um noch einen leichten Geschwindigkeitsschub zu erreichen aber an der Komplexitätsklasse ändert das ja nichts.


----------



## kirdie (5. Nov 2009)

Edit: Es funktioniert jetzt! Der Schlüssel war das Ersetzen von 


```
int compareResult = word.compareTo(line.toString());
```
durch

```
int compareResult = word.compareToIgnoreCase(line.toString());
```

Der Befehl "sort" von Linux ignoriert beim Sortieren also Groß- und Kleinschreibung.

Zur Geschwindigkeit: Auf meinem IBM T42 Laptop mit 1,8 GHz bei einer Eingabedatei von 37MB (was viel größeres habe ich gerade nicht da) liegt die Zeit bei 500 ms pro 1000 Suchen. Bei 100 MB dürften es (da Komplexität log n) also ca 1000-1500 ms sein, für eine Million Suchen also ca. 20 Minuten.
Aber mit einem dual core lässt sich das sicher noch beschleunigen und das mit dem in den Speicher lesen ist sicher auch eine gute Alternative.


```
import java.io.IOException;
import java.io.RandomAccessFile;

public class BinarySearchTextFile
{
	public static boolean contains(RandomAccessFile in,String word) throws IOException
	{
		in.seek(0);
		boolean found = false;
		long lowerBound = 0;
		long upperBound = in.length()-2;
		do
		{
			long pos = (lowerBound+upperBound)>>1; //start in the middle 

			in.seek(pos);
			char c;
			if(pos>0) do {c=(char)in.readByte();} while(c!='\n');

			StringBuffer line = new StringBuffer();
			while((c=(char)in.readByte())!='\n'&&c!='\r')
				line.append(c); 
			int compareResult = word.compareToIgnoreCase(line.toString());
			if(compareResult==0) {found=true;break;}
			if(compareResult<0) upperBound = pos-1;
			//attention here. because \n is needed to recognize the next word, we don't go +1 here
			//the file pointer already points on the next to-read byte
			if(compareResult>0) lowerBound = in.getFilePointer();
			if(lowerBound>upperBound) {found=false;break;}

		} while(true);
		return found;
	}
	
	public static boolean contains(String fileName,String word) throws IOException
	{
		RandomAccessFile in = new RandomAccessFile(fileName, "r"); // open in read only mode
		boolean isContained  = contains(in,word); 
		in.close();
		return isContained;
	}

	public static void main(String[] args) throws IOException
	{
		//String fileName = "input/test/sortedwords.txt";
		String fileName = "input/wortschatz/de_words_all_sorted.txt"; // 37 MB text file
		RandomAccessFile in = new RandomAccessFile(fileName, "r");
		String[] searchWords = {"Abraham","Giraffe","Moses"};
		//StopWatch watch = new StopWatch();
		//watch.start();
		final int repetitions = 1000;
		for(int i=0;i<repetitions/searchWords.length;i++)
			for(String searchWord : searchWords)
			{
				boolean isContained = contains(in,searchWord);
			}
		//System.out.println(repetitions+" repetitions");
		//System.out.println(watch);
		//System.out.println("Looking for "+searchWord+": "+contains(fileName,searchWord));
	}	
}
```

Anmerkungen:
- nur für Linux (\n) geschrieben und getestet, das Windowsformat mache ich evtl. später noch (an einer Stelle ist das \r aber schon drin aber ich glaube das reicht noch nicht)
- es muss eine Leerzeile am Ende der Datei sein sonst könnte es evtl. abstürzen wenn das gesuchte Wort das allerletzte ist oder dahinterliegt
- ist also erstmal ein Prototyp fürs Prinzip ohne es erstmal zu kompliziert zu machen, da kommt aber noch mehr

Es funktioniert bereits mit einem kleinen Testcase, der so aussieht (die Datei sortedwords.txt):

```
Abraham
Bangladesh
Cemetary
Dorothy
Elephant
Fungus
Giraffe
```

Ich habe es ausserdem mal mit einer über 30 MB großen Textdatei (Liste aller deutschen Wörter) probiert. Damit ging es allerdings leider nicht. Ich habe den Verdacht, dass die Sortierung von Java anders ist als die vom Linuxbefehl "sort" (ich habe "sort datei > datei_sortiert" gemacht). Vielleicht ist ja String.compareTo() lexikographisch und sort funktioniert über die Reihenfolge der ASCII-Zeichen oder so, dem gehe ich auch noch nach.


----------



## Gast (6. Nov 2009)

Ich würde darüber nachdenken, die Datei schlicht in kleine Teile zu zerlegen. Erstelle aus der großen Datei mehrere kleinere, die garantiert in den Speicher passen. Das ganze kann man auch automatisch on the fly erledigen. So kannst du im Grunde im Speicher suchen und musst "nur" noch swappen, wenn der Suchbereich gewechselt werden muss.


----------



## Guybrush Threepwood (6. Nov 2009)

So spontan habe ich das Gefühl, das man so etwas einer Datenbank überlassen sollte. Man kann ja beispielsweise mit Derby eine lokale dem Programm mitgeben.


----------



## JohannisderKaeufer (6. Nov 2009)

Mal abgesehen von dem Memoryproblem.

Warum nutzst du keine "Vernünftigere" Datenstruktur?

Auto
Autobahn
Autohändler
Autoverkäufer
Automat
Automatenhändler
Autonom
Autor

Fällt dir war auf?

Genau, fängt alles mit Auto an.

(ist ein enthaltenes Wort)
bahn
händler
verkäufer
mat
matenhändler
nom
r

Das wäre die Datenmenge, wenn man Auto wegläßt.

Meine Idee wäre das ganze gedöhns in eine Baumstruktur einzulesen.

```
A -> u -> t -> o (ist ein enthaltenes Wort)
                       b -> a -> h -> n (ist ein enthaltenes Wort)
                       h -> ä -> n -> d -> l -> e -> r (...)
                       ...
                       m -> a -> t (...)
                                        -> e -> n  (...)
                                                      -> h -> ä -> n -> d -> l -> e -> r (...)
...
```

Die Suche wäre dann nicht mehr binär, sie wäre O(n) (wenn man davon ausgeht das die suche zwischen 26 Buchstaben konstant ist). Wobei n die länge des Wortes wäre.


----------



## bygones (6. Nov 2009)

Guybrush Threepwood hat gesagt.:


> So spontan habe ich das Gefühl, das man so etwas einer Datenbank überlassen sollte. Man kann ja beispielsweise mit Derby eine lokale dem Programm mitgeben.



oder apache lucene nutzen


----------



## JohannisderKaeufer (6. Nov 2009)

@Kirdie

hab mal eine eigene Implementierung geschrieben.

Wie hast du eine 37 MB Textdatei erzeugt (linux), hab leider nur mit 4 MB testen können.
Zeilenumbruch und Sortierung sind hierbei egal.

Mich würde es gerne interessieren wie das ganze mit 37 oder 100 MB ausschaut.

Bei 4 MB sind es ohne "Einlesen", da das noch locker in den RAM paßt. 0 - 4 ms pro 1000 Suchanfragen.


----------



## kirdie (12. Nov 2009)

Eine gute Datei zum Testen ist die Deutsche Wortliste des Wortschatzprojektes.

Wortschatz - International Portal

Hier von den Plaintextfiles bei German "3M" auswählen, dann hast du eine Liste mit 3 Millionen deutschen Wörtern 
Ist allerdings eine csv-Tabelle mit meheren Spalten, musst also auf Linux vorher noch "cat datei | cut -f<spaltennummer> > neuedatei" machen bzw. unter Windows ein Javaprogramm schreiben, dass dir die eine Spalte extrahiert, so a la:

```
BufferedReader in = ...
PrintWriter out = ...
String line;
while((line=in.readLine())!=null)
{
 out.println(line.split("\t")[spaltennummer]);
}
in.close();
out.close();
```


----------

