Форум: "Основная";
Текущий архив: 2004.08.29;
Скачать: [xml.tar.bz2];
ВнизПоиск в бинарном файле по маске Найти похожие ветки
← →
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, то нужен алгоритм нечеткого поиска.
В приведенном тобой примере маска фиксированная, так как известно растояние в байтах между двумя известными частями маски.
← →
GuAV © (2004-08-13 15:22) [20]
> Любой файл (и двоичный тоже) в дельфи можно представить
> как одну строку. Считав его в эту строку целиком или частями.
Да. Полностью согласен, строки же тоже как бы массивы.
Читать можно так.
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 то вобше проблем небудет.
← →
Romkin © (2004-08-13 16:16) [22]http://algolist.manual.ru/search/esearch/
← →
Cosinus © (2004-08-13 16:17) [23]Всем спасибо. Все учту, тем более, когда ТАК ПОДРОБНО разжевали :))) Но лишним никогда не будет. Но писать буду уже видимо в понедельник. Еще раз спасибо.
← →
Cosinus © (2004-08-13 16:18) [24]>>Romkin © (13.08.04 16:16) [22]
http://algolist.manual.ru/search/esearch/
Интересует алгоритм с легким разжевыванием почему так, а не по другому. Я понимаю, что своей следующей фразой я вызову чуть ли не ненависть мастеров, но все же я скажу:)-"то, что описано на algolist.manual.ru я буду разбирать ОЧЕНЬ долго. К огромному сожалению, но как написано в одном из орехов - "Дело в том, что в наше время программисты редко являются специалистами в математике. К сожалению.". Это правда! И мое незаконченное, к сожалению пример.
← →
GuAV © (2004-08-13 16:30) [25]
> 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]);
Мы же про быстродействие...
← →
GrayFace © (2004-08-15 10:47) [26]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];
Это просто бред - если уж использовать строку, то она и быдет буфером, но строку использоветь не нужно.
← →
GrayFace © (2004-08-15 10:56) [27]Иллюстрацию сопируй в блокнот, или куда-нибудь еще, где у шрифта все символы одинаковой ширины.
Вот что я имел в виду:
Маска:_-------+-----+
Файл:_______________+________
Сдивигаем.
Маска:_______-------+-----+
Файл:_______________+________
Где под _ в маске подразумивается пробел.
← →
GrayFace © (2004-08-15 12:32) [28]В смысле вот так:
Маска:__-------+-----+
Файл:_______________+________
Сдивигаем.
Маска:________-------+-----+
Файл:_______________+________
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2004.08.29;
Скачать: [xml.tar.bz2];
Память: 0.53 MB
Время: 0.065 c