Граф состояний автомата транслитерации
В статье показана возможность и необходимость использования автоматов [1] в задачах, существующих в прикладном программировании. В том числе, в области интернет-программирования. При этом неважно, на стороне клиента или сервера.
В повседневном программировании часто требуется решить некоторую задачу максимально быстро, при этом эффективность отступает на второй план. Также желательно подумать о будущем программы. К сожалению, процесс это довольно долгий и нетривиальный, поэтому в большинстве случаев им пренебрегают ("сроки поджимают, думать нет времени").
В работе будет показано, как с помощью использования несложных автоматов ускорить и упростить процесс разработки алгоритма транслитерации. И, что немаловажно, будет показано, как, затратив минимум усилий, получить программу, которая сравнительно легко может быть изменена.
Дана строка (сообщение), состоящая из символов первой половины таблицы ASCII. В этой части таблицы отсутствуют символы кириллицы (русского алфавита). Таким образом, в строке используются символы латиницы, знаки препинания, цифры и некоторые неалфавитные символы.
Также дана таблица правил, в которой записаны пары:
"символы латиницы" - "символ кириллицы"
Требуется построить программу, которая преобразовывает строку в соответствии с данными правилами. Этот процесс и называется "транслитерацией", или побуквенным переводом.
При этом следует учесть, что в строке могут находиться ссылки (ссылка - любая подстрока без пробелов, начинающаяся с символов "http:"), почтовые адреса (почтовый адрес - подстрока без пробелов, в которой присутствует символ "@"), смайлики (цепочки символов, которые представляют собой одинарное слово, заключенное в двоеточия). Последние применяются для обозначения мест, где позже могут быть вставлены небольшие картинки. Эти три группы символов транслитерировать не требуется. Также должна быть обеспечена возможность указывать адресата, которому предназначено данное сообщение. Будем обозначать адресата цепочкой:
"to [<имя адресата>]"
И, наконец, любая цепочка символов, заключенная в квадратные скобки "[:]", не должна переводиться. Это оказывается необходимым при цитировании.
Программа транслитерации применяется в тех случаях, когда пользователи, по каким-либо причинам не могут писать сообщения с помощью символов кириллицы. Продемонстрируем различные подходы к разработке такой программы. Все программы написаны на языке JavaScript.
Таблица транслитерации приведена ниже:
| рус - англ | рус - англ | рус - англ |
| а - a | к - k | х - kh |
| б - b | л - l | ц - c |
| в - v | м - m | ч - ch |
| г - g | н - n | ш - sh |
| д - d | о - o | щ - shh |
| е - e | п - p | ъ - " |
| е - jo | р - r | ы - y |
| ж - zh | с - s | ь - ' |
| з - z | т - t | э - eh |
| и - i | у - u | ю - ju |
| й - jj | ф - f | я - ja |
Она соответствует ГОСТ на транслитерацию [2]. Опыт показывает, что выбранная таблица весьма удобна, однако она не лишена некоторых недостатков. Например, с ее помощью не удается корректно транслитерировать текст с кавычками.
Приведем примеры строк до и после транслитерации:
было: Privet, kak dela? стало: Привет, как дела? было: SHHaz smajjlik poshlju: :smile: стало: Щаз смайлик пошлю: :smile:
Рассмотрим простейший способ решения задачи. Он состоит в следующем. Проходя по строке столько раз, сколько в таблице имеется правил, будем применять их по очереди (листинг 1).
Листинг 1. Программа, демонстрирующая первый подход
// Объявляем массивы, в которых задаются
// правила перевода (mapEn[i] -> mapRu[i])
// Поскольку программа пишется на языке JavaScript, то размер кода
// более важен, чем скорость
var mapEn = "eh|ju|ja|shh|" +
"ch|sh|kh|jo|" +
"zh|a|b|v|g|" +
"d|e|z|i|j|" +
"k|l|m||" +
"n|o|p|r|s|t|" +
"u|f|c|"|y|'".split('|');
var mapRu = 'э|ю|я|щ|" +
"ч|ш|х|е||" +
"ж|а|б|в|г|д|" +
"е|з|и|й|к|л|м||" +
"н|о|п|р|с|т|" +
"у|ф|ц|ъ|ы|ь'.split('|');
// Функция транслитерации.
function translateStr(str)
{
var s = sS;
for(i = 0; i < mapEn.length; ++i)
while (s.indexOf(mapEn[i]) >= 0)
s = s.replace(mapEn[i], mapRu[i]);
return s
}
Если выбрать последовательность применения правил, при которой сначала используются более "длинные" (по числу символов в латинской части правила), а затем более "короткие", то строка корректно преобразуется.
При применении этого подхода возникает проблема со всеми исключениями, например со ссылками. Поэтому перейдем к рассмотрению второго подхода.
Этот подход позволяет частично устранить указанный выше недостаток. Для этого будем выполнять преобразование не по буквам, а по словам. Если допустить, что разделителем слов являются исключительно пробелы (что довольно часто является верным), то, разделив строку на подстроки по пробелам, можно выделить сразу и ссылки, и почтовые адреса, и смайлики (листинг 2).
Листинг 2. Функция, транслитерирующая по словам
// Функция преобразования подстроки побуквенно.
function convert(str)
{
for(var i=0;i<map_en.length;++i)
while (str.indexOf(map_en[i])>=0)
str = str.replace(map_en[i],map_ru[i]);
return str;
}
// Функция транслитерации с использованием второго подхода.
function translate(str)
{
strarr = str.split(, ,);
for(var k=0; k < strarr.length; k++)
{
if(strarr[k].indexOf("http://") < 0 &&
strarr[k].indexOf('@') < 0 &&
strarr[k].indexOf("www.") < 0 &&
!(strarr[k].charAt(0)==":" &&
strarr[k].charAt(strarr[k].length-1)==":"))
{
if ((k<strarr.length-1) &&
(strarr[k]=="to" || strarr[k]=="private") &&
(strarr[k+1].charAt(0)=="["))
{
while ((k<strarr.length-1) &&
(strarr[k].charAt(strarr[k].length-1)!="]"))
k++;
}
else
strarr[k] = convert(strarr[k])
}
}
return strarr.join(' ');
}
Данный подход не позволяет корректно обрабатывать некоторые подстроки, например, содержащие фрагмент вида: "privet:hi:". В этом случае смайлик ":hi:" не отделен от транслитерируемого слова пробелом. Поэтому, алгоритм не сможет распознать этот смайлик и транслитерирует его, что не является корректным.
Данный алгоритм работает в несколько проходов:
Это, естественно, сказывается на быстродействии, что не особо важно в случае, если строка одна и имеет небольшую длину, однако неприемлемо при транслитерации большого числа строк в реальном времени.
В этом случае приведенный подход не применим. Он также не подходит, если требуется обрабатывать указанные связки различных типов подстрок, не разделенные пробелами.
Последний подход, который будет описан, лишен всех указанных недостатков. При этом, однако, программа несколько увеличивается. Поставленная задача решается с помощью алгоритма, который представляется с помощью графа переходов конечного автомата.
Приведем этот граф переходов.
Граф состояний автомата транслитерации
В этом графе прямоугольники - это состояния, в которых может находиться программа. Дуги и петли графа показывают, из каких состояний в какие могут быть выполнены переходы. Дуги и петли помечаются условиями, при которых выполняются переходы. Условия записываются с помощью обозначений, которые поясняются ниже.
Входные переменные
Выходные воздействия
Исходно автомат находится в нулевом состоянии. При этом он начинает считывать символ за символом, добавляя их во временный буфер. На каждом шаге проверяется, какой символ считан в буфер и какая строка находится в буфере. Если после этой проверки выясняется, что выполняются условия перехода в какое-либо состояние, то происходит переход в это состояние.
Листинг 3. Программа транслитерации, построенная на основе автомата
// Строки таблицы транслитерации не приводятся, так как их можно
// посмотреть в первом листинге.
// Глобальные переменные. Они объявляются глобальными, так как
// язык JavaScript не позволяет элегантно реализовать объектное решение.
var sourceString = '';
var resultString = '';
var state = 0;
var currentPosition = 0;
var currentString = '';
var currentChar = '';
var curStringLength = 0;
// Транслитерирование подстроки.
function transliterateByLetter(sS)
{
var s = sS;
for(i = 0; i < mapEn.length; ++i)
while(s.indexOf(mapEn[i]) >= 0)
s = s.replace(mapEn[i],mapRu[i]);
return s;
}
// Равна ли подстрока compareTo.
function isSubStrEqual(str, length, index, compareTo)
{
return (str.substr(length - index) == compareTo)
}
// Транслитерировать подстроку.
function transliterateSubStr(str, length, index)
{
return transliterateByLetter(str.substr(0, length - index), length)
}
// ------------------------------------------------------
// Входные переменные.
function x1(compareStr)
{
return isSubStrEqual(currentString, curStringLength,
compareStr.length, compareStr)
&&
sourceString.charAt(currentPosition + 1) == '[';
}
function x2(compareStr)
{
return isSubStrEqual(currentString, curStringLength,
compareStr.length, compareStr);
}
function x3()
{
return currentPosition >= sourceString.length;
}
// ------------------------------------------------------
// Выходные воздействия.
function z0()
{
currentChar = sourceString.charAt(currentPosition++);
currentString = currentString + currentChar;
curStringLength = currentString.length;
}
function z1()
{
resultString += currentString;
currentString = '';
}
function z2()
{
resultString += transliterateByLetter(currentString);
currentString = '';
}
function z3(translCnt, addStr, newCurStr)
{
resultString += transliterateSubStr(currentString, curStringLength, translCnt) + addStr;
currentString = newCurStr;
}
function z4()
{
resultString += transliterateByLetter(
currentString.substr(0, current-String.lastIndexOf(' ')),
curStringLength);
currentString = currentString.substr(currentString.lastIndexOf(' '), curStringLength);
}
// ------------------------------------------------------
// Автоматная функция.
function translit(str)
{
sourceString = str;
while (true)
{
// Берем следующий символ.
z0();
// Автомат.
switch (state)
{
case 0:
if (x3()) { z2(); state = 4; }
else if (x1('to')) { z3(2, 'to', ''); state = 0; }
else if (x1('private')) { z3(7, 'private', ''); state = 0; }
else if (x2('[')) { z3(1, '', '['); state = 1; }
else if (x2('http:')) { z3(5, '', 'http:'); state = 2; }
else if (x2('www.')) { z3(4, '', 'www.'); state = 2; }
else if (x2('@')) { z4(); state = 2; }
else if (x2(':')) { z3(1, '', ':'); state = 3; }
break;
case 1:
if (x3()) { z1(); state = 4; }
else if (x2(']')) { z1(); state = 0; }
break;
case 2:
if (x3()) { z1(); state = 4; }
else if (x2(' ')) { z1(); state = 0; }
break;
case 3:
if (x3()) { z2(); state = 4; }
else if (x2(':')) { z1(); state = 0; }
else if (x2(' ')) { z2(); state = 0; }
break;
case 4:
break;
}
if (x3())
break;
}
return resultString;
}
В данной реализации выполняются два прохода: при первом определяются границы подстрок для транслитерации, а при втором - они транслитерируются. Таким образом, к каждому символу происходит два обращения.
Можно добиться однопроходности алгоритма (то есть транслитерировать символы по мере их поступления), и, как следствие, большей скорости. При этом отметим, что граф переходов не изменяется, а должны быть модифицированы только функции выходных воздействий.
Не правда ли, просто? Понятно и легко расширяемо. Добавить или убрать правило перехода совсем несложно.
Покажем это на примере. Пусть необходимо ввести еще два разделителя: "табуляция" и "перевод каретки". После этого программа станет корректно транслитерировать не только фразы в чате, но и, например, сообщения на форумах.
В рассмотренной выше версии программы (листинг 3) происходит сравнение последнего считанного символа с пробелом, и в результате проверки выясняется, достигнут ли пробел или нет. Для учета новых разделителей, добавим в функцию проверки все необходимые условия для их определения.
После такого изменения, практически не повлиявшего на размер программы, ее функциональность существенно возросла. Фрагмент нового варианта автоматной программы приведен на листинге 4.
Листинг 4. Транслитерация с различными разделителями
function x2(compareStr)
{
if (compareStr == ' ')
return isSubStrEqual(currentString, curStringLength, 1, ' ') |
isSubStrEqual(currentString, curStringLength, 1, '\t') |
isSubStrEqual(currentString, curStringLength, 1, '\r');
else
return isSubStrEqual(currentString, curStringLength,
compareStr.length, compareStr);
}
Примерно таким же образом можно "научить" программу обрабатывать HTML-теги, удаляя те из них, которые запрещено использовать по причинам безопасности. Программа при этом не превратится в нагромождение непонятных заплаток, каждая из которых делает кое-как что-то непонятное, а, сохранив структуру, приобретет новую функциональность. Перед внесением изменений в программу должен корректироваться граф переходов и пояснения к нему, чтобы он соответствовал новой функциональности.
Есть еще одна, принципиально иная возможность для написания этой программы. Если язык программирования поддерживает регулярные выражения, то можно закодировать в одно выражение все правила преобразования [1]. Тогда программа сама построит автомат, прогонит строку через него и получит результат.
В качестве примера работы с регулярными выражениями рассмотрим следующую задачу. Предположим, что требуется заменить все буквы "а" на буквы "б" в строке str. Этому соответствует выражение вида:
str.replace(/а/g, 'б');
Полную транслитерацию написать в таком виде непросто, но если это удастся, то получится решение, не сильно уступающее по скорости автоматному и при этом имеющее минимально возможный размер.
Знакомство с автоматным программированием, можно продолжить, посетив сайт http://is.ifmo.ru, где есть множество примеров, реализованных с помощью автоматного программирования с хорошей проектной документацией.
Автор выражает благодарность А.А. Шалыто за помощь при написании настоящей работы.
Александр Александрович Бабаев - студент магистратуры кафедры "Компьютерные технологии" Санкт-Петербургского государственного университета информационных технологий, механики и оптики. С ним можно связаться по адресу: alex@ezhiki.ru