萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

在資料流中高效搜尋任意字串的 Delphi 實作

問題背景

開發過程中常需在資料流(TStream)中搜尋特定字串,該字串可能包含 ASCII 擴展字元或混合編碼。網路上常見的演算法或程式碼冗長、效率不佳,因此自行實作了一個精簡且高效的函數供參考。

核心函數:ScanStream

function ScanStream(T: TStream; S: String): Integer;
var
  i, j: Integer;
  p: PChar;
begin
  Result := -1; { 預設未找到 }
  if (T.Size = 0) or (S = '') then Exit;

  GetMem(p, T.Size);           { 配置記憶體緩衝區 }
  try
    T.ReadBuffer(p^, T.Size);  { 一次性讀取整個資料流 }

    for i := 0 to T.Size - 1 do
    begin
      { 嘗試從位置 i 開始比對字串 S }
      for j := 1 to Length(S) do
      begin
        { 邊界檢查:避免超出緩衝區 }
        if (i + j - 1) >= T.Size then Break;
        if p[i + j - 1] <> S[j] then Break; { 字元不符,提早結束內層迴圈 }
      end;

      if j > Length(S) then
      begin
        Result := i;           { 找到,回傳 0-based 位移 }
        Break;                 { 結束外層迴圈 }
      end;
    end;
  finally
    FreeMem(p);                { 釋放緩衝區 }
  end;
end;

演算法解析

  • 一次性讀取:呼叫 ReadBuffer 將整個資料流載入記憶體,避免重複 I/O,適合中小型資料流。
  • 雙層迴圈比對:外層遍歷資料流每個位元組作為潛在起始點,內層逐字元比對目標字串。
  • 提早剪枝:內層迴圈一旦發現字元不符即 Break,減少不必要比較。
  • 記憶體安全:使用 try...finally 確保緩衝區釋放,並檢查邊界防止存取違規。

使用範例

var
  fs: TFileStream;
  pos: Integer;
begin
  fs := TFileStream.Create('data.bin', fmOpenRead or fmShareDenyWrite);
  try
    pos := ScanStream(fs, '目標字串');
    if pos >= 0 then
      ShowMessage(Format('找到於位移 %d', [pos]))
    else
      ShowMessage('未找到');
  finally
    fs.Free;
  end;
end;

效能與適用場景

此函數時間複雜度為 O(n×m)(n 為資料流長度,m 為搜尋字串長度),對於較短模式字串(如關鍵字、標記)效能極佳。若需處理超大檔案或高頻搜尋,建議改用 KMP、Boyer-Moore 等進階演算法,或採用記憶體對映檔案(TMemoryMappedFile)避免完整載入。

注意事項

  • 函數回傳 0-based 位移,若需轉換為 1-based 位置請自行 +1。
  • 字串比對採用 大小寫敏感、逐位元組 比對,適用於 ANSI/UTF-8 等單位元組編碼;若涉及 Unicode(UTF-16),需將 PChar 改為 PWideChar 並調整步進邏輯。
  • 資料流位置會改變,呼叫者若需保留原位置請自行 Seek 還原。
copyright © 萬盛學電腦網 all rights reserved