Комбинаторика в парсере русского языка
Не секрет, что в предложении на русском языке слова могут стоять почти в произвольном порядке.
Чтобы подобрать к команде, введенной игроком, функцию с подходящим шаблоном, необходимо в цикле перебрать все возможные перестановки слов.
Перебор перестановок делается с помощью очень простого и старого алгоритма, открытого аж в 14 веке индийским математиком Пандитом Нарайаной.
Всё это замечательно работает, пока не возникает необходимость в усложнении команд. Практически любая команда может иметь дополнительные обстоятельства, важные или не важные в зависимости от ситуации, сконструированной автором игры:
> возьми яблоко
> возьми яблоко со стола
> возьми яблоко левой рукой
Количество функций в этом случае растет по правилу комбинаторного взрыва, хотя делают они примерно одно и то же. Комбинаторный взрыв, это как раз то, от чего хотелось бы оградить и себя и всех авторов. Автор должен заниматься творческим трудом, а перебирать комбинации может и машина.
Все похожие варианты можно описать с помощью одной единственной функции, если в описании обозначить необязательные аргументы:
функция с таким описанием должна срабатывать на следующие команды:
> осмотри мусор
> осмотри мусор на полу
> на полу осмотри мусор
> осмотри на полу мусор
> мусор осмотри
> мусор осмотри на полу
> на полу мусор осмотри
> мусор на полу осмотри
Но это значит, что наш замечательный алгоритм перебора перестановок должен как-то справляться с аргументами, которые иногда есть, а иногда их нет. Да и длина функции при этом перестаёт быть константой.
Но вся прелесть алгоритма Нарайаны в том, что ему совершенно всё равно какую последовательность чисел перемешивать. С пропусками или без: 1-2-3 или 1-4-6, алгоритм в любом случае переберёт все необходимые нам перестановки.
То есть, для функции с необязательными аргументами задача сводится к формированию начальной расстановки.
Получается 2 вложенных цикла. В первом мы перебираем все возможные варианты состава аргументов функции, во втором цикле перебираем перестановки токенов по текущему варианту аргументов функции.
Надеюсь, данная статья будет интересна тем, кто вплотную занимается парсерами.
P.S. поддержка необязательных аргументов функций появятся на платформе ТОМ2 в следующей версии 2.a.4.3
Следите за обновлениями.
Чтобы подобрать к команде, введенной игроком, функцию с подходящим шаблоном, необходимо в цикле перебрать все возможные перестановки слов.
Функции в ТОМ2
Функции в ТОМ2 несколько специфичны — они не имеют имён, а описания аргументов служат шаблоном для подбора функции к введенной команде, или вызову в коде.
Пример описания функции:
Я не буду здесь глубоко вдаваться в работу функций, это отдельная большая тема.
Здесь для нас важно что функция, описанная выше, должна срабатывать на команды:
> осмотри мусор
> мусор осмотри
Пример описания функции:
action(осматривать#Пф, мусор#Вп){ ...code... }
Я не буду здесь глубоко вдаваться в работу функций, это отдельная большая тема.
Здесь для нас важно что функция, описанная выше, должна срабатывать на команды:
> осмотри мусор
> мусор осмотри
Перебор перестановок делается с помощью очень простого и старого алгоритма, открытого аж в 14 веке индийским математиком Пандитом Нарайаной.
Алгоритм Нарайаны
Описание и реализацию алгоритма практически на любом языке программирования можно легко нагуглить.
Вот мой вариант:
Здесь:
token_line — список токенов введенной команды, массив объектов типа token;
operator[](0) — первое слово в команде, operator[](1) — второе слов и т.д.
token_line::Pos — позиция первого слова в команде (для упрощения можно считать = 0);
token_line::FnLen — длина функции, к которой примеряется команда.
operator[](n).p — номер аргумента функции, с которым сопоставляется токен n;
Перед началом перебора индекс p всех токенов устанавливаются в начальную позицию 0,1,2...FnLen-1. Далее в цикле перебираются все варианты перестановок, каждый вариант проверяется на применимость к функции. Варианты, не прошедшие проверку, откидываются, прошедшие — обрабатываются далее.
Сама проверка довольно сложная и многоступенчатая, здесь мы её рассматривать не будем.
Вот мой вариант:
bool __fastcall token_line::NextComb(void)
{ //перебираем перестановки
for(int m=FnLen-2; m>=0; m--)
//найдем крайний правый m больший чем m+1
if(operator[](Pos+m).p < operator[](Pos+m+1).p)
{ //справа от m найдём наименьший k больший чем m
int k=m+1;
for(int i=k+1; i<FnLen; i++)
if( operator[](Pos+i).p > operator[](Pos+m).p &&
operator[](Pos+i).p < operator[](Pos+k).p ) k=i;
//переставляем m и k
int x=operator[](Pos+m).p;
operator[](Pos+m).p=operator[](Pos+k).p;
operator[](Pos+k).p=x;
//переворачиваем позиции справа от m
m++; k=FnLen-1;
while(m<k)
{ x=operator[](Pos+m).p;
operator[](Pos+m++).p=operator[](Pos+k).p;
operator[](Pos+k--).p=x;
}
return true;
}
return false; //перестановок больше нет
}
Здесь:
token_line — список токенов введенной команды, массив объектов типа token;
operator[](0) — первое слово в команде, operator[](1) — второе слов и т.д.
token_line::Pos — позиция первого слова в команде (для упрощения можно считать = 0);
token_line::FnLen — длина функции, к которой примеряется команда.
operator[](n).p — номер аргумента функции, с которым сопоставляется токен n;
Перед началом перебора индекс p всех токенов устанавливаются в начальную позицию 0,1,2...FnLen-1. Далее в цикле перебираются все варианты перестановок, каждый вариант проверяется на применимость к функции. Варианты, не прошедшие проверку, откидываются, прошедшие — обрабатываются далее.
Сама проверка довольно сложная и многоступенчатая, здесь мы её рассматривать не будем.
Всё это замечательно работает, пока не возникает необходимость в усложнении команд. Практически любая команда может иметь дополнительные обстоятельства, важные или не важные в зависимости от ситуации, сконструированной автором игры:
> возьми яблоко
> возьми яблоко со стола
> возьми яблоко левой рукой
Количество функций в этом случае растет по правилу комбинаторного взрыва, хотя делают они примерно одно и то же. Комбинаторный взрыв, это как раз то, от чего хотелось бы оградить и себя и всех авторов. Автор должен заниматься творческим трудом, а перебирать комбинации может и машина.
Все похожие варианты можно описать с помощью одной единственной функции, если в описании обозначить необязательные аргументы:
action(осматривать#Пф, мусор#Вп, [на], [пол#ПпМу]){ ...code... }
функция с таким описанием должна срабатывать на следующие команды:
> осмотри мусор
> осмотри мусор на полу
> на полу осмотри мусор
> осмотри на полу мусор
> мусор осмотри
> мусор осмотри на полу
> на полу мусор осмотри
> мусор на полу осмотри
Но это значит, что наш замечательный алгоритм перебора перестановок должен как-то справляться с аргументами, которые иногда есть, а иногда их нет. Да и длина функции при этом перестаёт быть константой.
Но вся прелесть алгоритма Нарайаны в том, что ему совершенно всё равно какую последовательность чисел перемешивать. С пропусками или без: 1-2-3 или 1-4-6, алгоритм в любом случае переберёт все необходимые нам перестановки.
То есть, для функции с необязательными аргументами задача сводится к формированию начальной расстановки.
Получается 2 вложенных цикла. В первом мы перебираем все возможные варианты состава аргументов функции, во втором цикле перебираем перестановки токенов по текущему варианту аргументов функции.
Код
Методы первого цикла:
Здесь:
fn_it — объект для подбора функций;
fn_it::BitMap — карта расстановки аргументов. Каждый бит соответствует аргументу с тем же номером;
fn_it::Fn — массив аргументов функции;
fn_it::Fn[n] — n-ый аргумент;
fn_it::Fn[i].Required — флаг обязательности аргумента.
Методы второго цикла:
Здесь:
token_line — список токенов введенной команды, массив объектов типа token;
token_line::Pos — позиция первого слова в команде (для упрощения можно считать = 0);
token_line::FnLen — длина функции, к которой примеряется команда.
Token.p — номер аргумента функции, с которым сопоставляется токен;
Метод token_line::NextComb(void) остаётся без изменений, см. код выше.
Ну и сами циклы в упрощенном виде выглядят так:
Здесь:
Fns — список функций, массив объектов класса fn_it.
void __fastcall fn_it::FirstComb(void)
{ //подготовим карту аргументов
BitMap = 1 << Fn.GetCount();
BitMap--;
}
bool __fastcall fn_it::NextComb(void)
{ //получим следующий вариант расстановки аргументов
unsigned int Flag = 1 << (Fn.GetCount()-1);
for(int i=Fn.GetCount()-1; i>=0; i--)
{ if(!Fn[i].Required)
{ if(BitMap&Flag)
{ BitMap^=Flag;
return true;
}
else BitMap|=Flag;
}
Flag>>=1;
}
return false;
}
Здесь:
fn_it — объект для подбора функций;
fn_it::BitMap — карта расстановки аргументов. Каждый бит соответствует аргументу с тем же номером;
fn_it::Fn — массив аргументов функции;
fn_it::Fn[n] — n-ый аргумент;
fn_it::Fn[i].Required — флаг обязательности аргумента.
Методы второго цикла:
bool __fastcall token_line::FirstComb(unsigned int BitMap)
{ //BitMap - карта расстановки аргументов по позициям
//расставляем токены на исходную позицию
int p=-1, t=-1;
for(; BitMap; BitMap>>=1) //цикл по карте
{ p++;
if(!(BitMap&1)) continue; //пропускаем позицию
t++;
if(Pos+t>=GetCount()) return false; //вышли за пределы выражения
token&Token=operator[](Pos+t); //текущий токен
if(Token.GetCount()==0) return false; //нет значений
Token.p = p; //назначаем токену начальную позицию в функции
}
FnLen = t+1; //запомним длину обрабатываемой функции
return true;
}
Здесь:
token_line — список токенов введенной команды, массив объектов типа token;
token_line::Pos — позиция первого слова в команде (для упрощения можно считать = 0);
token_line::FnLen — длина функции, к которой примеряется команда.
Token.p — номер аргумента функции, с которым сопоставляется токен;
Метод token_line::NextComb(void) остаётся без изменений, см. код выше.
Ну и сами циклы в упрощенном виде выглядят так:
for(int f=Fns.GetCount()-1; f>=0; f--) //цикл по списку функций
{
Fns[f].FirstComb();
do //цикл по аргументам
{
if(Tokens.FirstComb(Fns[f].BitMap)) do //цикл по перестановкам
{
... проверка ....
... обработка ....
}while(Tokens.NextComb()); //цикл по перестановкам
}while(Fns[f].NextComb()); //цикл по аргументам
... отбраковка функций ...
} //цикл по списку функций
Здесь:
Fns — список функций, массив объектов класса fn_it.
Надеюсь, данная статья будет интересна тем, кто вплотную занимается парсерами.
P.S. поддержка необязательных аргументов функций появятся на платформе ТОМ2 в следующей версии 2.a.4.3
Следите за обновлениями.
Возникала ли необходимость отслеживать порядок слов в некоторых случаях? Типа перемешиваем все, но слово B всегда должно быть после слова A?
Порядок остальных значений можно при необходимости проверить внутри самой функции. Для каждого аргумента в функцию передаётся его номер в исходной команде. Бывают случаи, когда от порядка зависит не только смысл, но и тип всего выражения.
«красная роза» — словосочетание из всех роз указывающее на красную. Фильтр объектов по признаку.
«роза красная» — утверждение. Выполнение приводит к присвоению объекту нового признака.
Ну к примеру. 1 и 2 — приоритеты. 2 всегда после 1. Но тут конечно вопрос что проще/лучше.