Полная версия

Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом.

Пусть Vq — множество связных ориентированных деревьев с корнем, в которых каждое ребро принадлежит хотя бы одной цепи, ведущей из корня к какой-либо концевой вершине. Пусть D G Vq. Обозначим через Со — множество всех цепей в D, ведущих из корня к какой-либо концевой вершине.

Если С = (а1,а2),(а2,аз),...,(аг-1,аг) — ориентированная цепь,

г—1

то обозначим через Пс мощность следа цепи С, т. е. пс = Фон

»=1

Обозначим

где D — количество концевых вершин в дереве D, к принимает натуральные значения.

Дерево D, такое, что Z(D) = Z(D), назовем деревом с минимальным следом.

Лемма 8. Для любого натурального к существует дерево с минимальным следом с к концевыми вершинами, полустепень исхода любой внутренней вершины которого равна либо 2, либо 3.

Доказательство. Предположим, что дерево D содержит ветвь D вида изображенного на рис. 2.1, где / ^ 4. Рассмотрим дерево Ог вида, указанного на рис. 2.2, где г = [//2]. Имеем

Таким образом, мы показали, что если в дереве есть ветвь вида D, то ее всегда можно заменить на ветвь вида 1?2> и дерево от этого не усложнится.

Осталось заметить, что ветвь вида D3, изображенного на рис. 2.3, всегда можно заменить на ветвь D4, не усложняя при этом дерева. Тем самым лемма доказана.

Обозначим

где к принимает натуральные значения.

Лемма 9. Для любого натурального к выполняется Z(k) = W(k).

Доказательство. Доказывать будем индукцией по числу к. Базис индукции, k = 1; Z( 1) = 0 = W(l). к = 2; Z(2) = 2 = W{2). к = 3; Z{3) = 3 = W{3).

Шаг индукции. Пусть для любого t < к выполнено Z(t) = W(t). Согласно лемме 8, существует дерево с минимальным следом с к концевыми вершинами, которое имеет либо вид D, изображенный на рис. 2.4, либо вид D2, изображенный на рис. 2.5.

Рассмотрим 3 случая:

  • 1) 31 < к ^ 3,Ч-3,[1]. Тогда 3/_1 < к/3[ ^ З^З[1]"[1]. Откуда согласно предположению индукции Z(]k/3[) = 3(/ — 1) 4- 1 =31 — 2, и, значит, Z(Dl) >3 + 31-2 = 31 + 1 = W(k).
  • 2) 3[1] 4- З*-[1] < к ^ 2 • 3*. Тогда З'”[1] 4- З'"{{ 3l 4- З*-1 < к ^ 2 • 3Z. Тогда ]к/2 > (31 4- 3,’[1])/2 = 2 • З'"1,]к/2[ ^ 3*. Отсюда согласно предположению индукции Z(]k/2[) = 3/,и, значит, Z(D2) >2 + 31 = W (к).}} < ]к/3[ ^ 2 • З*"[1]. Отсюда согласно предположению индукции Z(]k/3[) = 3(/ — 1) 4- 2 = 3/ — 1, и, значит, Z(D) >3 + 31 — 1 = 3/ 4-2 = W(k).
  • 3) 2 • 3* < А: ^ 3,+1. Тогда 2 • З*”1 < ]к/3[ > 3*. По предположению индукции Z(]k/3[) = 3/, и, значит, Z(Di) > 3/ 4- 3 = И^(А:).

Рассмотрим 3 случая:

3) 2 • 3* < к ^ 3I+1. Тогда

Согласно предположению индукции 3/ + 1 ^ Z(]k/2) ^ 3/ + 2, и, значит, ?(Дг) ^ 3/ + 1 + 2 =

С другой стороны, если D^D^, D'3 деревья с минимальным следом и их мощности (т. е. количество концевых вершин) различаются не более чем на 1, то Z(D) — W(k) и D — дерево с минимальным следом, а если 3^log3fc) ^ к ^ 8 • и D" и D3 — деревья

с минимальным следом, такие, что ||D|| — |Щ ^ 15 то Z(D2) = W(k) и D2 — дерево с минимальным следом.

Тем самым лемма доказана.

Справедлива следующая теорема.

Теорема 8. Если I = (X,V,p) — ЗИП, обладающая В-свойст- 00м, Т — (F, 0) — измеримое базовое множество, допустимое для I,

mo T(I,F)>W(V).

Доказательство. Возьмем произвольный ИГ UU(I, Т). Согласно теореме 6 существует такое информационное дерево DV1, что T(U) ^ T(D). Оценим В-сложность ИД D.

В силу произвольности U теорема доказана.

Следствие 5. Если I = (X, V,p)ЗИП, обладающая В-свойст- вом, Т — (F, 0) — измеримое базовое множество, допустимое для I,

такое, что Fq С F, то T(I,F) = WAV’!).

Доказательство. Нижняя оценка следует из теоремы 8, а верхнюю дает ИД, изображенное на рис. 2.3, где D4 дерево с минимальным следом с к концевыми вершинами, которые одновременно являются листьями графа, нагрузка листьев записями из V выбрана произвольно, а нагрузка ребер осуществляется по методу, описанному в доказательстве теоремы 6, так, чтобы выполнялось С-свойство.

Тем самым следствие доказано.

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

Теорема 9. Если I = (X, V,p) — ЗИП, обладающая В-свойством, Т = (F, G)измеримое базовое множество, допустимое для I, такое, что любой переключатель из G принимает не более т значений, где т > 1, то Т(1,Т) ^ ]logm |V|[.

Доказательство. Возьмем произвольный ИГ UЫ{1,Т). Так как ЗИП I обладает В-свойством, то легко видеть, что если мы удалим все ребра, исходящие из листьев, то функционирование ИГ не изменится. В самом деле, цепи, начинающиеся в некотором листе и ведущие в некоторый другой лист, которому приписана другая запись, неизбежно должны иметь такую проводимость, которая при умножении на функцию фильтра исходного листа равна тождественному нулю. Цепи, которые ведут из листа в лист, и обоим листьям приписана одна и та же запись, также можно разорвать без нарушения функционирования.

После удаления ребер, исходящих из листьев, удалим также образовавшиеся несущественные ребра и вершины. Полученный ИГ обозначим U'. Понятно, что U'и(1,Т) и T(U) ^ T(U').

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

Теперь каждой ориентированной цепи, начинающейся в корне, сопоставим последовательность целых чисел, которую назовем кодом цепи, следующим образом. В начальный момент код некоторой цепи не содержит ни одного числа. Начиная с первого, просматриваем по очереди ребра цепи и для каждого выполняем следующее: если данное ребро переключательное, то добавляем к концу кода число, приписанное данному ребру; если данное ребро предикатное и имеет номер <7, а из начала ребра исходит г ребер, то добавляем к концу кода сначала q чисел “-1”, а затем тq чисел “—2”. Понятно, что для каждой цепи однозначно выписывается код и коды, соответствующие разным цепям, разные.

Предположим, что T(U') = п < ]logm V[. Рассмотрим множество С всех цепей ИГ U ведущих их корня в некоторый лист, проводимость которых не равна тождественному нулю. Возьмем произвольную цепь С G С. Через пс обозначим длину кода цепи С. Пусть fc — проводимость цепи С. Возьмем произвольный запрос х 6 ЛГ/С. Так как fc{%) = = 1, то запрос х доходит до каждой вершины цепи С, откуда следует, что число вычисленных переключателей и предикатов на запросе х будет равно по крайней мере п^, т.е. T(U>x) ^ пс• Следовательно, пс ^ п для любой цепи С € С. Так как все листья в U' концевые вершины, и так для каждой записи из V существует лист, которому приписана эта запись и в который ведет из корня некоторая цепь, то

|С| > v.

Теперь, если для некоторой цепи С € С выполнено пс < п, то добавим п — пс нулей к коду цепи С. Полученные коды цепей из С обладают следующими свойствами:

  • 1. коды, соответствующие разным цепям, разные;
  • 2. никакой код не может быть префиксом другого кода;
  • 3. для любых двух кодов, имеющих общий префикс длины / (Z < п), в обоих кодах / + 1-й элемент является одновременно
  • • либо отрицательным числом,
  • • либо нулем,
  • • либо положительным числом.

Из свойств 2 и 3 сразу следует, что различных кодов может быть не более чем тпп. Так как п < ]logm |V|[ и п — целое число, то п < < logm |V|. Отсюда следует, что число различных кодов не более чем mn <бт1Ч = |V|. То есть, кодов длины п не хватит, чтобы закодировать все цепи из С. Противоречие.

Таким образом, мы показали, что для любого ИГ UU(I,T) выполняется T(U) ^ )logm |V|[. Следовательно, Т(/, Т) ^ ]logm V[.

Тем самым теорема доказана.

Результат теоремы 9 аналогичен теоретико-информационной нижней оценке [121], но все же является несколько более сильным, поскольку доказан для произвольных сетей, а не бинарных деревьев.

  • [1] 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
  • [2] 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
  • [3] 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
  • [4] 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
  • [5] 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
  • [6] 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
  • [7] 3l 4- З*-1 < к ^ 2 • 3Z. Тогда ]к/2 > (31 4- 3,’{{ 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
  • [8] 3* < к ^ З1 4-31’1. Тогда По предположению индукции Z(]fc/2[) = 3(/ — 1) 4-2 = 3/ -1, и, значит,Z(D2) 5*24-3/ -1 = 3/ 4-1 = W(k).
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>