Подтвердить что ты не робот

Есть ли поиск строки Boyer-Moore и быстрый поиск и замена функции и быстрое количество строк для Delphi 2010 String (UnicodeString)?

Мне нужны три функции fast-on-large-strings: быстрый поиск, быстрый поиск и замена, а также быстрый подсчет подстрок в строке.

Я столкнулся с поисковыми строками Boyer-Moore в С++ и Python, но единственный алгоритм Delphi Boyer-Moore, используемый для быстрого поиска и замены, который я нашел, является частью FastStrings Питером Моррисом, ранее имевшим программное обеспечение DroopyEyes, и его веб-сайт и электронная почта больше не работают.

Я уже портировал FastStrings вперед, чтобы отлично работать для AnsiStrings в Delphi 2009/2010, где байт равен одному AnsiChar, но делает они также работают со строкой (UnicodeString) в Delphi 2010, которая выглядит нетривиальной.

Используя этот алгоритм Бойера-Мура, можно легко делать нечувствительные к регистру поисковые запросы, а также без учета регистра и замены без какой-либо временной строки (используя StrUpper и т.д.) и без вызова Pos(), который медленнее чем поиск Boyer-Moore, когда требуется повторный поиск по тому же тексту.

(Edit: у меня есть частичное решение, написанное как ответ на этот вопрос, оно почти на 100% завершено, оно даже имеет функцию быстрой замены строки. Я считаю, что ДОЛЖЕН иметь ошибки, и особенно думаю, что, поскольку он притворяется чтобы быть Unicode способным, что должно быть, что есть глюки из-за невыполненного Unicode promises.)

(Edit2: Интересный и неожиданный результат: большой размер стека таблицы кодовых слов в кодировке Unicode в стеке - SkipTable в коде ниже помещает серьезный демпфер на количество выигрышной оптимизации, которую вы можете сделать здесь, в Строка поиска юникода string boyer-moore. Спасибо Florent Ouchet за то, что я сразу заметил.)

4b9b3361

ОТВЕТЫ

Ответ 1

Теперь этот ответ завершен, за исключением того, что код не прошел успешно (Unit) и, вероятно, может быть оптимизирован дальше, например, я повторил локальную функцию __SameChar вместо того, чтобы использовать обратный вызов функции сравнения, который был бы быстрее, и фактически, позволяя пользователю передавать функцию сравнения для всех этих функций, было бы замечательно для пользователей Unicode, которые хотят предоставить дополнительную логику (эквивалентные наборы символов Unicode для некоторых языков). Однако у меня есть решение Boyer-Moore для чувствительного к регистру Pos и ​​более быстрый подсчет подстроки, а теперь поиск и замена тоже:

Основываясь на коде Dorin Dominica, я построил следующее.

{ _FindStringBoyer:
  Boyer-Moore search algorith using regular String instead of AnsiSTring, and no ASM.
  Credited to Dorin Duminica.
}
function _FindStringBoyer(const sString, sPattern: string;
  const bCaseSensitive: Boolean = True; const fromPos: Integer = 1): Integer;

    function __SameChar(StringIndex, PatternIndex: Integer): Boolean;
    begin
      if bCaseSensitive then
        Result := (sString[StringIndex] = sPattern[PatternIndex])
      else
        Result := (CompareText(sString[StringIndex], sPattern[PatternIndex]) = 0);
    end; // function __SameChar(StringIndex, PatternIndex: Integer): Boolean;

var
  SkipTable: array [Char] of Integer;
  LengthPattern: Integer;
  LengthString: Integer;
  Index: Integer;
  kIndex: Integer;
  LastMarker: Integer;
  Large: Integer;
  chPattern: Char;
begin
  if fromPos < 1 then
    raise Exception.CreateFmt('Invalid search start position: %d.', [fromPos]);
  LengthPattern := Length(sPattern);
  LengthString := Length(sString);
  for chPattern := Low(Char) to High(Char) do
    SkipTable[chPattern] := LengthPattern;
  for Index := 1 to LengthPattern -1 do
    SkipTable[sPattern[Index]] := LengthPattern - Index;
  Large := LengthPattern + LengthString + 1;
  LastMarker := SkipTable[sPattern[LengthPattern]];
  SkipTable[sPattern[LengthPattern]] := Large;
  Index := fromPos + LengthPattern -1;
  Result := 0;
  while Index <= LengthString do begin
    repeat
      Index := Index + SkipTable[sString[Index]];
    until Index > LengthString;
    if Index <= Large then
      Break
    else
      Index := Index - Large;
    kIndex := 1;
    while (kIndex < LengthPattern) and __SameChar(Index - kIndex, LengthPattern - kIndex) do
      Inc(kIndex);
    if kIndex = LengthPattern then begin
      // Found, return.
      Result := Index - kIndex + 1;
      Index := Index + LengthPattern;
      exit;
    end else begin
      if __SameChar(Index, LengthPattern) then
        Index := Index + LastMarker
      else
        Index := Index + SkipTable[sString[Index]];
    end; // if kIndex = LengthPattern then begin
  end; // while Index <= LengthString do begin
end;

{ Written by Warren, using the above code as a starter, we calculate the SkipTable once, and then count the number of instances of
  a substring inside the main string, at a much faster rate than we
  could have done otherwise.  Another thing that would be great is
  to have a function that returns an array of find-locations,
  which would be way faster to do than repeatedly calling Pos.
}
function _StringCountBoyer(const aSourceString, aFindString : String; Const CaseSensitive : Boolean = TRUE) : Integer;
var
  foundPos:Integer;
  fromPos:Integer;
  Limit:Integer;
  guard:Integer;
  SkipTable: array [Char] of Integer;
  LengthPattern: Integer;
  LengthString: Integer;
  Index: Integer;
  kIndex: Integer;
  LastMarker: Integer;
  Large: Integer;
  chPattern: Char;
    function __SameChar(StringIndex, PatternIndex: Integer): Boolean;
    begin
      if CaseSensitive then
        Result := (aSourceString[StringIndex] = aFindString[PatternIndex])
      else
        Result := (CompareText(aSourceString[StringIndex], aFindString[PatternIndex]) = 0);
    end; // function __SameChar(StringIndex, PatternIndex: Integer): Boolean;

begin
  result := 0;
  foundPos := 1;
  fromPos := 1;
  Limit := Length(aSourceString);
  guard := Length(aFindString);
  Index := 0;
  LengthPattern := Length(aFindString);
  LengthString := Length(aSourceString);
  for chPattern := Low(Char) to High(Char) do
    SkipTable[chPattern] := LengthPattern;
  for Index := 1 to LengthPattern -1 do
    SkipTable[aFindString[Index]] := LengthPattern - Index;
  Large := LengthPattern + LengthString + 1;
  LastMarker := SkipTable[aFindString[LengthPattern]];
  SkipTable[aFindString[LengthPattern]] := Large;
  while (foundPos>=1) and (fromPos < Limit) and (Index<Limit) do begin

    Index := fromPos + LengthPattern -1;
    if Index>Limit then
        break;
    kIndex := 0;
    while Index <= LengthString do begin
      repeat
        Index := Index + SkipTable[aSourceString[Index]];
      until Index > LengthString;
      if Index <= Large then
        Break
      else
        Index := Index - Large;
      kIndex := 1;
      while (kIndex < LengthPattern) and __SameChar(Index - kIndex, LengthPattern - kIndex) do
        Inc(kIndex);
      if kIndex = LengthPattern then begin
        // Found, return.
        //Result := Index - kIndex + 1;
        Index := Index + LengthPattern;
        fromPos := Index;
        Inc(Result);
        break;
      end else begin
        if __SameChar(Index, LengthPattern) then
          Index := Index + LastMarker
        else
          Index := Index + SkipTable[aSourceString[Index]];
      end; // if kIndex = LengthPattern then begin
    end; // while Index <= LengthString do begin

  end;
end;

Это действительно хороший алгоритм, потому что:

  • Скорее посчитайте экземпляры подстроки X в строке Y таким образом, великолепно.
  • Для простой замены Pos() функция _FindStringBoyer() быстрее, чем чистая версия asm версии Pos(), внесенная в Delphi пользователями проекта FastCode, которые в настоящее время используются для Pos, и если вам нужна нечувствительность к регистру, вы можете представьте себе повышение производительности, когда нам не нужно вызывать UpperCase со скоростью 100 мегабайт. (Хорошо, ваши строки не будут такими большими. Но все же эффективные алгоритмы - это красота красоты.)

Хорошо, я написал String Replace в стиле Boyer-Moore:

function _StringReplaceBoyer(const aSourceString, aFindString,aReplaceString : String; Flags: TReplaceFlags) : String;
var
  errors:Integer;
  fromPos:Integer;
  Limit:Integer;
  guard:Integer;
  SkipTable: array [Char] of Integer;
  LengthPattern: Integer;
  LengthString: Integer;
  Index: Integer;
  kIndex: Integer;
  LastMarker: Integer;
  Large: Integer;
  chPattern: Char;
  CaseSensitive:Boolean;
  foundAt:Integer;
  lastFoundAt:Integer;
  copyStartsAt:Integer;
  copyLen:Integer;
    function __SameChar(StringIndex, PatternIndex: Integer): Boolean;
    begin
      if CaseSensitive then
        Result := (aSourceString[StringIndex] = aFindString[PatternIndex])
      else
        Result := (CompareText(aSourceString[StringIndex], aFindString[PatternIndex]) = 0);
    end; // function __SameChar(StringIndex, PatternIndex: Integer): Boolean;

begin
  result := '';
  lastFoundAt := 0;
  fromPos := 1;
  errors := 0;
  CaseSensitive := rfIgnoreCase in Flags;
  Limit := Length(aSourceString);
  guard := Length(aFindString);
  Index := 0;
  LengthPattern := Length(aFindString);
  LengthString := Length(aSourceString);
  for chPattern := Low(Char) to High(Char) do
    SkipTable[chPattern] := LengthPattern;
  for Index := 1 to LengthPattern -1 do
    SkipTable[aFindString[Index]] := LengthPattern - Index;
  Large := LengthPattern + LengthString + 1;
  LastMarker := SkipTable[aFindString[LengthPattern]];
  SkipTable[aFindString[LengthPattern]] := Large;
  while (fromPos>=1) and (fromPos <= Limit) and (Index<=Limit) do begin

    Index := fromPos + LengthPattern -1;
    if Index>Limit then
        break;
    kIndex := 0;
    foundAt := 0;
    while Index <= LengthString do begin
      repeat
        Index := Index + SkipTable[aSourceString[Index]];
      until Index > LengthString;
      if Index <= Large then
        Break
      else
        Index := Index - Large;
      kIndex := 1;
      while (kIndex < LengthPattern) and __SameChar(Index - kIndex, LengthPattern - kIndex) do
        Inc(kIndex);
      if kIndex = LengthPattern then begin


        foundAt := Index - kIndex + 1;
        Index := Index + LengthPattern;
        //fromPos := Index;
        fromPos := (foundAt+LengthPattern);
        if lastFoundAt=0 then begin
                copyStartsAt := 1;
                copyLen := foundAt-copyStartsAt;
        end else begin
                copyStartsAt := lastFoundAt+LengthPattern;
                copyLen := foundAt-copyStartsAt;
        end;

        if (copyLen<=0)or(copyStartsAt<=0) then begin
                Inc(errors);
        end;

        Result := Result + Copy(aSourceString, copyStartsAt, copyLen ) + aReplaceString;
        lastFoundAt := foundAt;
        if not (rfReplaceAll in Flags) then
                 fromPos := 0; // break out of outer while loop too!
        break;
      end else begin
        if __SameChar(Index, LengthPattern) then
          Index := Index + LastMarker
        else
          Index := Index + SkipTable[aSourceString[Index]];
      end; // if kIndex = LengthPattern then begin
    end; // while Index <= LengthString do begin
  end;
  if (lastFoundAt=0) then
  begin
     // nothing was found, just return whole original string
      Result := aSourceString;
  end
  else
  if (lastFoundAt+LengthPattern < Limit) then begin
     // the part that didn't require any replacing, because nothing more was found,
     // or rfReplaceAll flag was not specified, is copied at the
     // end as the final step.
    copyStartsAt := lastFoundAt+LengthPattern;
    copyLen := Limit; { this number can be larger than needed to be, and it is harmless }
    Result := Result + Copy(aSourceString, copyStartsAt, copyLen );
  end;

end;

Хорошо, проблема: Стежок:

var
  skiptable : array [Char] of Integer;  // 65536*4 bytes stack usage on Unicode delphi

Прощай, черт возьми, ад ад. Если я перейду к динамическому массиву, то мне придется изменить его размер во время выполнения. Так что эта вещь в основном быстрая, потому что система виртуальной памяти на вашем компьютере не моргает при 256K, входящем в стек, но это не всегда оптимальный фрагмент кода. Тем не менее, мой компьютер не моргает в таком большом стеке. Он не станет стандартной библиотекой Delphi по умолчанию или не победит в какой-либо проблеме с быстрым кодом в будущем, с таким отрывом. Я думаю, что повторный поиск - это случай, когда вышеуказанный код должен быть записан как класс, а skiptable должен быть полем данных в этом классе. Затем вы можете построить таблицу боулер-moore один раз, и со временем, если строка является инвариантной, многократно используйте этот объект для быстрого поиска.

Ответ 2

Поскольку я просто искал то же самое: Jedi JCL имеет поисковую систему с поддержкой unicode, используя Boyer-Moore в jclUnicode.pas. Я понятия не имею, насколько хороши или как быстро это пока.