Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

IMHO © (2006-10-09 16:25:00)
Имеется двоичный файл (не текстовый) огромного размера (почти 1 Гб). Как можно реализовать быстрый поиск в нем определенной последовательности байтов, а точнее, быстрое нахождение количества вхождений определенной последовательности?

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

Barloggg (2006-10-10 09:25:00) [1]
а автору всего навсего надо было воспользоваться буфером.
то есть не по одному байту тянем с файлового потока, а грузим единым махом скажем килобайт или несколько и прошариваем их в памяти. потом следующие несколько килобайт.

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

default (2006-10-10 09:20:00) [2]
не очень понимаю проблемы
выбрать какой-нибудь алгоритм поиска подстроки в строке отличный от простого перебора и искать им
строкой поиска будет файл которая будет подгружаться по частям по мере просмотра

palva (2006-10-09 22:04:00) [3]
> Сейчас нашёл краткое описание алгоритма Бойера-Мура

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

Loginov Dmitry (2006-10-09 21:30:00) [4]
Когда-то давно программировал поиск в двоичном файле. Скачай

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

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

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

_Zeqfreed (2006-10-09 20:36:00) [6]
> [12] Leonid Troyanovsky © (09.10.06 20:20)
> [13] Джо © (09.10.06 20:22)

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

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

Джо (2006-10-09 20:22:00) [8]
Или Вирта, "Алгоритмы и структуры данных", эту хоть реально читать можно. Даже я полностью осилил :)

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

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

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

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

--
Regards, LVT.

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

Zeqfreed (2006-10-09 20:15:00) [11]
> [8] Ketmar © (09.10.06 20:09)

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

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

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

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

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

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

--
Regards, LVT.

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

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

Zeqfreed (2006-10-09 19:56:00) [14]
Мне тут в голову пришел безумный алгоритм. Тем не менее изложу :)

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

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

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

Leonid Troyanovsky (2006-10-09 19:45:00) [15]

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

> Memory Mapped Files.

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

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

--
Regards, LVT.

Kolan (2006-10-09 19:39:00) [16]
Ох когда-то была ветка постов на 200 по этому поводу.. Там решение было. Мож у кого осталось. Года полтора назад...

Rouse_ (2006-10-09 16:27:00) [17]
Медленно из-за частых обращений к диску, и поиск нужно делать последовательности, а не байта...

clickmaker (2006-10-09 16:27:00) [18]
Memory-mapped + CompareMem

@!!ex (2006-10-09 16:26:00) [19]
А какие еще варианты то?
Все равно все байты перебирать.

Ketmar (2006-10-09 16:26:00) [20]
Memory Mapped Files.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »