Эффективный подход к функциональности поиска файлов

Question

У меня очень большой текстовый документ.Я реализую функцию "Поиск", чтобы найти вхождения данной строки в файле и отобразить ее положение.Это не просто поиск по всему слову, он может содержать часть слова / отправления / абзаца.Я работаю над эффективной структурой данных для этого процесса.Если бы это был поиск по всему слову, я мог бы использовать попытку / хэш-таблицу.Я не смогу использовать массив суффиксов / дерево суффиксов, так как размер файла очень большой.Сортировка тоже не так эффективна.Другой простой вариант - просто использовать функцию поиска строк / регулярных выражений платформы, которая занимает линейное время.Есть ли какой-либо более известный подход для такого рода операций?Первоначально это просто поиск по строке, позже планируется выполнить поиск с метасимволами.

Answer 1

Три и суффикс дерева / массива - хороший вариант, но если они вам не нравятся, у меня есть другое решение: создайте хеш-таблицу:

• Создайте хеш-таблицу для всех строк длиной 1, 2, 3, .. N, где N - это любое число, сложность которого вы хотите O (N * size_of_text)

• Если вы хотите найти строку, у вас есть 2 варианта:

  Если размер строки меньше N, вы просто ищите ее в хеш-таблице ~ O (1) для поиска и o (size_of_string) для создания hash_key
  Если размер больше N, вы просто создаете чанки размера N и делаете это: ищите чанк и запоминаете все позиции. Чем вы проделываете то же самое для следующего фрагмента и проверяете, есть ли числа, которые являются последовательными (например: первый раз, когда у нас есть i, j и второй раз, когда мы имеем k, i + N, чем i, i + N - хорошая комбинация) сохраните последний номер в последовательной паре (i, i + N, оставьте только i + N) и продолжайте, пока у вас не останется номер в вашем стеке, или вы не закончили слово
  Надеюсь, это помогло.

Answer 2

Lucene.NET - это библиотека поисковой системы, которая выполняет сканирование текста по индексам: http://incubator.apache.org/lucene.net/