Сегодня я хочу поделиться с вами таким еще молодым проектом, как ORegex или Object Regular Expressions. Я уже довольно долго работаю в компьютерной лингвистике и хоть я не лингвист, но все же вижу в языках какие-то устоявшиеся конструкции, шаблоны.
Для тех кому интересно, как я решил их выделять — под кат.
Эти шаблоны могут быть как простыми:
- Смайлы;
- Хештеги;
- Даты;
- Телефоны;
- и т.д.
Так и сложными:
- Прямая речь;
- Названия разнообразных компаний;
- Имена;
- Перечисления в тексте;
- и т.д.
В основном моя работа заключалась в том, чтобы понять, что и как извлечь из последовательности объектов. Это можно делать через грамматики, можно через автоматы, а можно просто написать пару вложенных циклов. Но когда мне конкретно надоело писать тонны парсеров разнообразных последовательностей (токены, слова, объединения слов и т.д.) с разной сложностью и огромным количеством багов, мне пришел в голову резонный вопрос — можно ли сделать проще? Ответ пришел интуитивно: используй регулярные выражения для поиска.
Но как? Регулярные выражения, конечно, хорошо и быстро справятся с задачей поиска по шаблону, вот только все движки написаны исключительно под символьные последовательности, а те, что заточены под объекты совсем не радуют своими скоростными качествами и вообще находятся в других языковых плоскостях. В итоге недолгих раздумий было принято решение написать свой «велосипед с нормальной системой передач».
Проект я решил сделать с открытым исходным кодом по ряду причин, но сейчас не об этом.
Давайте взглянем на то, как вообще его можно использовать в боевых условия.
How to use?
Над синтаксисом я долго не думал, было решено использовать стандартную нотацию .NET + возможность добавлять комментарии и писать нормальные имена для атомарных условий. Это позволило бы без проблем выносить паттерны в отдельные файлы:
{MyPredicate1} | (?{MyPredicate2} {MyPredicate3}*)
Стоит заметит, что на данный момент некоторые функции .NET Regex не включены (условные операторы, lookahed), но в скором будущем они обязательно появятся. А теперь перейдем к самим примерам. Допустим, у нас есть последовательность чисел:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
И Ваша задача заключается в том, чтобы найти все последовательные простые числа. Для этого Вам нужно определить функцию, которая будет отвечать на вопрос является ли число простым, либо нет:
private static bool IsPrime(int number)
{
int boundary = (int)Math.Floor(Math.Sqrt(number));
if (number == 1) return false;
if (number == 2) return true;
for (int i = 2; i <= boundary; ++i)
{
if (number % i == 0) return false;
}
return true;
}
И определить паттерн для поиска простых последовательностей:
{IsPrime}(.{IsPrime})*
На этом, в общем и целом, сложная часть закончена. Опишем саму процедуру выделения:
public void PrimeTest()
{
var oregex = new ORegex<int>("{0}(.{0})*", IsPrime);
var input = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
foreach (var match in oregex.Matches(input))
{
Console.WriteLine(string.Join(",", match.Values));
}
//OUTPUT:
//2
//3,4,5,6,7
//11,12,13
}
Ну вот и все, но не так убедительно, да? Хорошо, тогда давайте приведем примерчик посложнее. Представим, что у нас есть некая последовательность слов пришедшая к нам из лексико-морфологического модуля. Вопрос, как по быстрому выделить наименования персон из последовательности? Довольно просто.
Определяем классы слова и персоны:
public enum SemanticType
{
Name,
FamilyName,
Other,
}
public class Word
{
public readonly string Value;
public readonly SemanticType SemType;
public Word(string value, SemanticType semType)
{
Value = value;
SemType = semType;
}
}
public class Person
{
public readonly Word[] Words;
public readonly string Name;
public Person(OMatch<Word> match)
{
Words = match.Values.ToArray();
Name = match.OCaptures["name"].First().Values.First().Value;
//Now just normalize this name and you are good.
}
}
И дополнительно какую-нибудь важную функцию, которая, будет определять что строка на самом деле является инициалом:
private static bool IsInitial(string str)
{
var inp = str.Trim(new[] { '.', ' ', '\t', '\n', '\r' });
return inp.Length == 1 && char.IsUpper(inp[0]);
}
Без лишних слов, составляем таблицу предикатов, паттерн и получаем наши объекты персон:
public void PersonSelectionTest()
{
//INPUT_TEXT: Пяточкова Тамара решила выгулять Джека и встретилась с Михаилом А.М.
var sentence = new Word[]
{
new Word("Пяточкова", SemanticType.FamilyName),
new Word("Тамара", SemanticType.Name),
new Word("решила", SemanticType.Other),
new Word("выгулять", SemanticType.Other),
new Word("Джека", SemanticType.Name),
new Word("и", SemanticType.Other),
new Word("встретилась", SemanticType.Other),
new Word("с", SemanticType.Other),
new Word("Михаилом", SemanticType.Name),
new Word("А.", SemanticType.Other),
new Word("М", SemanticType.Other),
};
//Создаем таблицу предикатов.
var pTable = new PredicateTable<Word>();
pTable.AddPredicate("Фамилия", x => x.SemType == SemanticType.FamilyName); //Check if word is FamilyName.
pTable.AddPredicate("Имя", x => x.SemType == SemanticType.Name); //Check if word is simple Name.
pTable.AddPredicate("Инициал", x => IsInitial(x.Value)); //Complex check if Value is Inital character.
//Создаем наше выражение из паттерна и таблицы.
var oregex = new ORegex<Word>(@"
{Фамилия}(?<name>{Имя}) //Comments can be written inside pattern...
|
(?<name>{Имя})({Фамилия}|{Инициал}{1,2})? /*...even complex ones.*/
", pTable);
//Выделяем персон в последовательности.
var persons = oregex.Matches(sentence).Select(x => new Person(x)).ToArray();
foreach (var person in persons)
{
Console.WriteLine("Person found: {0}, length: {1}", person.Name, person.Words.Length);
}
//OUTPUT:
//Person found: Тамара, length: 2
//Person found: Джека, length: 1
//Person found: Михаилом, length: 3
}
Ну вот и все. Постарался описать все вкратце и доходчиво =)
Если что библиотека доступна как в nuget так и на github.
Комментарии (17)
Holms
01.03.2016 07:41Я уж начал почесывать руки и сразу начал думать как бы я это использовал для моего проекта, но не тут то было, оказывается без разбивки текста (предложения) на токены ничего не будет работать.
Есть идеи как все это автоматизировать для больших текстов?
eocron
01.03.2016 08:13Как правило все проблемы в лингвистике решаются двумя путями: эвристики в которых безбожно пишутся регулярки и словарные методы и машинное обучение. В данном случае лучше машинным обучением на разделителях. Почитайте на мейл ру, а так же в интернете. Есть много литературы на эту тему и качество у моделей часто высокое и достаточное для бизнес процессов.
Nashev
01.03.2016 10:21Сейчас поверх дерева разбора, которое создает Компрено, у ABBYY продается работающий Data Extractor, который вместо ваших регулярок использует свой язык описания паттернов извлечения нужных данных (они сделанный для отдельной задачи комплект называют онтологией). Возможно, язык регулярок им тоже бы приглянулся, или Вам может быть при сравнении что-нибудь про его недостатки стало бы понятно
eocron
01.03.2016 10:59Я бы сказал, что некорректно сравнивать многофункциональную документо-дробилку и прикладной фреймворк для .NET на шаблонных коллекциях. Это же вообще разные задачи. Да даже если и можно их использовать (через обертку) так же удобно как в этой статье, то я не думаю, что это хорошая идея таскать за собой танкер вместо поплавка. Да и денежный вопрос как-то напрягает, не у всех есть возможность составить договор с ABBYY на круглую сумму.
Nashev
01.03.2016 11:05Неэтично, хотели сказать? Типа, это сравнение априори понятно по каждому аспекту, в чью пользу? Потому как параллели провести вполне полезно, ведь одну и ту же задачу решаете, только в разном масштабе заморочек и сложностей. Это как лопата и экскаватор — вещи разные, но общее назначение есть.
eocron
01.03.2016 11:18За тем исключением, что экскаватором цветы не сажают =) На самом деле это только кажущееся общее назначение. Параллели были проведены заранее с уже существующими инструментами: чтобы не придумывать свой язык, я выбрал уже устоявшийся в обществе язык регулярных выражений, его даже лингвист без проблем выучит и просто следовал Майкрософтовскому Дзен в видении регулярок. Их используют везде и знает практически каждый. Чего я бы не сказал об ABBYY.
Nashev
01.03.2016 11:35Зануда mode on
Я ж не спорю с тем, что отличия есть. Но вы зачем-то спорите с тем, что параллели тоже есть...
Я говорил о том, что опора на язык регулярок возможно пригодилась бы и им. Но так же и о том, что у него могут найтись недостатки.eocron
01.03.2016 12:12А, ну, они и сами не дураки, думаю, догадаются. Недостатки и плюсы регулярок описаны на википедии. А недостатки моей реализации исправляю, пока что, я сам.
potan
03.03.2016 14:22Есть методика построения парсеров — комбинаторные или монадические парсеры. По ней анализ последовательности с использованием дополнительных рукописных предикатов реашется очень легко и элегантно.
eocron
03.03.2016 15:59А при чем здесь парсинг? Парсинг в RE появился как полезный нарост с течением времени. Безусловно, грамматиками можно сделать все, но кому это надо? У них логика сложнее и часто вообще не практично их использовать. Ни в плане разработки, ни в плане конечного результата.
VersusVoid
Есть прекрасная библиотека от Стэнфорда. Правда на джаве, но с биндингами для .NET. Для лентяев поясните вкратце, пожалуйста, чем она вас не устроила и какие у вашей преимущества?
eocron
Честно скажу, она не успела произвести на меня впечатления, так как я узнал о ней недавно :)
Я изначально делал упор на общедоступность и скорость. К сожалению, использовать явовские библиотеки стенфорда свободно нельзя (лицензия) и интероп — тоже не сахар. Кстати, за неимением функциональности явовский аналог медленнее. Бенчмарк я постараюсь выложить на гитхабе, как будет минутка.
VersusVoid
Спасибо, именно это я и хотел бы увидеть. Один хороший бенчмарк стоит тысячи слов.
QtRoS
Без сравнительных тестов это маркетинг. Присоединяюсь к VersusVoid
eocron
А вы знаете, что такое маркетинг? Просто слово модное и, часто, не все понимают его значение )
QtRoS
Смысл же все равно уловили наверняка?
Так что насчет бенчмарков?
eocron
Нет, не уловил.
На выходных.