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

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

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

a 1 
b 10 
c 5 
z 4

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

источник

2009-02-13 Nikhil

Умм, как вы получаете содержимое файла В javascript? –

Как получить доступ к файлу с помощью javascript? – VolkerK

Я не уверен. Возможно, это тоже часть решения. – Nikhil

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

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

источник

2009-02-13 01:08:07 paxdiablo

Поиск в Perl :: Dict делает это: http://perldoc.perl.org/Search/Dict.html. Я не совсем уверен, как это работает внутри, но потенциально вы можете «прыгать» на основе байтов, а затем найти ближайший разрыв строки для сравнения. – Nikhil

Вы можете перейти к середине файла, но это не обязательно средняя линия. Например, если первый миллион строк составляет 100 байт, а последний миллион - 2 байта. Это не * довольно * бинарный, но все же лучше, чем последовательный поиск. – paxdiablo

Он все равно должен соответствовать ограничениям времени для двоичного поиска. –

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

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

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

источник

2009-02-13 01:26:40

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

ответ

Смежные вопросы