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

Question

Предположим, мне дан большой словарь в плоском файле с 200 миллионами слов, и моя функция должна проверять наличие любого данного слова в словаре, какой самый быстрый способ сделать это? Вы не можете сохранить словарь в памяти, потому что у вас есть только 1 ГБ памяти. Вы можете сохранить его в базе данных, однако запрос на него все равно будет очень и очень медленным без какой-либо оптимизации. Вы не можете индексировать полные слова, потому что у вас недостаточно ресурсов.

Редактировать: в дополнение к упомянутому ниже подходу к оптимизации файлов, есть ли какая-либо оптимизация базы данных? Я думаю о создании частичных индексов, скажем, для каждых 2 букв в слове до предела, я создаю индекс. Это ускорит запрос к БД?

Answer 1

Двоичный поиск

Если в словаре есть слова в алфавитном порядке, я бы попытался изменить двоичный поиск . Разделите и покорите файл, перейдя к средней точке в файле и увидев, какое слово там. Если угадано, разделите нижнюю пополам и попробуйте снова, пока не найдется место для файла или слово не найдено.

(Как уже упоминалось в комментарии 1007 *, после перехода к местоположению файла вам нужно будет сканировать назад и вперед, чтобы найти границы слова, на которое вы перешли

Возможно, вам удастся оптимизировать это, угадав кусочек местоположения сразу же, основываясь на первой букве слова. Например, если слово начинается с «c», начните поиск в 3/26-й секции файла. Хотя, на самом деле, я думаю, что это раннее предположение будет иметь незначительное значение в целом.

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

O (log n)

Answer 2

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

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

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

Answer 3

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

Answer 4

Если слова имеют много префиксов и суффиксов, вы, вероятно, можете загрузить их все в память, используя Направленный ациклический граф слов (Что случилось, DAWG!)

Это как три, но сжимает общие суффиксы. Будет ли это полезно, зависит от того, что в вашем словаре, но может быть целесообразно вписать 200 МБ в оперативную память 1 ГБ.

Answer 5

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

Answer 6

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

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

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

Если вам нужна дополнительная память, вы можете выбросить некоторые элементы из индекса. С помощью массива вы можете уменьшить индекс до 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-дерева вы можете легко объединить листья с их родителями.

Answer 7

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

Иногда самое простое решение - лучшее.

   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;
   }

Answer 8

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

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