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

что-то инет проглючил - два сообщения.

С чего ты взял, что создание таблицы тормозит поиск? Какое отношение имеет её создание к поиску?

И зачем создавать таблицу внутри цикла поиска?

 

Да и вообще, построение таблиц только ускоряет поиск.

Они специально для ускорения и придуманы, эти таблицы.

Их же не от нехрен делать строят ))



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

И чем длинее сигнатура, тем больший выигрыш даёт применение таблицы.

 

Hellspawn

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

Во-первых, по сути ты проверяешь лишь первый байт, т.к. у тебя i:=i+n делается и при совпадении и при несовпадении последнего байта. Такой метод вообще не должен работать, т.к. может пропускать искомые сигнатуры - возьми любой пример:

Код (Text):

1. строка:    ххх[u]1[/u]98[u]12345[/u]ххх
2. сигнатура:    [u]1[/u]2345
3. i+n           .....12345 - пропуск !!!
4. БМ            ...[u]12345[/u]   - нашли

Во-вторых, такой бестабличный метод может работать правильно только в случае, когда делается проверка последнего байта и этот байт в сигнатуре больше не встречается - тогда при совпадении последнего и несовпадении первого мы можем сразу скакнуть на длину сигнатуры. Но такой метод будет значительно медленнее даже упрощенного БМ, т.к. у тебя большой скачок будет делаться только при совпадении байта (для случайных значений 0..255 вероятность совпадения ~ 1/256), а в остальных 255/256 случаях ты смещаешься на 1 символ как при простом "тупом" сканировании. Метод БМ позволяет скакать более чем на 1 символ при практически любом несовпадении (т.е. в 255/256 случаев) и средняя скорость поиска получается существенно больше.



О минимальном размере таблицы:

Во-первых, в TIntVect хранятся значения скачков <= n, поэтому при n < 256 можно использовать TByteVect = array[0..255] of Byte (а не integer)

Во-вторых, в БМ используются две идеи. Основная идея, это скачки по "bad char" - т.е. по несовпадению последнего символа, для ее реализации достаточно иметь только один массив TByteVector, т.е. всего 256 байт (= последнему столбцу твоей TBMTable). Вторая идея, это скачки по "bad suffix", т.е. когда идет совпадение группы последних символов, а затем несовпадение - поэтому вместо одного TByteVect используется таблица из n TByteVect, которая показывает насколько можно скакануть, при условии что было совпадение последних j символов. За исключением особых случаев эта идея работает значительно реже и дает меньший прирост скорости чем "bad char" - потому, что при случайном распределении байтов в файле вероятность совпадения группы быстро уменьшается с увеличением длины группы. Соответсвенно чем длиннее сигнатура тем менее эффективно (в среднем) работает этот метод - затраты памяти и время посторения таблицы велики, а толку мало, т.к. вероятность совпадения даже 4 символов уже достаточно маленькая, не говоря о 20 и т.п. Вывод: можно либо вообще отказаться от идеи "bad suffix" и использовать только "bad char" с одним массивом TByteVect или же ограничить длину суффикса, например 2-мя или 4-мя символами, тогда таблица будет состоять не из n векторов, а только из 2-х или 4-х.



Замечания о выборе сигнатуры:

БМ не панацея, он основан на статистике распределения символов в файле и в сигнатуре. Почему-то часто говорят только о длине сигнатуры (тем больше, тем лучше) и забывают о ее содержимом. А суть БМ в том, что он просматривает сигнатуру с конца и при несовпадении скачет на максимально возможную длину n-j, где j позиция символа в сигнатуре. Следовательно, быстрее будут обрабатываться те сигнатуры, у которых в конце расположены наименее "популярные" для данного файла символы, а популярные (включая маску "?") ближе к началу. Например, если взять сигнатуру "1234?6", то БМ лучше просто выкинуть на помойку, т.к. он в данном случае будет работать медленнее чем обычное сканирование (из-за "?" на предпоследней позиции мы всегда будем смещаться только на 1 символ - так лучше это делать явно, чем каждый раз брать 1 из таблицы). В этом случае лучше взять укороченную сигнатуру "1234" и проверять последний символ "6" отдельно, когда будет найден укороченный вариант. Аналогичная ситуация возникает и в случае "суперпопулярных" группирующихся символов, например нулей в PE-файлах или пробелов в форматированном тексте (inc,asm и т.п.). В данном случае также следует избегать нулей и пробелов в конце сигнатуры - лучше укоротить сигнатуру и использовать доп.постпроверку - это будет быстрее. Соответсвенно и наоборот, если сигнатура заканчивается на малопопулярную комбинацию, то можно использовать упрощенный БМ с одним простым массивом "bad char" на 256 символов, т.к. "bad suffix" тут практически ничего не даст кроме затарат памяти и времени на формирование таблицы.

 

Для начала можно просто увеличить буфер. И читать быстрее, и обновления реже будут происходить. Потоков не нужно.



и какой самый быстрый способ работы с файлами?

Драйвер. TFileStream эквивалентен OpenFile + ReadFile. У мэппинга есть доп. сервис и, соответственно, доп. расходы.



FreeMem(BMT[1]);

FreeMem(BMT[2]);

LfstFile.Free;

надо в finally запихнуть, лучше в единый (LfstFile создается перед try, BMT := 0 перед try и создаются в try)



cresta

с ReadFile получается 12 сигнатур - 120 мс

с MapView получается 12 сигнатур - 110 мс.

А не GetTickCount ли это засекалось?



Hellspawn

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

Если файл маленький, то да. Но на 7MB уже должно заметно ускорять.

 

А чем нужно было мерять? секундомером что-ли?

 

cresta

Если хочешь увидеть значимую разницу, то действительно секундомером

Т.е. тем же GetTickCount, но время обработки должно составлять единицы-десятки секунд, иначе сказывается погрешность метода измерения - хоть GetTickCount и выдает число миллисекунд, но считывает их по таймеру (или когда планировщик разрешит, фиг его знает) поэтому точнее 10-15 мс получить рез-т невозможно. "Проскальзывание" одного 10мс интервала роли не играет - фиг знает когда и какой системный поток проснется и как быстро сделает свои дела. Соответственно - при 100 мс это будет ~10%, а при 300 мс всего лишь ~3% и т.д.



Хотя ты и сам наверняка все знаешь

Меня в том посте больше другое "задело":

> "предыдущий опыт с сортировкой файлов ReadFile был в 2-3 раза быстрее"

Мой предыдущий опыт подсказывает, что при размерах файлов до единиц-десятков Мб существенной разницы между ReadFile и MMF при последовательном чтении нет, так что "суперскорость" и "супертормоза" MMF - это какие-то выдумки.

Хотя надо бы действительно сравнить их при случайном доступе к данным, т.е. ReadFile ес-но читает все подряд и затем уже работает чисто с памятью, а вот MMF вынужден подгружать страницы в случайном порядке и наверное может проигрывать на перемещении указателя файла.

Хотя 2-3 раза могли дать и не вполне корректные сравнения - повторные чтения, когда данные после ReadFile оседают в файловом кэше и ес-но повторно "читаются" намного быстрее

 

я прекрасно знаю о дисретности 15 мс, да и результат был получен усреднением, так что всё в порядке. Чтобы примерно оценить - вполне достаточно GetTickCount'а.

А точно измерить невозможно. Сам знаешь, что более или менее точно покажет rdtsc, но только если поток не был прерван планировщиком.

А на интервалах времени порядка 10 мс поток будет прерван неоднократно, и никакой точности от rdtsc всё равно не получишь, так что смысла замарачиваться с ним абсолютно никакого. GetTickCount даёт вполне объективный результат.



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

А вешать в граммах - 2 или 2,001 раза - это ни к чему. Но примерный порядок был такой.

 

значит так, я почти получил то, что хотел =) осталось только одно, переписать вот эту процедуру, чтоб она работала только с PBMTable = array [0..255] of Byte...

т.е. только "bad char" =) может кто подскажет как надо, а то я не до конца алго понимаю.. поэтому не получается поправить..

Код (Text):

1.  
2. procedure WCMakeBMTable( var BMT : PBMTable;const P : String);
3. var
4.   i, j, lp, MaxShift, CurShift, SufPos : Integer;
5.   Suffix : String;
6. begin
7.   lp := Length(P);
8.   if P[lp] = '?' then
9.     for i := 0 to 255 do BMT^[lp-1][i] := 0
10.   else
11.   begin
12.     for i := 0 to 255 do BMT^[lp-1][i] := lp;
13.        for i := lp downto 1 do
14.         if BMT^[lp-1][Byte(P[i])] = lp then BMT^[lp-1][Byte(P[i])] := lp - i;
15.   end;  MaxShift := lp;
16.   for i := lp - 1 downto 1 do
17.   begin
18.     SetLength(Suffix, lp - i);
19.     Move(P[i+1], Suffix[1], lp - i);
20.     if WCBeginsWith(Suffix, P) then MaxShift := i;
21.     if P[i] = '?' then
22.       for j := 0 to 255 do BMT^[i-1][j] := 0
23.     else for j := 0 to 255 do
24.     begin
25.       CurShift := MaxShift;
26.       SetLength(Suffix, lp - i + 1);
27.       Suffix[1] := Char(j);
28.       Move(P[i + 1], Suffix[2], lp - i );
29.       SufPos := WCFindRightmost(P, Suffix, lp - 1);
30.       if SufPos <> 0 then CurShift := i - SufPos;
31.       BMT^[i-1][j] := CurShift;
32.     end;
33.   BMT^[i-1][Byte(P[i])] := 0;
34.   end;
35. end;
36.  

 

cresta

я прекрасно знаю о дисретности 15 мс, да и результат был получен усреднением, так что всё в порядке. Чтобы примерно оценить - вполне достаточно GetTickCount'а.

А я всегда делаю цикл. Хотя есть и достаточно точный метод - QueryPerformenceCounter.



leo

Хотя надо бы действительно сравнить их при случайном доступе к данным, т.е. ReadFile ес-но читает все подряд и затем уже работает чисто с памятью, а вот MMF вынужден подгружать страницы в случайном порядке и наверное может проигрывать на перемещении указателя файла.

По-моему, при последовательном чтении выигрышь должен быть существеннее - с ReadFile можно обойтись 1-м фиксированным буфером и перезаписывать его, а MMF каждый блок грузит в отдельную память.



Hellspawn

Не до конца понимаю, что требуется сделать с этим кодом.

 

в данном случае BMT^[i-1][j] - это двумерный массив.. (таблица)

как было сказано выше, реализующий "bad char" и "bad suffix" вот второе можно убрать за ненадобностью, т.е. обойтись одномерным массивом =)

 

Цикл - источник неправильных результатов.

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

 

Hellspawn

Дык в приведенной же тобой ссылке первым делом рассматривается упрощенный вариант БМ с простым массивом. Нужно только добавить обработку '?', к примеру так:

Код (Text):

1. type
2.   TBMShifts = array[char] of byte; //или of integer, если не нужна экономия
3. procedure MakeBMShift(var BMT:TBMShifts;const P:string);
4. var
5.   c:char; j,n:integer;
6. begin
7.   n:=Length(P);
8.   for c:=#0 to #255 do BMT[c]:=n;
9.   for j:=n-1 downto 1 do  //!!! тут д.б. от (n-1)
10.     if P[j] = '?' then
11.     begin
12.       for c:=#0 to #255 do
13.         if BMT[c] = n then
14.           BMT[c]:=n-j;
15.       Exit; //дальше смотреть нечего
16.     end
17.     else
18.     if BMT[P[j]] = n then
19.       BMT[P[j]]:=n-j;
20. end;

Надеюсь ты понимаешь, что наличие символа '?' снижает эффективность метода - максимальный скачок ограничивается расстоянием от ближайшего к концу символа '?' до конца сигнатуры



GrayFace

> "По-моему, при последовательном чтении выигрышь должен быть существеннее..."

Если ты про отказы страниц, то легко показать, что обработка отказов занимает не более ~5% от времени чтения файла. Рассуждения на эту тему см. здесь. Практически, при последовательном чтении "небольших" файлов потери MMF по сравнению с блочной обработкой не превышают 10% для NO_BUFFERING и менее для обычного буферированного чтения (если конечо, данные уже не находятся в файловом кэше, тогда ReadFile может быть и в 2-3 раза быстрее, но это нечестно А серьезные тормоза начинают возникать, когда MMF не хватает физ.памяти

 

cорри туплю, с этой учебой фиг выспишься...

про маску мне всё ясно... но по-моему это самый приемлимый вариант...

 

Hellspawn

Кстати, забыл пояснить - в той статейке приведен совсем упрощенный вариант - для последнего символа P[n] устанавливается скачок n-n=0 и при несовпадении суффикса (окончания) делается приращение Pos на 1.

Правильнее делать в MakeBMShift цикл не for j:=n downto 1, а от j:=n-1 - в этом случае последнему символу сигнатуры будет присвоено смещение не 0, а от 1 до n в зависимости от того, встречается этот символ еще или нет. Соответственно в BMSearch при несовпадении суффикса нужно делать не inc(Pos), а inc(Pos,BMT[P[n]])



Говоришь, про маску все ясно, а сам постом раньше рассматривал вариант P[lp] = '?' - при котором простой БМ будет давать проигрыш по сравнению с простым сканированием (также как и при P[lp-1] = '?')

Если нужны '?' на малых расстояниях от конца сигнатуры, то следует подумать какие символы могут стоять на этих позициях и использовать несколько усложненный вариант с обработкой ограниченного множества символов (дельфийский set of char) или же проще - искать укороченную сигнатуру

 

Hellspawn
Кто-нибудь может написать рабочие процедуры алгоритма Боера-Мура(простой вариант) с использованием масок......намучился совсем....улучшенный вариант не подходит а в ростой не могу вставить использование масок('?')....

 

Garry_lonsdale

А в чем проблема ? Алгоритм заполнения таблицы см.выше в посте #52 - от обычного отличается тем, что делается доп.проверка символа на '?' и в случае совпадения выходим из цикла и заменяем в таблице все значения n на n-j (на асме это будет просто текущее значение счетчика ecx при выходе из цикла). Плюс изменяется проверка строки в случае совпадения последнего символа - в обычном алгоритме проверяются все n символов строки и при несовпадении делается возврат к поиску символа, а тут доп.делается проверка символа шаблона на '?' - если равно, то продолжаем сравнение строк, если нет, то возврат к поиску

PS: про (не)эффективность использования '?' в алгориме БМ я уж повторяться не стану, думаю и так ясно

 

HellSpawn
Глянь в сторону FastCodeProject.org. Там в принципе то что ты ищешь уже есть в оптимизированном виде. и не только. Конкретно:
http://fastcode.sourceforge.net/challenge_content/rtl_replcmnt_pkg.html вместе с описаловом

 

хех пасибки =) тока я давно уже всё реализовал,
просто сделал несколько видов поиска (с маской, без маски)
и в зависимости от задачи юзаю нужный.

з.ы. проект интересный на досуге поиграюсь.