Поиск в бинарном файле по маске

← →
Cosinus © (2004-08-12 14:23) [0]

Я как то задавал уже этот вопрос, но ситуация сложилась так, что только сейчас я к нему вернулся. Мне посоветовали регулярные выражения, но что то я не нашел ничего более-менее понятного, единственное, что я нашел - это "TRegExpr - Freeware Регулярные Выражения для Delphi", но при ближайшем рассмотрении оказалось, что это мне не подходит, потому что " Now pascal-strings converted into PChar, so you can"t find r.e. in strings with #0 -chars.". Может кто подскажет что-нибудь?

← →
GrayFace © (2004-08-12 14:42) [1]

Можно посмотреть исходники MatchesMask.

← →
GuAV © (2004-08-12 14:45) [2]

> Поиск в бинарном файле по маске

Как понимать сабж? Искать по маске and с которой ничё не поменяет? Искать по маске or с которой ничё не поменяет? Имхо, руками сделать не долго...

← →
Cosinus © (2004-08-12 14:59) [3]

Хм... Объясню поподробнее. Допустим у меня есть файл размером 16М и с расширением (и содержанием!:)) ".BIN". Так вот я хочу в нем искать строки вида
#$38+#$4e+#$00+3 любых байта+#$ff+#$ff+#$4a.

← →
GuAV © (2004-08-12 15:09) [4]

в применении к GuAV © (12.08.04 14:45) [2]
#$38+#$4e+#$00+#FF+#FF+#FF+#$ff+#$ff+#$4a. - and маска
#$38+#$4e+#$00+#00+#00+#00+#$ff+#$ff+#$4a. - or маска

такое я делал ещё на ТР, поверь, совсем не сложно.

← →
Cosinus © (2004-08-12 15:21) [5]

>>GuAV ©
По-моему ты что то не так понимаешь.
#$38+#$4e+#$00+3 любых байта+#$ff+#$ff+#$4a - это и есть маска. А искаться все это должно в 16-ти метровом файле. Результатом поиска должно быть во-первых адресс в файле, во вторых ВСЕ подходящие под это условия строки.

← →
Cosinus © (2004-08-12 16:30) [6]

>>GuAV © (12.08.04 15:09) [4]
Или это я не понимаю?
Нельзя ли раскрутить немного, то, что ты написал?

← →
Erik1 (2004-08-12 16:59) [7]

Сначала тебе придется загрузить в память блок, а уж после в памяти искать. Найдеш в памяти адрес в котором содержится #$38+#$4e+#$00 задавай вопрос дальше.

← →
Cosinus © (2004-08-12 18:05) [8]

>>Erik1
Да понятно все это про память то..
Это пример просто.
Сейчас это реализовано так -
1) Побайтово читая блок ищем #$38
2) Нашли, смотрим следующий байт, если он #$4е, то смотрим дальше и т.д.
Мне в данном случае критична скорость, поэтому интересен как сам алгоритм поиска, так и его исполнение. То, что у меня на данный момент есть (ищет строку длинной от N символов до M, в которой только цифры(в ее ASCII представлении) и несколько спец. символов, например "@") находит все вхождения в 3-ех метровом файле (их там примерно 7500)примерно за 24 сек (N=2, M=30). Это много.

← →
GuAV © (2004-08-12 18:28) [9]

Алгоритм в студию.

← →
QQ © (2004-08-12 18:55) [10]

Такие вещи делаются при помощи конечных автоматов.
Просто не получится - либо медленно - либо забибикаешься писать.

← →
Cosinus © (2004-08-13 11:44) [11]

Заранее прошу прощения за такой кривой листинг, просто я вчера пытался оптимизировать, перелопатил почти целиком - стало только хуже. Сейчас пытался вернуться к первому варианту, вроде так было(по крайней мере кол-во замеренного времени то же). Все функции запихал в тело, мне так вспоминать проще было. Если текст совершенно не удобочитаем, изменю и выложу.
var counter,PB_count:int64; Z : set of #$20..#$40; buffer:PChar; code:string; LenCode:byte; ColCode:integer; begin Reslts.Clear; reslts.lines.add(timetostr(time)); PB1.Position:=0; Code:=""; ColCode:=0; GetMem(buffer,$01); counter:=0; PB_count:=0; Z:=["0".."9","*","#"]; Reslts.Lines.BeginUpdate; while counter<BinSize do begin repeat Mem.ReadBuffer(buffer^,$01); Application.ProcessMessages; inc(counter); Inc(PB_count); If PB_count=100 then PB_count:=0; PB1.StepBy(1); Code:=Code+String(Buffer[0]); until (not (buffer[0] in Z{["0".."9",#$23,#$2a]})) or (counter>=BinSize); LenCode:=length(code)-1; If (LenCode>=Min) and (LenCode<=Max) then begin CheckCode(copy(Code,1,LenCode),LenCode,counter); Inc(ColCode); end; if counter>=BinSize then break; Code:=""; end; Reslts.Lines.EndUpdate; FreeMem(buffer); Mem.Free; Reslts.lines.add(timetostr(time)); showmessage("Finding "+IntToStr(ColCode)+" codes"); end;

← →
GrayFace © (2004-08-13 12:32) [12]

Для не очень большой строки можно так: Вначале ищешь, начиная с конца, в строке последний символ. Нашел - пишешь в array[1] расстояние от этого до последнего, не нашел - пишешь длину строки, потом ищешь 2 последних символа и т.д.
Во время поиска: (l - длина строки, L - длина файла)
N:=0;
while...
сравниваешь [N+l] в файле с последним элементом строки. Не равны => N:=N+a[1]. Равны=> сравниваешь [N+l-1] и т.д.
Строка, наверняка гораздо меньше файла и хранится в аперативке, поэтому этот алгоритм, придуманный мной, должен отлично подойти.

← →
GrayFace © (2004-08-13 12:38) [13]

> придуманный мной

Точнее мной на основе другого, вкотором использовался массив на 256 символов.

PS: Читать такой файл лучше большими блоками.

← →
GrayFace © (2004-08-13 12:44) [14]

> сравниваешь [N+l-1] и т.д.
Точнее:
сравниваешь [N+l-1] с предпоследним символом строки и т.д.

← →
Cosinus © (2004-08-13 12:54) [15]

>>GrayFace ©
Спасибо. Попробую въехать в алгоритм. Просто приехал coWorker из другого города... привез... да еще пятница... ;) Да еще и начальство усилинно предлагает "забить на эту ..... , и начать отдыхать". Сам бог велел.:)))))
ЗЫ Напиши, пожалуста, математический алгоритм, без какого-либо уклонения в программинг. Заранее спасибо.

← →
Smithson © (2004-08-13 13:14) [16]

Если маска фиксироавная, то можно использовать Pos. Он работает с null-содержащими строками.

← →
Cosinus © (2004-08-13 15:00) [17]

>>Smithson ©
Что я не очень понимаю, как приспособить POS к маске в файле... Он же ищет вроде как совершенно определенную строку(то есть как приспособить мысли есть, но по-моему это будет совсем не быстро(время исполнения я имею ввиду)).
У меня такое ощущение, что придется писать свой компонент(или модуль), потому что нужно это ОЧЕНЬ часто...
Но для этого нужны алгоритмы. Если так, то вопрос, где найти информацию по поиску в файле по маске или что-либо похожее? Интересует алгоритм с легким разжевыванием почему так, а не по другому. Я понимаю, что своей следующей фразой я вызову чуть ли не ненависть мастеров, но все же я скажу:)-"то, что описано на algolist.manual.ru я буду разбирать ОЧЕНЬ долго. К огромному сожалению, но как написано в одном из орехов - "Дело в том, что в наше время программисты редко являются специалистами в математике. К сожалению.". Это правда! И мое незаконченное, к сожалению пример.

← →
GuAV © (2004-08-13 15:09) [18]

> Mem.ReadBuffer(buffer^,$01);

По одному ? читай в буфер этак $1000 и ищи в массиве.
И тогда читать можно прямо с файла.

> Application.ProcessMessages;

После каждого байта ? LOL. Это - главные тормоза.

> Code:=Code+String(Buffer[0]);

Осознаёшь ваще, что творишь ?

И код таки напутан, разобраться несколько затруднительно.

И где Try.. finally ?

← →
Smithson © (2004-08-13 15:10) [19]

На самом деле забуть про файл и строки. Любой файл (и двоичный тоже) в дельфи можно представить как одну строку. Считав его в эту строку целиком или частями. А дальше тебе нужны алгоритмы четкого или нечеткого поиска в строке. Вот их и ищи. Соответсвенно, если маска фиксирована, то нужен алгоритм четгоко поиска. Если маска переменная или содержит wildcard, то нужен алгоритм нечеткого поиска.

В приведенном тобой примере маска фиксированная, так как известно растояние в байтах между двумя известными частями маски.

> Любой файл (и двоичный тоже) в дельфи можно представить
> как одну строку. Считав его в эту строку целиком или частями.

Да. Полностью согласен, строки же тоже как бы массивы.
Читать можно так.
SetLength(S,$1000);
BlockRead(F,S[1],$1000);

← →
Erik1 (2004-08-13 15:49) [21]

Незабудь про манипуляции с памятью, если надо записать 1000 байтов то:
SetLength(S, 1000);
for i := 1 to 1000 do
S[i] := Buffer[0];
Но думаю, что при правильном алгоритме тебе непридется работать с байтами. Учти, что обратится к Integer быстрее чем к byte, хотя это оптимизатор исправит. А если использовать Pos то вобше проблем небудет.

http://algolist.manual.ru/search/esearch/

Всем спасибо. Все учту, тем более, когда ТАК ПОДРОБНО разжевали :))) Но лишним никогда не будет. Но писать буду уже видимо в понедельник. Еще раз спасибо.

>>Romkin © (13.08.04 16:16) [22]
http://algolist.manual.ru/search/esearch/
Интересует алгоритм с легким разжевыванием почему так, а не по другому. Я понимаю, что своей следующей фразой я вызову чуть ли не ненависть мастеров, но все же я скажу:)-"то, что описано на algolist.manual.ru я буду разбирать ОЧЕНЬ долго. К огромному сожалению, но как написано в одном из орехов - "Дело в том, что в наше время программисты редко являются специалистами в математике. К сожалению.". Это правда! И мое незаконченное, к сожалению пример.

> for i := 1 to 1000 do
> S[i] := Buffer[0];

Это что? Если имелось ввиду
for i := 1 to 1000 do
S[i] := Buffer[i];
то Move(Buffer[1], S[1], 1000);
, а если как есть, то
FillChar(S[1], 1000, Buffer[0]);

Мы же про быстродействие...

Cosinus © (13.08.04 12:54) [15]
> ЗЫ Напиши, пожалуста, математический алгоритм, без
> какого-либо уклонения в программинг. Заранее спасибо.

А как? Я алгоритмы умею только программировать и объяснять на пальцах. Здесь пальцев не хватает.

> Интересует алгоритм с легким разжевыванием почему так, а не по другому.

Попытаюсь разжевать. У нас сошлись n символов на конце строки, n+1 - нет. Чем могут быть эти n символов? Концом строки или какой-то частью. Если эта последовательность символов не встречается на определенном промежутке(длина которого есть в массиве под номером n), то мы смело можем сдвигаться на длину этого промежутка, т.к. если сдвинуться меньше, то совпавший участок попадет в промежуток, с котором он заведомо не совпадает.
Примерно так:

Маска: -------+-----+
Файл:_______________+________

Сдивигаем.

Маска: -------+-----+
Файл:_______________+________

Erik1 (13.08.04 15:49) [21]
Придется читать по байтам по двум причинам:
1) Некоторые байты могут быть любыми(хотя с этим можно поступить, как советовал GuAV [4], но выигрыш не большой - 2 сравнения вместо 4)
2) У алгоритмы, типа моего значительно уменьшается эффективность.
Читать я предлагаю так:
Заполняем первую половину буфера, при нужде заполняем вторую, а перевая еще понадобится, ведь строка сравнивается справа налево. Далее заполняем первую половину буфера и т.д. Одно ограничение: строка должна быть меньше половины буфера.

>for i := 1 to 1000 do
> S[i] := Buffer[0];

Это просто бред - если уж использовать строку, то она и быдет буфером, но строку использоветь не нужно.

Иллюстрацию сопируй в блокнот, или куда-нибудь еще, где у шрифта все символы одинаковой ширины.
Вот что я имел в виду:
Маска:_-------+-----+
Файл:_______________+________

Сдивигаем.

Маска:_______-------+-----+
Файл:_______________+________

Где под _ в маске подразумивается пробел.

В смысле вот так:
Маска:__-------+-----+
Файл:_______________+________

Сдивигаем.

Маска:________-------+-----+
Файл:_______________+________

Поиск в бинарном файле по маске Найти похожие ветки