Sobre Expressões Regulares

Vamos falar um pouco sobre a prática da linguística computacional?

O tema de hoje é algo fundamental para o processamento de linguagem natural: as expressões regulares!

Mas o que diabos é isso? De novo, vamos partir de uma definição da Wikipedia:

Nas ciências da computação e na teoria das linguagens formais, uma expressão regular é uma sequência de caracteres que definem um padrão de busca, usado principalmente para buscas textuais. O conceito surgiu nos anos 50, quando o matemático americano Stephen Kleene formalizou a descrição de uma linguagem regular que se popularizou  ao ser incorporada no processador de texto do sistema Unix.

Ainda hoje, pequenas variações da linguagem regular descrita por Kleene estão no coração dos principais editores de texto, mecanismos de busca e linguagens de programação.

Sem entrar nos pormenores envolvendo teoria da computação, autômatos ou linguagens formais, quero focar na extrema utilidade e elegância das expressões regulares — No fim do post deixarei alguns  links com explicações mais técnicas, para quem se interessar por esse caminho.

deterministic-finite-state-machine
Hoje não vamos falar de autômatos de estados finitos 😦

Podemos pensar nessa ferramenta (também chamada de “regex”) como uma forma simples e elegante de definir padrões de texto. A partir de uma regex, é possível procurar por esse padrão definido em qualquer documento ou conjunto de documentos.

É bem fácil ver a utilidade de uma ferramenta como essa, certo? A imensa quantidade de texto disponível num mundo pós-internet criou uma necessidade também imensa de métodos para explorar e investigar esses documentos.

Por isso, as regex são fundamentais nas áreas de extração de informação (data mining, em português contemporâneo), big data, processamento de linguagem natural, etiquetagem morfossintática, reconhecimento de entidades nomeadas, entre outras. O princípio é o seguinte: uma regex é uma sequência de caracteres. Alguns desses caracteres têm funções específicas e, a partir do padrão desenhado pela combinação desses caracteres, é possível fazer operações, como copiar as partes importantes de um texto e organizá-las em uma tabela.

Por exemplo, se você tivesse um conjunto grande de e-mails formais e quisesse descobrir o nome do destinatário de todos eles… O que você faria?Para resolver essa questão é necessário usar não só as expressões regulares, mas também algum conhecimento linguístico.

Vamos pensar: o nome do destinatário, por convenção, é sempre posto na primeira linha de um e-mail/carta formal, num formato como ‘Caro senhor X’, ‘Cara senhora X’ ou ainda ‘Prezado senhor X’ ou ‘Prezada senhora X’. Além disso, temos outra convenção importante: os nomes próprios são representados com a primeira letra maiúscula.

Em seguida, as questões dessa abordagem: temos que percorrer os dados uma vez para cada uma dessas variações de Caro/Cara/Prezado/Prezada? Isso é bastante ineficiente! Além disso, os nomes próprios são bem traiçoeiros, nenhuma lista contém todas as variações de todos os nomes possíveis do português brasileiro! Como a gente identifica um nome? Uma palavra também pode começar com letra maiúscula se ela for a primeira depois de um símbolo como “!”, “.”, “?” e isso não significa que ela é um nome, certo?

Por fim,  a nossa questão central: como fazemos para o computador capturar esse valor variável que é o nome? E o sobrenome?

Usando uma expressão regular simples, conseguimos captar o nome de qualquer e-mail que comece com algum dos cabeçalhos indicados acima, a expressão é a seguinte:

((Car(a|o)|Prezad(a|o)) (S|s)enho(ra|r)) ([A-Z][a-z]+( )*)+

Nota: essa solução não é a mais curta possível. Eu foquei mais em obter uma resposta legível do que uma resposta compacta.

O primeiro trecho, “((Car(a|o)|Prezad(a|o)) (S|s)enho(ra|r))”, identifica qualquer uma das variações de cumprimento que eu levei em conta. As expressões regulares são bem eficientes em lidar com a ideia de alternativa e o símbolo “|” expressa essa noção (como um bom operador Booleano): ou o que está à esquerda ou o que está à direita dele. Com isso, as variações são todas contempladas de uma única vez pela expressão.

O segundo trecho, muito mais condensado, é o que efetivamente captura o nome. “([A-Z][a-z]+( )*)+” identifica o seguinte padrão:

1- Uma letra maiúscula “[A-Z]” seguida por

2- Uma ou mais letras minúsculas “[a-z]+” seguidas por

3- Zero ou mais espaços  “( )*”.

4 – Repita esse processo enquanto for possível  (representado por aquele “+” no fim).

Isso faz com que a expressão identifique nomes e sobrenomes, se houver.

Note o poder expressivo dessa pequena série de caracteres. Esse é o motivo pelo qual as expressões regulares são absolutamente indispensáveis hoje para diversas áreas.

regular_expressions
XKCD já adianta: regex salvam vidas!

Ficou com vontade de estudar mais? Seguem alguns links úteis!

1 –  Regular Expressions —Wikipedia

Mais uma vez, a página da Wikipedia é um ótimo lugar para se ter um panorama sobre o assunto. É um artigo um tanto quanto técnico, ideal para quem quer entender um pouco melhor como a coisa toda funciona.

2 – Capítulo do livro Speech and Language Processing — Jurafsky & Martin

Ótima explicação, pensando no caso da aplicação na linguística computacional mesmo. Bem técnico, mas tem a vantagem de, ao contrário da Wikipedia, pensar num público alvo específico e destacar as aplicações dessa técnica para a linguística computacional. O melhor? Disponível de graça na internet!

3 – Testador de expressões regulares

Uso bastante esse site para ir construindo uma expressão regular aos poucos. A vantagem é que você escolhe os textos em que quer fazer a busca e, conforme escreve a expressão, dá pra ver ao vivo o que está sendo selecionado no texto. Grande recurso!

 

Bônus — Regex Golf

Na verdade, as regex são praticamente a base de um culto. Existe uma modalidade chamada Regex Golf, que eu conheci através do monstro Peter Norvig, em que o desafio é criar uma expressão que identifique todos os membros de um grupo de palavras e nenhum do outro grupo. Recomendo o link para uma discussão leve e extremamente produtiva sobre esse tópico.

Bônus 2 – Abecedário de regex

Nessa página, temos um resumão contendo todos os comandos de regex! Para imprimir e ter sempre à mão!

 

((A|a)braç(o|os)|(B|b)eij(o|os)\!+)

 

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s