Backend Developer, ML
2,4
рейтинг
1 ноября 2014 в 17:09

Разработка → Разбитие текста на предложения лингво-независимым методом на примере библиотеки AIF

В прошлой статье мы уже рассказывали о новой NLP библиотеке. Однако тогда мы рассказали «обовсем» и не о чем конкретном. Сегодня мы поговорим о теоретических аспектах разбития предложения на токены лингво-независимыми алгоритмами. Теоретические выкладки будут подкреплены практической реализацией в библиотеке AIF. Поехали…

Термины

Мы решили указать термины, которыми мы пользуемся, чтобы строить нашу статью на их базе.

  • токен — часть текста (массив символов), отделенная проблемами или концом/началом строки;
  • технические символы — символы, которые используются для логического группирования токенов в тексте (:,.!?”;);
  • технические символы первой группы — символы, которые чаще всего используются в тексте для деления текста на предложения;
  • технические символы второй группы — символы, которые чаще всего используются в тексте для деления предложений на части;


Теперь перейдем к более запутанному дефиницию — предложению. Берем определение из википедии:

Предложе́ние (в языке) — это единица языка, которая представляет собой грамматически организованное соединение слов (или слово), обладающее смысловой и интонационной законченностью.[1] С точки зрения пунктуации, предложение как законченная единица речи оформляется в конце точкой, восклицательным или вопросительным знаками — или многоточием.


Данное определение можно использовать почти как есть, немного переделав вторую его часть (пунктуационную):

предложение — часть токенов, разделенных между собой техническими символами, которые используются для разбития текста на предложения;

Так мы оставляем за кадром какие именно символы используются для разбития текста на предложения.

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

Для начала давайте определимся с условием задачи:

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


Задача разбития текста на предложения в таких условиях разбивается на 4 подзадачи:
  1. найти в тексте технические символы;
  2. поделить найденные технические символы на группы;
  3. определить какая из групп технических символов является первой, а какая второй;
  4. разбить текст на предложения при помощи выделенных групп символов;


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

1 Поиск технических символов в тексте

wiki

Как можно найти технические символы в тексте?

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

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

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

В результате формула вероятности того, что символ является техническим выглядит так:

(1) P1(ch)*(P2(ch)^2)

где:

P1(ch) — это вероятность того, что символ ch в данном тексте стоит в конце токенов
P2(ch) — это вероятность того, что символ стоящий перед символом ch в данном тексте — тоже стоит в конце токенов

давайте рассмотрим пример расчета вероятности P2. Допустим, у нас есть такие символы:

. y a b

и вероятность того, что они стоят в конце токенов:
P1(.) = 0.8
P1(y) = 0.9
P1(a) = 0.01
P1(b) = 0.02

символ точка в конце токенов встретился 4 раза, а перед точкой стояли такие символы:
y — 3 раза
a — 1 раз

в этом случае P2('.') будет рассчитываться следующим образом:
3/4 * P1(y) + 1/4 * P1(a) = 0.75 * 0.9 + 0.25 * 0.01 = 0.6775

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

Дело в том, что даже эта формула не дает 100% желаемого результата. Ибо есть языки, в которых слова часто оканчиваются на одни и те же два символа. Ну, например, текст в котором существенно преобладает окончание “ec”. И при этом сам по себе символ “е” часто стоит в конце токенов. В результате символ “с” будет выделен в качестве технического, так как он стоит часто в конце токенов и перед ним символ, который также встречается в конце токенов.

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

В результате AIF делает нечто следующее:

Отбирает N-символов с самой высокой вероятностью, рассчитанной по формуле 1, а из них отбирает N2-символов, которые имеют наибольшую вероятность P1. Как правильно подобрать N/N2 числа — это еще та задача, но углубляться в ее подробности мы сейчас не будем, так как AIF пока берет эти числа в некотором роде «с потолка». Нам еще предстоит проверить на практике несколько гипотез на этот счет.

В первой статье на Хабре был показан график первого прохода формулой по тексту. Я хочу лишь сказать, что с того момента формула была изменена и теперь работает точнее (намного точнее).

А теперь давайте немного поговорим о качественном анализе.

Качественный анализ подхода показывает такие результаты (на 186 книг):
12 книг, в которых не удается найти точку на 186 книг;
2 книги, в которых не удается найти запятую;
3 книги, в которых в качестве технического символа была выделена буква;

2 Деление технических символов на группы

wiki

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

.,!?:;()”-

Теперь необходимо поделить этот список на группы. В этом примере символы могут быть поделены на группы следующим образом:

.!?()”
-:;,

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

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

связи точки:
.
P=32, S=16, T=63, F=15, W=44, {=67, N=14

связи запятой:
,
p=47, a=59, b=84, c=52, s=102, d=76, t=295, e=49, w=318, m=59

связи латинской буквы ‘y’:
y
s=3, t=2, w=6

Данные связи взяты из реального текста и они отфильтрованы. Дело в том, что AIF для анализа оставляет только наиболее весомые связи. Без фильтрации граф будет выглядеть несколько иначе.

Само собой, абсолютные весы нам неинтересны и данные связи будут переконвертированные в вероятностные.

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

Реализацию сравнения графов в AIF лучше всего рассмотреть на примере. Допустим у нас есть два графа связей:
.
А 0.2
П 0.6
а 0.05
п 0.15

,
а 0.4
п 0.6

А теперь алгоритм сравнения:

P(ch1, ch2) = ch1.connections.keys.mapToDouble(connectionKey -> (ch1.connections.get(connectionKey) + ch2.connections.get(connectionKey)) / 2).sum() / ch1.connections.keys.size()

вот как-то так. Да, тут есть свои нюансы, например, P(ch1, ch1) может не быть равным P(ch2, ch1). Но никто и не говорит, что Alpha2 — это финальная версия;)

Особенно хорошо этот подход работает на языках, в которых используется регистр (т.е. большая или маленькая буквы). Чуть хуже, но все равно эффективно, работает на арабском и подобных языках.

Качество работы данного модуля:
~0.5 книги на 100 книг, где точка и запятая попадают в одну и ту же группу.

Само собой, в этом пункте ОЧЕНЬ много осталось за кадром. Например, после какого порога вероятности P(ch1, ch2) считаем, что два графа будут равными, и что два символа, которые образуют эти графы из одного кластера?

Случайные примеры групп для разных книг:
книга 1: [“; ,] [.]
книга 2: [! .] [:; ,]

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

wiki

А вот тут все совсем просто. Отображаем массив токенов в новый массив, где каждому токену ставится в соответствие номер группы технического символа, которым заканчивается токен. Если в токенах нету технического символа, то ставим ему нулевую группу. Например, у нас есть такие токены:

Привет! Как твои дела? Я, думаю, что все в порядке. Нет?

И на прошлом этапе у нас были выделены такие группы разделителей:
1 — [!?,]
2 — [,]

Соответственно после отображения мы получим такой массив:
1 0 0 1 2 2 0 0 0 1 1

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

Ну и пример: вот связи первой группы с символами — взято из реальной книги(связи нормализованы по отношению к максимуму):

{A=0.36, B=0.26, "=0.39, C=0.10, D=0.08, E=0.1, H=0.37, I=0.72, L=0.08, M=0.14, N=0.1, O=0.15, S=0.26, T=1.0, W=0.26, Y=0.08}

А вот связи для второй группы:

{A=0.05, a=1.0, "=0.11, b=0.24, c=0.08, d=0.06, e=0.05, f=0.11, h=0.17, I=0.09, i=0.22, m=0.07, n=0.06, o=0.16, p=0.05, s=0.21, t=0.40, w=0.35}

Как и в прошлый раз, AIF фильтрует связи, оставляя только самые весомые. Так что до фильтрации связи будут немного другими.

А вот связи нулевой группы:

{a=0.61, b=0.25, c=0.26, d=0.18, e=0.15, f=0.26, g=0.12, h=0.41, I=0.05, i=0.35, l=0.17, m=0.26, n=0.13, o=0.48, p=0.22, r=0.14, s=0.42, t=1.0, u=0.07, v=0.06, w=0.43, y=0.06}

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

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

Качественный анализ результатов показывает:
4 книги из 180, где точка была отнесена к неверной группе;
2 книги из 180, где запятая была отнесена к неверной группе;

4 Разбить текст на предложения при помощи выделенных групп символов

wiki

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

Например, как понять, что точка в конце “С.С.С.Р.” не для конца предложения, а просто окончание аббревиатуры. Ну или сокращения типа “тыщ.” и т.д.

И опять же, все просто.

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

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

Примеры из книги с местами найденными AIF, где разделитель первой группы был отмечен как разделитель второй группы:

«Последнее восстание» в Сеуле Международная биеннале
«Этот убийца… он такой мягкий и
Эльдара Рязанова. «Ирония судьбы», «Служебный роман»
5–7 мин. также может стать простым
1 мин. горячая вода(+37–38°), 1
5–10 сек. – холодная вода(
5 тыс. лет назад и выполняли

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

by U.S. federal laws and
the U.S. unless a copyright

К сожалению, для текущего шага у нас нету никаких результатов качества =(

Послесловие

Все увиденное — это лишь Alpha2, мы еще даже не начинали заботиться о качестве и скорости работы.

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

Сам алгоритм и API библиотеки детально расписаны на вики проекта: github.com/b0noI/AIF2/wiki

В месте с библиотекой мы так же обновили простенький консольный клиент — AIF-CLI, который теперь умеет показывать найденные технические символы и группы этих символов.

Наша команда

Kovalevskyi Viacheslav – algorithm developer, architecture design, team lead (viacheslav b0noi.com / b0noi)
Ifthikhan Nazeem – algorithm designer, architecture design, developer
Sviatoslav Glushchenko — REST design and implementation, developer
Oleg Kozlovskyi QA (integration and qaulity testing), developer.
Balenko Aleksey (podorozhnick@gmail.com) – added stammer support to CLI, junior developer
Evgeniy Dolgikh — QA assistance, junior developer

PS: Если у вас есть интересный проект NLP, свяжитесь с нами ;)

Ссылки на проект и подробности

project language: Java 8
license: MIT license
issue tracker: github.com/b0noI/AIF2/issues
wiki: github.com/b0noI/AIF2/wiki
source code: github.com/b0noI/AIF2
developers mail list: aif2-dev@yahoogroups.com (subscribe: aif2-dev-subscribe@yahoogroups.com)

Условия тестирования

Все тесты проводились на 186 книгах следующих языков:

  • польский;
  • итальянский;
  • французский;
  • немецкий;
  • английский;
  • русский.
Viacheslav V Kovalevskyi @b0noII
карма
44,2
рейтинг 2,4
Backend Developer, ML
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (12)

  • 0
    Или я что-то не пойму, или у меня просто текст (диктант по украинскому) оно определяет весь, как одно предложение…
    Такая команда запуска правильная?:
    java -jar aif-cli.jar -ssplit temp.txt
    

    Вывод команды
    log4j:WARN No appenders could be found for logger (com.aif.language.token.TokenSplitter).
    log4j:WARN Please initialize the log4j system properly.
    log4j:WARN See logging.apache.org/log4j/1.2/faq.html#noconfig for more info.
    Sentence: [ Марися вільно розкинулась у траві. Задивилася на завислі кетяги акації. Пахнуть вони густо, медово. Бджоли гудуть, обліплюють біло-рожевий цвіт, — десь, видно, здалека прилітають за нектаром. Десь із глибини урочища соловей подає голос. Кажуть, меншає на світі солов’їв. Невже планета справді прощається з цим сіреньким, самобутнім, найніжнішим своїм поетом? А з ким же ділити оте почуття, що підіймається, росте в тобі, хоча й не знаєш, для кого? Незвичайний стан переживає душа в цім давнім урочищі. Ніби п’янить самий дух акації, від нього аж чадієш, умліваєш, поринаєш у безміри якогось блаженства. Марися змружує очі, і одразу ніби зникає все, тане. Маєш над собою лише цей дивний світ, зітканий із золотавості сонця й клубків білого, обліпленого бджолами цвіту. Досягається якась не знана раніш гармонія, сонце розлилося, і сама ти вже ніби розчиняєшся в солодкій млості природи. в її запашистих медах… Зовсім заплющуєш очі, і тоді тебе нема, життя розтануло, світ зіллявся—на місці сонця вирує в небі тільки жовто-бура гаряча туманність, сповнена пахощів цвіту й золотої бджолиної музики. ]

    Так же попробовал:
    java -jar aif-cli.jar -ess temp.txt
    

    Вывод команды
    log4j:WARN No appenders could be found for logger (com.aif.language.token.TokenSplitter).
    log4j:WARN Please initialize the log4j system properly.
    log4j:WARN See logging.apache.org/log4j/1.2/faq.html#noconfig for more info.
    log4j:WARN No appenders could be found for logger (com.aif.language.token.TokenSplitter).
    log4j:WARN Please initialize the log4j system properly.
    log4j:WARN See logging.apache.org/log4j/1.2/faq.html#noconfig for more info.
    Group: 'GROUP_1', characters: ]
    Group: 'GROUP_2', characters: ]
    • 0
      Спасибо, глянул, к сожалению текст оказался достаточно мал для корректной работы программы. Для теста скачал книгу на Украинском: vk.com/doc29866988_335722041?hash=00089797d7cd249b90&dl=e4d4a5250e944d2db5

      команда:

      java -jar ./aif-cli-1.1-jar-with-dependencies.jar -ess ./text_ukr2.txt


      результат работы команды
      log4j:WARN No appenders could be found for logger (com.aif.language.token.TokenSplitter).
      log4j:WARN Please initialize the log4j system properly.
      log4j:WARN See logging.apache.org/log4j/1.2/faq.html#noconfig for more info.
      Group: 'GROUP_2', characters: [; ,]
      Group: 'GROUP_1', characters: [!: .]


      Главное ограничение для алгоритма — размер входящего текста, для каждого языка (и даже конкретного случая) минимальный размер индивидуальный.
    • 0
      В добавок к предыдущему комментарию — да Вы верно запускаете команду. Просто сообщение (текст) очень маленькое что бы его хватило выучить язык на котором оно написано.
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Но и это прекрасно решается если 90% текста все жа разделены запятыми;) Хотя в данной версии мы этого не делаем
  • 0
    токен — часть текста (массив символов), отделенная проблемами или концом/началом строки;

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


    Это, мягко говоря, не для всех языков правда. Например, тайский:
    В отличие от латиницы или кириллицы в тайском алфавите не различаются строчные и прописные буквы. Пробелы между словами обычно не ставятся. Предложения разделяются пробелами.

    • 0
      Очень корректное замечание. Мы пока что не планируем поддерживать группу языков к которой относится упомянутый Вами тайский. Не по тому что там алгоритм не будет работать, а потому что текущая имплементация пока не может причинить алгоритм к этим языкам. Поддержка подобных языков будет включена в план после выхода первой релизной версии AIF, так что не очень скоро =(
      • +1
        Я не совсем понимаю, вы позиционируете свою библиотеку как лингво-независимую, но тут же делаете замечание, что она работает только для определённых языков и текстов определённого размера. Не проще ли задать жёсткие правила для каждого языка с его знаками препинаний, аббревиатурами и числовыми разделителями, как сделано во всех программах для перевода?
        • 0
          Именно потому что программы перевода используют этот подход они столь плохо переводят человеческие тексты где вполне могут использоваться термины не внесенные в банк знаний языково модели. Наша библиотека и остальные решаем разные задачи. Мы пытаемся построить разные связи в тексте и на их основе обработать текст, что позволяет работать намного лучше в условиях когда текст на входе не литературно идеальный. Попробуйте скормить OpenNLP библиотеке на вход дамп из чата игроков eve Online. Собственно изначально прототип прошлой версии решал задачу обработки чата где общались носители Украинского и Русского языков и при этом использовали «суржик».

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

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

    Как это делал в своё время я. Я брал текст, и, не используя никакой априорной информации о его структуре, начинал разбирать. Методом выделения в тексте часто встречающихся подстрок. Такими подстроками со временем выделялись слова с окончаниями, например «дождь.\n». От подстроки «дождь» подстрока «дождь.\n» отличается частотой встречаемости в тексте. Частота появления в тексте дождь с точкой ниже частоты появления в тексте дождь без точки. Запомним отношение частот для обеих подстрок. Тогда, выделив ".\n" в отдельную подстроку, мы можем заметить, что соотношение частот других подстрок (других слов) с точкой и без точки примерно такое-же, как и для дождя. Из чего можно сформировать гипотезу, что ".\n" — является универсальным разделителем, применимым к любым словам. Применяя указанный подход дальше можно выделить отдельно характеристики "." и "\n" и сформировать какие-то гипотезы и по ним.

    Копая таким методом, у нас выделяются для большинства слов псевдокорни, а для тех, для которых не выделяются, можно по частотам совместного использования определить взаимозаменяемые слова (которые близки по смыслу, что, собственно, и искали).
    • 0
      Sound really interesting!

      Have small question:
      if you have next tokens in text:
      cat
      cats
      cat.

      How you will separate 's' and '.'. Both of this characters could be in the end of different tokens?

      Also, maybe you have interest and time to help in this project?
    • 0
      Текст, записанный в текстовый файл, использует априорно известную информацию о знаках используемой кодировки. Думаю, вполне резонно опереться и на заложенную в них семантику — хотя-бы на уровне деления на пробельные и пунктуационные символы, буквы и цифры. Раз уж на восьмибитность или UTF8 разрешаем себе опереться.

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