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

13

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

пример

a\n
c\n
d\n
f\n
g\n

Учитывая ввод 'foo', я бы получил вывод 9.

Это легко сделать, просто просматривая весь файл, но, будучи миллиардами строк переменной длины, было бы быстрее выполнить бинарный поиск.

Такой инструмент обработки текста уже существует?

Редактировать:

Это делает сейчас: https://gitlab.com/ole.tange/tangetools/blob/master/bsearch/bsearch

text-processing search Оле Танге
источник
Какова длина строки, которую вы ищете (в символах)? и сколько таких строк нужно искать?
Гогуд
@gogoud Я не ищу ограниченный инструмент, но работающий с любым текстовым файлом (независимо от длины строки или количества строк).
Оле Танге
для тех, кто хотел бы генерировать такой гигантский ввод: unix.stackexchange.com/a/279098/9689
Гжегож Вежовецкий,

Ответы:

4

Я не знаю ни одного стандартного инструмента, делающего это. Однако вы можете написать свой собственный. Например, следующий скрипт ruby ​​должен сделать эту работу.

file, key = ARGV.shift, ARGV.shift
min, max = 0, File.size(file)

File.open(file) do |f|
  while max-min>1 do
    middle = (max+min)/2
    f.seek middle
    f.readline
    if f.eof? or f.readline>=key
      max = middle
    else
      min = middle
    end
  end
  f.seek max
  f.readline
  p f.pos+1
end

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

Михась
источник
Можно ли изменить -n / -r для обработки файлов, отсортированных по sort -rи sort -n?
Оле Танге
Код выше, в основном, чтобы показать идею. Это далеко от совершенства. (Например, он не работает, если ключ идет на первое место.) Не стесняйтесь адаптироваться к вашим потребностям.
Михас
5

(Это не правильный ответ на ваш вопрос, просто отправная точка.)

Я использовал sgrep (отсортированный grep) в аналогичной ситуации.

К сожалению (нам нужно текущее состояние), у него нет вывода со смещением байтов; но я думаю, что это может быть легко добавлено.

JJoao
источник