Конференция "Начинающим" » Посоветуйте библиотеку для Delphi
 
  • Larin © (10.04.18 10:11) [0]
    Для быстрой работы с содержимым файла. Например, нужно открыть файл и быстро найти все вхождения определенной подстроки (или определенной последовательности байтов). Пример: формат файла неизвестен, но в файле в разных частях записаны JPEG-и и нужно их все извлечь (ищем FF D8 FF E0)

    Спасибо заранее.
  • aka © (10.04.18 10:20) [1]
    Читать файл блоками от начала до конца и считать вхождения.
  • Larin © (10.04.18 10:20) [2]
    Ищем все FF D8, при этом тут же находя концовку FF D9
  • Larin © (10.04.18 10:21) [3]

    > aka ©   (10.04.18 10:20) [1]


    каков размер блока?
  • aka © (10.04.18 10:25) [4]

    > вхождения определенной подстроки (или определенной последовательности
    > байтов)

    Это две разные вещи.
  • kilkennycat © (10.04.18 13:26) [5]

    >  (ищем FF D8 FF E0)

    вообще-то, не гарантирует, что это джпег. а так - [1] и никаких библиотек тут не надо.
  • Larin © (10.04.18 17:35) [6]

    > aka ©   (10.04.18 10:20) [1]
    > Читать файл блоками от начала до конца и считать вхождения.
    >


    А если возникнет такая ситуация: читаем блоками на 1024 байт и ищем подстроку "Hello my little world". А она попадает частично в один блок, а частично - в следующий.

    Как быть?
  • KilkennyCat © (10.04.18 18:08) [7]

    > читаем блоками на 1024 байт и ищем подстроку "Hello my little world". А она попадает частично в один блок, а частично
    > - в следующий.
    >
    > Как быть?

    увеличить блок вдвое. если читать по 2048 байт, то "Hello my little world" точно влазит целиком
  • aka © (10.04.18 18:13) [8]

    > А если возникнет такая ситуация: читаем блоками на 1024
    > байт и ищем подстроку "Hello my little world". А она попадает
    > частично в один блок, а частично - в следующий.
    >
    > Как быть?

    В [4] - ре ж писал, ты либо ищешь строки либо байты. Потому что грубо говоря строка может быть в разных кодировках, отсюда и байтами разными она будет кодироваться
  • aka © (10.04.18 18:19) [9]

    > увеличить блок вдвое. если читать по 2048 байт, то "Hello
    > my little world" точно влазит целиком

    Ну тоже не вариант. Например блок заканчивается на "Hello ", следующий начинается на "my little world" в алгоритме это нужно предусмотреть
  • kilkennycat © (10.04.18 18:37) [10]
    тогда 4096. теперь точно влезет, нутром чую.
  • aka © (10.04.18 18:56) [11]

    > тогда 4096.

    ну так скорее всего.
  • Dimka Maslov © (11.04.18 23:43) [12]
    По одному читать надо. По одному.
  • SergP © (12.04.18 17:12) [13]
    Читаем 2 блока, ищем. Когда прошли первый блок, грузим третий, прошли второй блок - грузим четвертый и т.д.
  • Redmond (13.04.18 10:50) [14]
    > Посоветуйте библиотеку для 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
  • kilkennycat © (13.04.18 20:14) [15]

    > С таким подходом единственный вариант гарантированно исключить
    > попадание на границу - тупо прочитать файл целиком. :3

    и это есть верное решение. и вся библиотека искомая - TFileStream да небольшая оптимизация поиска, реализация которой зависит от условий. Например, если ищем вхождение FF D8 и только его, то нет смысла читать побайтово, можно через один. Если искать строго FF D8 FF E0,  то можно читать лишь каждый 4-ый байт, что сокращает время тормознутых файловых операций.
    А вообще, по поиску паттернов и поиску вообще существует масса литературы. Например, полезно начать с https://www.livelib.ru/author/19753/latest-dzhulian-baknell
  • Redmond (13.04.18 20:44) [16]
    Верное? Весь файл? Ну допустим что в теории может и так, но на практике появляются проблемы вида - например файл весом 20+ гигов как-то не очень получится прочитать целиком.

    TFileStream это не библиотека... В случае с JPEG полагаю сперва надо искать FF, а уже при нахождении делать всякие дополнительные вещи.
  • Redmond (13.04.18 20:55) [17]
    Писал я утилиту с целевой этой самой == "Нетбук, 1GB DDR2, WinXP" - там если пытаться читать из файла блоками больше 256 метров - уже нехилые проблемы вылазили, а файлы гигабайтами мерялися.
  • SergP © (13.04.18 21:05) [18]

    > С таким подходом единственный вариант гарантированно исключить
    > попадание на границу - тупо прочитать файл целиком.


    А почему нельзя поблочно читать?
    если строка поиска не превышает размер блока, то выделяем буфер размером в 2 блока, и читаем туда блоки, бегаем кругами по буферу и ищем... Прочесали один блок, и сразу же на его место грузим очередной.
  • Redmond (13.04.18 21:27) [19]
    Можно и нужно. Это просто этакой ответ предыдущим человекам, которые силялися всё решить лишь увеличением буфера. (%

    Алгоритм желательно изначально проектировать так, чтоб размер буфера можно было легко менять (буквально одним действием, хотя бы константой в коде), и чтоб работало даже если задать размер буфера "1 байт". :3

    Зачем два блока? Всё равно заранее не определить понадобится ли второй, а всегда читать по два будет накладным. хотя... Может зависеть от задачи, надо обмозговать.
  • kilkennycat © (13.04.18 21:38) [20]

    > Redmond  


    > TFileStream это не библиотека..

    автор хочет библиотеку.


    > Верное? Весь файл?

    Да. Простое, но не оптимальное, об оптимизации далее говорил.
    Например, вариант "читаем блоками на 1024 байт и ищем подстроку "Hello my little world"",  можно реализовывать как чтение всего файла, но без загрузки в память. Читаем каждый 21-ый байт (с юникодом, разумеется, иначе), проверяем его на вхождение в массив байтов [H,e,l,o, ,m,y,i,t,w,r,d]. Если оно есть, мы легко получаем область вероятного нахождения сей подстроки, размером всего в 41 байт.
    Чтобы найти все вероятные области вхождения подстроки, нам требуется прочитать данных в 21 раз меньше, чем объем файла.
    Разумеется, это не прямое руководство к действию, во многих случаях это будет неоптимально,  и не является единственным (и даже законченным для этого случая) решением.
  • kilkennycat © (13.04.18 21:40) [21]
    Чет я как-то заумил. невыспался. но, думаю, мысля понятна ))
  • Игорь Шевченко © (14.04.18 11:11) [22]
    MMF наше все - просто и незатратно.
  • SergP © (14.04.18 12:45) [23]

    > Зачем два блока? Всё равно заранее не определить понадобится
    > ли второй, а всегда читать по два будет накладным. хотя.
    > .. Может зависеть от задачи, надо обмозговать.


    Ну 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;
    ...
  • Игорь Шевченко © (14.04.18 14:26) [24]
    SergP ©   (14.04.18 12:45) [23]

    Почитал бы ты МакКоннелла...
  • SergP © (14.04.18 15:09) [25]

    > Игорь Шевченко ©   (14.04.18 14:26) [24]
    >
    > SergP ©   (14.04.18 12:45) [23]
    >
    > Почитал бы ты МакКоннелла...


    Никогда не читал его.  С чего именно советуете начать?
  • Игорь Шевченко © (14.04.18 15:31) [26]
    SergP ©   (14.04.18 15:09) [25]


    > С чего именно советуете начать?


    "Совершенный код"
    https://www.ozon.ru/context/detail/id/138437220/
  • SergP © (20.04.18 00:14) [27]

    > Игорь Шевченко ©   (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], по крайней мере не меньше, а даже и чуть больше.
  • Игорь Шевченко © (20.04.18 10:32) [28]

    > Правда не было времени читать все. Пока только бегло переглянул.
    >  Но не совсем понял что именно Вам не понравилось в [23].
    >  


    Надо пересилить себя и прочитать
  • имя (16.06.18 00:51) [29]
    Удалено модератором
 
Конференция "Начинающим" » Посоветуйте библиотеку для Delphi
Есть новые Нет новых   [95536   +17][b:0.001][p:0.003]