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

Логическое выражение поискового условия – это синтаксическая конструкция языка, задающая порядок и способ вычисления величины, принимающей значение «0» или «1». Выражение представляет собой последовательность операндов, соединенных друг с другом знаками операций. Нотация Бэкуса для такого выражения следующая: <Выражение>::=<Операнд>½<Выражение><Операция>

<Выражение>½ (<Выражение><Операция><Выражение>) Обычно: операнд – термин(дескриптор); операция – одна из логических операций. Первый этап вычисления логического выражения может состоять в построении двоичного дерева операций. Все логические операции (кроме NOT) – бинарные => можно представить любое логическое выражение запроса в виде несбалансированного двоичного дерева, прохождение по которому снизу вверх приводит к получению результата. В узлах дерева расположены логические операции (o_i), а листья (конечные узлы) представляют собой строки матрицы L₀, соотвующие терминам запроса .Операнд запроса – отдельно вычисляемое выражение, соответствующее поддереву запроса. Расширенная матрица «термин-документ» . Строки – не только показатели встречаемости терминов, но и результирующие векторы запросов (Q_i).

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

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

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