Textindexierungs Algorhitmen

the_alien

Hi

Ich suche einen Algorhitmus um eine Textdatei zu indexieren. Alles was ich wissen muss ist, wo in einer Datei ein "P" alleine in einer Zeile steht. Bisher gehe ich die Datei zeilenweise durch und brauche ca 50 Sekunden bei einer 8 MB Datei. Da die Dateien aber mehrere GB groß werden können fällt diese Methode komplett raus. Jetzt suche ich halt nach Algorithmen die das Indexieren schneller machen könnten.

Danke.

Jester

Da wirst Du nicht viel machen können. Wenn theoretisch jede Zeile in Frage kommt, dann wirst Du wohl auch jede anschauen müssen.

Sgt. Nukem

Jester schrieb:

Da wirst Du nicht viel machen können. Wenn theoretisch jede Zeile in Frage kommt, dann wirst Du wohl auch jede anschauen müssen.

Das wollte ich auch gerade sagen. Also: ACK

Wenn du nicht mehr Informationen über den zu durchsuchenden Text hast, wirst du wahrscheinlich den Algorithmus nicht verbessern können. Aber 50 Sekunden für lächerliche 8 MB ?? Liest du jedes Byte einzeln von der Platte?

Bashar

Du kannst die Datei auch zeichenweise durchgehen und nach "P\n" scannen. Ich nehm an, dass dabei weniger Kopieraktionen stattfinden, und es ein wenig schneller werden müsste. Besser gehts aber natürlich nicht, du kannst keine Aussage über Dateiteile machen, die du überhaupt nicht angeguckt hast, es sei denn, es existiert eine vorberechnete Indizierung o.ä.

Jester

hm, vielleicht hängt er an dem UraltSTL-Bug vom VC6?

Ansonsten mal mit nem istreambuf_iterator drüberlaufen, das ist eigentlich recht flott.

Bashar: nicht eher nach "\nP\n"?

Bashar

Äh ja richtig Plus Spezialfall, dass "P\n" am Anfang der Datei steht, und evtl. ob "\nP" am Ende der Datei steht, falls man nicht Newline-abgeschlossene Dateien zuläßt.

the_alien

Optimizer schrieb:

Wenn du nicht mehr Informationen über den zu durchsuchenden Text hast, wirst du wahrscheinlich den Algorithmus nicht verbessern können. Aber 50 Sekunden für lächerliche 8 MB ?? Liest du jedes Byte einzeln von der Platte?

Ums gleich vorweg zu sagen, ich machs mit Java. Aber wir sind ja in "Rund um die Programmierung"

Das mit den 50 Sekundne für 8 MB stößt mir auch ziemlich auf.
Eigentlich gehe ich hin und lese eine Zeile aus der Datei und guck ob sie nur ein Zeichen lang ist und ein "P" enthält.

Leider hab ich im vorhinein keine Informationen über die Datei, also Länge der Seite, Anzahl der Zeichen oder sonstiges...

Alles was ich weiss ist, dass die Zeile entweder ein Leerzeichen am Anfang hat, oder ein einzelnes "P" in ihr steht.

Schalte einen BufferedStream dazwischen oder poste doch gleich mal ein bisschen Code, so groß kann der nicht sein. Das darf auf keinen Fall so lange dauern.

Und dann wäre es noch interessant zu wissen, in welcher Zeichenkodierung die Datei gespeichert ist. Wenn es UTF-8 oder ISO bla blubb ist, wäre es töricht, nen Reader zu nehmen, der alles in Java-chars umwandelt.

the_alien

while(buff.indexOf("null") != 0){
			if(buff.indexOf("P") == 0 && buff.length() == 1){
				PageCount ++;
				CurrentLineCount = 0;
				FilePosWrapper = new Long(pos);
				PageFilePointers.addElement(FilePosWrapper);
//				when updated to 1.5 use this: PageFilePointers(Long.valueOf(file.getPos()));
			}
			pos = file.getPos();
			buff.delete(0, buff.length()); 					
			buff.append(file.readLine());
		}

Ich denke der Quelltext ist verständlich genug.
Wie schalte ich einen BufferedStream dazwischen?

Achja: file ist ein RandomAccessFile

Termite

Hi

[edit]
ich habs geant das er sowas in der art macht

String line = in.getLine(); // Zeile der Textdatei besorgen

if (line.length() == 1) // Zeilenlänge prüfen
{
  if (line.getChar(0) == 'P') // inhalt ein P
  {
    // DO something
  }
}

ich würd versuchen das auf Byte ebene zu lösen.

\nP\n währe ja dann unter windows 0x13 0x10 0x50 0x13 0x10 für Unix/Linux und Appel siehts dann entsprechend anders aus 0x10 0x50 0x10 oder 0x13 0x50 0x13.

man müsste dan dafür eine nentsprechenden Automaten basteln. ( der hat ja nur 3/5 zustände)

einen BufferdReader/BufferdInputStream dazwischen schieben ist ein muss

ZeilenNummern mit zählen währe auch kein problem.

das was mir dann noch einfällt wird dan aufwendiger zu implementieren. würde Multithreading was bingen?
1 thread kümmert sich um das einlesen der datei, ein oder mehre andere threads um das auswerten des ByteArrays. Ich weis nähmlich nicht wie effizient so ein BufferdReader implementiert ist.

[edit]

von welchem typ sind buffer und file? das anlegen dieser Variablen währe auch interesant

gruss Termite

Shade Of Mine

wozu brauchst du buff?
der ganze code ist komisch.

Vorschlag:

String line;
int pos=0;
while( (line=file.readLine()) != null)
{
  if(line.equals("P"))
  {
    //wozu auch immer?
    ++pageCount;
    currentLineCount=0;

    pageFilePointers.addElement(new Long(pos));
  }
  pos+=line.length();
}

das "while(buff.indexOf("null") != 0)" verstehe ich nicht

file sollte natuerlich ein BufferedReader sein.

Wozu eigentlich ein RandomAccessFile??

the_alien

Ja, so ziemlich genau so läuft das ganze ab.

Ich weiss nicht, was mich da so Performance kostet, aber das RandomAccessFile dürfte es nicht sein.

Wenn ich die Datei nach den P's durchsuche dauert das ein paar mal so lang, als wenn ich einfach hingehe und die Datei von vorne nach hinten einlese, Steuerzeichen über reguläre Ausdrücke ersetzen lasse und das dann auf der Konsole ausgebe.

while(buff.indexOf("null") != 0)

Was ist das?
Was ist buff überhaupt?
[hier stand wahrscheinlich Unsinn]

Und warum brauchst du Random Access? Für was anderes noch? Wenn nicht, wäre es reichlich... unnötig.

Shade Of Mine

the_alien schrieb:

Ich weiss nicht, was mich da so Performance kostet, aber das RandomAccessFile dürfte es nicht sein.

offensichtlich ist mal buffer, der absolut sinnlos ist und ne menge kopieren muss.
Dann verwendest du scheinbar keinen BufferedReader was ziemlich starke IO Last verursacht.

und wieviel ein RandomAccessFile an overhead mitbringt, weiss ich nicht, aber gratis ist das sicher auch nicht.

ist aber schwer genaueres zu sagen, wenn du keine informationen hergibst...

Termite

Hi

das convertieren eines byteArrays in einen String kostet erstam zeit.
Ohne Bufferd.... wird jede zeile einzeln von der Festplatte angefordert. kostet auch wieder zeit.

gruss

virtuell Realisticer

Termite schrieb:

Hi

das convertieren eines byteArrays in einen String kostet erstam zeit.
Ohne Bufferd.... wird jede zeile einzeln von der Festplatte angefordert. kostet auch wieder zeit.

gruss

Stichwort: Memory Mapped I/O

mfg
v R

the_alien

Ok, ich versuche das jetzt mal komplett auszulagern, so dass ich kein RandomAccessFile mehr nutze und das hin und herkopieren zu unterlassen, ich meld mich dann im laufe des Tages nochmal

Bashar

Termite schrieb:

\nP\n währe ja dann unter windows 0x13 0x10 0x50 0x13 0x10 für Unix/Linux und Appel siehts dann entsprechend anders aus 0x10 0x50 0x10 oder 0x13 0x50 0x13.

Gibts in Java keine Textstreams?