1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.

Поиск строки в файле

Тема в разделе "Программирование", создана пользователем Voyager, 08.02.05.

  1. Voyager

    Voyager Активный участник

    3.066
    0
    Пишу программу. Есть проблема:
    Есть нетипизированный файл. Есть строка длиной 18 байтов. Нужно найти эту строку в файле (или найти максимальную длину части строки, которая встречается в файле).
    Вопрос думаю ясен.
    Так вот, сделал я этот поиск, но уж больно медленно он происходит. Знаю что можно его значительно ускорить. Есть ли варианты, алгоритмы?
     
  2. AlTk

    AlTk Читатель

    10.692
    0
    есть.
    1. алгоритм Боуера-Мура и его усовершенствования, связанные с размером строки, файла, алфавита и т.д. - скорее всего как раз для Вашего случая.
    2. есть еще алгоритм Кнута-Морриса-Пратта.
    если в файле есть начала строки, то эффективен 2, иначе 1. с другой стороны в этом случае 1 позволит найти максимальную длину части строки.

    если же Вы под частью строки понимаете любую непрерывную часть, необязательно начинающуюся с первого символа или заканчивающуюся на последнем, то тут придется еще помудрить.
     
  3. Гость

    Гость Гость

    У вас ошибка в третьей строчке. Потому и медленно работает.

    G100m
     
  4. Voyager

    Voyager Активный участник

    3.066
    0
    AlTk
    Смотрел эти алгоритм. Как Боуэра применить хз, так как он в основном для текстовых файлов применяется, а у меня нетипизированный.
    Строка начинается с первого символа. И ищется до того момента, пока найденное вхождение не будет такой же длины или наибольшее меньшее. Т. е. если ищем dqwrereet, а встречается только dqwrer, то эта строка dqwrer нам подходит.
     
  5. AlTk

    AlTk Читатель

    10.692
    0
    да какая разница. просто если файл текстовый, то под алфавитом будут пониматься все буквенные символы, а если файл нетипизированный - то есть набор байтов, алфавит будет составлять 0x00 ... 0xFF. вот и все. сравнивай1те байты, а не символы.
     
  6. Voyager

    Voyager Активный участник

    3.066
    0
    Ты бы пример функции привел бы :)
    У меня пока так:
    Код:
    Function FindBlock(Memory: TMemoryStream;block:Tblock;len:byte;pos:integer):integer;
    var
    sz,i,fpos,maxpos,ppos:integer;
    blocktmp:Tblock;
    flen,max:byte;
    ch:char;
    begin
    Result:=-1;
    ppos:=pos-4095;
    If ppos<0 then ppos:=0;
    max:=3;
    sz:=pos;
    While sz>ppos do
    begin
    sz:=sz-1;
    Memory.Seek(sz, soFromBeginning);
    Memory.Read(blocktmp,len);
    i:=0;
    flen:=0;
    While (i<len) and (blocktmp[i+1]=block[i+1]) do
    begin
    inc(i);
    flen:=i;
    end;
    If (flen>=max) and (flen>=3) then
    begin
    max:=flen;
    fpos:=sz;
    Result:=100*fpos+max;
    If flen=len then exit;
    end;
    end;
    
    Memory - файл висит в памяти.
    block - искомая строка.
    len - длина (18)
    pos - позиция в файле (ищем в 4 кб до данной позиции).
     
  7. AlTk

    AlTk Читатель

    10.692
    0
    никаких примеров я приводить не собираюсь.
     
  8. Voyager

    Voyager Активный участник

    3.066
    0
    А и не надо. :D
    Решил проблему, скорость работы увеличилась в 24 раза.
     
  9. ABM

    ABM Новичок

    13
    0
    По-моему, поиск умещается в одну строчку:

    while(length(Block)>0)and(pos(block,BlockFromFile)=0)do Block:=copy(Block,1,length(Block)-1);
    ----------------------------------------------------------------------------------------------------------------
    ShowMessage('Результат поиска: в позиции '+IntToStr(pos(block,BlockFromFile))+
    ' найдена подстрока - '+block);

    Ограничения - ищет только "левую" подстроку, весь файл должен поместиться в переменной BlockFromFile.
    Будет ли это работать медленне или быстрее, чем Function FindBlock, я не знаю.