@ aloobe получил ответ об использовании индексного файла, который сопоставлял слова местам. Я просто хочу пояснить это, хотя думаю, что ответ, который ищет ОП, может быть Бойер-Мур.
Индексный файл будет выглядеть следующим образом (упрощено использование удобных для чтения двузначных чисел):
53 17 89 03
77 79 29 39
88 01 05 15
...
Каждая запись выше - это смещение в байтах слова или буквы, которые вы считаете достаточно важными для индексации. На практике вы не будете использовать буквенные индексы, так как тогда ваш индексный файл будет больше, чем ваш корпус!
Хитрость в том, что если бы вы заменили слова в этих местах местоположениями, ваш индексный файл был бы отсортированным по алфавиту версией корпуса:
and and are as
ate bad bat bay
bear best bin binge
Это позволяет вам выполнять Бинарный поиск по корпусу через индексный файл. Если вы ищете слово «лучший» выше, вы бы взяли среднюю запись в индексном файле, 79. Затем вы бы пошли на позицию / байт 79 в корпусе и увидели, какое слово там. Это bad. Мы знаем это в алфавитном порядке best > bad, поэтому позиция должна быть во 2-й половине индексного файла.
Итак, мы берем средний индекс между 79 (6-м) и 15 (12-м), что в моем примере равно 01. Затем мы смотрим на позицию / байт 88 (9-й) в корпусе, чтобы найти bear. best > bear поэтому мы попробуем еще раз - средний индекс теперь равен 01 (10-му) или 05 (11-му) в зависимости от того, как вы округлили. Но ясно, что мы найдем best в еще 1 или 2 поисках. Если у нас есть 12 слов, как в примере, в худшем случае потребуется не более 4 запросов. Для файла 25 ГБ со средней длиной слова, скажем, 5 букв и пробелами между ними, это ~ 4 миллиарда слов. Тем не менее, в худшем случае вы будете искать только ~ 32 раза. В этот момент больше времени вашей программы тратится на раскручивание диска и буферизацию ввода, чем на самом деле поиск!
Этот метод также работает с дублирующимися словами. Если вы хотите найти все местоположения слова the, вы будете выполнять бинарный поиск по the, пока не найдете индекс. Затем вы должны были бы вычесть 1 из позиции в индексном файле несколько раз, используя значение каждый раз, чтобы заглянуть в корпус. Если слово в этом месте все еще the, продолжайте. Когда вы наконец остановитесь, у вас будет самый ранний индекс в файле индекса, который отображается на the.
Создание индексного файла - единственная сложная часть. Вам нужно пройтись по каждому слову в корпусе, выстроив структуру данных слов и их индексов. Попутно пропустите слова, которые являются слишком общими или короткими, чтобы быть в списке, например, "a", "I", "the", "и", "is" и т. Д. Когда вы закончите, вы можете взять эту структуру данных и превратить его в индексный файл. Для файла размером 25 ГБ, к сожалению, ваши индексы должны быть> 32 бита, поэтому для их хранения используйте long (в Java) или long long (в C). Нет причин, по которым он должен читаться человеком, поэтому выведите индексы в виде 64-битных значений, а не строк.
Я бы порекомендовал структуру самобалансирующегося бинарного дерева поиска . Каждый узел представляет собой строковое значение (слово) и индекс. Однако дерево сравнивает узлы только на основе строки. Если вы сделаете это, то обход по порядку (слева, узел, справа) даст вам именно файл индекса.
Надеюсь, это поможет! Пример, который я использовал несколько лет назад при разработке словаря для мобильных телефонов, - EDICT Джима Брина. Это может быть трудно подобрать из-за кодировки EUC и японских символов, но цель та же.