Wie sucht man möglichst schnell Strings in einer Datei?

[OlderCoder]

Hallo allerseits,

ich möchte in beliebigen Dateien nach Zeichenketten suchen.

Bisher mache ich das so:

Code: Alles auswählen

Text$="" 
If  ReadFile(1,datei$)
   While Not Eof(1)
     Text$+ReadString(1)
   Wend  
  CloseFile(1)
EndIf

Anschließend suche ich nach dem String so:

Code: Alles auswählen

gefunden=FindString(text$,such$)

Das hat den Vorteil, dass aus der Datei alle Null-Bytes entfernt sind und diese in ihrer Gesamtheit als String behandelt werden kann, sonst würde FindString nicht funktionieren.
Aber es hat den Nachteil, dass das String-weise Auslesen und Wieder-Zusammensetzen ziemlich lange dauert.
Bei Dateien von mehreren hundert kB wartet man pro Datei schon eine kleine Ewigkeit.

Die Alternative, mit einem Speicherbereich zu arbeiten, hab ich hier im Forum gefunden

http://forums.purebasic.com/german/view ... 0205b1f1e9
matbal hatte hier in einem Programm diesen Vorschlag für das Einlesen:

Code: Alles auswählen

If ReadFile(0, datei$)
      l = Lof(0)
      If l
        *mem = AllocateMemory(l + 2)
         If *mem
            fmt = ReadStringFormat(0)
            ReadData(0, *mem, l)
            Text$ = PeekS(*mem, -1,fmt)
            FreeMemory(*mem)
         EndIf
      EndIf
      CloseFile(0)
    EndIf

Das geht vielleicht viel schneller, aber die Variable Text$ enthält häufig nur einen kleinen Teil der Datei, weil das erste 0-Byte die Variable abschließt.
Und solche 0-Bytes kommen oft vor.

Welche Methode gibt es noch, in einer beliebigen Datei nach Zeichenketten zu suchen, und zwar möglichst schnell?

Und noch eine zusätzliche Frage hab ich. Wie kann man in Word- und pdf-Dateien von einem PB-Programm aus nach Zeichenketten suchen? Sieht man sich die Zeichen einer solchen Datei in Rohform an, dann scheinen diese überhaupt nichts mit den Zeichen gemeinsam zu haben, die tatsächlich in den Dokumenten vorhanden sind.

Vielen Dank erst mal fürs Lesen.

Gruß
OlderCoder

[matbal]

Wie schnell es ist, weiß ich nicht. Nachteil könnte sein, daß immer die komplette Datei in den Speicher passen muß.

Ich lese die Datei in den Speicher ein und gehe dann byte-weise durch die Datei und peeke mir jedesmal soviele Bytes heraus heraus, wie der Suchbegriff lang ist. Mein Code sucht nach ASCII-Text. Für Unicode und UTF8 müssen die Flags und der Pointer geändert werden.

Code: Alles auswählen

EnableExplicit

Define File$ = "Test.pdf"
Define Such$ = "PDF"


Define SuchLen = Len(Such$)
Define *mem, length, i, *p.ascii

If ReadFile(0, File$)
   length = Lof(0)
   If length
      *mem = AllocateMemory(length)
      If *mem 
         ReadData(0, *mem, length)
         *p = *mem
         
         length - SuchLen
         
         For i = 0 To length
            If *p\a = Asc(Such$)
               If PeekS(*p, SuchLen, #PB_Ascii) = Such$
                  Debug "Gefunden an Pos" + Str(i)
                  ; Break 
               EndIf
            EndIf
            *p + 1
         Next i
         FreeMemory(*mem)
      EndIf
   EndIf
   
   CloseFile(0)
EndIf

[H.Brill]

Hab für dich im engl. Forum gesucht.
Manchmal braucht man ja selber sowas.
Wie man sieht, gehts sogar mit Nullbyte
als Memory oder String.

Code: Alles auswählen

Structure MemoryArray 
    Byte.c[0] 
EndStructure 

Procedure.l Quicksearch(StartPos.l, *MainMem, MainLen.l, *FindMem, FindLen.l) 

    *MainByteArray.MemoryArray = *MainMem
    *FindByteArray.MemoryArray = *FindMem 
    StartPos =- 1

    ; Build BadChr Array
    Dim BadChar.l(255)
    
    ; set all alphabet to max shift pos (length of find string plus 1)
    For i = 0 To 255
        BadChar(i)  =  FindLen + 1
    Next
    
    ;Update chars that are in the find string to their position from the end.
    For i = 0 To findlen -1
        BadChar(*FindByteArray\byte[i]) = findlen - i    
    Next     

    MainArrayLoop.l = StartPos 
    EndSearchPos.l = MainLen - (FindLen -1)
    
    While MainArrayLoop <= EndSearchPos
    
        If CompareMemory(*MainMem + MainArrayLoop, *FindMem, FindLen) = 1
            FoundPos = MainArrayLoop + 1
            Break
        EndIf 
        
        ;Didn't find the string so shift as per the table.
        MainArrayLoop + BadChar(*MainByteArray.MemoryArray\byte[MainArrayLoop + FindLen])
    
    Wend

    ProcedureReturn FoundPos

EndProcedure 

mystr.s
c0byte.s = Chr(0)
mystr = "Hallo Welt !" + Chr(0) + " da bin ich !"
*buffer = AllocateMemory(26)
PokeS(*buffer, mystr)

Debug Quicksearch(1, @"ABCDEF", 6, @"A", 1) 
Debug Quicksearch(1, @"ABCDEF", 6, @"F", 1)
Debug Quicksearch(1, @"ABCDEF", 6, @"BC", 2)

Debug Quicksearch(1, *buffer, 26, @c0byte, 1)
Debug Quicksearch(1, @mystr, 26, @c0byte, 1)

FreeMemory(*buffer)

[OlderCoder]

Danke Euch!

@matbal:
Erste Tests zeigen, dass Dein Vorschlag um Größenordnungen schneller ist wie meine Methode.
Auf sowas hab ich gehofft.

Magst Du mir noch erklären, was es mit dem Sternchen vor dem Variablennamen genau auf sich hat?
Ein bisschen verwirren tut mich auch noch der Ausdruck *p\a.

@H.Brill:
Danke für Deine Suche. Muss ich mir erst mal anschauen, den Code, damit ich verstehe, wie er funktioniert.

Dankeschön!

[matbal]

Magst Du mir noch erklären, was es mit dem Sternchen vor dem Variablennamen genau auf sich hat?
Ein bisschen verwirren tut mich auch noch der Ausdruck *p\a.

Die Idee war, daß bei Übereinstimmungen das erste Byte im Speicher ja auch mit dem ersten Buchstabe vom Suchbegriff übereinstimmen muß. Nur wenn ich den Anfangsbuchstaben im Speicher finde, prüfe ich, ob der Rest auch übereinstimmt.

Mit AllocateMemory() hole ich mir einen Speicherbereich für die Daten der Datei.
*mem ist die Speicheradresse des ersten Bytes von diesem Speicher.

*p.ascii ist ein Pointer, den ich am Anfang auf diesen Speicher setze. Die angehängte Struktur .ascii ermöglicht mir, den Speicherinhalt an der Adresse, die in *p gespeichert ist, als ASCII-Wert zu lesen. *p enthält also die Speicheradresse, und mit *p\a lese ich den Inhalt an dieser Adresse aus. Ich brauche dann nur *p immer um eins erhöhen, und bin dann auf dem nächsten Buchstaben, den ich dann wiederum mit *p\a auslesen kann.

[OlderCoder]

Danke!
Ich bin sicher, darüber gibt es auch in der PB-Hilfe etwas zu lesen.
Aber ich hab schon öfter dort etwas gesucht und bei weitem nicht immer auch etwas gefunden. Und ganze Kapitel komplett durchzulesen, dafür fehlt mir einfach die Zeit.

[H.Brill]

Im obigen Code kannst du auch per Iteration mehrfach
suchen. Einfach ersten Parameter (Startpos) mit dem
Ergebnis des letzten QuickSearch() + 1 belegen. Das
dann solagne machen, bis als Ergebnis 0 kommt.

Code: Alles auswählen

Startpos.l = 1
While Startpos > 0
  Startpos = QuickSearch(Startpos + 1, ...)
Wend

Ist auch nicht schlimm, wenn man es nicht sofort
versteht. Einfach benutzen. So mache ich das auch
öfter.

[Waldixxl]

Hallo OlderCoder

Hier ein Beispiel welches mich fasziniert, weil ich nicht verstehe, warum es um soviel schneller geht.
Stammt im übrigen von Kukulkan

Code: Alles auswählen

Text$=""
dummy$=""
If  ReadFile(1,datei$)
   While Not Eof(1)
     dummy$+ReadString(1)
    If Len(dummy$) > 5000: Text$+dummy$: dummy$="": EndIf
  Wend
  Text$+dummy$
  EndIf

Walter

[NicTheQuick]

Wenn es darum geht in einer Datei viele verschiedene Strings zu suchen, sollte man sich einen Suffixbaum bauen.

[OlderCoder]

@H.Brill:
Danke!

@Waldixxl:
Das ist in der Tat wirklich bemerkenswert!

Ich hab mal mein Verfahren mit Deinem, das sich nur in einem kleinen Detail unterscheidet, an einer Datei mit 770 384 Bytes verglichen.

Der Ergebnis-String bei mir hat anschließend eine Länge von 671053 Bytes. Es müssten also 99331 Null-Bytes herausgefallen sein (soviel? Das sind 12.9%!)
Die Suche hat 41 Sekunden gedauert.
Mit Deiner Variante hat sie gerade mal 1,6 Sekunden gedauert, das ist über 25 mal so schnell.
Man sollte meinen, dass es eher noch länger dauert, weil schließlich eine weitere Variable im Spiel ist.
Allerdings bleibt bei Dir nur noch ein Ergebnis-String von 668418 Bytes übrig, es fehlen weitere 2635 Bytes.
Aber warum? Hier passieren Dinge, die für mich nicht nachzuvollziehen sind.

Und das Ergebnis kann doch dann nur noch falsch sein.
Dann werde ich mich wohl von der reinen Stringverarbeitung verabschieden und versuchen, die Lösung von matbal oder H.Brill zu verwenden.
Hier gibt es allerdings noch ein Zusatzproblem, weil mein Programm auch so suchen soll, dass Groß- und Kleinbuchstaben nicht unterschieden werden. Und dann kann ich diese Aufgabe nicht mehr einfach mit UCASE lösen.

Und für meine Nebenfrage wegen dem Auslesen von pdf und Word-Dateien gibt es vermutlich keine einfache Lösung, oder?