Изменения

== Идея ==Рассмотрим задачу: найти '''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в словаре. Если оно начинается на букву "А"данной [[Контекстно-свободные грамматики, то никто не будет искать его в серединевывод, а откроет словарь ближе к началу. В чём разница между алгоритмом человека лево- и другими? Отличие заключается в томправосторонний вывод, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше"дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.

== Алгоритм ==Пусть '''Вход:''' КС грамматика <tex> a </tex> {{---}} отсортированный массив из <tex> n </tex> чиселG=\langle N,\Sigma, P, <tex> x S \rangle</tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что слово <tex> x w</tex> лежит между <tex> a_l .<br/tex> и '''Выход:''' <tex> a_r true</tex>, то следующая проверка выполняется примерно на расстоянии если <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdotw</tex> выводится в <tex> (r - l) G</tex> от ; <tex> l false</tex>— иначе.

Формула для разделительного элемента ==Определения=={{Определение|definition =Пусть <tex> m G = \langle N, \Sigma, P, S \rangle</tex> получается из следующего уравнения: <tex dpi = "170"> \frac{x {--- a_l}{m } [[Контекстно- l} = \frac{a_r свободные грамматики, вывод, лево- a_l}{r и правосторонний вывод, дерево разбора|контекстно- l} свободная]] грамматика и <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> m = l + — правило из <tex>P</tex> и <tex dpi = "170"> 0 \frac{x - a_l}{a_r - a_l} leqslant i \cdotleqslant n</tex> — позиция в <tex> (r - l) w</tex>. На рисунке внизу показано, из каких соображений берется такая оценка. Интерполяционный поиск основывается на томназывается '''ситуацией''', что наш массив представляет из себя что-то наподобии арифметической прогрессииотносящейся к цепочке <tex>w</tex>.[[Файл:interpolation_search_from_gshark.png|500px|center|Размещение разделительного элемента]] }}

== Псевдокод ={{Определение|definition =<code> '''int<tex>j</tex>-м списком ситуаций''' interpolationSearch(a : '''int<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, key \delta : '''int''') S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i \rbrace</tex>. То есть <font color=greentex> \gamma \alpha </tex> выводит часть <tex>w</ a должен быть отсортирован tex> c первого по <tex>j</fonttex>-й символ.}} left {{Лемма|statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0 ] \in I_n) \Leftrightarrow w \in L(G)<font color/tex>.|proof =greenПоскольку <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) </fonttex>. right }} {{Определение|definition = aПоследовательность списков ситуаций <tex>I_0, I_1, .length ., 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>, то <font colortex>[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>. === Псевдокод ===greenДля простоты добавим новый стартовый вспомогательный нетерминал <tex> S'</tex> и правило <tex>(S' \rightarrow S)</ правая граница поиска tex>.  <tex>I_0</tex> = <tex>\lbrace [S' \rightarrow \cdot S, 0] \rbrace</fonttex># Правило (0) — инициализация useful_loop(0)

for j = 1..n for <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex> <tex>I_j</tex> &cup;= <tex>\{ [A \rightarrow \alpha a_{j} \cdot \beta, i] \}</tex> # Правило (1) useful_loop(j)  function useful_loop(j): do for <tex>[B \rightarrow \eta \cdot , k] \in I_j</tex> for <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_{k}</tex> <tex>I_j</tex> &cup;= <tex>\lbrace [A \rightarrow \alpha B \cdot \beta, i] \rbrace</tex> # Правило (2) for <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j</tex> for <tex>\beta : (A \rightarrow \beta) \in P</tex> <tex>I_j</tex> &cup;= <tex>\lbrace [A \rightarrow \cdot \beta, j] \rbrace</tex> # Правило (3) while на данной итерации какое-то множество изменилось ==Корректность алгоритма=={{Теорема|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'while, \gamma' \Rightarrow^* a_1...a_{i} </tex>. Значит, <tex> \alpha = \alpha'a_{j} \Rightarrow^* a_{i+1}...a_{j} </tex> и при <tex>\gamma = \gamma', \delta = \delta' a</tex> <tex>[leftA \rightarrow \alpha \cdot \beta, i] \in I_j</tex>. 2. Включаем по правилу < key 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'and\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' key < a/tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} </tex>. Значит, при <tex>\gamma = \gamma', \delta = \delta'</tex> <tex>[rightA \rightarrow \alpha \cdot \beta, i]\in I_j</tex>.  mid 3. Включаем по правилу <tex>(3)</tex>.<br/>Тогда <tex>\alpha = \varepsilon, i = left 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}, (key - aA \rightarrow \alpha \beta) \in P, \alpha \Rightarrow^* a_{i+1}...a_{j}</tex>, то алгоритм добавит <tex> [leftA \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}(right - left\tau) </tex> — длина кратчайшего вывода <tex>\gamma \Rightarrow^* a_1...a_{i}</ tex>, <tex>\tau_{\alpha}(a\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>[rightS' \rightarrow \cdot S, 0] - a[left]) <font color=green/tex> будет добавлена в <tex>I_0</tex>.<br/>Индукционный переход:пусть ранг <tex> \tau</tex> равен <tex>r > 0</ индекс элементаtex>, пусть для всех наборов с которым будем проводить сравнение меньшими рангами утверждение верно. Докажем для набора <tex>\tau</fonttex>. Для этого рассмотрим три случая:  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'if), \tau_{\gamma}(\tau) = \tau_{\gamma}(\tau'), \tau_{\alpha}(\tau) = \tau_{\alpha}(\tau')</tex>. Значит, по предположению <tex>[A \rightarrow \alpha' a\cdot a_{j} \beta, i] \in I_{j-1}</tex>, и <tex>[midA \rightarrow \alpha \cdot \beta, i] < key/tex> будет добавлена в <tex>I_{j}</tex> по правилу <tex>(1)</tex>. 2. <tex>\alpha</tex> оканчивается нетерминалом.<br/> left <tex>\alpha = mid \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'else if}(\tau'') \leqslant \tau_{S' a[mid] }(\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> key right \tau_{\alpha}(\tau) = mid - 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'else') = \tau_{\gamma}(\tau) + n_1</tex>. Тогда ранг <tex>\tau'' </tex> равен <tex>\tau_{S'}(\tau''return) + 2(\tau_{\gamma}(\tau'') + \tau_{\alpha}(\tau' mid ') + j) \leqslant \tau_{S'}(\tau) + 1 + 2(\tau_{\gamma}(\tau) + n_1 + n_2 - 1 + j)</tex> <tex>= \tau_{S'if}(\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' a\cdot B \beta, i] \in I_{k}</tex> и <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex>, по правилу <tex>(2)</tex> <tex>[leftA \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>. 3. <tex>\alpha =\varepsilon</tex>.<br/>В этом случае <tex>i = keyj, \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'return'A \delta'\delta' left '</tex>, где <tex>(B \rightarrow \gamma''else ifA \delta'') \in P</tex>. Рассмотрим набор <tex>\tau' a[right] == key \langle \gamma'', A \delta'', \gamma', \delta', B, k, j \rangle</tex>, где <tex>k</tex> такое, что <tex>\gamma'\Rightarrow^* a_1...a_{k}, \gamma''return\Rightarrow^* a_{k+1}...a_{j}</tex>.Пусть длина кратчайшего вывода <tex>\gamma'\Rightarrow^*a_{1}...a_{k}</tex> равна <tex>n_1</tex>, а длина кратчайшего вывода <tex> \gamma'' right\Rightarrow^* a_{k+1}...a_{j}</tex> равна <tex>n_2</tex>.<br/> Найдём ранг <tex>\tau'</tex>. <tex>\tau_{S'}(\tau'else) = \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''return\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 ]<font color/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=green"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]</fonttex>|| 3|-|<tex>[F \rightarrow \cdot a, 3]</codetex>|| 3|}|} ||

{| class==Пример работы вместе с сравнением с бинарным поиском=="wikitable"|-!<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>[Файл:ip_vs_bin_from_gshark.pngS \rightarrow T \cdot , 3]</tex> |900px|center2|Сравнение бинарного и интерполирующего поисков-|<tex>[S \rightarrow T + S \cdot , 1]</tex> || 2|-|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2|}|}

При {| 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> O(n) [S' \rightarrow S \cdot , 0]</tex>.|| 2|}|}

==Примечания==Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5<references/tex>, то <tex>w \in L(G) </tex>.<br>

*[http://rulpcs.wikipediamath.orgmsu.su/~sk/lehre/wikifivt2013/%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 Википедия Earley.pdf Алексей Сорокин {{---}}Интерполирующий поискАлгоритм Эрли]* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.