Реферат: Фильтрация строк с использованием автоматов

Фильтрация строк с использованием автоматов

Alexander Babaev

Необходимость фильтрации строк

Строки используются очень часто. А применимо к Интернет-программированию можно сказать, что строки используются постоянно. Любой ответ сервера – это строка, запрос клиента – тоже строка. Работа с XML-файлами – это опять работа со строками, пускай и очень формализованная. Поэтому необходимо уметь быстро и эффективно обрабатывать строковые данные. Основная операция, которая используется – это конкатенация (слияние). Она реализована для всего, чего угодно и обычно очень прозрачна. Вторая же операция – это изменение строк. И тут мнения относительно того, что использовать, расходятся.

Стандартные методы фильтрации строк

Для начала вспомним, как происходит работа со строками в обычной программе. Используется несколько методов. Первый можно назвать классическим. В этом случае для получения результата используются стандартные операции поиска, замены, конкатенации и удаления частей строки. Такой метод оправдан для быстрого решения самых простых задач, но как только требуется реализовать что-нибудь более-менее сложное, мгновенно начинаются проблемы. Кроме того, этот способ совершенно не масштабируется и очень сложно изменяется.

Второй метод – использование регулярных выражений (регэкспов). Подробно рассматривать их не имеет смысла, есть отличная книга Дж. Фридла [1], в которой все подробно описано, в том числе и применимо к Java. Достоинства подхода заключаются в том, что регулярные выражения стандартизованы, обладают огромнейшими возможностями и очень компактно записываются. То есть если вы научились использовать регулярные выражения в Perl или PHP, вам ничего не стоит использовать их в Java (хотя все равно приходится каждый раз выяснять нюансы реализации). Самый главный недостаток – сложность, которая произрастает из огромной мощности регулярных выражений. Простые регэкспы может понять даже начинающий программист, но более-менее сложные начинающему уже не по зубам. Регэкспы же, подобные представленному в листинге 1, не поймет никто даже при очень большом желании (в листинге представлена примерно восьмая часть регулярного выражения, предназначенного для проверки корректности e-mail адреса и его соответствия RFC). Впрочем, есть люди, которые «читают» регулярные выражения «с листа». Данный пример не совсем показателен в том смысле, что и программа, выполняющая аналогичную функцию, будет очень и очень сложна. Но есть и гораздо более простые задачи, (примеры таких задач будут рассмотрены ниже), в которых регулярные выражения использовать так же неудобно.

Листинг 1.Часть регулярного выражения, предназначенного для проверки корректности e-mail адреса, соответствия его RFC.

^[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-

\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-

\xff\n\015()]*)*\))[^\\\x80-

\xff\n\015()]*)*\)[\040\t]*)*(?:(?:[^(\040)<>@,;:".\\\[\]\000-

\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-

\xff])|"[^\\\x80-\xff\n\015"]*(?:\\[^\x80-\xff][^\\\x80-

\xff\n\015"]*)*")[\040\t]*(?:\([^\\\x80-

\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-

\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-

… … … … …

\xff])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-

\xff])*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-

\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-

\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*)*>)$

Другой немаловажный недостаток регулярных выражений состоит в том, что мало кто понимает, как они работают. «Я пишу это, он делает то…» А как – это проблема тех, кто библиотеку разрабатывает. «Чукча не читатель, чукча писатель». В результате – ляпы, непонятные «глюки», и неправильно, некорректно работающий программный код. Зачастую регэкспы ненастраиваемы. Чтобы изменить регулярное выражение, часто приходится изменять код и перекомпилировать его. Нельзя просто поменять значение одной переменной для того, чтобы немного изменить логику работы.

Фильтрация строк

После довольно длительного использования различного рода методов обработки строк появилось желание совместить настраиваемость обычного класса и мощность регулярных выражений, а в качестве базы для этого использовать автоматы [2-4]. Рассмотрим такой подход на конкретном примере. Пускай необходимо обрабатывать строки записей в интернет-форуме. При этом требуется реализовать обработку следующих правил:

Все слова длиннее некоторого количества символов N разбивать пробелами на отрезки, длина которых меньше, либо равна N.

Если длина сообщения больше M, то оставлять только первые M символов.

Заменять три точки символом многоточия.

Заменять два подряд идущих символа «минус», обрамленных пробелами, символом «тире».

Заменять символы «"»правильными кавычками в русском тексте – «елочками» и «лапками».

Заменять ссылки на интернет-ресурсы (http://..., ftp://...) HTML-ссылками.

Заменять e-mail адреса HTML-ссылками. При этом адресом для упрощения считаем последовательность непробельных символов, которая содержит «@». Это не самое лучшее определение, но работающее достаточно часто.

Заменять комбинации символов, которые обозначают стандартные эмотиконы (смайлы), соответствующими картинками.

«Обезвреживать код». То есть делать так, чтобы пользователь не мог в тексте сообщения ввести вредоносный HTML-код. Таким кодом традиционно считается любой кроме некоторых очень простых тегов <b>, <i>, <u> и аналогичных.

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

Эти правила достаточно стандартны для практически любой системы, где используется работа с текстом. Существует множество вариантов их реализации. Самый распространенный – при помощи уже упоминавшихся регулярных выражений [5]. При этом строится по одному или несколько выражений на каждое правило, после чего они в определенном порядке применяются к строке. Выполнение каждого регулярного выражения – это один проход по строке, следовательно, таких прогонов будет огромное количество. Правда, большая часть из них будет пустой, но даже они занимают какое-то время.

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

Возможен другой вариант, который и подводит непосредственно к автоматному методу работы. Те, кто более глубоко интересовался регулярными выражениями, скажут, что автоматы и регэкспы – это одно и то же. Да, любое регулярное выражение – это всего лишь короткая строковая запись автомата. Но обсуждение такого рода различий выходит далеко за рамки статьи.

Код, обрабатывающий строку, называется фильтром. Фильтр посимвольно перебирает строку, и для каждого символа проверяет, есть ли обработчик этого символа. Если есть – то передает управление ему. Иначе просто добавляет символ в выходной поток и переходит к следующему.

На рисунке 1 представлен граф состояний автомата, управляющего работой фильтра.

Рисунок 1. Граф состояний автомата, управляющего работой фильтра.

Листинг 2 показывает, как эта логика реализована в коде.

Листинг 2. Реализация автомата.

public String process(String aString) throws FilterException

{

// что такое правила – будет объяснено чуть позже, тут они

// инициализируются, потому что фильтр может быть использован

// повторно

initRules();

// проверим, что на вход получена корректная строка

if (aString == null || aString.length() == 0)

{

return "";

}

// инициализация

Source source = new Source(aString);

Result result = new Result();

// основной цикл длится, пока мы находимся «не в состоянии завершения»

while (!result.getLastRuleResult().

equals(RuleResult.FILTER_FINISHED_PROCESSING))

{

result.setLastRuleResult(RuleResult.CHAR_NOT_CHANGED);

// строка обработана полностью

if (source.isStringFinished())

{

break;

}

// перед каждой обработкой – происходит внутренняя инициализация

// так же проверяется, что нет зацикливания

try

{

source.prepare();

}

catch (FilterException e)

{

e.printStackTrace();

if (e.getCanContinue().equals(FilterException.CONTINUABLE))

{

source.addToPosition(1);

continue;

}

else if (e.getCanContinue().equals(FilterException.FATAL))

{

throw e;

}

// прогоняем правила, соответствующие текущему символу

processRules(source, result);

// если ни одно правило не было применено, то

// выполняем правило по умолчанию

if (result.getLastRuleResult().

equals(RuleResult.CHAR_NOT_CHANGED))

{

EMPTY_RULE.process(source, result, this);

}

else if (result.getLastRuleResult().equals(

RuleResult.FILTER_FINISHED_PROCESSING))

{

break;

}

// В процессе работы фильтра в строку включаются тэги (основное

// его предназначение – форматирование для вывода в HTML)

// В результате ошибок и неаккуратностей некоторые теги могут быть

// незакрыты. Следующий метод дополняет строку закрывающими

// тегамивкорректномпорядке.

result.appendEndAppendersInReverseOrder();

return result.getResult();

}

Теперь, когда понятно, как работает основной цикл программы, посмотрим на некоторые правила. Например, вот правило замены трех точек специальным символом (в листинге 3 приведен только метод обработки символа, но не весь класс).

Листинг 3. Реализация правила замены трех точек на «&hellip;»

public class HellipRule extends AbstractRule

{

private static final char CHARACTER = '.';

private static final Character INITIATOR = new Character(CHARACTER);

public Character getInitiatorCharacter()

{

return INITIATOR;

}

public void process(Source aSource, Result aResult, IFilter aFilter)

{

// проверяем, что за текущей точкой будут еще две точки

if (StringUtils.isSymbol(aSource.getSource(),

aSource.getPosition() + 1, CHARACTER) &&

StringUtils.isSymbol(aSource.getSource(),

aSource.getPosition() + 2, CHARACTER))

{

// в результат выводим нужную строку

aResult.append("…");

// выставляем состояние автомату, чтобы он

// переходилкследующемусимволу

aResult.setLastRuleResult(RuleResult.CHAR_FINISHED_PROCESSING);

// перескакиваем обработку всех трех точек

aSource.addToPosition(3);

}

В листинге 4 представлено правило общей обработки «двойных символов». Это правило, которое является базой для множества правил форматирования, позволяющих выделять текст «жирным», «наклонным» и так далее, не прибегая к тегам HTML, но обрамляя нужные куски текста в «звездочки», «наклонные черты» и другие легко запоминающиеся символы.

Листинг 4. Реализация правила обработки «двойных символов».

public void process(Source aSource, Result aResult, IFilter aFilter)

{

int nextPosition = aSource.getPosition() + 1;

// проверяется, что следующий символ – такой же, как и предыдущий

if (isSymbol(aSource.getSourceString(), nextPosition, getSymbol()))

{

// смотрим на текущее состояние правила, чтобы определить,

// создавать открывающий или закрывающий тег

if (getState().equals(DoubleCharacterState.STATE_OUT))

{

// открывающий тег

setState(DoubleCharacterState.STATE_IN);

aSource.addToPosition(2);

aResult.append(getPrefix());

// записываем в «строки окончаний» закрывающий тег, который

// является парным к текущему – чтобы автоматически

// закрыть тег в конце строки, если не окажется

// парного к тому, который сейчас вставляется (1)

aResult.addEndAppend(getPostfix());

// устанавливаем состояние «окончания обработки символа»

aResult.setLastRuleResult(RuleResult.CHAR_FINISHED_PROCESSING);

}

else if (getState().equals(DoubleCharacterState.STATE_IN))

{

if (aResult.containsEndAppend(getPostfix()))

{

setState(DoubleCharacterState.STATE_OUT);

aSource.addToPosition(2);

aResult.append(getPostfix());

// удаляем закрывающий тег из «строк окончаний».

// Если бы мы его тут не удалили, после окончания

// обработки строки, он бы вставился автоматически.

aResult.removeEndAppend(getPostfix());

// устанавливаем состояние «окончания обработки символа»

aResult.

setLastRuleResult(RuleResult.CHAR_FINISHED_PROCESSING);

}

Структура библиотеки JFilter

Классы

На рисунке 2 представлена диаграмма классов библиотеки, при этом большая часть классов правил убрана, чтобы повысить читаемость.

Рисунок 2. Диаграмма классов.

Описание

В библиотеке JFilter есть несколько интерфейсов:

IFilter (листинг 5), который описывает сам фильтр.

Листинг 5. Интерфейс фильтра

public interface IFilter extends Serializable

{

/**

* Обрабатывает строку, возвращая в качестве результата строку

* после фильтрации.

* @param aSourceString – исходная строка

* @return - обработанная строка

* @throws FilterException - если произошла фатальная ошибка

* (зацикливание)

public String process(String aSourceString) throws FilterException;

/**

* Выключает правило по его rule.getClass().getName()

* @param aRuleClass – класс правила (что-то вроде IRule.class)

public void disableRuleByClassName(Class aRuleClass);

/**

* Включает правило по его rule.getClass().getName()

* @param aRuleClass – класс правила (что-то вроде IRule.class)

public void enableRuleByClassName(Class aRuleClass);

/**

* Включает все правила.

public void enableAllRules();

/**

* Выключает все правила.

public void disableAllRules();

/**

* Добавляет правило в фильтр.

* @param aRule правило, которое нужно добавить в фильтр.

void addRule(IRule aRule);

}

IRule (листинг 6), показывающий, какие методы должны быть у правила.

Листинг 6. Интерфейс правила.

public interface IRule extends Serializable

{

/**

* Метод, который вызывается перед обработкой произвольной строки.

public void initialize();

/**

* Инициализация параметров правила. Этот метод используется в

* основном для установки параметров правила при загрузке

* конфигурации фильтра из XML.

* @param aParameters - карта параметров.

void setParameters(Map aParameters) throws FilterException;

/**

* Включаетиливыключаетправило.

public void setEnabled(boolean aEnabled);

/**

* @return true, если правило включено, false – иначе.

public boolean isEnabled();

/**

* @return - символ, который является инициатором данного правила.

public Character getInitiatorCharacter();

/**

* Обрабатывает текущую строку при помощи правила.

* @param aSource - исходная строка, текущая позиция

* @param aResult - текущий результат обработки

* @param aFilter - текущий фильтр

public void process(Source aSource, Result aResult, IFilter aFilter);

}

IRuleGroup (листинг 7) – интерфейс работы с группой однотипных правил, как, например, правила транслитерации.

Листинг 7. Интерфейс группы правил.

public interface IRuleGroup

{

/**

* Добавляет правила группы в указанный фильтр.

* @param aFilter

public void addRules(IFilter aFilter);

/**

* Включает или выключает все правила, входящие в группу.

public void setEnabled(boolean aEnabled);

/**

* Возвращает true, если все правила группы включены в указанном фильтре.

* @param aFilter

public boolean isEnabled(IFilter aFilter);

/**

* Инициализация параметров группы. Этот метод используется в

* основном для установки параметров правила при загрузке

* конфигурации фильтра из XML.

* @param aParameters карта параметров

public void setParameters(Map aParameters);

}

Для упрощения работы с системой написано несколько классов, помогающих при создании новых фильтров и правил. Такими классами являются AbstractFilter и AbstractRule. Первый описывает все методы, необходимые для работы стандартного фильтра. Поэтому для того, чтобы создать нужный фильтр, можно просто создать класс-наследник AbstractFilter и в конструкторе вызвать метод addRule(), добавив все необходимое в нужной последовательности (листинг 8).

Листинг 8. Составление фильтра из отдельных правил.

public class WikiFilter extends AbstractFilter

{

public WikiFilter(int aMaxWordLength, int aMaxStringLength)

{

// замена < на <

addRule(new ReplaceLeftTagBracketRule());

// замена & на &

addRule(new ReplaceAmpersandTagBracketRule());

// правило экранирования – для возможности вывода спецсимволов

addRule(new EkranRule());

// правило замены http://... - ссылками

addRule(new AnchoringRule(aMaxWordLength));

... ... ...

// правило разбивания длинных слов пробелами

addRule(new BreakWordsRule(aMaxWordLength));

// правило «обрезания» длинных строк

addRule(new MaxLengthRule(aMaxStringLength));

}

После этого обработка строки данным фильтром представляет собой тривиальную задачу:

String result =

new WikiFilter(maxWordLength, maxStringLength).process(sourceString);

AbstractRule определяет методы setEnabled() и isEnabled(), одинаковые для большинства фильтров.

public abstract class AbstractRule implements IRule

{

// это поле сделано ThreadLocal для того, чтобы можно было одним фильтром

// обрабатыватьнесколькострокодновременно

private ThreadLocal _enabledThreadLocal = new ThreadLocal()

{

protected Object initialValue() {

// поумолчаниюправиловключается

return Boolean.TRUE;

}

};

public void setParameters(Map aParameters) throws FilterException

{

// для многих правил этот метод не используется, поэтому делаем

// его необязательным

}

public void initialize()

{

// так же, как и setParameters – делаем этот метод необязательным

}

public void setEnabled(boolean aEnabled)

{

_enabledThreadLocal.set(Boolean.valueOf(aEnabled));

}

public boolean isEnabled()

{

return ((Boolean) _enabledThreadLocal.get()).equals(Boolean.TRUE);

}

Есть возможность отключать некоторые правила непосредственно в процессе работы фильтра или между исполнениями метода process(). Можно также динамически изменять фильтр или настраивать его. При этом не требуется перекомпиляции кода или самого фильтра.

Также создан вспомогательный класс CustomFilterFromXML, который позволяет загрузить конфигурацию фильтра из XML-файла и автоматически ее обновляет при изменении XML-файла.

Применение

Метод фильтрации строк, представленный в данной статье, применим не только в узкоспециализированной области работы с интернет-текстами. Создавая разные правила, легко создавать строки, которые будут управлять, например поведением программы. Возможности неограниченны. Описанная здесь система называется JFilter и распространяется свободно, ее страничка в интернете: http://blog.existence.ru/exception/.products.JFilter. Там можно найти как библиотеку в формате jar, так и исходные тексты с документацией. В приложении приведен код интерфейсов фильтра и правила, которые являются основными интерфейсами системы. JFilter используется в системе блогов JDnevnik [6] и еще в нескольких проектах.

Правила, входящие в поставку

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

Стандартные правила (jfilter.rules.general)	BreakWorksRule – разбивает длинные слова пробелом.
EkranRule – правило экранирования спецсимволов.
MaxLengthRule – правило, которое ограничивает длину строк.
HTML-правила (jfilter.rules.html)	AnchoringRule – замена текста, начинающегося с http:// (или аналогов) и заканчивающегося пробелом, HTML-ссылкой.
MailRule – замена текста, заключенного в пробелы и содержащего символ «@», HTML-ссылкой.
Эмотиконы (jfilter.rules.smiles)	PreSmiler – замена обозначений эмотиконов («:-)», «;)» и так далее) на их стандартные обозначения для обработки SmilesRule’ом.
SmilesRule – замена одиночных слов, заключенных в парные двоеточия «::», HTML-картинками.
Транслитерация (jfilter.rules.transliteration)	Lat2RusTransliterationRuleGroup – транслитерация. Соответствует ISO и ГОСТ (то есть можно писать как по ГОСТу, так и обозначениями ISO; пока конфликтов такого варианта я не обнаружил).
Типографика (jfilter.rules.typografica)	AbbreviationsRule – замена (c), (p), (r), (tm) соответствующими HTML-символы.
HellipRule – замена трех точек подряд символом «многоточие».
LongDashRule – Замена символа «минус», обрамленного пробелами символом «тире».
QuotesRule – замена «знака дюйма» корректными кавычками для русского языка.
Вики-форматирование (jfilter.rules.wacko)	AnchorRule – создание ссылок в виде ((link)).
BlockquoteRule – цитата (>>текст>>).
BoldRule – выделение полужирным начертанием (полужирный).
HeaderRule – заголовок (==заголовок==).
ItalicRule – выделение курсивом (//курсив//).
MonospaceRule – выделение моноширинным шрифтом (##моноширинный##).
NoteRule – выделение замечания (span class=”note”).
ParagraphRule – Работа с переводами строки (одиночный перевод строки - <br/>, два подряд - <p>).
PreformattedRule – выделение предварительно отформатированного текста (%%уже форматрованный текст%%).
ReplaceAmpersandTagBracketRule – замена символа “&” соответствующим HTML-аналогом (&).
ReplaceLeftTagBracketRule – замена символа “<” соответствующим HTML-аналогом (<).
SmallRule – выделение мелким шрифтом (++мелкий++).
StrikeRule – выделение перечеркиванием (--перечеркнутый--).
SubscriptRule – выделение нижним индексом (vvнижний индексvv).
SuperscriptRule – выделение верхним индексом (^^верхний индекс^^).
UnderlineRule – выделение подчеркиванием (__подчеркивание__).

Таблица 1. Стандартные правила.

Сравнение работы разных типов обработки строк

Свойство	Классический способ	Регулярные выражения	Фильтрация
Простота реализации	Просто	Очень сложно	Сложно
Возможности изменения	Для простых задач – очень большие, для сложных – очень сложные	Только вместе с перекомпиляцией выражения	Максимальные
Простота использования	Очень просто	Просто для тех, кто потратил много времени на обучение	Очень просто
Скорость работы	Быстро на простых вариантах, обычно медленно на сложных, сильно зависит от реализации	Быстро, если правильно использовать	Быстро

Таблица 2. Сравнение разных типов обработки строк.

Заключение

Хочется отметить, что библиотека JFilter продолжает развиваться, на настоящий момент реализовано очень много, но далеко не все из того, что хотелось бы реализовать. В ближайшем будущем предполагается написание дополнительных правил для классической, «бумажной» типографики, которые помогали бы редакторам и верстальщикам самых обычных, бумажных книг/журналов/газет.

Список литературы

ФридлДж., Mastering Regular Expressions. Питер, 2003 год.

http://is.ifmo.ru, Санкт-Петербургский Государственный университет информационных технологий, механики и оптики, кафедра «Технологии программирования».

Бабаев А., МИР ПК - ДИСК. 2003. №12, Транслитерация и как правильно ее надо программировать.

http://is.ifmo.ru/projects/bone/ – cоздание скелетной анимации на основе автоматного программирования.

http://wackowiki.com/projects/WackoFormatter –библиотека для форматирования текста WackoFormatter.

http://blog.existence.ru/exception/.products.JDnevnik – Система блогов JDnevnik.