Вариации на тему кодирования
Я хочу сейчас привести тексты пяти макросов, которые я постоянно использую в своей повседневной работе. Почти все они являются вариациями одной из классических задач, возникающих при работе с текстами. Эта задача, которую будем называть задачей о трансляции символов, формулируется следующим образом: "Дан текст - последовательность символов. Каждый символ текста требуется заменить строкой символов или в частном случае - одним символом". Вот несколько типичных ситуаций, приводящих к этой задаче:
- При работе с двуязычным текстом фрагмент текста на русском языке ошибочно набран в английской раскладке клавиатуры. Требуется его преобразовать в соответствии с русской раскладкой
- Обратная задача - фрагмент текста на английском языке ошибочно набран в русской раскладке клавиатуры
- Задача транслитерации часто возникает при посылке за рубеж сообщений по Email русскоязычным абонентам, у которых нет кириллицы, и приходится русский текст набирать латинскими буквами. Существует общепринятые соглашения на кодировку символов. Большинство символов русского алфавита кодируются символами английского алфавита, но некоторые из них кодируются последовательностью из двух - трех символов.
- Наиболее распространенная вариация задачи этого типа связана с различными способами кодирования и декодирования символов. Например, Вы можете создать для переписки с абонентами собственный способ кодирования - декодирования, не защищающий, конечно от грубого взлома, но предохраняющий от простого любопытства. На эту тему написано большое число кодировщиков.
Прежде чем приводить реализацию частных случаев скажем несколько слов об общей схеме решения задачи трансляции. Для ее решения достаточно построить два массива одинаковой длины Source и Dest, первый - массив исходных символов, требующих перевода, второй - массив строк, задающих перевод каждого символа. Dest(i) задает перевод символа Sourse(i). Разумно задавать Source в виде строки символов, упорядоченных в соответствии с их кодировкой. Если кодирование имеет тип "символ в символ", то и Dest представляется строкой символов. Пусть теперь Text - это исходный текст, подлежащий переводу, а TextResult - результирующий текст после первода. Алгоритм решения задачи трансляции выглядит следующим образом:
TextResult = "" For Each Sym In Text Index = FindIndex(Sym, Source) TextResult = TextResult & Dest(Index) Next
Листинг 2.17.
(html, txt)
Функция FindIndex определяет индекс вхождения символа Sym в строку Source. Эффективная ее реализация может использовать классический алгоритм бинарного поиска, имеющий сложность logM, где M - длина строки Source (количество символов исходного множества). Общая сложность алгоритма трансляции символов - NlogM, где N - длина текста. Учитывая, что, как правило, M < 256, общая сложность не превосходит 8N. Поиск индекса можно реализовать проще и эффективнее бинарного при условии, что исходное множество символов имеет плотную кодировку, то есть код следующего символа на 1 больше предыдущего. В этом случае используется встроенная функция Asс, возвращающая код символа.
