Поиск частично известного слова в словаре

Исследуется проблема поиска частично известных слов в машинной памяти. Рассматривается важный частный случай, когда каждое слово состоит из двух частей, называемых первым и вторым ключами соответственно. Требуется находить слово, зная лишь один из ключей. Предполагается, что в словаре использовано $A$ разных первых ключей, на каждый из которых приходится по $r$ вторых ключей. Если в каждой ячейке машинной памяти хранится не более одного слова, т. е. нет склеиваний, то по заданному первому ключу можно найти слово за г шагов, а по второму – за $A$ шагов. Предлагается простой алгоритм, позволяющий разместить без склеиваний любой словарь с двух- ключевыми словами, используя объем машинной памяти $A^{3/2}$ – по порядку равный минимальному. Известные методы поиска Р. Райвеста, а также Д. Слепяна и Д. Вулфа при размещении допускают склеивания и используют объем памяти $Ar$. Однако время поиска слова при таком размещении по первому или второму ключу не превосходит $Ar$ а не $r$ или $A$.
Табл. 1, библиогр. 4.