Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
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
Code:
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.
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
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.
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,
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...
- 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.
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.
Edit: Es funktioniert jetzt! Der Schlüssel war das Ersetzen von
Java:
int compareResult = word.compareTo(line.toString());
durch
Java:
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.
Java:
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):
Java:
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.
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.
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.
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.
Code:
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.
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.
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:
Java:
BufferedReader in = ...
PrintWriter out = ...
String line;
while((line=in.readLine())!=null)
{
out.println(line.split("\t")[spaltennummer]);
}
in.close();
out.close();
