Регулярные выражения и конечно-автоматные методы

Практические методы, основанные на регулярных языках — сопоставление с образцом с помощью регулярных выражений и отображение строк с помощью конечно-автоматных преобразователей — которые эффективно справляются с токенизацией, нормализацией и морфологическим анализом.

Definition

Конечно-автоматные методы — это методы обработки языка, в которых шаблоны и отображения выражаются в виде регулярных выражений или конечно-автоматных автоматов и преобразователей, что гарантирует эффективное распознавание за линейное время.

Scope

Охватывает регулярные выражения как язык шаблонов для строк, конечно-автоматные автоматы и преобразователи как их вычислительную реализацию, а также их применение к нормализации текста, токенизации, проверке орфографии и вычислительной морфологии. Включает взвешенные конечно-автоматные методы, используемые в обработке речи и поверхностной обработке. Полная фонологическая теория и глубокий синтаксический анализ выходят за рамки данного рассмотрения.

Core questions

• Как регулярные выражения могут точно специфицировать и извлекать текстовые шаблоны?
• Как конечно-автоматные преобразователи отображают поверхностные формы в лексический анализ, как, например, в морфологии?
• Почему конечно-автоматные методы предпочтительны для токенизации и нормализации?

Key concepts

• регулярное выражение
• конечно-автоматный преобразователь
• токенизация
• нормализация текста
• морфологический анализ
• двухуровневая морфология
• взвешенные автоматы
• редакционное расстояние

Key theories

Регулярные модели морфологии и фонологии

Результат, согласно которому фонологические правила перезаписи и морфологические чередования могут быть скомпилированы в конечно-автоматные преобразователи, что делает анализ и генерацию единой эффективной системой.

Эквивалентность регулярных выражений и конечных автоматов

Регулярные выражения, регулярные грамматики и конечные автоматы описывают в точности регулярные языки, поэтому декларативный шаблон может быть скомпилирован в эффективный распознаватель.

History

Регулярные выражения вошли в вычислительную технику из работ Клини и стали повсеместно использоваться в текстовых инструментах. В 1980-х годах двухуровневая морфология Коскенниеми и компиляция фонологических правил в преобразователи Капланом и Кеем утвердили конечно-автоматную технологию как основной инструмент морфологической обработки, подход, консолидированный в справочнике Бисли и Карттунена.

Debates

Насколько масштабируемы конечно-автоматные методы?

Конечно-автоматные методы чрезвычайно эффективны, но ограничены регулярными явлениями; дискуссия касается того, какие задачи обработки языка лучше всего решаются ими по сравнению с более богатыми статистическими или нейронными моделями.

Key figures

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

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

Почему для морфологии используется конечно-автоматный преобразователь вместо простой таблицы поиска?

Преобразователь компактно кодирует систематические чередования и может анализировать или генерировать словоформы, которые он никогда не видел, тогда как таблица хранит только те формы, которые явно в ней перечислены.