Недавно на одном из собеседований мне задали задачу по парсингу строки, используя только MySQL. После этого я задумался: вообще, насколько сложные задачи такого рода можно решить с помощью одной лишь СУБД? Ответ был найден быстро: с помощью MySQL можно решить вообще любую задачу распознавания строк.
А чтобы сделать это более удобным и универсальным способом, достаточно написать примитивный эмулятор конечного автомата, а еще лучше — машины Тьюринга, разумеется, используя только конструкции, любезно предоставленные MySQL. Итак, приступим к эксперименту.
Мы проектируем
Любая программа начинается с проекта.Так будет и на этот раз.
Прежде всего, что такое машина Тьюринга, что она делает, что она может? Знает, честно говоря, немного.
Имея в своем распоряжении бесконечную ленту и устройство управления (каретку), машина может:
- Двигайтесь влево и вправо по ленте
- Чтение с символа ленты
- Напишите символ на ленте
- Езжайте в разные штаты
Конечно, давать инструкции машине Тьюринга таким способом не очень удобно, поэтому формализуем наши инструкции следующим образом: '> ' — двигаться вправо '<' — move left '#' - останавливаться Вот примерный набор инструкций для машины: 0,1,> ,1 1,0,> ,2 2,0,> ,3 3, ,> , 4 4, ,1, 4 4,1,#,4 Эта довольно бесполезная программа проверяет, является ли записанное на ленте двоичное число числом 4, и если да, то через пробел записывает число 1. Эта машина делает некоторые предположения.
Во-первых, исходное положение устройства управления вполне может находиться слева, а не справа от исходных данных.
Во-вторых, лента «бесконечная» только в одном направлении.
В-третьих, как вы могли заметить, описанная выше машина Тьюринга после считывания символа может сделать только одно: либо записать символ, либо двигаться по ленте.
Мы разработаем эмулятор с учетом этих предположений.
Весь проект будет состоять из следующих частей:
- Таблица, предназначенная для имитации фида, состоящая из одного поля
- Таблица отображения ошибок, также с одним полем
- Таблица самих инструкций, состоящая из 4 полей (начальное состояние, символ чтения, действие, результирующее состояние).
- Сохраненная рекурсивная процедура, содержащая логику эмулятора.
Поэтому информация о том, почему программа споткнулась, не будет лишней.
Итак, как будет работать работа с эмулятором? Вы вставляете текст программы в предназначенную для нее таблицу по правилу одна инструкция — одна строка, вставляете исходные данные в ленточную таблицу и запускаете процедуру.
В зависимости от того, что вы напишете в своей программе, что окажется на ленте.
А если произойдет что-то совсем неожиданное, вы сможете посмотреть таблицу ошибок.
Что ж, пришло время приступить к кодированию.
Мы развиваемся
Сначала давайте создадим базу данных и таблицы.
В таблице вывода ошибок output_string нужно создать одну пустую строку и больше ее не трогать.CREATE DATABASE turing; CREATE TABLE program ( in_state INT NOT NULL , sread VARCHAR( 1 ) NOT NULL , actions VARCHAR( 1 ) NOT NULL , out_state INT NOT NULL ) ENGINE = MYISAM CHARACTER SET utf8 COLLATE utf8_unicode_ci; CREATE TABLE output_string ( output TEXT NOT NULL ) ENGINE = MYISAM ; CREATE TABLE ribbon ( sinput TEXT NOT NULL ) ENGINE = MYISAM ;
Теперь приступим к самому главному — созданию процедуры.
Но перед этим нам нужно включить рекурсию в конфиге MySQL, так как она нам очень понадобится.
Для этого пропишите max_sp_recursion_length = 255 в my.cnf. Код процедуры я сначала приведу полностью, а ниже приведу расшифровку, чтобы не портить вид комментариями.
delimiter //
CREATE procedure turing(IN sstate INT(11), IN pos INT(11))
BEGIN
turing:BEGIN
SET @p=pos;
SET @sstate=sstate;
SELECT @inread:=SUBSTRING(sinput, @p, 1) FROM ribbon;
SELECT @instate:=in_state, @sread:=sread, @actions:=actions, @out_state:=out_state, @numrows:=count(in_state)
FROM program
WHERE in_state = @sstate AND sread = @inread;
IF @numrows > 1 THEN
UPDATE output_string SET output= 'Confused :(';
LEAVE turing;
ELSEIF @numrows = 0 THEN
UPDATE output_string SET output='Do not understand what to do next :(';
LEAVE turing;
ELSE
SELECT @lin:= LENGTH(sinput) FROM ribbon;
SELECT @input:=sinput FROM ribbon;
IF @actions = '>' THEN
IF @lin = pos THEN
SELECT @new_input:=CONCAT(sinput, ' ') FROM ribbon;
UPDATE ribbon SET sinput=@new_input;
END IF;
SET @pos=pos+1;
ELSEIF @actions = '<' THEN
IF pos>1 THEN
SET @pos=pos-1;
ELSE
UPDATE output_string SET output='Carriage has left the ribbon';
LEAVE turing;
END IF;
ELSEIF @actions = '#' THEN
LEAVE turing;
ELSE
SELECT @head:=SUBSTRING(sinput, 1, pos-1) FROM ribbon;
SELECT @tail:=SUBSTRING(sinput, pos+1, @lin) FROM ribbon;
SELECT @inp:=CONCAT(@head, @actions, @tail);
UPDATE ribbon SET sinput=@inp;
SET @pos=pos;
END IF;
CALL turing(@out_state, @pos);
END IF;
END;
END //
Начало понятно, создаём процедуру и передаем ей два параметра — состояние состояния машины и положение устройства управления поз.
Затем мы помечаем наш блок BEGIN.END меткой Тьюринга, чтобы мы могли использовать его для выхода.
После этого читаем в переменную @inread символ, на котором в данный момент находится каретка.
Из таблицы программы выбираем строки, в которых состояние равно переданному в параметре, а поле sread — считываемый символ равен фактическому символу, на котором находится наше управляющее устройство.
Эти два параметра однозначно определяют инструкцию для машины Тьюринга, поэтому строка, удовлетворяющая условию, должна быть единственной.
Обрабатываем ситуацию, когда соответствующих инструкций нет — эмулятор завершает свою работу с ошибкой — он просто не знает, что делать дальше.
Мы обрабатываем ситуацию, когда существует более одной инструкции, удовлетворяющей условию.
В этом случае машина тоже не знает, что делать дальше, и эмулятор завершает работу с ошибкой, говоря, что она запуталась.
Если все в порядке, то есть количество строк равно 1, то считаем длину входной строки и начинаем обработку действий.
Здесь также есть несколько нюансов.
Во-первых, надо помнить, что лента должна быть бесконечной в одном направлении, а длина входных данных ни в коем случае не бесконечна.
Поэтому, если управляющее устройство находится в конце входной строки, а программа предписывает нам двигаться вправо, мы добавляем несколько пробелов и выполняем инструкцию, увеличивая позицию на 1. В случае движения влево мы обрабатываем ситуацию, когда каретка выходит за пределы ленты.
Вы ничего не можете с этим поделать.
Извините, лента «бесконечная» только в одну сторону.
Когда программа подает сигнал «стоп», обозначенный символом #, мы выходим из процедуры.
Если символ не соответствует ни одному из вышеперечисленных, то есть это не > , < or #, this means that it needs to be written to the tape, overwriting the current one. We perform this trick using the simple built-in function CONCAT().
Дальше продолжаем в том же духе, передавая уже измененные значения параметров.
@out_state в данном случае — это состояние вывода, которое является состоянием ввода для следующей инструкции.
Тестирование
Итак, мы подошли к заключительному этапу – тестированию.Я хотел сделать с этим эмулятором что-то грандиозное, чтобы доказать, что MySQL действительно всемогущ.
Поэтому мы решим довольно нетривиальную, хоть и распространенную задачу — проверку правильности римских цифр.
Программа будет работать достаточно просто — на вход берется строка символов и, если эта строка является допустимой римской цифрой, через пробел на ленте выводится «ОК».
Несмотря на кажущуюся сложность, задача проста.
Необходимо для каждого символа, используемого для написания римской цифры, определить, какой из них не может следовать за ней.
Например, за буквой L не может следовать буква C, то есть обозначение LC не может считаться римской цифрой.
Число 50 записывается просто как L. Или, например, максимальное количество последовательных I равно 3, поэтому IIII не является римской цифрой и т. д. Я не буду подробно останавливаться на этих правилах, потому что это тема отдельная статья.
Наш входной алфавит состоит из следующих символов: M, D, C, L, X, V и I. Я решил назвать начальное состояние номером 47, потому что мне нравится число 47, а также для того, чтобы продемонстрировать, что можно использовать любые состояния, и не обязательно начинать с 0 (по крайней мере в этом эмуляторе нулевое состояние вообще не обязательно).
Вставим нашу программу в базу данных: вставить в программу значения (47,' ','#',47), (48,' ','> ',64),(49,' ','> ',64), (50,' ','> ',64),(51,' ','> ',64),(52,' ','> ',64), (53,' ','> ',64), (54,' ','> ',64),(55,' ','> ',64), (56,' ','> ',64), (57,' ','> ',64),(58,' ','> ',64), (59,' ','> ',64), (60,' ','> ',64), (61,' ','> ',64), (62,' ','> ',64), (63,' ','> ',64),(65,' ','> ',64), (66,' ','> ',64), (64,' ','O',64),(64,'O','> ',70), (70,' ','к',70),(70,'к','> ',71), (47,'I','> ',48),(48,'V','> ',51),(48,'X','> ',51), (51,'V','#',51),(51,'C','#',51),(51,'L','#',51), (51,'D','#',51), (51,'M','#',51), (51,'X','#',51), (48,'C','#',48),(48,'L','#',48),(48,'D','#',48), (48,'M','#',48),(48,'I','> ',49), (49,'I','> ',50), (50,'I','#',50),(50,'V','#',50), (50,'C','#',50), (50,'L','#',50),(50,'D','#',50), (50,'M','#',50), (50,'X','#',50), (47,'V','> ',52),(52,'I','> ',48),(52,'V','#',48), (52,'X','#',48),(52,'C','#',48),(52,'M','#',48), (52,'D','#',48),(52,'L','#',48),(47,'X','> ',53), (53,'V','> ',52),(53,'I','> ',48),(53,'D','#',53), (53,'M','#',53),(53,'L','> ',53),(53,'C','> ',53), (53,'X','> ',55),(55,'D','#',55),(55,'M','#',55), (55,'C','#',55),(55,'L','#',55),(55,'V','> ',52), (55,'I','> ',48),(55,'X','> ',56),(56,'X','#',56), (56,'D','#',56),(61,'C','> ',62),(56,'M','#',56), (56,'C','#',56),(56,'L','#',56),(56,'V','> ',52), (56,'Я','> ',48), (47,'L','> ',54),(54,'X','> ',53),(54,'V','> ',52), (54,'I','> ',48),(54,'D','#',54),(54,'C','#',54), (54,'М','#',54),(54,'L','#',54), (47,'C','> ',59),(59,'X','> ',53),(59,'I','> ',48), (59,'L','> ',54),(59,'V','> ',52),(59,'M','> ',65), (65,'M','#',65),(65,'V','> ',59),(65,'X','> ',59), (65,'I','> ',59),(65,'L','> ',59),(65,'C','#',65), (59,'Д','> ',66),(66,'Д','#',66),(66,'М','#',65), (66,'V','> ',59),(66,'X','> ',59),(66,'I','> ',59), (66,'L','> ',59),(66,'C','#',65),(59,'C','> ',61), (61,'C','> ',62),(61,'I','> ',47),(62,'X','> ',53), (62,'I','> ',48),(62,'L','> ',54),(62,'V','> ',52), (62,'C','#',62),(61,'M','#',59),(61,'D','#',59), (62,'М','#',62),(62,'Д','#',62), (47,'D','> ',60),(60,'M','#',60),(60,'C','> ',59), (60,'D','#',60),(60,'X','> ',53),(60,'I','> ',48), (60,'L','> ',54),(60,'V','> ',52), (47,'M','> ',63),(63,'M','> ',63),(63,'C','> ',59), (63,'D','> ',60),(63,'X','> ',53),(63,'I','> ',48), (63,'V','> ',52),(63,'L','> ',54) Первый блок программы отвечает за финальный этап — сюда мы попадаем, когда номер успешно прошел валидацию и каретка доехала до места.
С этого момента начинаем набирать «Ок».
Последующие блоки представляют собой инструкции из разных комбинаций состояний машины и букв входного алфавита.
Большинство фрагментов кода используются многократно.
Например, когда мы написали все правила для символа I и пишем для символа V, то мы можем написать (47,'V','> ',52), (52,'I','> ',48), где состояние 48 уже было описано нами ранее.
И каков результат? Давайте вставим в качестве входной строки, скажем, CCCXXIV (правильный номер).
Теперь набираем в консоли: mysql> вызов Тьюринга(47,1) // 47 – исходное состояние, 1 – положение устройства управления.
Мы получаем:
+--------------------------------------+
| CCCXXIV Хорошо |
+--------------------------------------+
Теперь давайте попробуем ввести неправильный номер, скажем MXXLC.
Мы получаем:
+----------------+
| MXXLC |
+----------------+
Все!
Давайте подведем итоги
Такая реализация эмулятора не идеальна и может бесконечно дорабатываться и улучшаться.Это всего лишь прототип, демонстрирующий далеко не очевидные возможности использования MySQL. И, конечно же, данная реализация создана исключительно ради спортивного интереса и развлечения.
Надеюсь, вам также понравилось читать эту статью.
Больше сумасшедших идей и успешного программирования вам! Теги: #MySQL #Тьюринг #Ненормальное программирование
-
Adobe Air Alpha 1 Для Linux
19 Oct, 24 -
Byod: Статистика И Плюсы
19 Oct, 24 -
Oem-Неттоп Получил Имя И Цену
19 Oct, 24 -
Планирование Рабочего Времени
19 Oct, 24 -
Небольшое Улучшение Gmail
19 Oct, 24
