>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь

Упаковать Слова ;:  1 _ _ Конечный Автомат

;:y есть список упакованных слов, выделенных из списка y в соответствии с правилами словообразования из Главы I и правилами относительно NB. . Функция неплохо работает и с обычным текстом.

Для подходящего левого аргумента x , результат x;:y эквивалентен ;:y . Таким образом:

mj=: 256$0                     NB. X другое
mj=: 1 (9,a.i.' ')}mj          NB. S пробел или табуляция
mj=: 2 ((a.i.'Aa')+/i.26)}mj   NB. A A-Z a-z кроме N B
mj=: 3 (a.i.'N')}mj            NB. N буква N
mj=: 4 (a.i.'B')}mj            NB. B буква B
mj=: 5 (a.i.'0123456789_')}mj  NB. 9 цифры и _
mj=: 6 (a.i.'.')}mj            NB. D .
mj=: 7 (a.i.':')}mj            NB. C :
mj=: 8 (a.i.'''')}mj           NB. Q кавычки

sj=: _2]\"1 }.".;._2 (0 : 0) 
' X    S    A    N    B    9    D    C    Q ']0
 1 1  0 0  2 1  3 1  2 1  6 1  1 1  1 1  7 1 NB. 0 прб
 1 2  0 3  2 2  3 2  2 2  6 2  1 0  1 0  7 2 NB. 1 дрг
 1 2  0 3  2 0  2 0  2 0  2 0  1 0  1 0  7 2 NB. 2 а/ц
 1 2  0 3  2 0  2 0  4 0  2 0  1 0  1 0  7 2 NB. 3 N
 1 2  0 3  2 0  2 0  2 0  2 0  5 0  1 0  7 2 NB. 4 NB
 9 0  9 0  9 0  9 0  9 0  9 0  1 0  1 0  9 0 NB. 5 NB.
 1 4  0 5  6 0  6 0  6 0  6 0  6 0  1 0  7 4 NB. 6 чсл
 7 0  7 0  7 0  7 0  7 0  7 0  7 0  7 0  8 0 NB. 7 '
 1 2  0 3  2 2  3 2  2 2  6 2  1 2  1 2  7 0 NB. 8 ''
 9 0  9 0  9 0  9 0  9 0  9 0  9 0  9 0  9 0 NB. 9 ком
)

   x=: 0;sj;mj
   y=: 'sum=. (i.3 4)+/ .*0j4+pru 4'

   x ;: y
+---+--+-+--+---+-+-+-+-+-+---+-+---+-+
|sum|=.|(|i.|3 4|)|+|/|.|*|0j4|+|pru|4|
+---+--+-+--+---+-+-+-+-+-+---+-+---+-+
   (x ;: y) -: ;: y
1

   (5;sj;mj) ;: y
 0 _1 0 2 2 1
 1  0 2 2 2 0
 2  0 2 2 2 0
 3  0 2 0 1 2
 4  3 1 6 1 0
 5  3 1 1 0 3
 6 _1 0 0 1 1
 7  6 1 2 2 2
 8  7 2 6 1 0
 9  7 1 5 6 2
10  9 6 1 0 5
11 _1 0 5 6 1
12 11 6 0 1 4
13 12 1 0 1 2
14 13 1 0 1 2
15 14 1 1 0 3
16 _1 0 6 1 1
17 16 1 0 1 2
18 17 1 5 6 2
19 18 6 2 6 0
20 18 6 5 6 0
21 18 6 0 1 4
22 21 1 2 2 2
23 22 2 2 2 0
24 22 2 2 2 0
25 22 2 1 0 3
26 _1 0 5 6 1
   

 
 

x;:y реализует конечный автомат (последовательную машину). Где x — спецификация автомата, включающая таблицу переходов между состояниями, а y его входной поток. Конечный автомат решает проблему распознавания “слов” во входном потоке. Он начинает с некоторого начального состояния и обрабатывает входной поток последовательно по одному элементу; Новое состояние и выход автомата определяются из таблицы переходов, исходя из текущего состояния и элемента на входе. Потом автомат переходит к обработке следующего входного элемента. Детально:

y может быть любым массивом, а x=.f;s;m;ijrd должен быть списком упаковок, где ijrd (или m вместе с ijrd ) можно опустить.

f — код функции, целое число от 0 до 5 (обьясняется ниже).

m — список, задающий преобразование элементов входного потока: каждый упакованный элемент m содержит элементы y , отображаемые на индекс этого элемента; преобразованный таким образом входной поток есть my=. (y i.~;m) { (#m),~(#&>m)#i.#m . Если y строка (текстовый список), m может быть списком неотрицательных целых, соответствующих каждому атому алфавита a. , тогда входной поток будет отображен как my=.(a.i.y){m . Наконец, если m пуст или опущен (а y — числовой список), то отображенный входной поток my есть просто y .

Массив s трехмерный, он состоит из двух-колоночного массива неотрицательных целых (таблицы) переходов и таблицы выходов. Его размерность p,q,2 , где p — количество состояний, а q — количество отображенных элементов входного потока. Тоесть, p>0{"1 s , и q>#m если m есть список упаковок, или q>m если m список целых.

ijrd представляет собой список целых (содержащий до 4-х элементов). i — начальное значение счетчика итераций (начальный индекс во входной массив y), r — начальное состояние, j — индекс начала текущего слова, и d параметр, определяющий действие при окончании входного потока (см. ниже). Требуется, чтобы (0<:i)*.i<#y и (_1=j)+.(0<:j)*.j<i . Если ijrd опущен, вместо него берется 0 _1 0 _1 .

x;:y проходит по всем атомам отображенного входного потока my. Пусть r — текущее состояние, а j — индекс начала слова; по умолчанию (если ijr опущен) r равно 0, а j равно _1 . На итерации i , текущий отображенный входной элемент есть c=.i{my и соответствующий элемент таблицы переходов e=.s{~<r,c (список из двух целых). Новое состояние при этом есть 0{e , а код вывода 1{e обозначает следующее:
  0    нет вывода
  1    j=.i
  2    j=.i  [ ew(i,j,r,c)
  3    j=._1 [ ew(i,j,r,c)
  4    j=.i  [ ev(i,j,r,c)
  5    j=._1 [ ev(i,j,r,c)
  6    остановиться

ew(i,j,r,c) (“emit word”) выдает ошибку индексации (index error) если j равно _1 , иначе собирает в результирующий массив информацию о текущем слове, в соответствии с кодом функции f :
 0   <y{~j+i.i-j   упакованное слово
 1   y{~j+i.i-j   слово
 2   j,i-j   индекс и длина слова
 3   c+q*r  индекс в таблице переходов
 4   j,(i-j),c+q*r  и 2 и 3 выше
 5   i,j,r,c,s{~<r,c  трассировка
ev(i,j,r,c) (“emit vector”) работает подобным образом, только текущее слово и все промежуточные присоединяются к предыдущему слову если предыдущий вывод был при помощи ev и состояние на тот момент было r .

После обработки последнего атома my , i принимает значение #y и осуществляется (если задано) действие, определяемое параметром d : Если d=.3{ijrd не отрицательно, выполняется дополнителная итерация с c=.d ; при отрицательном d и j не равном _1 , выполняется
ev(j,i,r,c) .

Код функции f=5 обозначает трассировку; в этом случае, результат x;:y — матрица целых из 6-ти столбцов, где каждой итерации соответствует строка i,j,r,c,s{~<r,c . Эта матрица обычно имеет #y строк, но их может быть и меньше, если выполнение машины закончилось по коду 6 или были встречены коды выхода от 2 до 5, когда j было _1 .

Таким образом (0;s;m);:y есть список упакованных элементов y , (2;s;m);:y есть матрица (из двух колонок) индексов и длин, и:

((0;s;m);:y) -: (2;s;m) (,"0@;: <;.0 ]) y



   s=: '*: @ -: @ i. 2 3'
   do=: ".
   do s
   0 0.25    1
2.25    4 6.25

   ;: s
+--+-+--+-+--+---+
|*:|@|-:|@|i.|2 3|
+--+-+--+-+--+---+

   ; ;: s
*:@-:@i.2 3

   p=: 'When eras die, their legacies/'
   q=: 'are left to strange police'
   r=: 'Professors in New England guard'
   s=: 'the glory that was Greece'

   ;: p
+----+----+---+-+-----+--------+-+
|When|eras|die|,|their|legacies|/|
+----+----+---+-+-----+--------+-+

   > ;: p,q
When    
eras    
die     
,       
their   
legacies
/       
are     
left    
to      
strange 
police 

   |.&.;: p
/ legacies their , die eras When

Следующие примеры диады ;: выделяют цитаты из текста. Кавычки отображаются в 1, а все остальные символы в 0; столбец 0 таблицы переходов соответствует “просто тексту” (не цитате), а столбец 1 цитате.

   sq=: 4 2 2$ 1 1 2 1  1 0 2 2  2 0 3 0  1 2 2 0
   <"1 sq
+---+---+
|1 1|2 1|
+---+---+
|1 0|2 2|
+---+---+
|2 0|3 0|
+---+---+
|1 2|2 0|
+---+---+
   ] y=: '''The Power of the Powerless'' by Havel and ''1984'' by Orwell'
'The Power of the Powerless' by Havel and '1984' by Orwell
   (0;sq;''''=a.) ;: y
+----------------------------+--------------+------+----------+
|'The Power of the Powerless'| by Havel and |'1984'| by Orwell|
+----------------------------+--------------+------+----------+
   (2;sq;''''=a.) ;: y
 0 28
28 14
42  6
48 10
   (3;sq;''''=a.) ;: y
6 3 6 2
   (4;sq;''''=a.) ;: y
 0 28 6
28 14 3
42  6 6
48 10 2

   sqx=: 4 2 2 $ 1 1 2 0  1 0 2 3  2 0 3 0  1 1 2 0
   <"1 sqx
+---+---+
|1 1|2 0|
+---+---+
|1 0|2 3|
+---+---+
|2 0|3 0|
+---+---+
|1 1|2 0|
+---+---+
   (1;sqx;''''=a.) ;: y
 by Havel and  by Orwell

   f=: (1;sqx;''''=a.)&;:
   g=: (+: ~:/\)@(''''&=) # ]
   (f -: g) y
1

Подобный автомат можно использовать и для извлечения только строк в кавычках (цитат). При этом, для предотвращения ситуации, когда последняя незакрытая кавычка считается началом цитаты, необходимо (при помощи параметра ijrd) изменить интерпретацию конца строки (не считая его кавычкой, оканчивающей неоконченную цитату):

   ] y=: '''Preposterous!''  He couldn''t go on.'
'Preposterous!'  He couldn't go on.
   sq=: 4 2 2$ 1 1 2 1  1 0 2 1  2 0 3 0  1 3 2 0
   (0;sq;''''=a.) ;: y
+---------------+---------+
|'Preposterous!'|'t go on.|
+---------------+---------+
   (0;sq;(''''=a.);0 _1 0 0) ;: y
+---------------+
|'Preposterous!'|
+---------------+

Лабораторные “Sequential Machines” и “Huffman Coding” содержат другие примеры использования конечных автоматов.



>>  <<  Ркв  Ввд  JfC  LJ  Фрз  Слв  Изм  Рзг  !:  Помощь  Словарь