Pull to refresh

ORegex: От символов к объектам

Reading time 4 min
Views 8.6K
Добрый вечер, хаброжители!
Сегодня я хочу поделиться с вами таким еще молодым проектом, как 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.
Tags:
Hubs:
+10
Comments 18
Comments Comments 18

Articles