Эсперимент

Два дня экспериментирую с грамматикой связей (взял здесь http://www.codeplex.com/sharpnlp). В принципе, встроить ее в мою программу можно легко. Однако есть некоторые проблемы. В комплекте с библиотекой идут .nbin файлы в которых и содержится описание грамматики. Если использовать их - то при парсинге эти файлы полностью грузятся в память - это порядка 250 Мб. Есть альтернативный вариант - использовать sqlite. В этом случае - используется порядка 30 Мб памяти, но! скорость резко падает - я так и не дождался когда будет обработан текстовый пример. Кроме того, примерно в 3 раза больше места требуется для файлов моделей. Попробую ее полностью прикрутить к переводчику (пока что парсер я еще не подключал) - посмотрю что получится на выходе...

Ссылки - 2

Гугл рулит! (Конечно не сам гугл, а его codesearch, но все-таки...) Предельно глупыми запросами было найдено столько всего интересного...

• Генератор парсеров
• Link Grammar для английского языка
• • а вот тут ее порт на .Net Framework + еще кое-что
• Oleander Stemming Library
• Ну и еще один стеммер можно вытащить отсюда, также на C#

Модель предложения в переводчике

Вроде бы про слова более-менее рассказал, теперь очередь за предложениями. Итак, предложения (строки) бывают двух видов TMStr и TRStr.

• TMStr - описание английского предложения
• TRStr - результат перевода на русский

TMStr является одним из базовых классов. Умеет:

1. Добавлять/удалять связи между словами
2. Добавлять/удалять слова (с учетом/коррекцией связей между словами)
3. Сегментировать часть предложения

Сначала поговорим про сегментирование и вообще о том, что такое сегменты в системе.

Сегмент - это группа слов, по отношению к предложению представляемая как одно слово. Для чего это нужно?

Возьмем, например, такое предложение: I am looking at the big, fast river.

В нем можно выделить следующие участки: I am looking [at [the [big, [fast river]]]]. Вот именно по выделенным участкам и будет произведено сегментирование (свертка). В результате предложение выродится в: I am looking river (естественно, river приобретет ряд дополнительных параметров(свойств), которые будут установлены в процессе свертки предложения).

Для чего это нужно? Для упрощения алгоритма синтаксического анализа (по-крайней мере - моей реализации этого алгоритма). После проведения свертки для определения подлежащего/сказуемого нам достаточно проверить простое правило вида: местоимение/существительное+глагол_ing+уловия_для_дополнений (ну, на самом деле проверяемые правила несколько сложнее, но принцип именно такой). Таким образом мы преобразовали сложное предложение в более простое, тем самым упростив синтаксические правила, которые необходимо проверять на предложениях. Более того - теперь для описания синтаксической структуры предложений вида Present Continuous достаточно всего 3-х правил (обычная форма, вопросительная форма, пассив), а не бесконечного количества :)

При создании сегмента (свертке) указывается какое их слов в будущем сегменте является главным. Снаружи сегмента будет видно именно это слово, со всеми его параметрами.

Допускается (даже желательна) вложенность сегментов (см. пример выше).

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

Класс TRStr не умеет работать с сегментами - только разворачивать по данным из TMStr, кроме того производится корректировка ссылок между словами. Именно этот класс содержит результаты перевода, именно по нему генерируется выходной текст для пользователя.

Ну и напоследок - немного о том как реализован TMStr.

1. список всех слов в предложении
2. список индексов
3. список сегментов

Все слова предложения хранятся в одном списке, причем положение слова в предложении и в списке могут быть совершенно разными.

Реальная последовательность слов хранится в списке индексов (каждый индекс указывает на слово в списке слов).

Список сегментов - содержит только сегменты самого верхнего уровня.

Сегменты обладают примерно такой же структурой что и TMStr, т.е. также содержат индексы слов, список слов (это ссылка на основной список слов в TMStr) и список сегментов.

Удалять/добавлять слова можно только в TMStr, в сегменты - нельзя (ну если только вручную...).

При создании сегмента в его список индексов переносятся индексы из основного списка индексов предложения. Сами слова никуда не перемещаются.

Связи между словами бывают четырех видов:

1. между словами в предложении
2. связь ведет от слова к слову-сегменту
3. связь ведет от слова-сегмента к слову
4. связь ведет от слова-сегмента к слову-сегменту

Соответственно, при каких-либо модификациях предложения связи корректируются.

Уф... Ну вроде бы пока - все.

Зависимости

Потратив четыре часа времени таки построил зависимость кол-ва вариантов перевода предложений (Y) от кол-ва слов в предложении (X). (Excel 2007 - это что-то! :) Зато нашел много нового и интересного... )

А вот еще - относительный разброс количества вариантов перевода в зависимости от кол-ва слов в предложении (т.е. величина характеризует, насколько разное количество вариантов получается для предложений с одинаковым количеством слов.):

Данные сняты со стандартного текста для тестирования. Размер - 29 кб, 395 предложений.

Ссылки на интересное про алгоритмы обработки текстов

В этом посте буду публиковать найденные интересные ссылки касающиеся вопросов автоматической обработки текста (все что касается перевода, поиска и т.п.) Интересные блоги:

• Text Mining Explained [Rus]
• community.livejournal.com/ru_ir [Rus]

Статьи про семантические сети:

• OWL, язык веб-онтологий. Руководство [Rus]

Поиск и все с ним связанное:

• Searchengines.ru

Back to basics

Посмотрел предыдущие посты и понял, что про реализацию переводчика я практически ничего и не написал. Исправляюсь. Не секрет, что любой компьютерный переводчик - ошибается. Иногда - сильно. (Почему про это забыли ПРОМТовцы - я не имею ни малейшего представления). Поэтому система изначально спроектирована под работу с несколькими вариантами перевода, т.е.:

• каждое английское слово имеет несколько вариантов перевода
• каждое английское предложение также имеет несколько вариантов перевода

В общем виде, реализованный мной алгоритм перевода выглядит так:

1. Получение текста для перевода.
2. Лексический анализ
3. Преобразование разбитого на элементы текста во внутреннее представление (TextParser)
4. Для каждого предложения текста производится поиск всех вариантов перевода для каждого слова предложения
5. Выполняется первичный синтаксический анализ. Его особенность в том, что применяемые правила должны быть 100% истинными (без исключений/неясностей). Например, для словосочетания "his hand" можно сразу отбросить варианты перевода-глаголы для слова hand.
6. Генерируются варианты предложения. Их особенность в том, что у каждого слова в предложении должны быть переводы только одной части речи (соотв. в другом варианте предложения - у этого слова будут переводы другой части речи)
7. Для каждого варианта предложения опять запускаем синтаксический анализ
8. Формируем русские предложения по английским
9. Склоняем все слова в каждом варианте русских предложений
10. Формируем текст для пользователя

Ну, до кучи, там еще меняются приоритеты некоторых вариантов перевода слова (как захочет пользователь) и предложений, ну и некоторые другие действия.

Конечно, у многих сразу возникает вопрос - как много вариантов перевода предложения будет генерироваться и насколько сильно такой подход требователен к памяти/процессору?

Отвечаю: на текущий момент, при 1500 слов в словаре, в среднем по 0,77 перевода на слово более 16 вариантов перевода предложения не было получено ни разу. При этом процесс перевода тестового фрагмента (29 кб текст, кусок книжки) длится на Athlon 3000+ порядка 6 секунд. Этот же текст в ПРОМТе переводится не менее 10 мин. (Ну понятно, что когда будет реализован хоть какой-то алгоритм семантического анализа скоростные показатели изменятся, но пока что...)

Разрабатываемый сейчас алгоритм поиска фраз будет находиться между 4-ым и 5-ым пунктами.

Фразеологический анализ-2

А теперь перейдем к первым проблемам. Первоначально я хотел сделать как у всех (да собственно, так и сделал) - английская фраза является отдельной словарной статьей. Не самый лучший вариант. Почему? Потому что это резко усложняет алгоритм поиска фраз:

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

(ну и попутно есть некторые проблемы связанные с конкретной реализацией класса TMStr. Вообщем-то это не настолько существенно, но еще усложняет алгоритм)

Стоит ли говорить о том, что такой подход - медленнен? Поиск по базе с выбором всех вариантов, проверка всех слов на совпадение с выбранными первыми словами фраз и т.п. - циклы, циклы, циклы...

Буквально на днях реализовал другую мысль - перевод английской фразы задается у первого слова фразы, но к этому варианту перевода добавляются дополнительные условия.

Рассмотрим , например, предлог because of: это производная форма от слова because с "пристегнутым" к нему предлогом of. Соответственно, перевод данной фразы задаем у слова because, но дополнительно указываем, что после этого слова должен стоять предлог of.

Чем такой лучше? Если учесть то, как работает система в целом - он идеально в нее вписывается: морфологический анализатор определяется исходные формы слов фразы, после чего производится поиск всех возможных вариантов перевода слов. Соответственно, перевод фразы также будет добавлен к слову because.

И вот тут в дело вступает алгоритм поиска фраз, который выбирает те слова, у которых есть варианты перевода - английские фразы (обращаю внимание - именно английские, т.к. есть еще и русские фразы - переводы английских слов и фраз) и проверяет условия фразы. При совпадении условий выполняет заданные действия.

В принципе, это все. Однако, если бы все было настолько просто - никаких вопросов бы и не возникло.

Проблемы:

1. фразы могу быть написаны по разному: shut up, shut the hell up и т.п.
2. разные формы основных и "пристегнутых" слов дают разные фразы: going to и go to - это разные фразы (ну... в большинстве случаев, просто пример получше как-то не придумывается).
3. думаю стоит упомянуть, что во фразе могут быть слова не в исходной форме, при этом эти слова могут отсутствовать в словаре или же там может быть задан перевод не той части речи, что использован во фразе -> алгоритм морфологического анализа на этих словах даст неверный результат, что не позволит обнаружить фразу
4. для некоторых фраз существуют слова-модификаторы, не являющиеся частью фразы, но прямо влияющие на ее перевод (пример был раньше: going to do и going to)

Возможно еще что-то забыл, когда вспомню - допишу.

Ну с п.3 я сделать ничего не могу по-определению.

п.1. Можно задать специальный вид слова фразы (регулярное выражение?), который будет позволять задавать условия вида shut smth up. Реализуемо, вообщем-то. Конечно, хотелось бы чего-нибудь попроще...

п.2. Ввести в параметры перевода основного (первого) слова фразы отдельное поле для параметров, которыми должно обладать английское слово в предложении, чтобы этот вариант перевода мог быть добавлен к слову.

п.4. Ну, опять-таки можно задать отдельный список (в какой форме?) этих слов-модификаторов... Надо думать...

О! Кстати, вокруг всего этого еще и неопределенность с границами фраз есть например: so beautiful as far as i know...

Есть идеи? Замечания?

Фразеологический анализ

Ну, все что было раньше - это так, вступление. А теперь, наверное, самое интересное - алгоритм находится в разработке в данный момент, соответственно, есть возможность приложить свою руку к его созданию... Цель: получив на входе предложение выделить в нем все фразы и подготовить предложение к дальнейшей обработке. Примечание: здесь и далее, если это не оговорено особо, под предложением понимается его реализация в системе TMStr или TRStr (по умолчанию - TMStr), под словом - TMWord. Начнем, пожалуй с выработки теории. Я предполагаю, что фраза (как группа слов) характеризуется двумя независимыми параметрами: 1.

• единой, как, например, going to
• разрывной, как, например, so ... as

2.

• постоянной, т.е. группа слов будет переводиться строго определенным образом вне зависимости от переводов отдельных слов группы. Пример - shut up.
• непостоянной, т.е. группа слов может восприниматься и как единое целое и как каждое слово, образующее группу, поотдельности.

Кроме того, следует пожалуй учесть, что для некоторых постоянных/непостоянных фраз существуют слова-модификаторы, которые меняют вторую характеристику фразы на противоположное значение. Пример:

1. i was going to do smth
2. i was going to smth

В первом случае наличие глагола после to полностью меняет значение фразы going to.

P.S.: безусловно, все вышеизложенное - спорно и не факт что близко к реальности... Но в любом случае - пока что чего-то более умного мне в голову не пришло

Морфологический анализ

Ну этот алгоритм я думаю для большинства сложности не составит... Реализация проста как кирпич:

Берем слово, ищем его в базе. Если нашли - добавляем к слову все варианты перевода которые есть в базе. Если не нашли, то возможны 3 варианта:

1. Слово написано не в исходном виде.
2. Слово отсутствует в словаре.
3. Слово - имя собственное.

Подробнее:

1. по правилам английского языка (см. школьный учебник) изменяем окончание слова так, чтобы получить исходную форму слова. Пытаемся найти слово в базе. Если не нашли - см п.2.
2. добавляем как перевод само слово (дополнительно, мой алгоритм еще по окончанию делает предположение о возможной части речи слова, но это уже не главное).
3. по определенным причинам несловарные имена собственные (имена, фамилии) вынесены в отдельную базу - это позволяет загружать/сохранять их вместе с текстом

В принципе, это все :)

P.S.: вот хоть убейте, я не могу понять почему ПРОМТовцы уже лет 20 не могут научить переводчик самостоятельно определять имена собственные в тексте. Проблема решается за 2 минуты (я - решил :) ).

Лексический анализ

С вводной частью пока что закончили... Перейдем к описанию отдельных этапов перевода. Первым у нас будет лексический анализ. Основные цели лексического анализатора в разрабатываемой системе это:

• выделение слов и знаков препинания в тексте
• определение и пометка границ предложений и абзацев

Первоначально алгоритм был довольно примитивным: более-менне корректно помечались концы предложений, а потом перед каждым знаком препинания ставился пробел, двойные пробелы удалялись, а получившийся текст нарезался по пробелам. Естественно, что долго так жить было нельзя :) Поэтому родился тот ужас что есть сейчас. Встречаем:

- текст режется на отдельные элементы, т.е. слова (числа воспринимаются как слова) и знаки препинания.

- на выходе получаем массив элементов текста. Для каждого элемента расставляются следующие свойства:

• кол-во пробелов до начала элемента (если элемент - не первый в предложении, то оно всегда 0)
• кол-во пробелов после элемента
• маркер конца предложения
• маркер конца абзаца

- после чего сложные знаки препинания склеиваются, т.е. "..." будет восприниматься как один элемент, а не как 3 разных.

- помимо этого, лексический анализатор активно взаимодействует со словарем для того, чтобы корректно обрабатывать различные сокращения (например "Mr." и т.п.)

По окончании работы алгоритма получаем массив промаркированных элементов текста, который и отдаем TTextParser на растерзание.

Основы-2

Продолжим :) Ранее я уже упоминал элементы алгоритмя перевода. На всякий случай еще раз:

1. лексический анализ
2. морфологический анализ
3. фразеологический анализ
4. синтаксический анализ
5. семантический анализ

Сразу хочу сообщить - я не лингвист. Я простой программист :) Поэтому мои подходы к решению лингвистических задач несколько хм... отличаются от общепринятых. Прошу сильно не бить :)

Я решал проблему перевода по самому простому пути. А именно - на каждый этап перевода был сделан отдельный алгоритм. Прежде чем переходить к самим алгоритмам я думаю стоит написать что именно каждый из них должен делать.

1. лексический анализатор - получает на входе текст и выделяет в нем слова, предложения, и абзацы.
2. морфологический анализатор - получает на входе слова и определяет их исходную форму. В моей версии алгоритма перевода - на этом этапе еще и определяются все переводы слов.
3. фразеологический анализатор - получает на входе слова и принимает решение об объединении некоторых из них в одно слово.
4. синтаксический анализатор - получает на входе предложения (массив слов) и определяет отношения между словами, корректирует характеристики и части речи слов.
5. семантический анализатор - отсутствует на данный момент :(

Наверное теперь самое время определиться - что же такое слово/предложение/текст?

Слово описывается специальным классом TMWord и содержит следующие основные элементы:

• оригинальная форма (то, как слово было написано в тексте)
• исходная форма (то, как слово записано в словаре)
• части речи слова
• параметры слова
• переводы слова

Не секрет, что слова в английском языке (как и в русском, вообщем-то) при одинаковом написании могут быть различных частей речи. Соответственно, части речи слова - это список всех возможных в предложении частей речи данного слова

Каждый вариант перевода слова описывается:

• русское слово
• часть речи
• параметры слова
• шаблон склонения

Параметры слова - это синтаксические и семантические характеристики слова. Например, для глаголов - это переходный/непереходный, совершенный/несовершенный и т.п.

Параметры на данный момент делятся на три вида:

• применимые к английским словам
• применимые к русским слова
• применимые ко всем языкам

Таким образом, параметры слова в предложении - это совокупность всех параметров всех вариантов перевода данного слова в предложении.

Ну со словом вроде более-менее определились. Перейдем к предложению. Я думаю ни для кого не секрет, что предложение - это группа слов :) Английское предложение описывает специальный класс TMStr, русское - TRStr. Ну, об их особенностях поговорим позже...

Текст обычно состоит из абзацев, абзацы из предложений. Эту структуру описывает класс TTextParser. Фактически - это третий самый главный базовый класс (первые два - это TMWord и TMStr). Все взаимодействие GUI-модулей с текстом идет через него.

Основы

Продолжаю свой рассказ :) Услышав, что я пишу переводчик у многих сразу же возникает вопрос - зачем? Ведь есть ПРОМТ и подобные программы? Ответ будет м... неприятным.... Да, пожалуй так точнее всего. Я более менее активно пользуюсь ПРОМТом уже лет 7 (года на два больше чем я пишу переводчик). С того времени перевод ПРОМТом тестового кусочка текста не изменился. (Нет, конечно, я немного привираю - перевод отдельных предложений чуть-чуть улучшился/ухудшился, однако каких либо радикалных изменений не было и нет даже в текущей - только-что вышедшей - 8-ой версии) Что собственно и не удивительно, т.к. я встречал интервью с разработчиками (2002-ого года, кажется), где они прямо сказали, что алгоритм перевода существенно не менялся с 1992 года!!! А за это время столько всего изменилось.... Вы спросите - "а что же другие программы?". Ну... Знаете, мне сложно оценивать переводчик, неспособный корректно склонять простые русские слова (я уж не упоминаю о самом переводе - перлы Stylus и ПРОМТа, ставшие уже классикой - это корректно, абсолютно точно переведенный текст :) ) На данный момент я не вижу ни одной программы, реально могущей конкурировать с тем же ПРОМТом. Чем лучше мой вариант перевода? Я предоставляю базовый "движок" перевода, легко модифицируемый сторонними разработчиками. Это позволяет легко, с минимальными затратами, создавать и - самое главное - тестировать новые алгоритмы. Пожалуй, пример не помешает... Допустим вы занимаетесь исследованием ну... например... семантических алгоритмов. Тема эта актуальна уже лет 30 и интерес к ней с каждым днем все возрастает. Итак, для проверки своего алгоритма вам придется:

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

А теперь вспомним еще и про сопутствующие трудности, как-то:

• реализация базы данных (словаря)
• реализация различных программ редактирования всего чего нужно: словаря, синтаксических правил, ваших семантических правил и куче чего еще
• ну и до кучи - борьба с глюками, глюками, глюками...

Весело? А казалось бы все так просто: придумал алгоритм - реализовал и получил Нобелевку :)

Именно поэтому мой переводчик - вам просто-таки жизненно необходим! :)

Итак, достоинства моего подхода:

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

Ну если забыть про независимых разработчиков, то можно добавить еще и:

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

За сим, пожалуй, пока все.

Приветствие!

Доброго времени суток! Надеюсь, что кто-то будет читать этот блог. Планирую писать здесь о процессе разработки программы-переводчика с английского на русский (почему только с английского на русский? Ну пытаться перевести с русского на английский - это все равно что программу на C++ перевести на бейсик :) ) Пишу на C# уже три года (и на С++ не вернусь ни за что :) ). Переводчик пишу уже 5-ый год. На данный момент более-менее работают следующие компоненты системы: - лексический анализ - морфологический анализ - фразеологический анализ (на данный момент - только-только дописан черновой вариант) - синтаксический анализ Основное достоинство моего переводчика - модульная структура, все элементы алгоритма выполнены как независимые модули, что позволяет расширять и/или улучшать отдельные элементы системы независимо от остальных Последнюю версию можно взять тут: http://ertranslator.narod.ru/ERTranslateIt_21_04_07.rar В комплекте: редактор-переводчик - Editor-translator2.0.exe редактор словаря - BaseEditor2.0.exe редактор синтаксических правил - IdmEdit.exe редактор склонения русских слов - Sklon_Phrases.exe