Морфология. Задачи и подходы к их решению


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

    Для русского языка это несколько сотен тысяч слов. Может быть, это не экономично, зато дает нам очень много бонусов.

    Во-первых, мы можем проверить, есть ли слово в словаре. С помощью правил, основанных на регулярных выражениях, мы не выясним, есть слово «мымымымыться» в русском языке. Окончание вполне подчиняется правилам русского языка, повторение слогов – тоже не исключительный случай. Регулярное выражение это слово пропустит, но на самом деле никакого «мымымымыться» в русском языке не существует.

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

    Для решения этих задач нам нужно хранить не только все слова, но и все их формы. Все правила образования форм для группы слов, похожих друг на друга, называются парадигмой словоизменения. Возьмем глагол «будлануть»: будланул, будланешь, будланет, будланул, будланула, будланули. Можно найти массу глаголов, которые будут изменяться по тем же правилам; с другой стороны, огромное количество глаголов будет изменяться по иным правилам. Значит, эти глаголы принадлежат разным парадигмам.

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

    Хранение словаря

    Таким образом, словарь, хранимый в системе, решает массу задач, что не может не радовать. Но как же хранить этот словарь? В русском языке несколько сотен тысяч слов. В среднем на одно слово приходится 15 форм. Откуда мы берем это число? Рассмотрим падежи: их 6 для единственного числа и 6 для множественного – уже 12. И это не говоря о том, что в русском языке не 6 падежей, как учат в школе, а 8.

    Во-первых, в предложном падеже прячется падеж, который называется локатив. Если мы поставим в предложный падеж слово «лес», у нас получится два варианта: «о лесе» и «в лесу». В лесу – это локативный падеж, а не предложный. Для многих существительных формы этих падежей совпадают, потому что мы не различаем «в столе», «о столе», и «на столе». Все потому, что локации «в столе» нет, а вот локация «в лесу» есть.

    Восьмой падеж носит название партитив. Этот падеж показывает на часть от целого. Если у нас закончился чай, вставать лень, а рядом ходит кто-то незанятый, мы ему говорим: «Налей мне, пожалуйста, чаю». Как правило, форма слов в партитиве совпадает с родительным или винительным падежом. Википедия приводит нам прекрасный пример слова, которое не имеет никаких других форм, кроме партитива множественного числа – «щец» («Щец не желаете?»; «Налей-ка мне щец!»)

    Итого, 8 падежей умножить на 2 формы (единственное и множественное число) — уже 16. У глаголов же есть время, число и род. Путем нехитрых арифметических вычислений получаем, что 15 форм – довольно скромная оценка снизу.

    Среднее эмпирическое число символов в русском слове – 9. Умножаем полученные результаты, не забывая учесть, что на 1 символ приходится 2 байта, и выясняется, что для словаря всех форм русского языка необходимо 50 мегабайт. На практике же наши идеальные 50 мегабайт увеличиваются еще в полтора раза: в итоге текстовый файл со всеми формами слов русского языка занимает более 75 мегабайт.

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



    И это только на русский язык, а еще есть английский, французский, испанский, итальянский и масса других прекрасных и богатых языков. Если мы хотим, чтобы, например, FineReader распознавал и поддерживал много языков, нам одних морфологических словарей нужно будет уместить в него на гигабайт. Что говорить об эталонах для распознавания и других dll'ках? Пользователь нас с такой тяжеловесной технологией не поймет — и будет прав. Надо быть скромнее и хранить оптимальнее.

    Префиксное дерево

    Нам на помощь приходит префиксное дерево. Как оно устроено? Все начинается с вершины – пустого символа, в котором хранится алфавит. Для первой буквы там хранится весь алфавит, точнее, массив из 33 указателей. Каждый указатель соответствует своему символу. Первый указатель – символу А, второй – символу Б, некий К-тый указатель – символу К и некий П-тый – символу П. По указателям мы можем получить следующие узлы этого дерева, которые соответствуют буквам русского алфавита.

    В следующих узлах снова хранятся массивы. Причем для быстроты поиска мы пренебрегаем тем, что букв, на которые нам нужны указатели, будет уже меньше 33 (вряд ли нам потребуется сочетание «аы», например). Мы оставляем размерность массива неизменной, вставляя для отсутствующих символов нулевые указатели.


    На рисунке изображен пример префиксного дерева для четырех слов: «кот», «кошка», «кит» и «пес». Розовым закрашены финальные вершины.

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

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

    Что хранить в словаре



    Теоретически мы действительно можем хранить все формы слов в дереве, сохраняя при этом указатели на начальную форму (синие линии на рисунке). Однако обратите внимание: несмотря на то что «кот» и «котик» относятся к разным словообразовательным парадигмам, часть флексий (так мы называем окончания) у них совпадают. Что если эти хвосты слов хранить отдельно, а в дереве оставить начальные формы котов, котиков и китов? Так будет эффективнее.

    Основательный подход

    В школе слово делят на составные части следующим образом: приставка, корень, несколько суффиксов и окончание. Мы пойдем другим путем. Во-первых, мы не будем отделять приставку от корня. Это связано с тем, что часто приставка вместе с корнем образуют совершенно новый смысл. Возьмем для примера слова «приставка» и «ставка». «При-» – это всего лишь приставка у слова «ставка», но «приставка» и «ставка» – это совершенно разные вещи.

    Кроме того, приставка не выражает никакой грамматической категории. Когда мы добавляем приставку «пере-» («переделать» или «перекурдячить»), мы меняем лексический смысл слова, а не грамматический. Поэтому приставку и корень мы рассматриваем как единое целое и называем это основой слова.

    Еще одно отличие от школы: мы практически никогда не отделяем суффиксы от окончаний, так как в большинстве случаев они выражают грамматическую категорию. В нашем примере «-л-» и «-а-» выражают прошедшее время, женский род, и мы объединяем их в флексию. При таком делении мы получаем изменяемую часть слова – флексию и неизменяемую – основу.

    Удобные допущения


    Вы уже, наверное, привыкли к тому, что в компьютерной лингвистике ничего просто так не бывает. Вот и здесь: в разных формах слова может меняться даже часть корня. Можно, конечно, нудно рассуждать о том, что это всего лишь изменяемая согласная в корне «дру-г» и «дру-зь», но для решения практических задач нам удобнее принять, что у этих слов одинаковая основа «дру-», а флексии разные.

    Итак, мы определили, что лексемы (основы слов) и флексии будут храниться отдельно. Наконец мы подходим вплотную к тому, как решает задачи лемматизации наш морфологический модуль в ABBYY.

    Окончательная лемматизация


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

    Если внимательно посмотреть на окончания, можно заметить, что их можно приписать как к «коту», так и к «киту». Если мы добавим «а», получим родительный падеж, если «у», – дательный и так далее. Всё это – разные формы двух слов, которые принадлежат одной и той же парадигме, и поэтому одинаково меняются.

    Разбор китов

    Когда мы получаем форму слова, мы начинаем её анализировать не сначала, а с конца. Сначала мы предполагаем, что есть нулевое окончание, которое помечено розовым цветом и показывает, что перед нами именительный падеж, единственное число. Затем мы идём по данному нам слову «китами» и встречаем букву «и». Мы находим букву «и» в префиксном дереве. Следующая буква — «м». Эти буквы не являются последними, поэтому мы продолжаем двигаться вглубь дерева. Следующая буква «а», которая помечена розовым, конечный узел в дереве. Значит, «-ами» слева направо, или «-има» справа налево — это один из вариантов окончания, которым может заканчиваться слово.

    Итак, мы нашли два окончания: пустое и «-ами». Теперь нам нужно искать основу в префиксном дереве словаря. Этот поиск осуществляется уже слева направо. Мы последовательно находим буквы «к», «и» и «т», и на букве «т» дерево заканчивается. То есть «кит» — это одно из слов, хранящихся в этом дереве. Если мы попробуем искать дальше, то увидим, что следующая буква «а», но указателей на следующую вершину нет, значит, мы прекращаем поиск.

    Мы видим, что три буквы слева и три буквы справа срослись в слово, а вот пустое окончание нам не пригодилось. Мы принимаем решение, что «китами» — это форма множественного числа, творительного падежа, лексемы с начальной формой «кит».

    Об ещё не освещённых задачах, решаемых подсистемой морфологии, читайте в следующем посте.
    ABBYY
    112.53
    Решения для интеллектуальной обработки информации
    Share post

    Comments 20

      +5
      Как оказывается это увлекательно и интересно. Спасибо! Жду продолжения.
        +1
        А как это локации «в столе» нет, а как же тумбочка в столе и т.п.?
          0
          При этом есть фраза «писАть в стол».
            +2
            Да, вы правы. Есть такая локация «в столе». Имелось в виду, что в языке не закрепилась форма «в столу» или что-то подобное. У «стола» есть локативный падеж, но он совпадает с предложным.
            На самом деле, в нашем языке закрепилось всего несколько десятков существительных, у которых локатив отличается от предложного падежа. По какому принципу у других слов отпала особая локативная форма — можно только догадываться.
            0
            А про нечеткие дубликаты текста можете рассказать так же увлекательно?
              +2

              Кит конспирируется?
                0
                Однажды в фирме где я делал сайты, две девушки-лингвистки на соседнем проекте проверяли списки корней и гнёзда окончаний, исправляли разные исключения — теперь понял что конкретно они делали. Отлаживали подобный словарь.

                И как видно из вашего объяснения для каждого языка нужна совершенно своя схема хранения словаря? Ведь есть же языки в которых меняются не окончания, а середины слов, или слова сливаются воедино? А есть и языки где нет букв. И на каждый язык требуется работа программистов совместно со специалистом по этому языку, так ведь?
                  0
                  Есть разные группы языков с разными свойствами. Например, Агглютинативные языки. Под каждую группу приходится несколько модифицировать структуру хранения и логику работы со словарем. Есть еще особенности написания слов, например, композиты в немецком или отсутствие пробелов в тайском, и это решается дополнительной логикой разбора слов. Как Вы правильно заметили, есть еще иероглифические языки (китайский), но там словарь просто вырождается во множество коротких цепочек. Японский, кстати, в этом смысле особенный, там часть к иероглифам приписывают окончания с помощью алфавитного письма, но это не представляет собой большую проблему с точки зрения организации словаря. Но если учесть особенности очередной группы языков, то дальше уже не нужно под каждый язык что-то специальное придумывать.
                    +1
                    По поводу японского: запросто могут записать и все слово хираганой, и, в случае глагола/прилагательного, основу — катаканой, окончание — хираганой… Так что просто цепочкой, показанной в статье, тут уже не обойдешься. Или она вырастет в два с половиной-три раза.
                      0
                      В японском тогда омонимов будет очень много.
                      Кстати об омонимах. А как с ними будут обстоять дела в подобном словаре? Или это уже проблемы другого слоя — лексики?
                        0
                        Омонимов много, да. Но это смотря как записывать. С речью вариантов кроме анализа смысла никаких. Вот, например, три слова, читающееся как «koumon»: "校門", "閘門", "肛門" (соответственно «школьные ворота», «шлюз» и, простите, «задний проход»). Их все можно записать как "こうもん" или "コウモン", что, при соответствующем контексте, не помешает пониманию смысла конкретного слова. А вот для машины это будут огромные проблемы.
                      0
                      В семитских языках типично словоизменение сменой огласовок; т.е. меняется не «середина» слова, а сразу по всей длине слова меняются звуки.

                      Например, мн.ч. в арабском: сафӣна «корабль» — суфун «корабли», гурфа «комната» — гураф «комнаты», раджуль «мужчина» — риджа̄ль «мужчины».

                      (Подробнее в Википедии)
                    +3
                    К примеру, для русского языка это дерево вместе с дополнительными данными занимает порядка 2 мегабайт. Во-первых, по сравнению с 75 мегабайтами это, безусловно, успех.

                    Хм, интересно. Для уточнения — цифры тут про одно дерево или про способ хранения, описанный далее в статье?

                    У меня были такие эксперименты: берем 3млн слов (весь словарь OpenCorpora), загружаем их в Trie, получаем 100-200M занятой памяти (в зависимости от реализации дерева).

                    Я пробовал только реализации префиксных деревьев с «полным» алфавитом; уменьшение алфавита до 33 символов может максимум раз в 7 объем памяти уменьшить (на практике меньше), так что для основанного на указателях дерева, похожего на то, что тут описано, вместо 200Мб должно около 25-30Мб получиться. Дальше, у меня была кодировка utf8; при использовании однобайтовой кодировки до 15-20Мб сжаться все может (в 2 раза не выйдет, т.к. Trie хорошо жмет utf8). Если посчитать, что «несколько сот тысяч» — это раз в десять меньше, чем 3млн, и что размер Trie линейно зависит от количества слов (опять очень грубо), то 2Мб и правда как раз получается :) Хотя выглядит цифра все равно немного странно, по прикидкам все же больше должно быть. Это точно не цифра, которая получается с двумя префиксными деревьями?

                    Что интересно, 3млн слов, закодированные в utf8 и загруженные «как есть» в DAFSA/DAWG (брал готовую реализацию dawgdic) с алфавитом 256 символов, тоже мегабайта 2-3 занимают (7 с грамматической информацией и информацией о парадигмах для склонения), и разбор потом проще/быстрее, т.к. не нужно с двух концов идти и сопоставлять результаты.

                    В русском языке есть фишка — слова, оканчивающиеся одинаково, вероятно, имеют одинаковую форму и парадигму, поэтому DAWG может и эту информацию эффективно сжимать и не «разваливается» в Trie, если ее просто приписывать в конец слов.
                      –1
                      Локатив, партитив…
                      Предложный падеж всегда вызывал подозрения — покуда отвечает на вопросы и «где?» и «куда?», хотя сами вопросы, очевидно, разные. Почему-то кажется, что их можно различить чередованием «е» и «и» в конце (например, «приехал (куда?) в Залесье» или «живу (где?) в Залесьи») — однако нет такого правила! На безударном окончании всегда будет «е».

                      ЗЫ. А как же ещё звательный падеж? «Отче наш...» Девятый, выходит!
                        0
                        Падежей на самом деле намного больше чем указанное количество. В разное время исследователи выделяли до 16 разных вариантов.

                        Примеры можно посмотреть здесь: russian.stackexchange.com/questions/404/what-are-the-lesser-known-russian-cases?lq=1
                          0
                          Куда? в ... — это винительный, а не предложный.
                          Они различаются у большинства слов, совсем не обязательно чередованием «е» и «и».
                          Куда? в руку. Где? в руке.
                          Куда? в окно. Где? в окне.
                          Куда? в ящик. Где? в ящике.
                          Куда? в кота. Где? в коте.
                          0
                          Кстати, мымымымыться можно проверить с помощью регулярок. Кажется, повторение слога более трех раз в русском не встречается
                            –1
                            гоооооооооооооооооооооол!
                            0
                            Очень интересная статья. А можно ссылку на сам словарь? Или это Ваше ноу-хау?
                              0
                              Присоединяюсь к вопросу. Сам словарь открыт или нет?

                            Only users with full accounts can post comments. Log in, please.