Линейная модель механизма поиска по логическому выражению

Логическое выражение-это последовательность терминов, объединенных знаками логических операций; синтаксическая конструкция языка, вычисляющая величины, которые принимают значение «0» или «1».

Логические операции: AND, OR, XOR, NOT.

Первый этап вычисления логического выражения может состоять в построении двоичного дерева операций. Все логические операции (кроме операции НЕ) являются бинарными, могут представить любое логическое выражение запроса в виде несбалансированного двоичного дерева, прохождение по которому снизу вверх приводит к получению результата. В узлах такого дерева, включая корневую вершину, расположены логические операции (o_i), а листья (конечные узлы) представляют собой строки матрицы L₀, соответствующие терминам запроса ().

Будем называть операндом запроса отдельно вычисляемое выражение, соответствующее поддереву запроса.

Рассмотрим расширенную матрицу «термин-документ» L^’₀, строки которой могут представлять собой не только показатели встречаемости терминов в документах информационного массива, но и результирующие векторы запросов (Qi)

, где , D- словарь.

K – количество включенных в матрицу результирующих векторов запросов,

Поставим в соответствие каждой логической операции правило ее выполнения с использованием расширенной матрицы: где из множества бинарных логических операций: Для унарной операции NOT это правило реализуется следующим образом:

Тогда алгоритм разрешения двоичного дерева поискового запроса состоит в последовательном выполнении снизу вверх логических операций и в пополнении на каждом шаге матрицы L₀ очередной строкой-результатом.

Условием выполнения k-той операции служит наличие в матрице строк, соотв-щих правому и левому операнду. После выполнения k-той операции формируется результирующий вектор , который становится ()-й строкой матрицы.