Упаковать Слова | ;: 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 обозначает следующее: ew(i,j,r,c) (“emit word”) выдает ошибку индексации (index error) если j равно _1 , иначе собирает в результирующий массив информацию о текущем слове, в соответствии с кодом функции f :
После обработки последнего атома my , i
принимает значение #y и осуществляется (если задано) действие,
определяемое параметром d : Если d=.3{ijrd не отрицательно,
выполняется дополнителная итерация с c=.d ; при отрицательном
d и j не равном _1 , выполняется Код функции 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” содержат другие примеры использования конечных автоматов.