Efficient way to find a string in a stream in Delphi

Question

I have come up with this function to return the number of occurrences of a string in a Delphi Stream. However, I suspect there is a more efficient way to achieve this, since I am using "higher level" constructs (char), and not working at the lower byte/pointer level (which I am not that familiar with)

function ReadStream(const S: AnsiString; Stream: TMemoryStream): Integer;
var
  Arr: Array of AnsiChar;
  Buf: AnsiChar;
  ReadCount: Integer;

  procedure AddChar(const C: AnsiChar);
  var
    I: Integer;
  begin
    for I := 1 to Length(S) - 1 do
      Arr[I] := Arr[I+1];
    Arr[Length(S)] := C;
  end;

  function IsEqual: Boolean;
  var
    I: Integer;
  begin
    Result := True;
    for I := 1 to Length(S) do
      if S[I] <> Arr[I] then
      begin
        Result := False;
        Break;;
      end;
  end;

begin
  Stream.Position := 0;
  SetLength(Arr, Length(S));
  Result := 0;
  repeat
    ReadCount := Stream.Read(Buf, 1);
    AddChar(Buf);
    if IsEqual then
      Inc(Result);
  until ReadCount = 0;
end;

Can someone supply a procedure that is more efficient?

Answer 1

Stream has a method that will let you get into the internal buffer.

You can get a pointer to the internal buffer using the Memory property.

If you are working in 32 bit and you are willing to let go of the deprecated TMemoryStream and use TBytesStream instead you can use abuse the fact that a dynamic array and an AnsiString share the same structure in 32 bit.
Unfortunately Emba broke that compatibility in X64, Which means that for no good reason whatsoever you cannot have strings > 2GB in X64.

Note that this trick will break in 64 bit! (See fix below)

You can use Boyer-Moore string searching.

This allows you to write code like this:

function CountOccurrances(const Needle: AnsiString; const Haystack: TBytesStream): integer;
var
  Start: cardinal;
  Count: integer;
begin 
  Start:= 1;
  Count:= 0;
  repeat
    {$ifdef CPUx86}
    Start:= _FindStringBoyerAnsiString(string(HayStack.Memory), Needle, false, Start);
    {$else}
    Start:= __FindStringBoyerAnsiStringIn64BitTArrayByte(TArray<Byte>(HaySAtack.Memory), Needle, false, Start);
    {$endif}
    if Start >= 1 then begin
      Inc(Start, Length(Needle));
      Inc(Count);
    end;
  until Start <= 0;
  Result:= Count;
end;

For 32 bit you'll have to rewrite the BoyerMoore code to use AnsiString; a trivial rewrite.
For 64 bit you'll have to rewrite the BoyerMoore code to use a TArray<byte> as a first parameter; a relatively simple task.

If you are looking for efficiency, please try and avoid WinAPI calls that use pchars. c-style strings are a horrible idea, because they do not have a length prefix.

Answer 2

Johan has given you a good answer about Boyer-Moore searching. BM is fine if your are content to use it as a "black box", but if you want to understand what's going on, there is a bit of a gulf between the complexity of your own code and a BM implementation.

You might find it helpful to explore searching that's more efficient than your own code but not so complex as BM. There is one ultra-simple way to do what you want without getting invoved with pointers, PChars, etc.

Let's leave aside for a moment the fact that you want to work with a TMemoryStream, and consider finding the number of occurrences of a string SubStr in another string Target.

For efficiency, things you want to avoid are a) repeatedly scanning the same characters over and over and b) copying one or both strings.

Since D7, Delphi has included a PosEx function:

function PosEx(const SubStr, S: string; Offset: Cardinal = 1): Integer; Description PosEx returns the index of SubStr in S, beginning the search at Offset. If Offset is 1 (default), PosEx is equivalent to Pos. PosEx returns 0 if SubStr is not found, if Offset is greater than the length of S, or if Offset is less than 1.

So what you can do is repeatedly call PosEx, starting with Offset = 1, and each time it finds SubStr in Target you increment Offset to skip over it, like this (in a console application):

function ContainsCount(const SubStr, Target : String) : Integer;
var
  i : Integer;
begin
  Result := 0;
  i := 1;
  repeat
    i := PosEx(SubStr, Target, i);
    if i > 0 then begin
      Inc(Result);
      i := i + Length(SubStr);
    end;
  until i <= 0;
end;

var
  Count : Integer;
  Target : String;
begin
  Target := 'aa b ca';
  Count := ContainsCount('a', Target);
  writeln(Count);
  readln;
end.

The fact that PosEx and ContainsCount both pass SubStr and Target as consts meants that no string copying is involved, and it should be obvious that ContainsCount never scans the same characters more that once.

Once you've satisfied yourself that this works, you might care to trace into PosEx to see how it does its stuff.

You can do something which works in a similar way on PChars using the RTL functions StrPos/AnsiStrPos

To convert your memory stream to a string, you could use this code from Rob Kennedy's answer to this q Converting TMemoryStream to 'String' in Delphi 2009

function MemoryStreamToString(M: TMemoryStream): string;
begin
  SetString(Result, PChar(M.Memory), M.Size div SizeOf(Char));
end;

(Note what he says about the alternative version later in his answer)

Btw, if you look through the VCL + RTL code, you'll see that quite a lot of the string-parsing and processing code (e.g. in TParser, TStringList, TExpressionParser) all does its work with PChars. There's a reason for that of course, because it minimizes character copying and means that most scanning operations can be done by changing pointer (PChar) values.