Пишу программу. Есть проблема: Есть нетипизированный файл. Есть строка длиной 18 байтов. Нужно найти эту строку в файле (или найти максимальную длину части строки, которая встречается в файле). Вопрос думаю ясен. Так вот, сделал я этот поиск, но уж больно медленно он происходит. Знаю что можно его значительно ускорить. Есть ли варианты, алгоритмы?
есть. 1. алгоритм Боуера-Мура и его усовершенствования, связанные с размером строки, файла, алфавита и т.д. - скорее всего как раз для Вашего случая. 2. есть еще алгоритм Кнута-Морриса-Пратта. если в файле есть начала строки, то эффективен 2, иначе 1. с другой стороны в этом случае 1 позволит найти максимальную длину части строки. если же Вы под частью строки понимаете любую непрерывную часть, необязательно начинающуюся с первого символа или заканчивающуюся на последнем, то тут придется еще помудрить.
AlTk Смотрел эти алгоритм. Как Боуэра применить хз, так как он в основном для текстовых файлов применяется, а у меня нетипизированный. Строка начинается с первого символа. И ищется до того момента, пока найденное вхождение не будет такой же длины или наибольшее меньшее. Т. е. если ищем dqwrereet, а встречается только dqwrer, то эта строка dqwrer нам подходит.
да какая разница. просто если файл текстовый, то под алфавитом будут пониматься все буквенные символы, а если файл нетипизированный - то есть набор байтов, алфавит будет составлять 0x00 ... 0xFF. вот и все. сравнивай1те байты, а не символы.
Ты бы пример функции привел бы У меня пока так: Код: 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 кб до данной позиции).
По-моему, поиск умещается в одну строчку: 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, я не знаю.