Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2006.11.19;
Скачать: CL | DM;

Вниз

Быстрый поиск в двоичном файле   Найти похожие ветки 

 
IMHO ©   (2006-10-09 16:25) [0]

Имеется двоичный файл (не текстовый) огромного размера (почти 1 Гб). Как можно реализовать быстрый поиск в нем определенной последовательности байтов, а точнее, быстрое нахождение количества вхождений определенной последовательности?

Если открывать через TFileStream и читать каждый байт, то это занимает много времени.


 
@!!ex ©   (2006-10-09 16:26) [1]

А какие еще варианты то?
Все равно все байты перебирать.


 
Ketmar ©   (2006-10-09 16:26) [2]

Memory Mapped Files.


 
clickmaker ©   (2006-10-09 16:27) [3]

Memory-mapped + CompareMem


 
Rouse_ ©   (2006-10-09 16:27) [4]

Медленно из-за частых обращений к диску, и поиск нужно делать последовательности, а не байта...


 
Kolan ©   (2006-10-09 19:39) [5]

Ох когда-то была ветка постов на 200 по этому поводу.. Там решение было. Мож у кого осталось. Года полтора назад...


 
Leonid Troyanovsky ©   (2006-10-09 19:45) [6]


> Ketmar ©   (09.10.06 16:26) [2]

> Memory Mapped Files.


MMF не ускорит доступ к данным принципиально,
бо, оный есть таки последовательный.

Ну, а некоторые неудобства, связанные с поиском
в ограниченном буфере, т.е. трудности применения
CompareMem & etc  должны переноситься стоически,
токмо эффективности ради.

--
Regards, LVT.


 
Zeqfreed ©   (2006-10-09 19:56) [7]

Мне тут в голову пришел безумный алгоритм. Тем не менее изложу :)

Имеем массив — 256 связанных списков, содержащих индексы вхождений каждого значения байта (от 0 до 255) в искомой строке. Сформировав списки индексов формируются диапазоны пустых списков, т.е. например если у нас в искомой строке встречаются все символы от 32 до 255 то пустым диапазоном будет 0-31.

Далее загружаем исходные данные в буфер, думаю MMF будут удобным хранилищем и сдвигаемся по буферу с шагом ДЛИНА_ИСКОМОЙ_СТРОКИ - 1. На каждой итерации проверяем: если значение в текущей позиции принадлежит одному из пустых диапазонов, то пропускаем итерацию. Иначе, берем по очереди все индексы из списка и сравниваем области памяти с помощью CompareMem.

Кажется, такой алгоритм должен работать и может дать некоторый прирост в производительности. Сильно прошу не пинать :)


 
Ketmar ©   (2006-10-09 20:09) [8]

>[6] Leonid Troyanovsky(c) 9-Oct-2006, 19:45
>MMF не ускорит доступ к данным принципиально,
ну, принципиально не ускорит ничего. но побыстрее чтения потока будет. %-)

>[7] Zeqfreed(c) 9-Oct-2006, 19:56
это не вариация байера-мура часом? многа букав, не асилил сам понять. %-)


 
Leonid Troyanovsky ©   (2006-10-09 20:14) [9]


> Ketmar ©   (09.10.06 20:09) [8]

> >MMF не ускорит доступ к данным принципиально,
> ну, принципиально не ускорит ничего. но побыстрее чтения
> потока будет. %-)


Нет, конечно.
Т.е., быстрее чтения в подходящий по размеру буфер
(пусть даже путем TFileStream) предложить ч.-л. сложно.

--
Regards, LVT.


 
Zeqfreed ©   (2006-10-09 20:15) [10]

> [8] Ketmar ©   (09.10.06 20:09)


> это не вариация байера-мура часом

По поиску в тексте я никаких алгоритмов не знаю, не приходилось знакомиться :)


 
Ketmar ©   (2006-10-09 20:17) [11]

>[9] Leonid Troyanovsky(c) 9-Oct-2006, 20:14
>Нет, конечно.
пардон, оговорился. дальше было "побайтово". %-)


 
Leonid Troyanovsky ©   (2006-10-09 20:20) [12]


> Zeqfreed ©   (09.10.06 20:15) [10]

> По поиску в тексте я никаких алгоритмов не знаю, не приходилось
> знакомиться :)

Это вы, батенька, зря.
Т.е., RTFM: Д. Кнут : Алгоритмы и .. как их там.
Полезная такая книга, томов 3, зелененькие такие.

--
Regards, LVT.


 
Джо ©   (2006-10-09 20:22) [13]

Или Вирта, "Алгоритмы и структуры данных", эту хоть реально читать можно. Даже я полностью осилил :)


 
Ketmar ©   (2006-10-09 20:26) [14]

>[13] Джо(c) 9-Oct-2006, 20:22
>Или Вирта, "Алгоритмы и структуры данных", эту хоть
>реально читать можно. Даже я полностью осилил :)
Вирта вообще читать приятно у удобно. в отличие от Кнута. Кнуту череп мозги распирают. %-)


 
_Zeqfreed   (2006-10-09 20:36) [15]

> [12] Leonid Troyanovsky ©   (09.10.06 20:20)
> [13] Джо ©   (09.10.06 20:22)

Спасибо :) Если бы ещё продавалось такое в наших магазинах, а то только Фленовы всякие, да Архангельские…
Сейчас нашёл краткое описание алгоритма Бойера-Мура - интерсно, у меня сложнее :)


 
Ketmar ©   (2006-10-09 21:14) [16]

>[15] _Zeqfreed 9-Oct-2006, 20:36
>Сейчас нашёл краткое описание алгоритма Бойера-Мура -
>интерсно, у меня сложнее :)
ну, BM тоже можно усложнять. %-) минимальной болью, например, можно искать по "маскам" -- т.е. с перловой ".". и ты пы.


 
Loginov Dmitry ©   (2006-10-09 21:30) [17]

Когда-то давно программировал поиск в двоичном файле. Скачай

http://kladovka.net.ru/download.cgi?id=245

там можно посмотреть реализацию FindHexStringInFile()


 
palva ©   (2006-10-09 22:04) [18]

> Сейчас нашёл краткое описание алгоритма Бойера-Мура

Советую хорошую книгу Шеня по алгоритмам
http://bspu.secna.ru/~pvv/shen/contents_shen.html
глава Сопоставление с образцом


 
default ©   (2006-10-10 09:20) [19]

не очень понимаю проблемы
выбрать какой-нибудь алгоритм поиска подстроки в строке отличный от простого перебора и искать им
строкой поиска будет файл которая будет подгружаться по частям по мере просмотра


 
Barloggg   (2006-10-10 09:25) [20]

а автору всего навсего надо было воспользоваться буфером.
то есть не по одному байту тянем с файлового потока, а грузим единым махом скажем килобайт или несколько и прошариваем их в памяти. потом следующие несколько килобайт.

а поиск из файловых потоков медленный. сравнение двух фалов по 300 кб занимает несколько секунд. и потом минута тратится на заполнение memo результатами сравнения :) если этих результатов под тысячу :)



Страницы: 1 вся ветка

Текущий архив: 2006.11.19;
Скачать: CL | DM;

Наверх




Память: 0.51 MB
Время: 0.043 c
2-1162377933
gaval
2006-11-01 13:45
2006.11.19
FastReport


15-1162236939
Gero
2006-10-30 22:35
2006.11.19
Поставил себе Windows Vista


1-1159168787
fynjy1984
2006-09-25 11:19
2006.11.19
WebBrowser и картинки


11-1136725971
Grom PE
2006-01-08 16:12
2006.11.19
Почернение контролов в Design-Time


1-1160048830
Aleksandr.
2006-10-05 15:47
2006.11.19
Есть готовые решения для PickList ячеек TStringGrid?