Найдите существование слова в большом словаре

Это классический вариант использования фильтра Блума . Фильтр Блума - это вероятностная структура данных, которая оптимизирована для тестов членства («является ли X членом этой коллекции?») И обеспечивает поиск O (1) . Взамен вы вводите произвольно малую вероятность ложного срабатывания - то есть фильтр скажет, что определенное слово присутствует, но на самом деле его нет. Чем больше памяти вы используете, тем меньше эта вероятность. Однако вероятность ложноотрицательных результатов равна нулю: фильтр никогда не скажет, что слово отсутствует, если оно действительно присутствует.

В вашем конкретном случае, имея 8 миллиардов бит (1 ГБ) для работы, вы можете получить количество ложных срабатываний немного выше, чем 1 на каждые 1000000000 испытаний. Это чрезвычайно низкий уровень ложных срабатываний. Если вы просмотрели 200 миллионов случайных строк, вероятность того, что вы никогда не встретите ни одного ложного срабатывания, составляет около 82%.

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

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

Использовать алгоритм поиска строки Бойера – Мура?

http://en.wikipedia.org/ wiki / Boyer% E2% 80% 93Moore_string_search_algorithm

Если у вас нет индекса, просто используйте поток.

Иногда самое простое решение оказывается лучшим.

   public Int32 IndexOf(FileStream file, Byte[] ascii_bytes, Int32 start_index)
   {
       Int32 index = -1;
       {
           Int32 current = 0;
           Int64 original_index = 0;
           Boolean found = true;

           file.Position = start_index;
           current = file.ReadByte();
           while (current >= 0)
           {
               if ((Byte)current == ascii_bytes[0])
               {
                   found = true;
                   original_index = file.Position - 1;
                   for (Int32 i = 1; (i < ascii_bytes.Length && current > 0); i++)
                   {
                       current = file.ReadByte();
                       if ((Byte)current != ascii_bytes[i])
                       {
                           file.Position--;
                           found = false;
                           break;
                       }
                   }

                   if (found)
                   {
                       file.Position = original_index;
                       index = (Int32)original_index;
                       break;
                   }
               }
               current = file.ReadByte();
           }
       }
       return index;
   }

Предположения:

1. Вы собираетесь искать слово много раз за время существования процесса (в отличие от запуска процесса каждый раз, когда вы ищете слово).
2. Файл отсортирован.

Вы можете частично проиндексировать данные, занимая большую часть доступной памяти: сохранять слова и их начальную позицию в файле, используя B-дерево или отсортированный массив (последний - больше места эффективен, но требует одного непрерывного блока; кроме того, b-tree требует, чтобы вы сохраняли конечную позицию фрагмента, а массив - нет). Оставьте достаточно места в памяти, чтобы загрузить из файла один кусок слов. Найдите в индексе (обход дерева или двоичный поиск) фрагмент, который будет содержать слово. Как только вы нашли конкретный фрагмент из частичного индекса, загрузить соответствующий фрагмент из файла в память и выполнить по нему двоичный поиск.

Если вам нужна дополнительная память, вы можете выбросить некоторые элементы из индекса. С помощью массива вы можете уменьшить индекс до n элементов, используя следующий псевдокод C:

struct chunk {
    string word;
    int start;
};
chunk index[];
d = index.length / n;
for (i=0;i<n; ++i) {
    index[i] = index[i*d];
}
realloc(index, sizeof(chunk) * n);

Поскольку конец блока i равен index [i + 1] .start , алгоритм предельно прост для реализации массива. Для индексов на основе B-дерева вы можете легко объединить листья с их родителями.

Если некоторые слова с ними консультируются гораздо чаще, чем с другими, тогда может иметь смысл иметь кэш LRU в памяти и базу данных за ним.