Двоичный поиск строки в текстовом файле с использованием Javascript

Question

Есть ли способ выполнить дисковый двоичный поиск определенного ключа в текстовом файле в Javascript? Текстовый файл слишком велик для загрузки в память, но отсортирован по значениям ключа. В частности, я ищу способ имитировать Perl Search :: Dict функциональность в Javascript.

Например, Если у меня есть файл foo.txt:

a 1
b 10
c 5
z 4

look(c,foo.txt) должен вернуть строку 'c 5', выполнив двоичный поиск и не пройдя файл линейно.

Answer 1

Я не знаю Javascript, но, если вы можете выполнять случайный поиск, вы можете выполнить бинарный поиск, выполнив поиск до средней точки вашего текущего блока (в байтах), а затем идти вперед до тех пор, пока вы не используете новую строку, до тех пор, пока вы «знаете», что ваш ключ против новой строки.

Однако будут случаи, когда вам нужно идти назад, поэтому вы можете выполнять поиск со знанием буферизации файлов, чтобы обратные шаги не были дорогими.

Полагаю, это может немного раздражать, если вы не имеете дело с файлами ASCII.

Answer 2

Не совсем, бинарный поиск действительно возможен только тогда, когда вы можете определить начало записи. Похоже, у вас есть записи переменной длины, поэтому, если вы не создадите массив смещений начала строки, это не сработает.

Как справедливо отмечает Нихил в комментарии, одним из методов будет двоичное деление файла по размеру файла, а затем поиск ближайшей строки, начинающейся оттуда. Это все равно было бы относительно эффективно (т. Е. намного лучше, чем последовательный поиск).