Обработка текста при помощи автомата
Продолжаю разбор вариантов обработки текста. В этой небольшой статье я покажу как работать с текстом без регулярных выражений, на основе конечного автомата. И чтобы было наглядно, сделаю это на примере перевода текста русского языка в то, что называют "олбанским". Взглянуть на то, как это работает можно здесь.
Почему автоматы
Автоматы являются мощным средством обработки текстовой информации. По выразительности они эквивалентны регулярным выражениям: и те и другие описывают особый класс языков, называемый регулярными. Таким образом, данный код мог быть заменен набором регулярных выражений. Но я предпочел все же автоматное описание, потому что:
- данная реализация представляется более элегантной, чем использование регулярных выражений;
- в случае усложнения логики правил преобразования текста, логику автоматов проще структурировать: разделять правила, разбивать обработку на отдельные уровни;
Как это работает
Здесь я не буду в деталях описывать как устроены автоматы. Это тема отдельной большой статьи. Желающие глубже разобраться с этой тематикой могут посмотреть книгу "Введение в теорию автоматов, языков и вычислений" Хопкрофта, Мотвани и Ульмана. Сейчас же опишу основной принцип построения преобразователя.
Как известно "олбанский" строится на искажении русских слов и словосочетаний по определенным правилам. К примеру, "и" после шипящих заменяется на "ы". Буква "я" в определенных словах заменяется на "йа" и т.п. Основная идея заключается в описании каждого из правил отдельным небольшим автоматом, и далее, соединения автоматов в единый автомат.
Замечу, что здесь используется так называемый трансдьюсер, который является расширением "типичных автоматов" (акцепторов). Отличие заключается в том, что на каждый символ входа трансдьюсер может сгенерировать выходной символ. Этим он и удобен: такая техника позволяет преобразовывать входную последовательность символов по определенным правилам.
И так, разберем простое правило. Рассмотрим преобразование слова "яд" в "йад". Фактически, нам нужно заменить символ "я" на символы "йа". Построенный автомат для этого правила показан на левом рисунке. Нам достаточно одного состояния автомата с двумя петлями. Верхняя петля позволяет при каждом нахождении символа "я" преобразовывать его в нужные нам буквы "йа". Нижняя же петля позволяет обрабатывать другие символы, где "@" обозначает "любой другой символ".
Автомат на рисунке слева позволит сделать нужные нам преобразования буквы "я". Однако, это не то что мы ожидаем. К примеру, слово "мяч" будет преобразовано в "мйач", что не соответствует правилам жаргона. Если приглядеться, то мы заметим что это правило работает либо перед гласными (маяк->майак), либо вначале слова (якорь->йакорь, ). Это условия мы можем наложить, используя еще одно состояние. Это показано на правом рисунке, где изменяется только та "я", которая идет в начале слова. Символ "sep" обозначает любой разделитель слов: пробел и знаки пунктуации.
Чтобы учесть требования преобразования после гласной, необходимо просто добавить переходы из состояния "a" в состояние "b" по всем гласным русского языка (чтобы не загромождать диаграмму, на рисунке справа этого не показано).
Реализация
Ниже приводится полный код. Большая часть строк - описание правил преобразования текста. Они помечены префиксом "rule_".
#!/usr/bin/env python
#-*- coding=utf-8 -*-
class Node(object):
def __init__(self, is_final=False):
self.arcs = {}
self.is_final = is_final
def arc(self, node, itokens, otoken):
if not itokens:
itokens = [itokens]
for itoken in itokens:
if itoken in self.arcs:
self.arcs[itoken].append((node, otoken))
else:
self.arcs[itoken] = [(node, otoken)]
def traverse(node, itape):
otapes = []
if itape:
if itape[0] in node.arcs:
for child, otoken in node.arcs[itape[0]]:
if otoken == '@':
otoken = itape[0]
for otape in traverse(child, itape[1:]):
otapes.append([otoken] + otape)
if not otapes and '@' in node.arcs:
for child, otoken in node.arcs['@']:
if otoken == '@':
otoken = itape[0]
for otape in traverse(child, itape[1:]):
otapes.append([otoken] + otape)
if not itape and node.is_final:
otapes.append([])
return otapes
sp = u' ' # пробел
sep = sp + u',.;:!?-' # разделители
vov = u'аеёиоуыэюя' # гласные
bcons = u'кпстфх' # некоторые глухие согласные
alph = u'абвгдеёжзиклмнопрстуфхцчшщъыьэюя'
# животное -> жывотное
def rule_zhi_shi(root):
s0 = Node()
root.arc(s0, u'ж', u'ж')
root.arc(s0, u'ш', u'ш')
s0.arc(root, u'и', u'ы')
# яд -> йад
# юла -> йула
def rule_ya_yu(root):
s0, s1 = Node(), Node()
root.arc(s0, vov + sp, '@')
s0.arc(root, u'я', u'йа')
s0.arc(root, u'ю', u'йу')
s0.arc(root, u'ё', u'йо')
# под забором -> патзабором
def rule_pod_prep(root):
s0, s1, s2, s3 = Node(), Node(), Node(), Node()
root.arc(s0, sp, sp)
s0.arc(s1, u'п', u'п')
s1.arc(s2, u'о', u'а')
s2.arc(s3, u'д', u'т')
s3.arc(root, sp, u'')
# в топку -> фтопку
def rule_v_prep(root):
s0, s1, s2 = Node(), Node(), Node()
root.arc(s0, sp, sp)
s0.arc(s1, u'в', u'ф')
s1.arc(s2, sp, '')
s2.arc(root, bcons, '@')
# все -> фсе
def rule_v_begin(root):
s0, s1 = Node(), Node()
root.arc(s0, sp, sp)
s0.arc(s1, u'в', u'ф')
s1.arc(root, bcons, '@')
# автор -> аффтoр
def rule_v_middle(root):
s0, s1 = Node(), Node()
root.arc(s0, vov, '@')
s0.arc(s1, u'в', u'фф')
s1.arc(root, bcons, '@')
# мотив -> мотифф
def rule_v_end(root):
s0, s1 = Node(), Node()
root.arc(s0, vov, '@')
s0.arc(s1, u'в', u'фф')
s1.arc(root, sep, '@')
# мальчик -> мальчег
def rule_ig_end(root):
s0, s1 = Node(), Node()
root.arc(s0, u'cчлмд', '@')
s0.arc(s1, u'и', u'е')
s1.arc(root, u'к', u'г')
# привет -> привед
def rule_ed_end(root):
s0, s1, s2 = Node(), Node(), Node()
root.arc(s0, alph, '@')
s0.arc(s1, u'е', u'е')
s1.arc(s2, u'т', u'д')
s2.arc(root, sep, '@')
# учиться -> учиццо
def rule_ts_end(root):
s0, s1, s2 = Node(), Node(), Node()
root.arc(s0, u'т', u'ц')
s0.arc(s1, u'ь', '')
s1.arc(s2, u'с', u'ц')
s0.arc(s2, u'c', 'ц')
s2.arc(root, u'я', u'о')
# отстаивать -> оцтаивать
def rule_ts_middle(root):
s0, s1, s2 = Node(), Node(), Node()
root.arc(s0, u'тд', u'ц')
s0.arc(s2, u'с', u'')
s2.arc(root, vov, '@')
s2.arc(root, u'т', u'т')
# синица -> синицца
# лиц -> лицц
def rule_tss_middle(root):
s0, s1 = Node(), Node()
root.arc(s0, vov, u'@')
s0.arc(s1, u'ц', u'цц')
s1.arc(root, vov, '@')
s1.arc(root, sep, '@')
# что -> што
def rule_chto_middle(root):
s0, s1, = Node(), Node()
root.arc(s0, u'ч', u'ш')
s0.arc(s1, u'т', u'т')
s1.arc(root, u'о', u'о')
# ссылка -> сцылка
def rule_ss_begin(root):
s0, s1 = Node(), Node()
root.arc(s0, sep, '@')
s0.arc(s1, u'с', u'с')
s1.arc(root, u'с', u'ц')
# отвертки -> отвердки
# грядка -> грядко
def rule_dko_end(root):
s0, s1 = Node(), Node()
root.arc(s0, u'тд', u'д')
s0.arc(s1, u'к', u'к')
s1.arc(root, u'а', u'о')
s1.arc(root, sep, '@')
def prepare(text):
# Убираем лишние пробелы
s0, s1 = Node(is_final=True), Node(is_final=True)
s0.arc(s1, u' ', u' ')
s1.arc(s1, u' ', u'')
s0.arc(s0, '@', '@')
s1.arc(s0, '@', '@')
return .join(traverse(s0, text)[0])
def modify(text):
# Создаем корень и петлю
root = Node(is_final=True)
root.arc(root, '@', '@')
# Получаем список правил
g = globals()
for item in g:
if item.startswith('rule_'):
g[item](root)
# Подготавливаем текст
prep_text = ' ' + prepare(text) + ' '
# Бежим по автомату и возвращаем текст
modified_text = .join(traverse(root, prep_text)[0])
return modified_text[1:-1]
Пример использования:
>>> print modify('в топку')
фтопку
Хотя код получился довольно объемным, большую часть занимает конструкция правил. Вся логика содержится в классе Node и функции traverse. Класс Node представляет собой состояние автомата. Состояние может быть финальным (атрибут is_final=True). Метод arc создает переход на другое состояние по заданному входному символу.
Метод traverse пробегает по автомату от корня до финального узла, по пути преобразовывая входящую последовательность в исходящую. Надо отметить, что в автомат заложена небольшая хитрость. По символу "@" происходит переход только тогда, когда не получается найти путь по другим символам, исходящим из данного состояния. Это не совсем согласуется со стандартной моделью транспьютера, однако позволяет избежать лишних вариантов обхода автомата.
p.s. Здесь описаны далеко не все правила "олбанского". К примеру, отсутствует изменение безударных гласных. Но это преобразование потребовало бы знания морфологической информации слов. Я же хотел чтобы код был максимально прост.