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

← →
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)

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

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

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

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

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

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

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

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

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

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

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

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