Expressões Regulares e Métodos de Estados Finitos

Técnicas práticas baseadas em linguagens regulares — correspondência de padrões com expressões regulares e mapeamento de string para string com transdutores de estados finitos — que lidam com tokenização, normalização e análise morfológica de forma eficiente.

Definition

Métodos de estados finitos são técnicas de processamento de linguagem nas quais padrões e mapeamentos são expressos como expressões regulares ou autômatos e transdutores de estados finitos, garantindo reconhecimento eficiente em tempo linear.

Scope

Abrange expressões regulares como uma linguagem de padrões sobre strings, autômatos de estados finitos e transdutores como sua realização computacional, e sua aplicação à normalização de texto, tokenização, ortografia e morfologia computacional. Inclui métodos de estados finitos ponderados usados em fala e processamento superficial. A teoria fonológica completa e a análise sintática profunda estão fora do escopo.

Core questions

• Como as expressões regulares podem especificar e extrair padrões textuais com precisão?
• Como os transdutores de estados finitos mapeiam formas de superfície para análises lexicais, como na morfologia?
• Por que os métodos de estados finitos são preferidos para tokenização e normalização?

Key concepts

• expressão regular
• transdutor de estados finitos
• tokenização
• normalização de texto
• análise morfológica
• morfologia de dois níveis
• autômatos ponderados
• distância de edição

Key theories

Modelos regulares de morfologia e fonologia

O resultado de que as regras de reescrita fonológica e as alternâncias morfológicas podem ser compiladas em transdutores de estados finitos, tornando a análise e a geração um único arcabouço eficiente.

Equivalência de expressões regulares e autômatos finitos

Expressões regulares, gramáticas regulares e autômatos de estados finitos descrevem exatamente as linguagens regulares, de modo que um padrão declarativo pode ser compilado em um reconhecedor eficiente.

History

As expressões regulares entraram na computação a partir do trabalho de Kleene e tornaram-se ubíquas em ferramentas de texto. Na década de 1980, a morfologia de dois níveis de Koskenniemi e a compilação de regras fonológicas em transdutores por Kaplan e Kay estabeleceram a tecnologia de estados finitos como a principal ferramenta de processamento morfológico, uma abordagem consolidada no manual de Beesley e Karttunen.

Debates

Até que ponto os métodos de estados finitos podem escalar?

As técnicas de estados finitos são extremamente eficientes, mas limitadas a fenômenos regulares; o debate diz respeito a quais tarefas de processamento de linguagem continuam sendo melhor atendidas por elas em comparação com modelos estatísticos ou neurais mais ricos.

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

Por que usar um transdutor de estados finitos em vez de apenas uma tabela de consulta para morfologia?

Um transdutor codifica compactamente alternâncias sistemáticas e pode analisar ou gerar formas de palavras que nunca viu, enquanto uma tabela armazena apenas as formas explicitamente listadas nela.