Pull to refresh

Найдется даже икс

Reading time3 min
Views1.1K
Nigma.ru добавила в свою копилку новую фичу для пользователей. Теперь прямо через строку поиска можно решать различные математические задачи, например, x2-3x+2=0, sin2 x + cos2 x, 2 ч * 30 м/мин = х, системы уравнений типа 2x-y=4, 3y+x=9, x2+y=1, x*y=0 и т.п. (подробный список тут). Сервис рассчитан на школьников 6-10 класса.

Подробнее о системе можно узнать, прочитав документацию и новость на нашем сайте.

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

Как работает наш алгоритм?

Вначале мы распознаем математические запросы среди всего потока запросов. При выполнении этой задачи мы столкнулись с массой проблем. Так как запросы могут быть очень разные, следовательно для ее решения требуются множество сложных эвристик. Кроме того, требуется разбор выражений на естественном языке, так как пользовательский ввод может быть не только в виде формул, но и на естественном языке, то есть в неформализуемом виде. При помощи набора эвристичиских правил (список которых был составлен на основе анализа ввода в поисковую строку реальных школьников) мы преобразовываем текстовые запросы в формальное описание задачи со строгим синтаксисисом. В силу неоднозначности преобразования из нестрого синтаксиса в строгий приходится рассматривать несколько вариантов записи задачи, а далее необходимо отсеять наименее вероятные варианты разбора, так как их количество может расти экспоненциально относительно сложности введенного выражения, и, соответственно, решение такого количества задач займет слишком большое время, а пользователю будет слишком сложно искать решение среди сотни вариантов. Решение задач ведется в символьном виде, когда это возможно, что позволяет использовать систему для получения строгого решения задачи, что полезно в школьных задачах, в различных доказательствах и гораздо более важно в учебных целях, чем численное решение. Численное решение так же предлагается как один из вариантов, или как основной вариант, если задача подразумевает ответ в такой форме, как, например, конвертация величин или валют.

В ходе работы мы столкнулись с проблемой, что для многих запросов крайне трудно определить их математичность, особенно когда это запросы, содержащие в себе различные модели техники (в которых очень часто содержатся цифры и математические знаки), а так же различные фразы в которых много математических терминов. К сожалению, в общем случае задача разделения подобных запросов алгоритмически трудно разрешима, особенно если учесть то, что среди математических запросов могут быть и запросы с ошибками. Тем не менее, достаточно длительный анализ пользовательских запросов и ввода школьников позволил снизить уровень ошибки первого рода при определении математичности запроса, при этом уровень ошибок второго рода практически остался близок к нулю (в данном случае ошибка первого рода менее важна).

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

Система находится в состоянии альфа-тестирования, т.е. нам известны ряд ограничений и ошибок системы, над исправлением которых мы работаем. С удовольствием выслушаем ваши замечания и мнение относительно данной системы. Также хотим отметить, что эта система — лишь один из наших проектов по увеличению количества интеллекта Нигма.ру и мы с радостью примем в наш коллектив программистов, которые хотят разрабатывать новые интеллектуальные поисковые технологии.
Tags:
Hubs:
Total votes 99: ↑80 and ↓19+61
Comments104

Articles