Perfomante Suche in grosser Datei

[Grasstampfer]

HI,

ich bin auf der suche nach einer performanten (im sinne von geschwindigkeit) Suchmoeglichkeit in grossen dateien.

Ich habe folgendes:

Eine 1.5Gb grosse tab-delimited text datei in der einfache Strings stehen ala

ID1_1   ID1_2  ID1_3  ID1_4 .... 
ID2_1   ID2_2  ID2_3  ID2_4 .... 
ID3_1   ID3_2  ID3_3  ID3_4 ....

nun will ich eine suche implementieren die eine beliebige ID bekommt und die entsprechende Zeile der Datei ausgibt.

Die simpelste Loesung ist zeilenweise die datei einzulesen und ueber contains abzufragen, was aber schon 2min dauern kann.

Eine idee die ich hatte war das file in x files zu splitten (nach z.b. 100000 zeilen) und fuer jede dieser datei einen eigenen Thread zu starten, der auch wiederum zeilenweise seine datei durchliest. Findet ein Thread den Suchbegriff, so stoppen alle anderen und die zeile wird zurueckgegeben.

Nun ist es aber so, je mehr threads ich starte, desto laenger braucht er a) das ganze System zu starten (bis alle threads laufen) und b) die einzelenen leseoperationen scheinen laenger zu dauern. Je weniger Threads ich habe desto groesser sind die dateien und ich komme wieder an loesung 1 ran.

und auch hier ist es so, dass wenn der suchbegriff weit unten in irgendeiner datei steckt das suchen 20-30 sekunden dauern kann.

Nun meine Frage - muss ich damit leben oder hat jemand eine tolle Idee, wie ich eine performantere suche implementieren kann ? bin fuer jeden vorschlag offen

Ich kann ohne probleme das file vorher prozessieren, die suche selber sollte nur so schnell wie moeglich sein.

Eine DB zu nutzen waere der letzte ausweg ....

danke euch vielmals !
Gras

 

[Wildcard]

Nimm Lucene. Damit lässt du dir einen Index erstellen, die eigentlich Suche dauert Bruchteile von Sekunden.

 

[DocMcFly]

Eine DB zu nutzen waere der letzte ausweg ....

Auch wenn das der letzte Ausweg ist... es muss ja nicht immer ein großes DB-System sein: hSqlDb oder H2 ist Datenbanken die nur aus einem Treiber bestehen und auch recht flott arbeiten. - Wenn man die Daten wo möglich später noch bearbeiten will - ist eine DB vielleicht doch von Vorteil...

Mein ja bloß... Gruß Clemens

 

[Grasstampfer]

das mit der DB hat logistische gruende - aber danke nochmal fuer den hinweis.

da lucene gerade seinen index baut haette ich noch ne kurze frage dazu - vielleicht liest das eine hier kurz der dazu was sagen kann.

ich indiziere gerade jede zeile - die andere moeglichkeit waere die einzelenen eintraege (als zb ID1_1, ID1_3), also nicht die komplette zeile sondern die ids, nach denen ich dann auch suchen werde.

was ist besser vor allem unter dem gesichts punkt dass es bis zu 7 eintraege pro zeile sind die interessant sein koennten.

Danke euch mal wieder !

 

[Wildcard]

Du solltest indizieren was für dich interessante Informationen sind. Meistens sind zum Beispiel Wörter interessant bei regulären Textsuchen, Zeilen machen für mein empfinden eigentlich keinen Sinn. In deinem Fall also tatsächlich die IDs aus den Zeilen extrahieren.
Falls die Dateien auch von ausserhalb manipuliert werden und du denn index immer aktuell halten willst, würde ich dir noch die Kombination mit JNotify ans Herz legen. JNotify sagt dir bescheid sobald die Datei verändert wird, dann lässt du Lucene nochmal indizieren und schon ist alles wieder aktuell.

 

[Grasstampfer]

danke dir wildcard - das habe ich mir schon mittlerweilen selbst erschlossen dass es sinnvoll ist das zu indizieren was ich suchen will. und da man ja dem dokument auch eintraege (z.b. die zeile) geben kann ohne es zu indizieren erhalte ich ja noch sehr gut die kompletten informationen.

Die Datei wird nicht von aussen manipuliert, sie wird in einem update prozess einmal die woche geupdated, da lasse ich dann Lucene erneut drueber laufen.

Danke dir vielmals !

 

[Grasstampfer]

mhm laut lucene faq

Instead of indexing many small text fields, aggregate the text into a single "contents" field and index only that (you can still store the other fields).

somit ist es wahrscheinlich sinnvoll die relevanten IDs zusamenzufassen und diese zu indizieren, jedoch nicht die gesamte zeile.

hab mich momentan fuer diese loesung entschieden

IndexWriter index = new IndexWriter( "/home/data/iproclass/lucene2", new StandardAnalyzer(), true );
        // IndexWriter index = new IndexWriter( directory, new StandardAnalyzer(), false );
        BufferedReader reader = new BufferedReader( new FileReader( "/home/data/iproclass/iproclass.tb" ) );

        String line;
        Document document;
        StringBuilder idBuilder;
        while ( ( line = reader.readLine() ) != null ) {
            String[] split = line.split( "\t" );
            idBuilder = new StringBuilder();
            document = new Document();
            idBuilder.append( split[ 0 ] ).append( " " );
            idBuilder.append( split[ 1 ] ).append( " " );
            idBuilder.append( split[ 3 ] ).append( " " );
            idBuilder.append( split[ 4 ] ).append( " " );
            document.add( new Field( "content", idBuilder.toString(), Field.Store.NO, Field.Index.TOKENIZED ) );
            document.add( new Field( "line", line, Field.Store.COMPRESS, Field.Index.NO ) );
            index.addDocument( document );
        }
        index.optimize();
        index.close();

die relevanten IDs werden zusammengefuegt und nicht gespeichert, aber indiziert. Die komplette zeile die dann relevant ist dafuer gespeichert aber nicht indiziert.

Somit sollte ich dann ueber die IDs schnell suchen koennen und dann ueber 'line' die gesamte zeile erhalten.

ist das richtig durchdacht ?

Danke