k=l k=o k=\ P k=o

= P + 2{1-P) + H = H+ 2-P. I

В случае указателя KWIC (см. рис. 15) Р = 1304/3288 и 0.39659 и H{pi,рз5, 9о, • • • ,935) « 5.00635. Вследствие этого теорема В утверждает, что С > 3.3800 и согласно теореме М С < 6.6098.

""Алгоритм Гарсия-Воча. Возможно поразительное улучшение алгоритма К в специальном случае: pi = •.•=: р„ = 0. Этот случай, когда роль играют только вероятности листьев {qo,qi,..., qn), особенно важен, так как он нередко встречается во многих приложениях. Далее в этом разделе мы предполагаем, что вероятности Pj - нулевые. В данном случае теоремы В и М сводятся к неравенствам

H{qo,qi,--.,qn) < C{qo,qi,... ,qn) < H{qo,qi,... ,q„) + 2 (27)

и функция цены (14) упрощается до

C=Yqklk, 1к = уровень [к]. (28)

*;=0

Ключевое свойство, позволяющее упростить алгоритм, заключается в следующем наблюдении.

Лемма W. Если q-i > qk+i, то в каждом оптимальном дереве 1к < Ik+i Если же qk~i = qk+i, то в некоторых оптимальных деревьях < Ik+i.

Доказательство. Предположим, что q-i > qk+i, и рассмотрим дерево, в котором > h+i- Тогда [Т] должен быть правым дочерним узлом, а его левый "брат" L - поддеревом веса с > qk-i. Заменим родительский по отношению к \Tj узел

поддеревом L, а узел А:-Ц - узлом, дочерними узлами которого являются А:-Ц I. Такая замена изменит общую стоимость на -с - qk{lk ~ h+\ ~ 1) + qk+i < qk+\ -qk-i Значит, данное дерево не было оптимальным, если выполнялось условие qk-i > qk+i, в случае qk-i = qk+i оптимальное дерево было трансформировано в другое оптимальное дерево. В последнем случае последовательность таких трансформаций приведет к 4 < Ik+i. I

Более глубокий анализ структуры даст нам значительно больше.

Лемма X. Предположим, что j и к - индексы, такие, что j < к и

i) qi-i > qi+i при l<i <к;

ii) qk-i < qk+i;

iii) qi < qk-i + qk при j < i < к - 1;

iv) qj-i > qk-i +qk-

Тогда существует оптимальное дерево, в котором Ik-i = lk ч либо

a) lj - 1к - 1, либо

b) lj = lk и [JJ является левым дочерним узлом.

Доказательство. При замене "левого" "правым" в лемме W мы увидим, что (ii) означает существование оптимального дерева, в котором Ik-i > lk- Однако лемма W и (i) означают, что li < h < • < h- Следовательно, Ik-i = lk-

Предположим, что < t - 1 < Is+i для некоторого j < s < к. Пусть t представляет собой наименьший индекс, меньший к, такой, что It = lk- Тогда Ig+i = • • • = = - 1 и IS+11 представляет собой левый дочерний узел. Отсюда вытекает, что t - s нечетно и узел [Т] является левым дочерним узлом при i = s + 1, s + 3,... ,t.

узлом

Заменим родительский узел узла

а узел li

узлом г+1 I для

S < i < t. Кроме того, заменим внешний узел "7] внутренним узлом, дочерними узлами которого являются [Т] и s+11. Все эти замены приведут к изменению цены

яа < qs - qt - qt+i < qs - qk~i - qk, т. e. к улучшению дерева при < qk-i + qk-Следовательно, согласно (iii) lj >lk - I--

До этого момента мы ни разу не использовали гипотезу (iv). Если lj = 1кИ [71 не является левым дочерним узлом, то [J] должен быть правым "братом" узла j-l. Заменим их родительский узел узлом j-11, а затем заменим каждый лист J листом I г-11 для j < i < к. Заменим также внешний узел [F] внутренним узлом, являющимся родительским по отношению к к-1 и [Т]. Эти действия изменят цену на -qj-i +qk-i +qk < О, так что мы получим оптимальное дерево, удовлетворяющее условию (Ь). I

Лемма Y. Пусть j и к те же, что и в лемме X. Рассмотрим измененные вероятности {qo,---,qn-i) = iqo,---,qj-i,qk-i 9>.---.9*:-2,9+1, •• полученные посредством удаления qk-i и qk и вставки qk-i + qk после qj-\. Тогда

C{qo,...,qn-i) < {qk-i+qk)+C{qo,...,qn).

(29)

Доказательство. Достаточно показать, что любое оптимальное дерево для (qo,..., qn) может быть трансформировано в дерево той же цены, в котором fc-l и \Tj являются "братьями" т. е. имеют один и тот же родительский узел, и листья которого появляются в следующем порядке:

[о] [Ы

Jfc-l

А;-2 Jfc+l

(30)

Мы начнем с дерева, сконструированного в лемме X. Если это дерево типа (Ь), просто переименуем листья, сместив fc-l и [F] влево иак - 1-j мест. Если же это дерево типа (а), предположим, 4to/s i = /. -1 и /« = В этом случае мы действуем следующим образом: сначала сместим [fc-11 и Т] влево на fc - 1 - s мест, затем заменим их новый родительский узел узлом, дочерними узлами которого являются к-11 и Т], а также заменим узел \Т\ узлом г-11 для всех j <i < s.

Лемма Z. При выполнении условий леммы Y неравенство (29) становится равенством.

Доказательство. Каждое дерево для (q,..., qn-i) соответствует дереву с листьями (30), в котором выпадающие из общего порядка листья fc-l и [Т] представляют дочерние узлы одного и того же родительского узла. Пусть этот родительский узел - (х). Мы хотим показать, что любое оптимальное дерево этого типа может быть конвертировано в дерево той же цены, но в котором листья располагаются в нормальном порядке - [о] • • •

13 Щ.,

Рис. 18. Применение

Н I -I

...оритмаГарсия-Воча к данным о частотах

появления букв; фазы 1 и 2.