© Константин Дзреев (Colonel), г. Ростов-на-Дону
Последние два года ZX РЕВЮ все больше и больше места уделяет играм жанра ADVENTURE. Я сам являюсь большим поклонником этого жанра благодаря циклу статей "ADVENTURE GAMES" и "ADVENTURE PROJECT".
В ZX РЕВЮ 93/9-10, 11-12 в рубрике "Сделай сам" появилась статья "Adventure Building System (ABS). ABS является довольно неплохим инструментом для написания простеньких игр, однако алгоритм анализа предложения оставляет желать лучшего. Решив попробовать свои силы в написании аdventure - игрушек, я столкнулся со следующей проблемой, которую хотелось бы вынести на обсуждение.
Каким образом корректно проанализировать введенную пользователем строку, без ошибок выделить в ней все части речи (и предложения) и правильно прореагировать на команду?
Если Вы пишите программу на английском языке, то проблем у Вас почти не будет: нет никаких окончаний, приставок и всего остального, что присутствует в нашем родном русском. У них, если в словаре программы есть слово "APPLE", то, как ни пиши "TAKE APPLE" или "THROW APPLE TO TREE", в любом случае "APPLE" останется "APPLE'om". В нашем родном языке все гораздо сложнее. Пусть программа понимает слово "КАЛОША" (такой у нее словарь). Рассмотрим следующий пример: "ВЗЯТЬ КАЛОШУ" и "РАСКОПАТЬ КАЛОШЕЙ ПЕСОК".
Нетрудно заметить, что исходное слово из словаря отличается окончанием от приведенных в примерах.
Достаточно распространенной в англоязычных играх является идентификация слова по первым четырем (а иногда всего по трем) буквам (кстати, "ABS" работает по аналогичному принципу). В русском языке, когда только приставка в слове может занимать четыре буквы (пример - приставка "ПЕРЕ-": "ПЕРЕКИНУТЬ"), данный метод совершенно неприменим. Если производить идентификацию, минимум, по первым семи-восьми символам, то, что делать с короткими словами? Например, в выражении "КОПАТЬ ЯМУ" слово "ЯМУ" мы будем идентифицировать по всем трем буквам, а в словаре у нас слово "ЯМА", т. е. совпадения не произойдет. Альтернативным вариантом является хранение в словаре всех коротких слов во всех падежах. Но в этом случае довольно жестко встает вопрос о занимаемой словарем памяти. Вы можете отказаться ломать себе голову над этой проблемой, и перед игрой просто инструктируете пользователя о том, что программа немного не в ладах с русским языком, и все существительные нужно вводить только в именительном падеже. Приведенный выше пример будет звучать так: "ВЗЯТЬ КАЛОША" и "РАСКОПАТЬ КАЛОША ПЕСОК".
Но не думаю, что играющему в Вашу игрушку будет интересно коверкать русский язык.
Более удачным является вариант, когда в словарь программы записывается только корень слова. Наш пример в этом случае работает отлично, но и здесь не все так гладко. Отличным примером может послужить корень "ХОД": в этом случае программа одинаково прореагирует на слова "ХОД", "ХОДОК", "ХОДИТЬ", "ХОДКА" и т. п.
Но предположим, что с идентификацией слова нет никаких проблем. Тогда мы перейдем к рассмотрению целого ряда новых. Порядок слов в предложении в английском языке достаточно жестко ограничен: подлежащее, сказуемое, определение (если оно есть), дополнение. Как ни крути, по-другому не позволяет грамматика: в случае adventure игр мы вводим команду, поэтому подлежащее может опускаться: "TAKE RED APPLE" или "DIG SAND WITH STEEL KNIFE". В русском языке - полный хаос: и "АККУРАТНО ПОСТАВИТЬ КОРОВУ В СТОЙЛО", и "В СТОЙЛО АККУРАТНО ПОСТАВИТЬ КОРОВУ", и "КОРОВУ АККУРАТНО ПОСТАВИТЬ В СТОЙЛО", - все эти фразы имеют совершенно одинаковый смысл.
Достаточно легко уйти от этой проблемы, переложив ее на пользователя, т. е. подать ему очередную инструкцию, где будет написано, что ко всем прочим ограничениям программа понимает только определенно построенные грамматические конструкции, а именно: глагол + (прилагательное) + существительное + (предлог) + (прилагательное) + (существительное). Части речи, взятые в скобки, не обязательно должны присутствовать в предложении.
Пример: "ВЗЯТЬ ПАЛКУ" или "УДАРИТЬ РЕЗИНОВУЮ УТКУ ПАЛКОЙ", но "ПАЛКОЙ УДАРИТЬ РЕЗИНОВУЮ УТКУ" программа уже не поймет, так как порядок слов в предложении не совпадает с шаблонным.
В последнем примере необходимо отметить разницу между существительными "ПАЛКА" и "УТКА". Мы объектом "ПАЛКА" посредством глагола "УДАРИТЬ" воздействуем на объект "УТКА", но не наоборот.
Далее будем называть их соответственно ПЕРВОЕ и ВТОРОЕ существительное. Обычно в программах автоматизированного создания adventure игр (пример: Graphic Adventure Greator, Quill), проверка на введенное предложение реализуется следующим образом.
Пусть глагол "УДАРИТЬ" имеет в словаре номер 8, а существительные "УТКА" и "ПАЛКА", соответственно, номера 11 и 23. Тогда анализ строки может выглядеть как-то так:
If verb(8) AND noun(11) AND noun(23) THEN DO ., что в переводе на русский язык звучит как:
Если глагол (8) И сущ (11) И сущ (23) ТО СДЕЛАТЬ . что-то умное.
Даже невооруженным глазом видно, что два абсолютно разных по смыслу предложения ("УДАРИТЬ ПАЛКОЙ УТКУ" и "УДАРИТЬ ПАЛКУ УТКОЙ") будут восприняты совершенно одинаково. Опять же, объемная инструкция об ограничениях программы наверняка порадует пользователя, но не слишком ли много инструкций?
Мне хотелось бы предложить некоторые соображения, при помощи которых с достаточно большой долей вероятности можно разобраться с командами типа: (наречие) + глагол + (прилагательное) + существительное + ("прямая речь"), причем порядок слов в предложении жестко не ограничивается.
Пример: "ОСТОРЖНО ПОСАДИТЬ ОДНОГЛАЗУЮ МУХУ НА КАМЕННУЮ СТАТУЮ", "ГРОМКО ЗАКРИЧАТЬ ПОМОГИТЕ" и т. д.
Некоторые ограничения: во-первых, прямая речь должна стоять в конце предложения (ограничение легко снять), во вторых, глагол должен стоять в неопределенной форме (но это общепринято), в третьих, все слова придется вводить полностью, за исключением специально оговоренных сокращений. Некоторые достоинства:
Во-первых, порядок слов в предложении почти произволен. Программа отлично разберется и с предложением: "НА КАМЕННУЮ СТАТУЮ ОСТОРОЖНО ПОСАДИТЬ ОДНОГЛАЗУЮ МУХУ".
Во-вторых, если в предложении есть предлог, то со 100% вероятностью можно будет сказать, какое из двух введенных существительных ПЕРВОЕ, а какое - ВТОРОЕ. Если предлога нет, то вероятность определения будет где-то в пределах 97 %.
В-третьих, если даже введенное слово не будет найдено в словаре, то программа определит часть речи, к которой относится неизвестное слово, и Вы сможете вывести сообщение типа: "Не знаю прилагательного "ЦИАНОВЫЙ" или "Впервые вижу слово ЕЖ".
Алгоритм достаточно прост, и, вместе с тем, достаточно надежен. Он анализирует окончания слов. Глагол в неопределенной форме может иметь следующие окончания: -ТЬ, -ТИ и -СЯ.
Наречие всегда имеет окончание -О (что возможно и для существительных, и для прилагательных). Прилагательное может иметь одно из следующих окончаний: -ЫЙ, -АЯ, -ОЕ, -УЮ, -ЫЕ, -ЫМ, -ИЙ, -ЯЯ, -ЮЮ, -ОЙ, -ЕМУ, -ОМУ, -ОГО и т. п. (другие вряд ли будут использоваться). Особый случай окончание -ОЙ. Его могут иметь как прилагательные, так и существительные: "НАСТУПИТЬ НОГОЙ НА ГОЛУБОЙ ДИСК". Существительные вообще могут иметь любое окончание, а отличительной особенностью предлогов является их малая длина - до 5 символов, но это не редкость и для остальных частей речи.
Шаг первый - создание пяти словарей.
С Л О В А Р И :
|
Глаголы |
Наречия |
Предлоги |
Прилагательные |
Существительные |
|
1 взять |
1 быстро |
1 в |
1 красн(ый) |
1 куриц(а) |
|
1 подобрать |
2 медленно |
2 на |
2 прекрасн(ый) |
2 песок |
|
2 подняться |
3 высоко |
3 над |
3 желт(ый) |
3 калош(а) |
|
3 идти |
4 аккуратно |
4 через |
4 голуб(ой) |
4 ветк(а) |
|
4 положить |
4 тщательно |
5 по |
5 син(ий) |
4 веточк(а) |
|
4 поместить |
4 осторожно |
6 под |
6 красив(ый) |
5 ног(а) |
|
5 посмотреться |
5 низко |
6 к |
7 некрасив(ый) |
6 оград(а) |
|
6 выбросить |
6 точно |
7 до |
8 стар(ый) |
6 загородк(а) |
|
6 выкинуть |
7 страшно |
8 от |
9 полосат(ый) |
7 клоп |
и т.д. и т.д. и т.д. и т.д. и т.д.
Слова, записанные в одном словаре под одинаковыми номерами являются синонимами. У прилагательных и существительных опускаем окончание, то есть, оставляем приставку, корень и суффикс.
Шаг второй - написание программы, корректно анализирующей введенную пользователем строку, и также корректно ее исполняющей. На этом шаге остановимся.
Я не буду очень подробно приводить алгоритм, а только кратко опишу его работу. Подробно расписанный на языке высокого уровня алгоритм, достаточно велик по объему.
Суть алгоритма заключается в следующем. Пусть пользователь ввел какую-либо символьную строку. Для начала надо отделить в ней команду от прямой речи (многие наверняка знают, что это такое).
Делается это следующим образом: находим в этой строке символ-разделитель прямой речи и команды - обычно это одинарная или двойная кавычка. Все что слева от кавычки - это команда, все что справа - это прямая речь.
Например: "СКАЗАТЬ ДЖИНУ ЛЕЗЬ В БУТЫЛКУ". Командой является "СКАЗАТЬ ДЖИНУ", а прямой речью "'ЛЕЗЬ В БУТЫЛКУ'". Будем анализировать команду.
Во-первых, в строке необходимо найти глагол. Поиск производим следующим образом: ищем слово с окончанием : -ТЬ, -ТИ, -СЯ. Если слово найдено, то сравниваем его со словами из словаря глаголов. Если такого слова программа не знает, то ищем в предложении другое слово с таким окончанием. Это делается из-за того, что вышеперечисленные окончания могут иметь не только глаголы, но и существительные: "СХВАТИТЬ ГУСЯ ЗА ХВОСТ". Если предложение просмотрено полностью, а известных программе слов нет, то самое время высветить сообщение об ошибке: "Не вижу здесь глагола!"
Сравнение слов необходимо производить следующим образом: на слово ИЗ СЛОВАРЯ накладывать слово ИЗ ПРЕДЛОЖЕНИЯ, но не наоборот. Пусть в словаре есть слово "ПОСМОТРЕТЬСЯ". Тогда, накладывая на него любое из слов "ОСМОТРЕТЬСЯ", "ОСМОТРЕТЬ", "ПОСМОТРЕТЬ", мы получим совпадение, то есть не надо держать в словаре эти три слова, как синонимы, а достаточно только одного. Если глагол найден, то необходимо убрать его из предложения, чтобы он не мешал дальнейшему анализу. Далее будем изымать из предложения каждое из успешно идентифицированных слов.
Далее, в оставшемся предложении попытаемся отыскать наречие. Как известно, наречие всегда оканчивается на "-О", а по сему, проделываем для него все вышесказанное для глагола, но только поиск ведем в словаре наречий, и, в случае, если наречия не окажется или оно не будет опознано (т. е. слово с окончанием "-О" есть, но программа не знает его, как наречие - может быть это слово "ЯБЛОКО"), сообщения об ошибке не выдаем.
Затем найдем предлог. Предлог ищется по принципу: если длина слова меньше шести букв, то возможно это слово и есть предлог.
Как только короткое слово найдено, оно тут же пропускается через словарь предлогов, и, если такого предлога в словаре нет, то искать и анализировать надо следующее короткое слово. Отсутствие предлога не смертельно для предложения. Поэтому никаких сообщений о несовпадении или об отсутствии этой жизненно важной части предложения нет.
Продолжим и будем искать прилагательное. Прилагательных в предложении, как и существительных, может быть два, а может не быть вообще. Кроме того, после любого прилагательного обязательно должно стоять существительное, к которому это прилагательное относится ("КИНУТЬ В ПРОЗРАЧНУЮ ВОДУ БЕДНУЮ МУ-МУ"). Прилагательные распознаются по своему окончанию : -ЫЙ, -АЯ, -ОЕ, -УЮ, -ЫЕ, -ЫМ, -ИЙ, -ЯЯ, -ЮЮ, -ОЙ, -ОМУ, -ОГО. Пусть программа обнаружила слово с любым из приведенных окончаний. Тогда она обрезает это окончание и сравнивает полученное слово со словарем прилагательных. Если слово не распознано и окончание его на "-ОЙ" (такое окончание может иметь существительное), то выдать сообщение об ошибке : "Впервые вижу прилагательное БЕДНУЮ". В случае отсутствия прилагательного в предложении - ошибки нет.
И, наконец, существительные. Их идентификация не является особо сложной задачей. Проблема может возникнуть при анализе того, какое из них ПЕРВОЕ, а какое ВТОРОЕ. Если в предложении был предлог, то определенно можно сказать, что стоящее после предлога существительное - ВТОРОЕ, а оставшееся - наверняка ПЕРВОЕ. Но, ЕСЛИ ПРЕДЛОГА НЕТ, то возникают проблемы. Рассмотрим несколько примеров. "РАСКОПАТЬ ПЕСОК КАЛОШЕЙ", "УДАРИТЬ ВЕТКОЙ КУРИЦУ", "ЗАДАВИТЬ КЛОПА НОГОЙ".
А теперь сравните все существительные с их аналогами в словаре (см. выше). Не заметили? ПЕРВЫЕ существительные имеют окончания из двух букв, ВТОРЫЕ - либо вообще не имеют, либо окончание состоит всего из одной буквы. Таким образом, наложив слово из словаря на слово из предложения и проанализировав оставшееся окончание (по числу символов), можно определенно сказать кто чем на кого действует. Если в предложении всего одно существительное, то вышеописанных проблем вообще не возникает.
Анализ прямой речи можно свести к анализу простой команды, но необходимо учитывать, что глагол, скорее всего, будет стоять не в неопределенной форме.
Более "умные" алгоритмы при идентификации слова распознают в нем и приставку, и корень, и суффикс, и окончание. Но в этом случае процедура анализа предложения может занимать десяток-другой килобайт, что в случае Sinclair - совместимых компьютеров абсолютно неприемлемо (разве что у Вас 256-й Scorpion или ATM-TURBO 512-й). Но такой сложный алгоритм просто не нужен, ведь все разнообразие диалоговых ситуаций в хорошей ADVENTURE игре можно реализовать и при помощи более простых алгоритмов.
