\input mmm.sty

%&<<&Search & replace
%&<<&#define Expr, AsciiSet
\def\tascii{ {\it ascii } }
\def\tAsciiSet{ {\it AsciiSet } }
\def\tExpr{ {\it Expr } }
%&>>&3 0 3 8
%&<<&Task
Пусть мы работаем с алфавитом $\Sigma=\{ \alpha_0, ... , \alpha_{\sigma-1}\}$ длины
$\sigma$ (в случае использования  кодировки ASCII   $\sigma=256$ )
Имея текст $T=t_1t_2.....t_\theta$, являющийся в общем
случае достаточно произвольной последовательностью символов из
алфавита $\Sigma$ и  цепочки символов $P_i=p_{i1}...p_{il}$,
являющиеся подпоследовательностями в $T$,  нам  необходимо находить все
вхождения $P_i$ в $T$.
Можно обобщить данную задачу до следующих:
1)~Описать язык, позволяющий в достаточно общем виде задавать
$P_i$ в виде шаблонов для поиска.
2)~Предложить алгоритм поиска в $T$ выражений, соответствующих шаблонам.

%&>>&0 0 0 0
%&<<&alphabet descr.
Поскольку мы располагаем только алфавитом $\Sigma$, а для описания языка
необходимо наличие множества метасимволов, то нам придется объявить
некоторые символы из алфавита ''служебными'', а для их представления пользоваться
комбинациями служебных символов. В случае, когда алфавитом является
ASCII эту задачу можно решить например следующим образом: специальные символы --
{\it SpecialChars\tt = $\{$'[', ']', '(', ')', '$\{$', '$\}$', '\char124',
   '-', '\char94', '\char92', '?', '\#'$\}$. }
Для представления специальных символов
должна существовать возможность вместо любого символа $\alpha_{NN}$ ввести
{\tt\BSL xNN}, где {\tt NN} -- код символа (порядковый номер в алфавите).

%&>>&9 0 9 8
%&<<&AsciiSet description
Введем понятие \tAsciiSet --
это часть шаблона, определяющая множество символов, допустимых в
одной позиции. Это или один символ из $\Sigma \backslash SpecialChars$,
или {\tt '?'} -- что означеет возможность появления любого символа
алфавита в даной позиции, или заключеное в квадратные скобки выражение,
определяющее множество допустимых символов
({\tt[$\alpha_i$-$\alpha_j$]} -- любой символ от $\alpha_i$ до $\alpha_j$ ,
{\tt[$\alpha_{i_1}...\alpha_{i_k}$]} -- любой символ из  множества $\alpha_{i_1}...\alpha_{i_k}$ ,
{\tt[\char94 $M$]} -- любой символ из $\Sigma \backslash M$ ).

Пример 1) {\tt'a'} -- допустим один символ.
Пример 2) {\tt'[a-p]'} -- допустим любой символ от {\tt'a'} до {\tt'p'}.
Пример 3) {\tt'[acxv]'} -- допустим любой символ из множества
        {\tt$\{$'a','c','x','v'$\}$}.
Пример 4) {\tt'[\char94ac-f]'} -- допустим любой символ, кроме символов
        {\tt$\{$'a','c','d','e','f'$\}$}.

%&>>&F 0 F 10
%&<<&Expr description
Далее следует рассмотреть последовательности \tAsciiSet и из них конструировать
шаблоны \tExpr~ с использованием следующих правил:
при наличии нескольких выражений $e_1,...,e_i$  запись
{\tt ($e_1$ \char124 ... \char124 $e_i$)} означает допустимость
любого из данных выражений.
{\tt$\{$$expr$$\}$} означает, что $expr$ может повторяться $\ge0$ раз.
Для подобных грамматических конструкций допустима вложенность.

%&>>&5 0 5 8
%&<<&Expressions specification // grammar definition
Приведенное выше неформальное описание языка шаблонов можно
формализовать, указав механизм порождения шаблонов т.е.
грамматику.

{\tt
%&<<&temporary defines
\def\tmexa{ {\it e1 } }
\def\tmexb{ {\it Chain } }

%&>>&1 0 1 11
\halign{ #\quad & \hfil #  &\quad#\hfill &;{\rm # \hfil}\cr
\tascii      & = \hfill &  {\rm любой символ из $\Sigma$} & кроме специальных  \cr
             & \char124 & \BSL xNN           &   {\tt NN}  шестнадцатеричный код символа \cr
\noalign{\vskip 5pt }
\tmexa       & = \hfill & \tascii                      & \cr
             & \char124 & \tmexa\tascii                & \cr
             & \char124 & \tmexa\tascii-\tascii        & \cr
\noalign{\vskip 5pt }
\tAsciiSet   & = \hfill &  \tascii                     & \cr
             & \char124 &  [\tmexa]                    & один из символов \tmexa \cr
             & \char124 &  [\char94\tmexa]             & любой символ из $\Sigma$ кроме \tmexa \cr
\noalign{\vskip 5pt }
\tmexb       & = \hfill &  nothing                     & определяется цепочка из \tAsciiSet \cr
             & \char124 &  \tAsciiSet                  & \cr
             & \char124 &  \tmexb \tAsciiSet           & \cr
\noalign{\vskip 5pt }
\tExpr       & = \hfill &  \tmexb                      & \cr
             & \char124 &  (\tExpr\char124\tExpr\char124...\char124\tExpr) & одно из выражений \cr
             & \char124 &  $\{$\tExpr$\}$                  & повтор выражения $\ge0$ раз \cr
}
}

Пример \tExpr: {\tt Pa$\{$t$\}$[eo]rn} . Данному шаблону удовлетворяют например
следующие последовательности символов: {\tt'Paorn' , 'Paern' , 'Pattttttttorn' ,
'Pattern' }

%&>>&8 0 3 1E
\def\tAut{ { $\frak S$ } }
\vskip 5pt
%&<<&task-->automat
Теперь перейдем к рассмотрению второго вопроса.
Пусть мы имеем шаблон \tExpr и хотим найти в тексте последовательности символов,
удовлетворяющие данному шаблону. Для решения этой задачи необходимо построить
конечный автомат, соответствующий шаблону \tExpr.
\tExpr состоит из последовательности  \tAsciiSet : $A_0,...,A_{n-1}$  разделенных
специальными символами.  Предлагается рассмотреть
конечный автомат \tAut с $n+1$ состояниями $S_{-1},S_0,...,S_{n-1}$ ,
где $S_{-1}$ - начальное состояние автомата (вход).
Переходы между состояниями в автомате определяются следующим образом:
если после $A_i$ может следовать $A_j$, то в автомате допустим переход от
$S_i$ к $S_j$

%&>>&1 0 1 0
\def\vAsciiMask{{\it AsciiMask}}
\def\vTableMask{{\it TableMask}}
%&<<&TabkeMask definition
 Каждому $i-$му состоянию ставим в соответствие битовую маску
\vTableMask[$i$] длины $n+1$ такую что если $j-$й бит равен $1$, то  переход от
$S_i$ к $S_j$ возможен, иначе невозможен. Маска, соответствующая
$S_{-1}$, дает нам точки входа автомата \tAut .
Таким образом мы получаем матрицу $(n+1) \times (n+1)$,
состоящую из $0$ и $1$ , которая однозначно задает \tAut.

%&>>&0 0 0 4
%&<<&AsciiMask definition
Поскольку для произвольного \tAsciiSet допустимыми могут являться
несколько символов, то нам придется каждому $\alpha_i$ поставить в
соответствие битовую маску \vAsciiMask[$i$] длины $n+1$ ,
определяемую следующим образом: $j-$й бит маски, соответствующей $\alpha_i$,
равен 1 тогда и только тогда, когда $j-$й \tAsciiSet допускает символ
$\alpha_i$.

%&>>&3 0 3 4D
%&<<&Алгоритм
Для нахождения фрагмента текста, соответствующего шаблону можно
воспользоваться алгоритмом, приведенным здесь в синтаксисе, близком к
синтаксису языка C++.

%&<<&#defines для алгоритмов
\def\ppwhile{{\bf while}}
\def\ppfor{{\bf for}}
\def\ppif{{\bf if}}
\def\ppelse{{\bf else}}
\def\vCur{{\it~Cur}}
\def\vTmp{{\it~Tmp}}
%&>>&0 0 0 1

\vskip 15 pt
\vbox {\tt
\+ \vCur = \vTableMask [0] ; \cr
\+ \ppwhile & ( *$T$!=0 \&\& \vCur[$n$]==0 ) \cr
\+&   $\{$ \cr
\+&   \vCur \&= \vAsciiMask[*$T$++]; \cr
\+&   \vTmp = \vTableMask [0] ; \cr
\+&   \ppfor & ($i$=0 ; $i$ < $n$ ; $i$ ++) \cr
\+&&      \ppif & (  \vCur [$i$] != 0) \cr
\+&&&         \vTmp \char124=   \vTableMask [$i$+1] ; \cr
\+&   \vCur =$Tmp$ ; \cr
\+&   $\}$ \cr
}

В алгоритме $Tmp$, $Cur$ битовые маски. Цикл работает до тех пор, пока
не кончился текст $T$ или пока не встретилось соответствие текста шаблону.
Если $i-$й бит маски $Cur$ равен 1, то это значит, что в данный момент
автомат \tAut модет находиться в состоянии $i$ и текущий символ текста
может принадлежать $i-$му \tAsciiSet. Таким образом равенство последнего
бита маски $Cur$ единице означает найденное соответствие (найден конец
соответствия). В большинстве случаев необходимо найти начало фрагмента или
узнать его длину. Для этого, например, можно ''развернуть'' шаблон и
запустить алгоритм в обратную сторону по тексту.

  Можно построить оценку сверху на количество элементарных операций,
требуемых для реализации одного шага алгоритма.
Если $\varphi(n)$ -- трудоемкость одной операции с битовой маской
{\tt =, \&=, \char124=} , то оценка сверху на трудоемкость одного шага
данного алгоритма будет равна $O(n \times \varphi(n))$.

%&>>&A 0 0 A
%&<<&Алгоритм с простой оптимизацией
Если в конечном автомате
\tAut  существует несколько состояний $S_{i_0},...,S_{i_k}$ ,
таких что единственным допустимым переходом для
$S_{i_j}$ является переход к $S_{{i_j}+1}$ т.е. к следующему
по порядку состоянию, то можно добиться некоторой оптимизации
работы алгоритма, рассматривая такие ситуации отдельно, поскольку
для них вычисление следующего значения маски $Cur$ сводится к
ее сдвигу влево на 1 бит. Построим битовую маску {\it NextReg }
по следующему правилу: $i-$й бит равен 1 тогда, когда
переход от  $S_i$ возможен только к $S_{i+1}$.

\vskip 15 pt
\vbox {\tt
\+ \vCur = \vTableMask [0] ; \cr
\+ \ppwhile & ( *$T$!=0 \&\& \vCur[$n$]==0 ) \cr
\+&   $\{$ \cr
\+&   \vCur \&= \vAsciiMask[*$T$++]; \cr
\+&   \ppif (&\vCur $\longrightarrow${\it NextReg})     \cr
\+&&       \vCur<<=1;  \cr
\+&   \ppelse $\{$ \cr
\+&&   \vTmp = \vTableMask [0] ; \cr
\+&&   \ppfor & ($i$=0 ; $i$ < $n$ ; $i$ ++) \cr
\+&&&      \ppif & (  \vCur [$i$] != 0) \cr
\+&&&&         \vTmp \char124=   \vTableMask [$i$+1] ; \cr
\+&&   \vCur =$Tmp$ ; \cr
\+&&   $\}$ \cr
\+&   $\}$ \cr
}

Здесь предикат   {\it Cur$\longrightarrow$NextReg } работает следующим образом:
Значение ''{\tt TRUE}'' возвращается при выполнении
условия: если $i-$й бит {\it Cur} равен 1, то
$i-$й бит {\it NextReg} тоже равен 1, в противном случае возвращается
значение ''{\tt FALSE}''. Нетрудно заметить, что данный предикат
легко реализуется посредством логической функции
импликации.

%&>>&13 0 A 12
%&<<&Замечание по поводу такой оптимизации
Очевидно, что в вырожденном случае т.е. тогда, когда
для любого $i$ переход от $S_i$ возможен только к $S_{i+1}$,
данный алгоритм превратится в алгоритм, описанный
в статье [1].

\vskip 15 pt
\vbox {\tt
\+ \vCur = \vTableMask [0] ; \cr
\+ \ppwhile & ( *$T$!=0 \&\& \vCur[$n$]==0 ) \cr
\+&   $\{$ \cr
\+&   \vCur \&= \vAsciiMask[*$T$++]; \cr
\+&       \vCur<<=1;  \cr
\+&   $\}$ \cr
}

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

%&>>&9 0 9 A

%&>>&5 0 5 B
%&<<&References:
\vskip 25 true pt

{\bf  References:}

\halign{ {\bf #} \hfil & # \hfil \cr
1. & Sun Wu and Udi Mander {\it ''Fast Text Searching Allowing Errors''} \cr
   &  Communications Of The ACM / october 1992. \cr
}
%&>>&0 0 0 F
\end
%&>>&1 0 1 E
