Быстрый текстовый редактор найти - PullRequest
Новая
       10

Быстрый текстовый редактор найти

9 голосов
/ 10 февраля 2009

Кто-нибудь знает, как текстовые редакторы / редакторы-программисты могут выполнять такой быстрый поиск по очень большим текстовым файлам?

Индексируются ли они при загрузке, в начале поиска или какой-то другой умной технике?

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

Любые идеи действительно ценятся.

Это для реализации на C #, но эта техника меня интересует больше, чем сам код.

Ответы [ 4 ]

6 голосов
/ 10 февраля 2009

Начните с Бойера-Мура Алгоритм поиска. Он требует некоторой предварительной обработки (что быстро) и выполняет поиск довольно хорошо - особенно при поиске длинных подстрок.

1 голос
/ 10 февраля 2009

Grep

Хотя это не текстовый редактор сам по себе, но часто вызывается многими текстовыми редакторами. Мне интересно, если вы пробовали исходный код grep? Это всегда казалось мне невероятно быстрым, даже при поиске больших файлов.

1 голос
/ 10 февраля 2009

Я не удивлюсь, если большинство будет просто использовать базовую, наивную технику поиска (отыщите совпадение по 1-му символу, а затем проверьте, выпал ли удар).

0 голосов
/ 10 февраля 2009

Один из известных мне методов, о которых пока нет упоминания, - это Кнут-Моррис-Пратт-Поиск (KMP), но он не очень хорош для языковых текстов (из-за префиксного свойства алгоритма), но для вещей как ДНК-соответствие это очень, очень хорошо.

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

...