45815 (Фильтрация строк с использованием автоматов)
Описание файла
Документ из архива "Фильтрация строк с использованием автоматов", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "45815"
Текст из документа "45815"
Фильтрация строк с использованием автоматов
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-код. Таким кодом традиционно считается любой кроме некоторых очень простых тегов , , и аналогичных.
При условии соблюдения правила номер девять, дать пользователю возможность форматирования текста, а именно, выделения текста полужирным, наклонным начертанием, перечеркивания или подчеркивания текста, выделения цитаты и форматированного текста (кода программы, например).
Эти правила достаточно стандартны для практически любой системы, где используется работа с текстом. Существует множество вариантов их реализации. Самый распространенный – при помощи уже упоминавшихся регулярных выражений [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. Реализация правила замены трех точек на «…»
| 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
Классы
