Оптимизация алгоритма поиска Бойера-Мура

нет, это не БМ, это мой самодельный алгоритм, чем-то напоминает quick search. Таблицы ему готовить не надо, память под таблицу резервировать тоже не надо, он сам составляет на стеке таблицу из переданной сигнатуры. Написан на ассемблере, поэтому если прицепить к дельфи, то наверное лучше в виде dll.

Он не поддерживает поиск по маске, т.е. "gkKEUjjkeu*****h%764hT" не прокатит.

Хотя это можно обойти, например передать ему более длинную известную часть сигнатуры "gkKEUjjkeu", и если она найдена, допроверить побайтно оставшиеся "h%764hT".

если маппировать, ничего не надо грузить. Если использовать ReadFile, то 7Мб не такая большая величина, чтобы разбивать на куски.

 

так в принципе для меня всё ясно... =)

буду оптимизировать... и посл. вопрос.. после маппирования файла возвращается указатель (FP)... а в ф-ии поиска на вход нужно передать буффер.. правильно ли я делаю MOVE(FP,BUF^,SIZE) а потом передаю в функцию... =\



добавлено...

прочитал в одной статье, что с маппированным файлом мона работать как с pchar, сижу ща разбираюсь...

 

trash

Вопрос по фичам (и вообще)BDS2006. Че там за совместимость с .NET?



Совершенно не в курсе - грешно заставлять своих юзеров ставить 100 меторов всякой мути, чтобы они могли заценить мой шедевр. Поэтому я только Win32-компиляторы из BDS2006 ставил.



D9 - уж не псевдокодовый ли?

Он вообще-то D10. Девятка - это 2005. Впрочем, они оба генерят самый обычный 32-битный код для x86.



В обджи делать умеет?

С++ Builder - точно делает, в Delphi мне это было без надобности, потому не проверял. Чужие OBJ глотает без вопросов.

 

cresta

Написан на ассемблере, поэтому если прицепить к дельфи, то наверное лучше в виде dll



Лучше - обработать напильником и завернуть в скобочки asm-end А если из-за макросов или экзотического синтаксиса делать это совсем уж муторно - откомпилить в OBJ и подрубить принудительно.

 

Hellspawn

после маппирования файла возвращается указатель (FP)... а в ф-ии поиска на вход нужно передать буффер.. правильно ли я делаю MOVE(FP,BUF^,SIZE) а потом передаю в функцию... =\



Скорее всего - нет, если, конечно, ты не собираешься скопировать САМ указатель в буфер максимально медленным способом. Но тогда обычно пишут move (fp, buf^, sizeof(fp))



прочитал в одной статье, что с маппированным файлом мона работать как с pchar, сижу ща разбираюсь...

А еще можно как с AnsiString...

 

CyberManiac

В дельфи есть такое, чтобы сделать функцию без пролога/эпилога?
И выравнивание align?

 

cresta

В дельфи есть такое, чтобы сделать функцию без пролога/эпилога?



Насколько я знаю, только с волшебными словами inline (D2005+) и assembler (это еще с Turbo Pascal ). Ну или просто глобальную метку влепить и вообще писать, как вздумается, но такую "функцию" вызывать не очень удобно.



И выравнивание align?

Выравнивание _чего_? Если данных - то есть, по произвольным значениям границ. Если кода - не знаю, не проверял.

 

значит так, работал с файлом как с Pbytearray (присваивал адресс возвр. ф-ий маппирования) получилось порядка

350 миллисекунд для 25 сигнатур по 20 байт на 7 меговый файл... мне кажется можно быстрее =\ хотя на моём компе (P III 866 128mb) +)

 

Hellspawn

Интересно как ты маппинг используешь. Если при поиске каждой сигнатуры просматриваешь все 7 метров, затем берешь вторую и т.д., то это не совсем верно с точки зрения использования кэша процессора - постоянно идет подкачка данных из ОЗУ. Лучше обрабатывать блоками (теми же 64К) - берешь первый блок (просто ограничиваешь размер, передаваемый в BMSearch) и прогоняешь все сигнатуры. Затем смещаешь указатель на размер блока минус размер сигнатуры и т.д. При этом данные будут грузиться из ОЗУ в кэш только один раз, а не 25



PS: Похоже я упустил из вида нехилый размер 25 таблиц WCMakeBMTable ( Так что видимо блочная обработка тут не покатит. Если только использовать упрощенный BM и\или ужать таблицы (использовать byte или word)

 

Вот му алго для поиска строки в

shortstring

Код (Text):

1.  
2. type byte_array = array [0..65535] of byte; pstr = ^byte_array;
3. //////////////////////////////////////////
4. function pch (var str:string ): pchar;////
5. begin  str[Length (str)+1] := char(0);////
6.        Result  := @str[1];        end;////
7. //////////////////////////////////////////
8. function Ucase (ch:byte):byte;
9. begin
10.  if (ch >= byte('a') ) and (ch <= byte('z') ) then
11.  Result := ch -  32 else  Result := ch;
12. end;
13.  
14. function  word_cmp (str1, str2 : pstr;len:integer):boolean;
15.  var i:integer;
16.  begin  Result:=true;//pass2 cканировать слово
17.   for i:=0 to len do if Ucase (str1[i]) <> Ucase (str2[i]) then Result:=false
18.  end;
19.  
20. function SeekStr (wrd:pstr; wrd_len: integer;
21.                   txt:pstr; txt_len: integer):integer;
22. var i:integer;
23. begin {SeekStr}
24.   for i:=0 to txt_len do //pass1 cканировать байт
25.    if Ucase (txt[i]) = Ucase (wrd[0]) then
26.     if  word_cmp (@txt[i], wrd, wrd_len ) then break;
27.      if i > txt_len then Result:= -1 else SeekStr := i;
28. end;
29.  

Кому и короткие рулят!

 

конечно блоками... да с таблицами это не есть гууд...

буду думать...

trash - разве под мой случай этот поиск покатит?

 

function Ucase (ch:byte):byte;

begin

if (ch >= byte('a') ) and (ch <= byte('z') ) then

Result := ch - 32 else Result := ch;

end;



Самый быстрый Uppercase - это сделать таблицу преобразования любых букв в большие, и вместо функции просто выбирать элемент из массива of Char. 256 байт, полагаю, на доброе дело не жалко? Зато работать будет куда как быстрее.



Result:=true;//pass2 cканировать слово

for i:=0 to len do if Ucase (str1) <> Ucase (str2) then Result:=false





А если вот так:

for i:=0 to len do if UcaseArr[str1] <> UcaseArr[str2] then begin Result:=false; Exit end;

Result:=True;



Что-то мне подсказывает, что в общем случае это будет работать значительно быстрее.

 

Собственно этот поиск я когда-то применял во внутрених функциях дельфи (в модуле System.pas).



В общем хотел реализовать простейшие методы поиска в коротких строках..

Код (Text):

1.  
2. STR  := 'Hello World!';
3.  

Выражение:

Код (Text):

1.  
2. STR1 := '{Hello {R}!}' + STR;
3.  

Уже прокатывало вроде макроса, а команда {R} возврашала результат поиска (то бишь World)...



p.s

Ваял утилиты сборок (вместо .bat файлов).

 

короче я сделал так...

Код (Text):

1.  
2. function Find(const ps:integer;const P: String;S:Pbytearray;_size:dword) : Integer;
3. var
4.   i, j, n: Integer;
5. begin
6.   Result := 0;
7.   n:= Length(P);
8.   //if n > _size then Exit;
9.   for i := ps to _size - n + 1 do
10.     for j := 1 to n do
11.       if (ord(P[j]) <> S[i+j-1]) and (P[j]<>'?') then Break
12.       else if j = n then
13.       begin
14.         Result := i;
15.         Exit;
16.       end;
17. end;

будут предложения по убыстрению алго =) или другой заюзать =\

 

По-моему, это самое медленное, что можно было придумать?

Хотя бы BM используй.

 

да от бм пришлось отказаться, 400 сигнатур... ты прикинь скока таблицы будут весить...



вот - чуть переписал ща..

Код (Text):

1.  
2.   i:=ps; // начало поиска
3.   repeat
4.     If (ord(P[1]) = S[i]) then // нашли 1-ый символ
5.         If (ord(P[n]) = S[i+n-1]) then // посл символ
6.         begin
7.           For j:=2 to n-1 do // цикл сравнения
8.           begin
9.             If (ord(P[j]) <> S[i+j-1]) and (P[j]<>'?') then Break
10.             else If j = n-1 then
11.             begin
12.               Result := i;
13.               Exit;
14.             end;
15.           end;
16.           i:=i+n; // сдвигаемся на длину сигны
17.         end else i:=i+n; // аналогично
18.     inc(i); // след байт
19.   until i >= m;
20.  

 

Hellspawn

> "да от бм пришлось отказаться, 400 сигнатур... ты прикинь скока таблицы будут весить..."

Если длина сигнатуры < 255 символов, то для упрощенного БМ таблицу скачков можно реализовать в виде массива 255 байт. Поэтому даже для 400 сигнатур это будет "всего лишь" сотня Кб, плюс на сами сигнатуры десяток-другой Кб - ничего страшного, если размер L2 составляет 256 или 512К. Да и потом можно смешанный подход использовать - обрабатывать блочно по несколько сигнатур, затем повтор для другой группы сигнатур и т.д. Нужно только прикидывать суммарный размер памяти, чтобы блок данных и таблицы умещались в кэше.



> "i:=i+n; // сдвигаемся на длину сигны"

Ага, и в результате ничего не находим

Из факта совпадения или несовпадения первого и последнего символа, в общем случае не следует что не будет совпадения при смещениях 1..(n-1). Таблица скачков BM как раз и показывает на сколько можно макимум скакнуть при несовпадении и макимальный скачок = n только для тех символов, которых вообще нет в твоей сигнатуре. Твой вариант будет работать, если только первый символ сигны уникален, т.е. больше такого символа в сигнатуре нет. А в общем случае без таблицы ты можешь надежно перемещаться только на один символ

 

да нет, находим =)

я же проверяю первый и посл. байт... если не совпали, то сдвигаю... (работает вроде)

хм... а поподробнее

в исходеном примере всё делается так:

Код (Text):

1.  
2.   TIntVect = array [0..255] of Integer;
3.   TBMTable = array [0..0] of TIntVect;
4.   PBMTable = ^TBMTable;
5. ...
6.   GetMem(BMT,SizeOf(TIntVect)*Length(Data));
7.  

да длина меньше 255 =)

 

Hellspawn

это неправильно. Проверка первого и последнего байта не даёт гарантии, что можно смещаться сразу на размер сигнатуры. Именно для этого и существуют таблицы, чтобы из них получить максимально возможное смещение. А то, что у тебя "работает вроде" - это случайное стечение обстоятельств (определенные сигнатуры и определенные файлы). При других условиях будут возникать ошибки- сигнатура не будет найдена, хотя и будет существовать в файле.

И непонятно, чего ты зациклился на размерах таблиц и как их реализовывать. Зачем строить 400 таблиц, и держать их в памяти? Найди алгоритм, который сам строит таблицы, и не мучайся.

 

да это постройка таблиц значительно увеличивает время поиска... т.е. если их содать зранее, а не в цикле поиска, то всё будет гораздо быстрее...