Том 3, номер 4, 1996 г., Стр. 77-92

УДК 519.725
М. М. Трофимова
Поиск частично известного слова в словаре

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

Трофимова М. М. ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия

Статья поступила 9 октября 1996 г.