Участник:Shovkoplyas Grigory — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
== Идея ==
+
'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".
 
  
== Алгоритм ==
+
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex> и слово <tex>w</tex>.<br/>
Пусть <tex> a </tex> {{---}} отсортированный массив из <tex> n </tex> чисел, <tex> x </tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
+
'''Выход:''' <tex>true</tex>, если <tex>w</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
  
Формула для разделительного элемента <tex> m </tex> получается из следующего уравнения: <tex dpi = "170"> \frac{x - a_l}{m - l} = \frac{a_r - a_l}{r - l} </tex> {{---}}
+
==Определения==
откуда следует, что <tex> m = l + </tex> <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex>. На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на том, что наш массив представляет из себя что-то наподобии арифметической прогрессии.
+
{{Определение
[[Файл:interpolation_search_from_gshark.png|500px|center|Размещение разделительного элемента]]
+
|definition =
 +
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
 +
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>.
 +
}}
  
== Псевдокод ==
+
{{Определение
<code>
+
|definition =
'''int''' interpolationSearch(a : '''int[]''', key : '''int''') <font color=green> // a должен быть отсортирован </font>
+
'''<tex>j</tex>-м списком ситуаций''' <tex>I_j</tex> для входной цепочки <tex>w = a_1 a_2 ... a_n</tex>, где <tex>0 \leqslant j \leqslant n</tex>, называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* a_{i+1} ... a_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i \rbrace</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>w</tex> c первого по <tex>j</tex>-й символ.
  left = 0 <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) </font>
+
}}
  right = a.length - 1 <font color=green> // правая граница поиска </font>
+
 
 +
{{Лемма
 +
|statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow w \in L(G)</tex>.
 +
|proof = Поскольку <tex>S \Rightarrow^* \gamma S \delta</tex> (при <tex>\gamma = \delta = \varepsilon</tex>), из определения <tex>I_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* a_1 ... a_n = w)</tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
Последовательность списков ситуаций <tex>I_0, I_1, .., I_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
 +
}}
 +
 
 +
== Алгоритм Эрли ==
 +
Чтобы воспользоваться леммой, необходимо найти <tex>I_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <tex>I_j</tex> используются <tex>I_0, \ldots, I_{j}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
 +
 
 +
Алгоритм основывается на следующих трёх правилах:
 +
# Если <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex> (где <tex>a_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i] \in I_j</tex>.
 +
# Если <tex>[B \rightarrow \eta \cdot , k] \in I_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_{k}</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, i] \in I_j</tex>.
 +
# Если <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j</tex> и <tex>(A \rightarrow \beta) \in P</tex>, то <tex>[A \rightarrow \cdot \beta, j] \in I_j</tex>.
 +
 
 +
=== Псевдокод ===
 +
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
 +
 
 +
<tex>I_0</tex> = <tex>\lbrace [S' \rightarrow \cdot S, 0] \rbrace</tex> # Правило (0) — инициализация
 +
useful_loop(0)
 
   
 
   
  '''while''' a[left] < key '''and''' key < a[right]
+
for j = 1..n
    mid = left + (key - a[left]) * (right - left) / (a[right] - a[left]) <font color=green> // индекс элемента, с которым будем проводить сравнение </font>
+
    for <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex>
    '''if''' a[mid] < key
+
        <tex>I_j</tex> &cup;= <tex>\{ [A \rightarrow \alpha a_{j} \cdot \beta, i] \}</tex> # Правило (1)
      left = mid + 1
+
    useful_loop(j)
    '''else if''' a[mid] > key
+
 
      right = mid - 1
+
function useful_loop(j):
    '''else'''
+
    do
      '''return''' mid
+
        for <tex>[B \rightarrow \eta \cdot , k] \in I_j</tex>
+
            for <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_{k}</tex>
  '''if''' a[left] == key
+
                <tex>I_j</tex> &cup;= <tex>\lbrace [A \rightarrow \alpha B \cdot \beta, i] \rbrace</tex> # Правило (2)
    '''return''' left
+
           
  '''else if''' a[right] == key
+
        for <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j</tex>
    '''return''' right
+
            for <tex>\beta : (A \rightarrow \beta) \in P</tex>
  '''else'''
+
                <tex>I_j</tex> &cup;= <tex>\lbrace [A \rightarrow \cdot \beta, j] \rbrace</tex> # Правило (3)
    '''return''' -1 <font color=green>// если такого элемента в массиве нет </font>
+
    while на данной итерации какое-то множество изменилось
</code>
+
 
 +
==Корректность алгоритма==
 +
{{Теорема
 +
|statement = Приведенный алгоритм правильно строит все списки ситуаций.
 +
|proof =
 +
 
 +
 
 +
=====Алгоритм не добавит в список ситуацию, которая ему не принадлежит:=====
 +
Докажем индукцией по исполнению алгоритма.<br/>
 +
База (инициализация): <tex>\alpha = \varepsilon \Rightarrow^* \varepsilon </tex> и <tex>S' \Rightarrow^* \gamma S \delta </tex> при <tex>\gamma = \delta = \varepsilon </tex>.<br/>
 +
Индукционный переход: пусть в <tex> I_{0},...,I_{j} </tex> нет лишних ситуаций. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:
 +
 
 +
1. Включаем по правилу <tex>(1)</tex>.<br/>
 +
Тогда <tex>\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>. По предположению <tex>\alpha' \Rightarrow^* a_{i+1}...a_{j-1} </tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' \Rightarrow^* a_1...a_{i} </tex>. Значит, <tex> \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j} </tex> и при <tex>\gamma = \gamma', \delta = \delta'</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j</tex>.
 +
 
 +
2. Включаем по правилу <tex>(2)</tex>.<br/>
 +
Тогда <tex>\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> и <tex> [B \rightarrow \eta \cdot, k] \in I_{j} </tex>. По предположению, <tex>\alpha' \Rightarrow^* a_{i+1}...a_{k}, \eta \Rightarrow^* a_{k+1}...a_{j} </tex>, откуда <tex>\alpha = \alpha' B \Rightarrow^*a_{i+1}...a_{j} </tex>. Кроме того, существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} </tex>. Значит, при <tex>\gamma = \gamma', \delta = \delta'</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j</tex>.
 +
 
 +
3. Включаем по правилу <tex>(3)</tex>.<br/>
 +
Тогда <tex>\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \eta, k] \in I_{j}, A \Rightarrow \beta</tex>. По предположению <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}</tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' B \delta', \gamma' \Rightarrow^* a_1...a_{k} </tex>. Значит, при <tex>\gamma = \gamma' \alpha', \delta = \eta \delta' </tex>  выполнено <tex> S' \Rightarrow^* \gamma A \delta</tex>, следовательно <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j</tex>.
 +
 
 +
=====В каждый список попадут все ситуации, которые ему принадлежат:=====
 +
Для всех наборов <tex>\tau = \langle \alpha, \beta, \gamma, \delta, A, i , j \rangle</tex> нужно доказать, что, если <tex> S' \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{i}, (A \rightarrow \alpha \beta) \in P, \alpha \Rightarrow^* a_{i+1}...a_{j}</tex>, то алгоритм добавит <tex> [A \rightarrow \alpha \cdot \beta, i]</tex> в <tex> I_{j}</tex>.
 +
 
 +
''Рангом набора'' <tex> \tau </tex> называется <tex> \tau_{S'}(\tau) + 2(j + \tau_{\gamma}(\tau) + \tau_{\alpha}(\tau))</tex>, где <tex>\tau_{S'}(\tau)</tex> — длина кратчайшего вывода <tex>S' \Rightarrow^* \gamma A \delta </tex>, <tex>\tau_{\gamma}(\tau)</tex> — длина кратчайшего вывода <tex>\gamma \Rightarrow^* a_1...a_{i}</tex>, <tex>\tau_{\alpha}(\tau)</tex> — длина кратчайшего вывода <tex>\alpha \Rightarrow^* a_{i+1}...a_{j}</tex>.
 +
 
 +
Докажем утверждение индукцией по рангу набора.<br/>
 +
База: если ранг <tex>\tau</tex> равен 0, то <tex>\tau_{S'} = \tau_{\gamma} = \tau_{\alpha} = j = i = 0</tex>. Значит, <tex>A = S'</tex>, <tex>\alpha = \gamma = \delta = \varepsilon </tex>, <tex>\beta = S </tex>. При инициализации такая ситуация <tex>[S' \rightarrow \cdot S, 0]</tex> будет добавлена в <tex>I_0</tex>.<br/>
 +
Индукционный переход:
 +
пусть ранг <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>\tau</tex>. Для этого рассмотрим три случая:
 +
 
 +
1. <tex>\alpha</tex> оканчивается терминалом.<br/>
 +
<tex>\alpha = \alpha' c</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>c = a_{j}</tex>. Рассмотрим набор <tex>\tau' = \langle \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \rangle </tex>. <tex>(A \rightarrow \alpha' a_{j} \beta) \in P</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 2</tex>, так как <tex>\tau_{S'}(\tau) = \tau_{S'}(\tau'), \tau_{\gamma}(\tau) = \tau_{\gamma}(\tau'), \tau_{\alpha}(\tau) = \tau_{\alpha}(\tau')</tex>. Значит, по предположению <tex>[A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>, и <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex> по правилу <tex>(1)</tex>.
 +
 
 +
2. <tex>\alpha</tex> оканчивается нетерминалом.<br/>
 +
<tex>\alpha = \alpha' B</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>\mathcal {9} k</tex> такое, что <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}, B \Rightarrow^* a_{k+1}...a_{j}</tex>.<br/>
 +
Рассмотрим набор <tex>\tau' = \langle \alpha', B \beta, \gamma, \delta, A, i, k \rangle</tex>, его ранг меньше <tex>r</tex>, следовательно <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> по предположению.<br/>
 +
Пусть <tex>B \Rightarrow \eta</tex> — первый шаг в кратчайшем выводе <tex>B \Rightarrow^* a_{k+1}...a_{j}</tex>. Рассмотрим набор <tex>\tau'' = \langle \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \rangle</tex>. <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta</tex>, следовательно <tex>\tau_{S'}(\tau'') \leqslant \tau_{S'}(\tau) + 1</tex>.<br> Пусть длина кратчайшего вывода <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}</tex> равна <tex>n_1</tex>, а длина кратчайшего вывода <tex> B \Rightarrow^* a_{k+1}...a_{j}</tex> равна <tex>n_2</tex>. Тогда <tex>\tau_{\alpha}(\tau) = n_1 + n_2</tex>. Так как <tex> B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}</tex>, то <tex>\tau_{\alpha}(\tau'') = n_2 - 1</tex>. Очевидно, что <tex>\tau_{\gamma}(\tau'') = \tau_{\gamma}(\tau) + n_1</tex>. Тогда ранг <tex>\tau''</tex> равен <tex>\tau_{S'}(\tau'') + 2(\tau_{\gamma}(\tau'') + \tau_{\alpha}(\tau'') + j) \leqslant \tau_{S'}(\tau) + 1 + 2(\tau_{\gamma}(\tau) + n_1 + n_2 - 1 + j)</tex> <tex>= \tau_{S'}(\tau) - 1 + 2(\tau_{\gamma}(\tau) + \tau_{\alpha}(\tau) + j) < r</tex>. Значит, по предположению для <tex>\tau''</tex>, <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex>. Из того, что <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> и <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex>, по правилу <tex>(2)</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
 +
 
 +
3. <tex>\alpha = \varepsilon</tex>.<br/>
 +
В этом случае <tex>i = j, \tau_{\alpha}(\tau) = 0, (A \rightarrow \beta) \in P</tex>.<br/>
 +
<tex>\tau_{S'}(\tau) \neq 0</tex> т.к. иначе <tex> \gamma = \varepsilon</tex>, следовательно <tex> \tau_{\gamma}(\tau) = 0, i = 0 </tex>, откуда <tex> r = 0</tex>, но <tex>r > 0</tex>.
 +
Т.к. <tex>\tau_{S'}(\tau) > 0</tex>, <tex> \exists B, \gamma', \gamma'', \delta', \delta'' : S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''</tex>, где <tex>(B \rightarrow \gamma'' A \delta'') \in P</tex>. Рассмотрим набор <tex>\tau' = \langle \gamma'', A \delta'', \gamma', \delta', B, k, j \rangle</tex>, где <tex>k</tex> такое, что <tex>\gamma' \Rightarrow^* a_1...a_{k}, \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex>.
 +
Пусть длина кратчайшего вывода <tex>\gamma' \Rightarrow^*a_{1}...a_{k}</tex> равна <tex>n_1</tex>, а длина кратчайшего вывода <tex> \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex> равна <tex>n_2</tex>.<br/>
 +
Найдём ранг <tex>\tau'</tex>. <tex>\tau_{S'}(\tau') = \tau_{S'}(\tau) - 1, \tau_{\gamma}(\tau') = n_1, \tau_{\alpha}(\tau') = n_2</tex>. <tex>\tau_{\alpha}(\tau) = 0, \tau_{\gamma}(\tau) = n_1 + n_2</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 1</tex>. Значит, по предположению <tex>[B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}</tex>, следовательно по правилу <tex>(3)</tex> <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
 +
}}
 +
 
 +
==Пример==
 +
Построим список разбора для строки <tex>w = (a + a)</tex> в грамматике со следующими правилами:
 +
* <tex>S \rightarrow T + S</tex>;
 +
* <tex>S \rightarrow T </tex>;
 +
* <tex>T \rightarrow F * T</tex>;
 +
* <tex>T \rightarrow F</tex>;
 +
* <tex>F \rightarrow ( S )</tex>;
 +
* <tex>F \rightarrow a</tex>.
 +
 
 +
{|
 +
|-
 +
|
 +
 
 +
{| class="wikitable"
 +
|-
 +
!<tex>I_0</tex>
 +
|-
 +
|
 +
{|
 +
|-
 +
!Ситуация !! Из правила
 +
|-
 +
|<tex>[S' \rightarrow \cdot S, 0]</tex> || 0
 +
|-
 +
|<tex>[S \rightarrow \cdot T + S, 0]</tex> || 3
 +
|-
 +
|<tex>[S \rightarrow \cdot T, 0]</tex> || 3
 +
|-
 +
|<tex>[T \rightarrow \cdot F * T, 0]</tex> || 3
 +
|-
 +
|<tex>[T \rightarrow \cdot F, 0]</tex> || 3
 +
|-
 +
|<tex>[F \rightarrow \cdot ( S ), 0]</tex> || 3
 +
|-
 +
|<tex>[F \rightarrow \cdot a, 0]</tex> || 3
 +
|}
 +
|}
 +
 
 +
||
 +
 
 +
{| class="wikitable"
 +
|-
 +
!<tex>I_1</tex>
 +
|-
 +
|
 +
{|
 +
|-
 +
!Ситуация !! Из правила
 +
|-
 +
|<tex>[F \rightarrow ( \cdot S ), 0]</tex> || 1
 +
|-
 +
|<tex>[S \rightarrow \cdot T + S, 1]</tex> || 3
 +
|-
 +
|<tex>[S \rightarrow \cdot T, 1]</tex> || 3
 +
|-
 +
|<tex>[T \rightarrow \cdot F * T, 1]</tex> || 3
 +
|-
 +
|<tex>[T \rightarrow \cdot F, 1]</tex> || 3
 +
|-
 +
|<tex>[F \rightarrow \cdot ( S ), 1]</tex> || 3
 +
|-
 +
|<tex>[F \rightarrow \cdot a, 1]</tex> || 3
 +
|}
 +
|}
 +
 
 +
||
 +
 
 +
{| class="wikitable"
 +
|-
 +
!<tex>I_2</tex>
 +
|-
 +
|
 +
{|
 +
|-
 +
!Ситуация !! Из правила
 +
|-
 +
|<tex>[F \rightarrow a \cdot, 1]</tex> || 1
 +
|-
 +
|<tex>[T \rightarrow F \cdot * T, 1]</tex> || 2
 +
|-
 +
|<tex>[T \rightarrow F \cdot , 1]</tex> || 2
 +
|-
 +
|<tex>[S \rightarrow T \cdot , 1]</tex> || 2
 +
|-
 +
|<tex>[S \rightarrow T \cdot + S, 1]</tex> || 2
 +
|-
 +
|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2
 +
|}
 +
|}
 +
 
 +
|-
 +
|
 +
 
 +
{| class="wikitable"
 +
|-
 +
!<tex>I_3</tex>
 +
|-
 +
|
 +
{|
 +
|-
 +
!Ситуация !! Из правила
 +
|-
 +
|<tex>[S \rightarrow T + \cdot S, 1]</tex> || 1
 +
|-
 +
|<tex>[S \rightarrow \cdot T + S, 3]</tex> || 3
 +
|-
 +
|<tex>[S \rightarrow \cdot T, 3]</tex> || 3
 +
|-
 +
|<tex>[T \rightarrow \cdot F * T, 3]</tex> || 3
 +
|-
 +
|<tex>[T \rightarrow \cdot F, 3]</tex> || 3
 +
|-
 +
|<tex>[F \rightarrow \cdot ( S ), 3]</tex> || 3
 +
|-
 +
|<tex>[F \rightarrow \cdot a, 3]</tex> || 3
 +
|}
 +
|}
 +
 
 +
||
  
==Пример работы вместе с сравнением с бинарным поиском==
+
{| class="wikitable"
[[Файл:ip_vs_bin_from_gshark.png|900px|center|Сравнение бинарного и интерполирующего поисков]]
+
|-
 +
!<tex>I_4</tex>
 +
|-
 +
|
 +
{|
 +
|-
 +
!Ситуация !! Из правила
 +
|-
 +
|<tex>[F \rightarrow a \cdot , 3]</tex> || 1
 +
|-
 +
|<tex>[T \rightarrow F \cdot * T, 3]</tex> || 2
 +
|-
 +
|<tex>[T \rightarrow F \cdot , 3]</tex> || 2
 +
|-
 +
|<tex>[S \rightarrow T \cdot + S, 3]</tex> || 2
 +
|-
 +
|<tex>[S \rightarrow T \cdot , 3]</tex> || 2
 +
|-
 +
|<tex>[S \rightarrow T + S \cdot , 1]</tex> || 2
 +
|-
 +
|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2
 +
|}
 +
|}
  
== Время работы ==
+
||
Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с <tex> n </tex> до <tex> \sqrt n </tex>
 
<ref>[http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf Interpolation Search {{---}} A LogLogN Search]</ref>. То есть, после <tex>k</tex>-ого шага количество проверяемых элементов уменьшается до <tex dpi = 170>n^{\frac{1}{2^k}}</tex>. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда <tex dpi = 150>\frac{1}{2^k} = \log_{n}2 = \frac{1}{\log_{2}n} </tex>. Из этого вытекает, что количество шагов, а значит, и время работы составляет <tex>O(\log \log n)</tex>.
 
  
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до <tex> O(n) </tex>.
+
{| class="wikitable"
 +
|-
 +
!<tex>I_5</tex>
 +
|-
 +
|
 +
{|
 +
|-
 +
!Ситуация !! Из правила
 +
|-
 +
|<tex>[F \rightarrow ( S )\cdot , 0]</tex> || 1
 +
|-
 +
|<tex>[T \rightarrow F \cdot * T, 0]</tex> || 2
 +
|-
 +
|<tex>[T \rightarrow F \cdot , 0]</tex> || 2
 +
|-
 +
|<tex>[S \rightarrow T \cdot + S, 0]</tex> || 2
 +
|-
 +
|<tex>[S \rightarrow T \cdot , 0]</tex> || 2
 +
|-
 +
|<tex>[S' \rightarrow S \cdot , 0]</tex> || 2
 +
|}
 +
|}
  
Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями <tex>\log \log n</tex> и <tex>\log n</tex> становится значительной только при очень больших <tex>n</tex>. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.
+
|}
  
==Примечания==
+
Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5</tex>, то <tex>w \in L(G) </tex>.<br>
<references/>
 
  
 
==Источники информации==
 
==Источники информации==
 
* Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.
 
* Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.
 
*[http://en.wikipedia.org/wiki/Interpolation_search Wikipedia {{---}} Interpolation search]
 
*[http://en.wikipedia.org/wiki/Interpolation_search Wikipedia {{---}} Interpolation search]
*[http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B8%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия {{---}}Интерполирующий поиск]
+
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 +
* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.

Версия 18:26, 16 января 2016

Алгоритм Эрли позволяет определить, выводится ли данное слово [math]w[/math] в данной контекстно-свободной грамматике [math]G[/math].

Вход: КС грамматика [math] G=\langle N,\Sigma, P, S \rangle[/math] и слово [math]w[/math].
Выход: [math]true[/math], если [math]w[/math] выводится в [math]G[/math]; [math]false[/math] — иначе.

Определения

Определение:
Пусть [math]G = \langle N, \Sigma, P, S \rangle[/math]контекстно-свободная грамматика и [math]w = a_1 a_2 ... a_n[/math] — входная цепочка из [math]\Sigma^*[/math]. Объект вида [math][A \rightarrow \alpha \cdot \beta, i][/math], где [math]A \rightarrow \alpha \beta [/math] — правило из [math]P[/math] и [math]0 \leqslant i \leqslant n[/math] — позиция в [math]w[/math], называется ситуацией, относящейся к цепочке [math]w[/math].


Определение:
[math]j[/math]-м списком ситуаций [math]I_j[/math] для входной цепочки [math]w = a_1 a_2 ... a_n[/math], где [math]0 \leqslant j \leqslant n[/math], называется множество ситуаций [math]\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* a_{i+1} ... a_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i \rbrace[/math]. То есть [math]\gamma \alpha [/math] выводит часть [math]w[/math] c первого по [math]j[/math]-й символ.


Лемма:
[math](\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow w \in L(G)[/math].
Доказательство:
[math]\triangleright[/math]
Поскольку [math]S \Rightarrow^* \gamma S \delta[/math] (при [math]\gamma = \delta = \varepsilon[/math]), из определения [math]I_n[/math] получаем, что [math]([S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* a_1 ... a_n = w)[/math].
[math]\triangleleft[/math]


Определение:
Последовательность списков ситуаций [math]I_0, I_1, .., I_n[/math] называется списком разбора для входной цепочки [math]w[/math].


Алгоритм Эрли

Чтобы воспользоваться леммой, необходимо найти [math]I_n[/math] для [math]w[/math]. Алгоритм Эрли является динамическим алгоритмом: он последовательно строит список разбора, причём при построении [math]I_j[/math] используются [math]I_0, \ldots, I_{j}[/math] (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).

Алгоритм основывается на следующих трёх правилах:

  1. Если [math][A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}[/math] (где [math]a_j[/math][math]j[/math]-ый символ строки), то [math][A \rightarrow \alpha a_{j} \cdot \beta, i] \in I_j[/math].
  2. Если [math][B \rightarrow \eta \cdot , k] \in I_j[/math] и [math][A \rightarrow \alpha \cdot B \beta, i] \in I_{k}[/math], то [math][A \rightarrow \alpha B \cdot \beta, i] \in I_j[/math].
  3. Если [math][B \rightarrow \alpha \cdot A \eta, k] \in I_j[/math] и [math](A \rightarrow \beta) \in P[/math], то [math][A \rightarrow \cdot \beta, j] \in I_j[/math].

Псевдокод

Для простоты добавим новый стартовый вспомогательный нетерминал [math]S'[/math] и правило [math](S' \rightarrow S)[/math].

[math]I_0[/math] = [math]\lbrace [S' \rightarrow \cdot S, 0] \rbrace[/math] # Правило (0) — инициализация
useful_loop(0)

for j = 1..n
    for [math][A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}[/math]
        [math]I_j[/math] ∪= [math]\{ [A \rightarrow \alpha a_{j} \cdot \beta, i] \}[/math] # Правило (1)
    useful_loop(j)
function useful_loop(j):
    do
        for [math][B \rightarrow \eta \cdot , k] \in I_j[/math]
            for [math][A \rightarrow \alpha \cdot B \beta, i] \in I_{k}[/math]
                [math]I_j[/math] ∪= [math]\lbrace [A \rightarrow \alpha B \cdot \beta, i] \rbrace[/math] # Правило (2)
            
        for [math][B \rightarrow \alpha \cdot A \eta, k] \in I_j[/math]
            for [math]\beta : (A \rightarrow \beta) \in P[/math]
                [math]I_j[/math] ∪= [math]\lbrace [A \rightarrow \cdot \beta, j] \rbrace[/math] # Правило (3)
    while на данной итерации какое-то множество изменилось

Корректность алгоритма

Теорема:
Приведенный алгоритм правильно строит все списки ситуаций.
Доказательство:
[math]\triangleright[/math]
Алгоритм не добавит в список ситуацию, которая ему не принадлежит:

Докажем индукцией по исполнению алгоритма.
База (инициализация): [math]\alpha = \varepsilon \Rightarrow^* \varepsilon [/math] и [math]S' \Rightarrow^* \gamma S \delta [/math] при [math]\gamma = \delta = \varepsilon [/math].
Индукционный переход: пусть в [math] I_{0},...,I_{j} [/math] нет лишних ситуаций. Пусть включаем [math][A \rightarrow \alpha \cdot \beta, i] [/math] в [math]I_{j}[/math]. Рассмотрим три случая:

1. Включаем по правилу [math](1)[/math].
Тогда [math]\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math]. По предположению [math]\alpha' \Rightarrow^* a_{i+1}...a_{j-1} [/math] и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' A \delta', \gamma' \Rightarrow^* a_1...a_{i} [/math]. Значит, [math] \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j} [/math] и при [math]\gamma = \gamma', \delta = \delta'[/math] [math][A \rightarrow \alpha \cdot \beta, i] \in I_j[/math].

2. Включаем по правилу [math](2)[/math].
Тогда [math]\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math] и [math] [B \rightarrow \eta \cdot, k] \in I_{j} [/math]. По предположению, [math]\alpha' \Rightarrow^* a_{i+1}...a_{k}, \eta \Rightarrow^* a_{k+1}...a_{j} [/math], откуда [math]\alpha = \alpha' B \Rightarrow^*a_{i+1}...a_{j} [/math]. Кроме того, существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} [/math]. Значит, при [math]\gamma = \gamma', \delta = \delta'[/math] [math][A \rightarrow \alpha \cdot \beta, i] \in I_j[/math].

3. Включаем по правилу [math](3)[/math].
Тогда [math]\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \eta, k] \in I_{j}, A \Rightarrow \beta[/math]. По предположению [math]\alpha' \Rightarrow^* a_{k+1}...a_{i}[/math] и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' B \delta', \gamma' \Rightarrow^* a_1...a_{k} [/math]. Значит, при [math]\gamma = \gamma' \alpha', \delta = \eta \delta' [/math] выполнено [math] S' \Rightarrow^* \gamma A \delta[/math], следовательно [math][A \rightarrow \alpha \cdot \beta, i] \in I_j[/math].

В каждый список попадут все ситуации, которые ему принадлежат:

Для всех наборов [math]\tau = \langle \alpha, \beta, \gamma, \delta, A, i , j \rangle[/math] нужно доказать, что, если [math] S' \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{i}, (A \rightarrow \alpha \beta) \in P, \alpha \Rightarrow^* a_{i+1}...a_{j}[/math], то алгоритм добавит [math] [A \rightarrow \alpha \cdot \beta, i][/math] в [math] I_{j}[/math].

Рангом набора [math] \tau [/math] называется [math] \tau_{S'}(\tau) + 2(j + \tau_{\gamma}(\tau) + \tau_{\alpha}(\tau))[/math], где [math]\tau_{S'}(\tau)[/math] — длина кратчайшего вывода [math]S' \Rightarrow^* \gamma A \delta [/math], [math]\tau_{\gamma}(\tau)[/math] — длина кратчайшего вывода [math]\gamma \Rightarrow^* a_1...a_{i}[/math], [math]\tau_{\alpha}(\tau)[/math] — длина кратчайшего вывода [math]\alpha \Rightarrow^* a_{i+1}...a_{j}[/math].

Докажем утверждение индукцией по рангу набора.
База: если ранг [math]\tau[/math] равен 0, то [math]\tau_{S'} = \tau_{\gamma} = \tau_{\alpha} = j = i = 0[/math]. Значит, [math]A = S'[/math], [math]\alpha = \gamma = \delta = \varepsilon [/math], [math]\beta = S [/math]. При инициализации такая ситуация [math][S' \rightarrow \cdot S, 0][/math] будет добавлена в [math]I_0[/math].
Индукционный переход: пусть ранг [math]\tau[/math] равен [math]r \gt 0[/math], пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора [math]\tau[/math]. Для этого рассмотрим три случая:

1. [math]\alpha[/math] оканчивается терминалом.
[math]\alpha = \alpha' c[/math]. [math]\alpha \Rightarrow^*a_{i+1}...a_{j}[/math], значит [math]c = a_{j}[/math]. Рассмотрим набор [math]\tau' = \langle \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \rangle [/math]. [math](A \rightarrow \alpha' a_{j} \beta) \in P[/math], следовательно ранг [math]\tau'[/math] равен [math]r - 2[/math], так как [math]\tau_{S'}(\tau) = \tau_{S'}(\tau'), \tau_{\gamma}(\tau) = \tau_{\gamma}(\tau'), \tau_{\alpha}(\tau) = \tau_{\alpha}(\tau')[/math]. Значит, по предположению [math][A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math], и [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math] по правилу [math](1)[/math].

2. [math]\alpha[/math] оканчивается нетерминалом.
[math]\alpha = \alpha' B[/math]. [math]\alpha \Rightarrow^*a_{i+1}...a_{j}[/math], значит [math]\mathcal {9} k[/math] такое, что [math]\alpha' \Rightarrow^*a_{i+1}...a_{k}, B \Rightarrow^* a_{k+1}...a_{j}[/math].
Рассмотрим набор [math]\tau' = \langle \alpha', B \beta, \gamma, \delta, A, i, k \rangle[/math], его ранг меньше [math]r[/math], следовательно [math][A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math] по предположению.
Пусть [math]B \Rightarrow \eta[/math] — первый шаг в кратчайшем выводе [math]B \Rightarrow^* a_{k+1}...a_{j}[/math]. Рассмотрим набор [math]\tau'' = \langle \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \rangle[/math]. [math]S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta[/math], следовательно [math]\tau_{S'}(\tau'') \leqslant \tau_{S'}(\tau) + 1[/math].
Пусть длина кратчайшего вывода [math]\alpha' \Rightarrow^*a_{i+1}...a_{k}[/math] равна [math]n_1[/math], а длина кратчайшего вывода [math] B \Rightarrow^* a_{k+1}...a_{j}[/math] равна [math]n_2[/math]. Тогда [math]\tau_{\alpha}(\tau) = n_1 + n_2[/math]. Так как [math] B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}[/math], то [math]\tau_{\alpha}(\tau'') = n_2 - 1[/math]. Очевидно, что [math]\tau_{\gamma}(\tau'') = \tau_{\gamma}(\tau) + n_1[/math]. Тогда ранг [math]\tau''[/math] равен [math]\tau_{S'}(\tau'') + 2(\tau_{\gamma}(\tau'') + \tau_{\alpha}(\tau'') + j) \leqslant \tau_{S'}(\tau) + 1 + 2(\tau_{\gamma}(\tau) + n_1 + n_2 - 1 + j)[/math] [math]= \tau_{S'}(\tau) - 1 + 2(\tau_{\gamma}(\tau) + \tau_{\alpha}(\tau) + j) \lt r[/math]. Значит, по предположению для [math]\tau''[/math], [math][B \rightarrow \eta \cdot, k] \in I_{j}[/math]. Из того, что [math][A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math] и [math][B \rightarrow \eta \cdot, k] \in I_{j}[/math], по правилу [math](2)[/math] [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math].

3. [math]\alpha = \varepsilon[/math].
В этом случае [math]i = j, \tau_{\alpha}(\tau) = 0, (A \rightarrow \beta) \in P[/math].
[math]\tau_{S'}(\tau) \neq 0[/math] т.к. иначе [math] \gamma = \varepsilon[/math], следовательно [math] \tau_{\gamma}(\tau) = 0, i = 0 [/math], откуда [math] r = 0[/math], но [math]r \gt 0[/math]. Т.к. [math]\tau_{S'}(\tau) \gt 0[/math], [math] \exists B, \gamma', \gamma'', \delta', \delta'' : S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''[/math], где [math](B \rightarrow \gamma'' A \delta'') \in P[/math]. Рассмотрим набор [math]\tau' = \langle \gamma'', A \delta'', \gamma', \delta', B, k, j \rangle[/math], где [math]k[/math] такое, что [math]\gamma' \Rightarrow^* a_1...a_{k}, \gamma'' \Rightarrow^* a_{k+1}...a_{j}[/math]. Пусть длина кратчайшего вывода [math]\gamma' \Rightarrow^*a_{1}...a_{k}[/math] равна [math]n_1[/math], а длина кратчайшего вывода [math] \gamma'' \Rightarrow^* a_{k+1}...a_{j}[/math] равна [math]n_2[/math].

Найдём ранг [math]\tau'[/math]. [math]\tau_{S'}(\tau') = \tau_{S'}(\tau) - 1, \tau_{\gamma}(\tau') = n_1, \tau_{\alpha}(\tau') = n_2[/math]. [math]\tau_{\alpha}(\tau) = 0, \tau_{\gamma}(\tau) = n_1 + n_2[/math], следовательно ранг [math]\tau'[/math] равен [math]r - 1[/math]. Значит, по предположению [math][B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}[/math], следовательно по правилу [math](3)[/math] [math][A \rightarrow \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math].
[math]\triangleleft[/math]

Пример

Построим список разбора для строки [math]w = (a + a)[/math] в грамматике со следующими правилами:

  • [math]S \rightarrow T + S[/math];
  • [math]S \rightarrow T [/math];
  • [math]T \rightarrow F * T[/math];
  • [math]T \rightarrow F[/math];
  • [math]F \rightarrow ( S )[/math];
  • [math]F \rightarrow a[/math].
[math]I_0[/math]
Ситуация Из правила
[math][S' \rightarrow \cdot S, 0][/math] 0
[math][S \rightarrow \cdot T + S, 0][/math] 3
[math][S \rightarrow \cdot T, 0][/math] 3
[math][T \rightarrow \cdot F * T, 0][/math] 3
[math][T \rightarrow \cdot F, 0][/math] 3
[math][F \rightarrow \cdot ( S ), 0][/math] 3
[math][F \rightarrow \cdot a, 0][/math] 3
[math]I_1[/math]
Ситуация Из правила
[math][F \rightarrow ( \cdot S ), 0][/math] 1
[math][S \rightarrow \cdot T + S, 1][/math] 3
[math][S \rightarrow \cdot T, 1][/math] 3
[math][T \rightarrow \cdot F * T, 1][/math] 3
[math][T \rightarrow \cdot F, 1][/math] 3
[math][F \rightarrow \cdot ( S ), 1][/math] 3
[math][F \rightarrow \cdot a, 1][/math] 3
[math]I_2[/math]
Ситуация Из правила
[math][F \rightarrow a \cdot, 1][/math] 1
[math][T \rightarrow F \cdot * T, 1][/math] 2
[math][T \rightarrow F \cdot , 1][/math] 2
[math][S \rightarrow T \cdot , 1][/math] 2
[math][S \rightarrow T \cdot + S, 1][/math] 2
[math][F \rightarrow ( S \cdot ), 0][/math] 2
[math]I_3[/math]
Ситуация Из правила
[math][S \rightarrow T + \cdot S, 1][/math] 1
[math][S \rightarrow \cdot T + S, 3][/math] 3
[math][S \rightarrow \cdot T, 3][/math] 3
[math][T \rightarrow \cdot F * T, 3][/math] 3
[math][T \rightarrow \cdot F, 3][/math] 3
[math][F \rightarrow \cdot ( S ), 3][/math] 3
[math][F \rightarrow \cdot a, 3][/math] 3
[math]I_4[/math]
Ситуация Из правила
[math][F \rightarrow a \cdot , 3][/math] 1
[math][T \rightarrow F \cdot * T, 3][/math] 2
[math][T \rightarrow F \cdot , 3][/math] 2
[math][S \rightarrow T \cdot + S, 3][/math] 2
[math][S \rightarrow T \cdot , 3][/math] 2
[math][S \rightarrow T + S \cdot , 1][/math] 2
[math][F \rightarrow ( S \cdot ), 0][/math] 2
[math]I_5[/math]
Ситуация Из правила
[math][F \rightarrow ( S )\cdot , 0][/math] 1
[math][T \rightarrow F \cdot * T, 0][/math] 2
[math][T \rightarrow F \cdot , 0][/math] 2
[math][S \rightarrow T \cdot + S, 0][/math] 2
[math][S \rightarrow T \cdot , 0][/math] 2
[math][S' \rightarrow S \cdot , 0][/math] 2

Так как [math][S' \rightarrow S \cdot , 0] \in I_5[/math], то [math]w \in L(G) [/math].

Источники информации

  • Дональд Кнут — Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. — The Art of Computer Programming. Vol. 3. Sorting and Searching.
  • Wikipedia — Interpolation search
  • Алексей Сорокин — Алгоритм Эрли
  • Ахо А., Ульман Д.— Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. С. 358 — 364.