-
Для быстрой работы с содержимым файла. Например, нужно открыть файл и быстро найти все вхождения определенной подстроки (или определенной последовательности байтов). Пример: формат файла неизвестен, но в файле в разных частях записаны JPEG-и и нужно их все извлечь (ищем FF D8 FF E0)
Спасибо заранее.
-
Читать файл блоками от начала до конца и считать вхождения.
-
Ищем все FF D8, при этом тут же находя концовку FF D9
-
> aka © (10.04.18 10:20) [1]
каков размер блока?
-
> вхождения определенной подстроки (или определенной последовательности
> байтов)
Это две разные вещи.
-
> (ищем FF D8 FF E0)
вообще-то, не гарантирует, что это джпег. а так - [1] и никаких библиотек тут не надо.
-
> aka © (10.04.18 10:20) [1]
> Читать файл блоками от начала до конца и считать вхождения.
>
А если возникнет такая ситуация: читаем блоками на 1024 байт и ищем подстроку "Hello my little world". А она попадает частично в один блок, а частично - в следующий.
Как быть?
-
> читаем блоками на 1024 байт и ищем подстроку "Hello my little world". А она попадает частично в один блок, а частично
> - в следующий.
>
> Как быть?
увеличить блок вдвое. если читать по 2048 байт, то "Hello my little world" точно влазит целиком
-
> А если возникнет такая ситуация: читаем блоками на 1024
> байт и ищем подстроку "Hello my little world". А она попадает
> частично в один блок, а частично - в следующий.
>
> Как быть?
В [4] - ре ж писал, ты либо ищешь строки либо байты. Потому что грубо говоря строка может быть в разных кодировках, отсюда и байтами разными она будет кодироваться
-
> увеличить блок вдвое. если читать по 2048 байт, то "Hello
> my little world" точно влазит целиком
Ну тоже не вариант. Например блок заканчивается на "Hello ", следующий начинается на "my little world" в алгоритме это нужно предусмотреть
-
тогда 4096. теперь точно влезет, нутром чую.
-
> тогда 4096.
ну так скорее всего.
-
По одному читать надо. По одному.
-
Читаем 2 блока, ищем. Когда прошли первый блок, грузим третий, прошли второй блок - грузим четвертый и т.д.
-
> Посоветуйте библиотеку для Delphiгм? Не думаю что такие есть... > А если возникнет такая ситуация: читаем блоками на 1024
> байт и ищем подстроку "Hello my little world". А она попадает
> частично в один блок, а частично - в следующий.
> Как быть?Ватсон? Ну это же элементарно! Вы знаете номер блока? Вы знаете позицию блока? Знаете позицию в которой предположительно найдено совпадение? Просто вычислить новое смещение же! :) > тогда 4096. теперь точно влезет, нутром чую.Академики шутить изволят? С: Увеличение размера блока лишь уменьшают вероятность, но не исключают её. С таким подходом единственный вариант гарантированно исключить попадание на границу - тупо прочитать файл целиком. :3 > Ищем все FF D8, при этом тут же находя концовку FF D9Нюансы для размышлений: FF D8 - вовсе не обязательно начало файла JPEG, FF D9 - вовсе не обязательно конец файла JPEG, FF D8 и FF D9 могут попасться и в самом (остальном) файле и вообще не иметь отношения к JPEG. P.S. http://pda.delphimaster.net/?id=1459559016&n=7
-
> С таким подходом единственный вариант гарантированно исключить
> попадание на границу - тупо прочитать файл целиком. :3
и это есть верное решение. и вся библиотека искомая - TFileStream да небольшая оптимизация поиска, реализация которой зависит от условий. Например, если ищем вхождение FF D8 и только его, то нет смысла читать побайтово, можно через один. Если искать строго FF D8 FF E0, то можно читать лишь каждый 4-ый байт, что сокращает время тормознутых файловых операций. А вообще, по поиску паттернов и поиску вообще существует масса литературы. Например, полезно начать с https://www.livelib.ru/author/19753/latest-dzhulian-baknell
-
Верное? Весь файл? Ну допустим что в теории может и так, но на практике появляются проблемы вида - например файл весом 20+ гигов как-то не очень получится прочитать целиком.
TFileStream это не библиотека... В случае с JPEG полагаю сперва надо искать FF, а уже при нахождении делать всякие дополнительные вещи.
-
Писал я утилиту с целевой этой самой == "Нетбук, 1GB DDR2, WinXP" - там если пытаться читать из файла блоками больше 256 метров - уже нехилые проблемы вылазили, а файлы гигабайтами мерялися.
-
> С таким подходом единственный вариант гарантированно исключить
> попадание на границу - тупо прочитать файл целиком.
А почему нельзя поблочно читать?
если строка поиска не превышает размер блока, то выделяем буфер размером в 2 блока, и читаем туда блоки, бегаем кругами по буферу и ищем... Прочесали один блок, и сразу же на его место грузим очередной.
-
Можно и нужно. Это просто этакой ответ предыдущим человекам, которые силялися всё решить лишь увеличением буфера. (%
Алгоритм желательно изначально проектировать так, чтоб размер буфера можно было легко менять (буквально одним действием, хотя бы константой в коде), и чтоб работало даже если задать размер буфера "1 байт". :3
Зачем два блока? Всё равно заранее не определить понадобится ли второй, а всегда читать по два будет накладным. хотя... Может зависеть от задачи, надо обмозговать.
-
> Redmond
> TFileStream это не библиотека..
автор хочет библиотеку.
> Верное? Весь файл?
Да. Простое, но не оптимальное, об оптимизации далее говорил.
Например, вариант "читаем блоками на 1024 байт и ищем подстроку "Hello my little world"", можно реализовывать как чтение всего файла, но без загрузки в память. Читаем каждый 21-ый байт (с юникодом, разумеется, иначе), проверяем его на вхождение в массив байтов [H,e,l,o, ,m,y,i,t,w,r,d]. Если оно есть, мы легко получаем область вероятного нахождения сей подстроки, размером всего в 41 байт.
Чтобы найти все вероятные области вхождения подстроки, нам требуется прочитать данных в 21 раз меньше, чем объем файла.
Разумеется, это не прямое руководство к действию, во многих случаях это будет неоптимально, и не является единственным (и даже законченным для этого случая) решением.
-
Чет я как-то заумил. невыспался. но, думаю, мысля понятна ))
-
MMF наше все - просто и незатратно.
-
> Зачем два блока? Всё равно заранее не определить понадобится
> ли второй, а всегда читать по два будет накладным. хотя.
> .. Может зависеть от задачи, надо обмозговать.
Ну 2 блока ИМХО нужно иметь в памяти потому что концовка искомой строки может оказаться не в том блоке что и начало. Но читать по 2 блока я и не предлагал, это буфер размером на 2 блока должен быть, чтобы когда поиск в очередном блоке закончен, и мы переходим к следующему блоку, на место уже "прочесаного" блока грузился очередной. Т.е. просмотрели первый блок, переходим ко второму, и сразу на место первого блока грузится третий. Просмотрели второй блок, переходим к третьему, а на место второго грузится четвертый и т.д.
т.е. что-то типа этого (в файле filename ищется подстрока s и возвращается позиция первого вложения если найдена, или -1 если такое не найдено:
Написано абы как, под влиянием значительного кол-ва пива, но на работоспособность проверено. Исключительно в целях объяснения мысли, указаной в SergP © (12.04.18 17:12) [13]. Для практического применения следует дорабатывать напильником.
...
var
buffer:array[0..8191] of byte;
...
function SearchFirst(filename,s:string):integer;
var
d:integer;
f:file;
pos:integer;
i:integer;
fsize:integer;
flag:boolean;
begin
AssignFile(f,filename);
Reset(f,1);
fsize:=filesize(f);
reset(f,4096);
blockread(f,buffer[0],1,d);
for result:=0 to fsize-length(s) do
begin
if result and 4095 = 0 then blockread(f,buffer[result and 4096 xor 4096],1,d);
pos:=result and 8191;
if buffer[pos]=ord(s[1]) then
begin
flag:=true;
for i:=2 to length(s) do
begin
pos:=(pos+1) and 8191;
if buffer[pos]<>ord(s[i]) then
begin
flag:=false;
break;
end;
end;
if flag then
begin
CloseFile(f);
Exit;
end;
end;
end;
result:=-1;
CloseFile(f);
end;
...
-
SergP © (14.04.18 12:45) [23]
Почитал бы ты МакКоннелла...
-
> Игорь Шевченко © (14.04.18 14:26) [24]
>
> SergP © (14.04.18 12:45) [23]
>
> Почитал бы ты МакКоннелла...
Никогда не читал его. С чего именно советуете начать?
-
-
> Игорь Шевченко © (14.04.18 14:26) [24]
>
> SergP © (14.04.18 12:45) [23]
>
> Почитал бы ты МакКоннелла...
Нашел, скачал. Правда не было времени читать все. Пока только бегло переглянул. Но не совсем понял что именно Вам не понравилось в [23]. Я и не писал что то код для непосредственного использования. Просто хотел показать как я вижу возможность использования примитивного алгоритма поиска в файле, при условии его поблочного чтения...
А что касается алгоритма и пр. то вот ради интереса решил проверить как будет работать КМП (Алгоритм Кнута — Морриса — Пратта)
плюс
> Игорь Шевченко © (14.04.18 11:11) [22]
>
> MMF наше все - просто и незатратно.
function SearchFirstKMP(const filename,substring:string):integer;
var
hfile,hmap:THandle;
fSizeL,fSizeH:dword;
pData:pointer;
P:array of word;
i,j:integer;
SubstSize:integer;
ch:Char;
begin
Result:=-2;
hfile:=CreateFile(pansichar(filename),GENERIC_READ,FILE_SHARE_READ,nil,OPEN_EXIS TING, 0,FILE_FLAG_SEQUENTIAL_SCAN);
if hfile<>INVALID_HANDLE_VALUE then
begin;
fSizeL:=GetFileSize(hFile, @fSizeH);
{
// С файлами размером более 2 Гб заморачиваться не будем. игнорируем
if (fsizeH<>0) or (fSizeL and $80000000 > 0) then
begin
FileClose(hfile);
result:=-3;
Exit;
end;
}
hmap:=CreateFileMapping(hFile,nil,PAGE_READONLY,fSizeH,fSizeL,nil);
if hMap <> 0 then
begin
pData:=MapViewOfFile(hmap,FILE_MAP_READ,0,0,0);
if pData<>nil then
begin
// КМП - подготовка
SubstSize:=length(substring);
SetLength(P, SubstSize+1);
P[1]:=0;
j:=0;
for i:=2 to SubstSize do
begin
while (j>0) and (Substring[j+1] <> Substring[i]) do j:=P[j];
if Substring[j+1] = Substring[i] then inc(j);
P[i]:=j;
end;
//КМП - поиск
j := 0;
result:=-1;
for i:=0 to fsizeL-1 do
begin
ch:=pchar(pointer(cardinal(pData)+i))^;
while (j>0) and (SubString[j+1]<>ch) do j:= P[j];
if Substring[j+1] = ch then inc(j);
if j = SubstSize then
begin
result := i-SubstSize+1;
break;
end;
end;
UnmapViewOfFile(pData);
end;
CloseHandle(hmap);
end;
FileClose(hfile);
end;
end;
Возможно тестовый пример оказался неудачным, но время выполнения получилось почти такое же как и в [23], по крайней мере не меньше, а даже и чуть больше.
-
> Правда не было времени читать все. Пока только бегло переглянул.
> Но не совсем понял что именно Вам не понравилось в [23].
>
Надо пересилить себя и прочитать
-
Удалено модератором
|
Есть новые 
Нет новых [118451 +42][b:0][p:0.001]