Поиск по байтовому массиву?

Question

[useers]

Дано:
1) большой файл, состоящий из байтовой каши;
2) целевая строка, а точнее - определенная последовательность из 20 байт.

Вопрос:
Как осуществить быстрый поиск цели в таком файле?

Edit: поиск в файле нужно делать часто, т.к. целевая срока не одна и постоянно меняется;
данные в файле - просто набор подряд идущих байт, а мне нужно найти заданный набор из 20 байт.

Comments

[Алексей 〒.]

Большой файл слишком размытое понятие. Примерно какой разброс Гб, Тб?

[useers]

Думал что 1гб, но оказалось и того меньше ~600 мб

Answer 1

[Евгений Мамонов]

Думаю это сильно зависит от того, как часто вам нужно делать поиск в этом файле.
Если не часто - тогда можно просто вычитывать данные порциями, и искать последовательность в них.
Если же очень часто - нужно понять что там за данные и думать как сделать индекс для поиска в этом файле.

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

Еще, как вариант, можно сделать простенький индекс (упрощаю, чтобы было легче писать понятный пример)

Допустим у нас есть файл с таким содержимым
0x02 0x09 0x02 0x05 0x09 0x09, 0xf1 0xfa 0x02

Найти нужно последовательность 0x02 0x05

Строим индекс [массив байт от 0x00 до 0xff][слайс адресов этого байта в файле]
т.е.
[значение байта][адрес этого байта в файле1, адрес этого байта в файле2, адрес этого байта в файле3...]
Для указанного файла индекс получится вот такой
[0x00][]
[0x01][]
[0x02][0x00, 0x02, 0x08]
...
[0x05][0x03]
...
[0x09][0x01, 0x04, 0x05]
...
[0xf1][0x06]
...
[0xfa][0x07]
...

Первый байт в искомой последовательности 0x02 0x05 - будет 0x02.
Мы берём слайс в массиве по индексу 0x02 и получаем список адресов где в файле есть 0x02 - [0x00, 0x02, 0x08]
А дальше вы проверяете вашу последовательность только начиная с полученных смещений
Т.е. проверяем следующий байт по адресу 0x00 + 1 == 0x05 (второму символу последовательности) или нет.
Если нет - значит берём след. смещение 0х02 и опять проверяем равен ли след. символ 0x05.
Равен, значит нашли последовательность.

Comments

[useers]

Добавил:
поиск в файле нужно делать часто, т.к. целевая срока не одна и постоянно меняется (список);
данные в файле - просто набор подряд идущих байт, а мне нужно найти заданный набор из 20 байт.

[Евгений Мамонов]

А сам файл меняется или данные всегда одни и те же, а меняются только последовательности для поиска?
По возможности опишите задачу подробнее, возможно найдётся какое то менее ресурсоёмкое решение

[Евгений Мамонов]

Как часто нужно делать в файле поиск?
Как часто меняются последовательности, которые нужно менять?
Меняется ли сам большой файл, если да - то как часто, меняется ли полностью или данные дописываются в конец файла?
На сколько большой файл, нужны хоть какие то ориентиры, для кого-то 100мб большой файл, а для кого то 1Тб небольшой :)

В общем нужно понимать вашу задачу чтобы искать конкретное решение под неё.

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

https://medium.com/swlh/processing-16gb-file-in-se...

[useers]

Файл 1гб, полностью статичный.
Меняются только последовательности для поиска.
Поиск в файле нужен практически постоянно, т.к. новые последовательности генерируются очень часто

[Евгений Мамонов]

какая конечная цель?
проверить есть ли последовательность в файле или найти все последовательности или что-то еще?

[useers]

"Проверить есть ли последовательность в файле" - именно это и есть цель,
просто проверить одни данные с бд (назовём это так);
и да, с размером файла ошибся, оказалось что ~600мб,
наверное, имеет смысл держать файл в памяти.

[Евгений Мамонов]

а насколько быстро нужно получать результат?
возможно при таком объёме можно и не заморачиваться и просто последовательно сравнивать?

[Евгений Мамонов]

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

По сути это больше вопрос по структурам данных, чем по Go.

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

[Евгений Мамонов]

Первое, что пришло в голову

Допустим у нас есть файл с таким содержимым
0x02 0x02 0x02 0x05 0x05 0x09, 0xf1 0xfa 0x02
а найти нужно последовательность 0x02 0x05

Строим индекс вида
[значение][addr1, addr2, addr3...]
[0x00][]
[0x01][]
[0x02][0x00, 0x01, 0x02, 0x08]
...
[0x05][0x03, 0x04]
[0x09][0x05]
[0xf1][0x06]
[0xfa][0x07]

По значению 0x02 (первый символ последовательности) получаем список адресов где есть 0x02 - [0x00, 0x01, 0x02, 0x08]
А дальше вы проверяете вашу последовательность только начиная со смещения в файле [0x00, 0x01, 0x02, 0x08]

[Евгений Мамонов]

получилось?

[useers]

К сожалению, скорость совсем никакая - очень долго открывает и сравнивает..

[Евгений Мамонов]

Как именно реализовывали?
Просто чтение с горутинами и поиск?
Или вычитывали файл в память, делали индекс и потом все запросы уже через индекс?

[useers]

Пока что успел сделать только чтение и сравнение всей последовательности через bytes.Compare()
Вариант с bytes.Index() попробую сегодня-завтра, и отпишу по результату.

[Евгений Мамонов]

понял, жду )))

[useers]

Ладно, в теории я понял как это сделать, но на практике пока мозгов и времени не хватает)
В любом случае, Евгений, спасибо за помощь.

[Евгений Мамонов]

появится время, покрутите и всё получится!
рад помочь :)