Текстовый анализатор: распознавание авторства (продолжение)

    Эта статья об алгоритме распознавания авторства, реализованном в проекте «Текстовый анализатор». В продолжении статьи мы рассмотрим конечный автомат для разбиения текста на уровни. (Начало и окончание).

    Структура статьи:
    1. Анализ авторства
    2. Знакомство с кодом
    3. Внутренности TAuthoringAnalyser и хранение текстов
    4. Разбиение на уровни конечным автоматом на стратегиях
    5. Сбор частотных характеристик
    6. Нейросеть Хэмминга и анализ авторства

    Дополнительные материалы:
    • Исходники проекта «Текстовый анализатор» (Borland C++ Builder 6.0)
    • Тестирование нейросистемы Хэмминга в Excel'е ([xls])
    • Таблица переходов для КА, разбивающего текст на уровни ([xls])
    • Расчет благозвучия отдельных букв ([xls])
    • Презентация дипломного проекта «Текстовый анализатор» ([ppt])
    • Презентация проекта «Карта благозвучия» ([ppt])
    • Все эти материалы в сжатом виде ([zip], [7z], [rar])



    4. Разбиение на уровни конечным автоматом на стратегиях

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



    Выводы:
    • Уровни будут храниться в виде списков с индексами. Логичным образом сюда вписывается концепция диапазонов (Range, [1], [2], [3]); и хотя в то время я еще ничего не знал ни про Range, ни про Александреску ([1]), примитивные диапазоны у меня получились. У диапазонов есть начальный индекс и конечный индекс: RangeItem(BeginIndex, EndIndex), либо начальный индекс и количество (смещение): Range(BeginIndex, Count). Индексы в точности соответствуют позициям символов в тексте. Если мы хотим обозначить весь текст, то это будет RangeItem(1, Length(Text)). Если нам нужен какой-то абзац посередине, то мы получим RangeItem(312031, 312355). Список диапазонов будет представлять собой куски текста без их прямого копирования.
    • Диапазоны надо скрыть за абстракцией. Так, обращаясь к списку диапазонов, представляющих собой первый и последний абзацы, мы должны лишь видеть текст, который в них скрывается. Нам должно быть всё равно, сколько там этих Range и куда они указывают. Пусть мы будем обращаться к более высокому уровню, а он нам предоставит то, что мы хотим.
    • Определить слова — не проблема. Знай себе отделяй все буквы между другими знаками… Абзацы тоже выявляются легко. Если, конечно, забыть, что в разных ОС конец абзаца обозначается по-разному ([1]). А вот предложения… Сколько, вы бы думали, у нас есть «легальных» знаков, завершающих предложение? Три?! Точка, вопрос и восклицание?.. Куда там!.. Они же еще могут сочетаться!!! ([1]). Но даже это еще и не всё; я встречал конструкции, где в одном предложении фактически находится два и больше. И если считать неправильно, то вместо семи предыдущих предложений можно насчитать более пятнадцати. Вывод, в принципе, очевиден: нужен конечный автомат.


    КА — конечный автомат ([1], [2], [3]). Одно из его применений заключается в том, что он распознаёт в цепочке поступающих символов те или иные конструкции: слова, составные знаки препинания, функции, структуры, целые классы с их методами и полями. Так действуют спеллчекеры, анализаторы исходного кода, компиляторы, инструменты для подсветки синтаксиса, так действует ваш компьютер, и прочее, и прочее. Применимость у КА огромная. Например, своим студентам я задавал сделать генерацию сказки с помощью недетерминированных КА, — и такое возможно. Здесь применяется КА на стратегиях ([1]), написанный Сергеем Сацким ([1]) аж в 2003 году.

    Copy Source | Copy HTML
    1. template <class SState, class SEvent, class SFunctor = SEmptyFunctor<SState,SEvent>, class SUnknownEventStrategy = SThrowStrategy<SEvent> >
    2. class SFiniteStateMachine
    3. {
    4. public:
    5.     typedef SState StateType;
    6.     typedef SEvent EventType;
    7.  
    8. private:
    9.     StateType _CurrentState; // Current machine state
    10.     std::vector<StateType> _States; // A list of the registered states
    11.     std::vector<EventType> _Events; // A list of the registered events
    12.     std::vector< std::vector<StateType> > _Transitions; // A table of transitions between states
    13.     SFunctor _Functor; // Transition function
    14.     SUnknownEventStrategy _UnknownEventStrategy; // Unknown event strategy
    15.     std::deque<EventType> _EventsQueue; // Internal events queue to support events
    16.                                                                     // that were generated in the transition functions
    17.     bool _InProcess; // To be sure that we are in the process of events
    18.     int _CurrentStateIndex; // Index of column in a transition table (0 - based)
    19.     StateType _InitialState; // Start machine state
    20. // ...... 



    Конечный автомат Сацкого ([h]) реализован на паттерне «Стратегия». (Strategy, [1], [2], [3]). В качестве стратегий приходят типы SState, SEvent (событие, состояние), SFunctor (функтор перехода от одного состояния к другому) и SUnknownEventStrategy (поведение КА, если событие не распознано). Вот как выглядит функция, распознающая событие и переводящая КА в новое состояние:

    Copy Source | Copy HTML
    1. inline void ProcessEvent(const EventType & tEvent)
    2. {
    3.     int EventIndex(GetEventIndex(tEvent));
    4.     if (EventIndex == -1) return;
    5.  
    6.     StateType OldState(_CurrentState); // Сохраняем старое состояние.
    7.  
    8.     _CurrentState = (_Transitions[EventIndex])[_CurrentStateIndex]; //Определяем новое состояние.
    9.     _CurrentStateIndex = GetStateIndex(_CurrentState);
    10.  
    11.     _Functor(OldState, tEvent, _CurrentState); // Выполняем действие, связанное с новым состоянием.
    12. }


    Пусть где-то во внешней среде мы перебираем текст посимвольно. Мы берём очередной символ и передаем его в функцию ProcessEvent(). Конечный автомат по этому символу выбирает ячейку в таблице переходов, основываясь так же на текущем состоянии. В ячейке сказано, какое состояние должно наступить, и что делать дальше. Я слегка изменил КА, чтобы он понимал «символ» как событие. Так же я переопределил стратегию «Состояние», подсунув свой класс состояния. Таким образом, таблица переходов состояла из мною определенных событий и состояний.

    И ее было очень трудно разрабатывать. Она росла как на дрожжах. Если состояние было «Пусто», и приходила буква «А», то мы должны начать распознавание слова, предложения и абзаца, перейдя в соответствующее состояние. Если приходила точка, то мы должны перейти в специальное состояние и подождать, а не является ли это составным знаком препинания. Могли прийти «Б», «В», «б», «в», "!", «1», «2»… Все буквы алфавита, все знаки препинания, вообще все знаки таблицы ASCII. И на них ведь нужно как-то реагировать! Представьте себе таблицу, в которой ~ 255 строк (одна строка — одно событие, один символ) и около 20 столбцов, состояний КА. Это же убиться веником, сколько ячеек с командами перехода заполнять! 20*255=5100 ячеек. Я нашёл более простой подход. Все однотипные символы помещаются в наборы символов ([CCharsSet.h]; [UConstants.h]), и событием уже считается весь набор символов, если пришёл его символ. Разумеется, наборы могут пересекаться. Например, буква «Б» является элементов следующих наборов: «Все символы», «Буква», «Прописная буква», «Русская буква», «Русская прописная буква». Знак «точка» входит в наборы «Все символы», «Знак препинания», «Знак конца абзаца». И так далее. Наборов вышло порядочно, однако, это меньше, чем всех символов. Таблица переходов ([xls]) сократилась в десятки раз. Ещё одно важное преимущество в том, что наборы можно изменять, не влияя на таблицу переходов. Ну, забыли мы букву «Ё», ну вставили в соответствующие наборы, и делов-то!..

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

    Copy Source | Copy HTML
    1. class TState;
    2. typedef TCharsSetEvent TEvent;
    3.  
    4. typedef TCFDivisionTreeItem<TCFLevelDataType, TUnitType> TCFCustomUnitDivisionTreeItem;
    5. typedef TCFTreeLevel<TCFLevelDataType, TUnitType> TCFCustomUnitTreeLevel;
    6.  
    7. typedef void (*TFuncPtr)(TCFCustomUnitDivisionTreeItem *, const TEvent &);
    8. typedef TStateMachineDescriptor<TState, TEvent> TParSenWordDescriptor;
    9.  
    10. /*Класс используемого состояния.*/
    11.  
    12. class TState : public TFunctionalState<TEvent, TTextString>
    13. {
    14. private:
    15.     TFuncPtr _Function;
    16.     TCFCustomUnitDivisionTreeItem *_TargetTree;
    17. public:
    18.     void OnEnter(const TState & tStateFrom, const TEvent & tEvent) {
    19.         _Function(_TargetTree, tEvent);
    20.     };
    21.  
    22.     TState(const TTextString & tName, TFuncPtr tFunc, TCFCustomUnitDivisionTreeItem * tTargetTree)
    23.     : TFunctionalState<TEvent, TTextString> (tName, sat_None), _Function(tFunc), _TargetTree(tTargetTree){};
    24. };


    Класс TState, как следует из его названия, является состоянием КА. Внутри него лежит указатель на функцию для построения дерева, и указатель на само дерево. Функция вызывается, когда у TState запрашивается метод OnEnter(). Класс, который это дерево представляет (TCFCustomUnitDivisionTreeItem), довольно таки сложен: это доопределение какого-то более абстрактного шаблонного класса ([h]). Мы сейчас не будем заострять на нём внимание. Посмотрим дальше, на функции построения дерева.

    Copy Source | Copy HTML
    1. void FEmpty(TCFCustomUnitDivisionTreeItem * tItem, const TEvent & tEvent)
    2. {
    3.     return;
    4. };
    5.  
    6. void FOpenParagraph(TCFCustomUnitDivisionTreeItem * tTree, const TEvent & tEvent)
    7. {
    8.     TCFCustomUnitDivisionTreeItem NewItem( 0, TRangeItem(tEvent.Iterator(), tEvent.Iterator()));
    9.     tTree->AddItem( 0, NewItem);
    10. };
    11.  
    12. void FOpenSentence(TCFCustomUnitDivisionTreeItem * tTree, const TEvent & tEvent)
    13. {
    14.     TCFCustomUnitDivisionTreeItem NewItem(1, TRangeItem(tEvent.Iterator(), tEvent.Iterator()));
    15.     tTree->AddItem(1, NewItem);
    16. };
    17.  
    18. // .......
    19.  
    20. void FCloseAll(TCFCustomUnitDivisionTreeItem * tTree, const TEvent & tEvent)
    21. {
    22.     FCloseWord(tTree, tEvent);
    23.     FCloseSentence(tTree, tEvent);
    24.     FCloseParagraph(tTree, tEvent);
    25. };
    26.  
    27. // ... и еще несколько функций ... 


    У них у всех один тип. Мы можем замещать эти функции в классе TState друг другом, — таким образом, имеем здесь перегрузку и полиморфизм функций ([1], [2]).

    Но это всё определения и подготовка к главному. Мы же должны получить конкретный объект, содержащий настройки для КА, так? Вот как выглядит функция, возвращающая такой объект:

    Copy Source | Copy HTML
    1. TParSenWordDescriptor Descriptor(TCFCustomUnitDivisionTreeItem * tTree)
    2. {
    3. // Начальное состояние - q0, функция - FEmpty, таблица переходов называется "Параграфы, предложения, слова".
    4.     TParSenWordDescriptor D(TState("q0", FEmpty, tTree), "Paragraphs, Sentences, Words");
    5.  
    6.     // Задаём состояния, причем у каждого - своё имя: q0, q1, ... q14.
    7.     // Каждому состоянию передаем функцию (FEmpty, FOpenAll...), которая должна вызываться, если состояние наступает.
    8.     // Так же передаем указатель на дерево, которое строим - tTree.
    9.     D << TState("q0", FEmpty, tTree)
    10.         << TState("q1", FOpenAll, tTree)
    11.         << TState("q2", FOpenSentenceOpenWord, tTree)
    12.         << TState("q3", FOpenWord, tTree)
    13.         << TState("q4", FEmpty, tTree)
    14.         << TState("q5", FCloseWord, tTree)
    15.         << TState("q6", FCloseSentence, tTree)
    16.         << TState("q7", FCloseSentenceOpenSentenceOpenWord, tTree)
    17.         << TState("q8", FEmpty, tTree)
    18.         << TState("q9", FEmpty, tTree)
    19.         << TState("q10", FCloseWord, tTree)
    20.         << TState("q11", FCloseAll, tTree)
    21.         << TState("q12", FCloseSentenceCloseParagraph, tTree)
    22.         << TState("q13", FCloseParagraph, tTree)
    23.         << TState("q14", FEmpty, tTree);
    24.  
    25.     // Задаём события, у каждого - свое имя ("WinParagraph", "SentenceEnd"...).
    26.     // cWinParagraph, cSentenceEnd - это наборы символов, описанные в UConstants.h.
    27.     D << TEvent("WinParagraph", cWinParagraph)
    28.         <<"q0"<<"q11"<<"q11"<<"q11"<<"q11"<<"q12"<<"q12"<<"q11"<<"q12"<<"q13"<<"q12"<<"q0"<<"q0"<<"q0"<<"q12";
    29.     D << TEvent("SentenceEnd", cSentenceEnd)
    30.         <<"q0"<<"q10"<<"q10"<<"q10"<<"q10"<<"q14"<<"q14"<<"q10"<<"q14"<<"q9"<<"q14"<<"q0"<<"q0"<<"q0"<<"q14";
    31.     D << TEvent("Letters", cLetters + cDigits)
    32.         <<"q1"<<"q4"<<"q4"<<"q4"<<"q4"<<"q3"<<"q2"<<"q4"<<"q3"<<"q2"<<"q7"<<"q1"<<"q1"<<"q1"<<"q7";
    33.     D << TEvent("Space", cSpace + cTab)
    34.         <<"q0"<<"q5"<<"q5"<<"q5"<<"q5"<<"q8"<<"q9"<<"q5"<<"q8"<<"q9"<<"q6"<<"q0"<<"q0"<<"q0"<<"q6";
    35.     D << TEvent("PunctMarks and other symbols", TCharsSet(cPrintable) >> cWinParagraph >> cSentenceEnd >> cLetters >> cDigits >> cSpace >> cTab)
    36.         <<"q0"<<"q5"<<"q5"<<"q5"<<"q5"<<"q8"<<"q9"<<"q5"<<"q8"<<"q9"<<"q14"<<"q0"<<"q0"<<"q0"<<"q14";
    37.     D << TEvent("EndSign", TCharsSet(CTextStringEndSign))
    38.         <<"q0"<<"q11"<<"q11"<<"q11"<<"q11"<<"q12"<<"q13"<<"q11"<<"q12"<<"q13"<<"q12"<<"q0"<<"q0"<<"q0"<<"q12";
    39.  
    40. return D;
    41. };


    Очень хорошо видно, как в таблицу КА вносятся события и состояния, но саму таблицу в этих знаках "<<" увидеть трудно. Просто поверьте, здесь она записана вся.

    Можно было бы ещё заглянуть в класс TEvent, который, на самом деле, TCharsSetEvent ([cpp], [h]). Любопытным — добро пожаловать, а мы перейдём к менеджеру КА — TFiniteStateMachineManager ([h]). Задача этого класса следующая: пользуясь унифицированными интерфейсами, провести анализ с помощью абстрактного КА над абстрактным источником событий. Так же в менеджер можно передать функцию, которая будет где-то отображать прогресс распознавания. Код этого класса весьма богат, и я приведу только самые интересные участки.

    Copy Source | Copy HTML
    1. template <class EventType, class FiniteStateMachineType, class StateMachineDescriptorType, class SourceType>
    2. class TFiniteStateMachineManager
    3. {
    4. private:
    5.  
    6. StateMachineDescriptorType _Descriptor;
    7. SourceType _Source;
    8.  
    9. TUInt _Begin;
    10. TUInt _End;
    11. TUInt _Iterator;
    12. public:
    13. // <......>
    14. TFiniteStateMachineManager(const StateMachineDescriptorType &tDescriptor, const SourceType &tSource)
    15.     :
    16.     _Descriptor(tDescriptor),
    17.     _Source(tSource),
    18.     _ReportStep( 0),
    19.     _ProgressFunc(NULL)
    20. {};
    21. // <......> 


    Опять имеем дело с шаблонами. Если быть точным, то здесь также представлен паттерн «Стратегия». Мало того, что у нас сам конечный автомат на стратегиях, так ещё и какой-то менеджер! Не утаю, скажу, что этот же менеджер используется для создания карты благозвучия, только работает он с другим конечным автоматом, специальным. Ему, по сути, вообще всё равно, что за КА подсунут, лишь бы был интерфейс одинаков. Менеджер берёт этот «подсунутый» КА, и перенаправляет всю работу ему. Один КА обрабатывает правила звучания, другой — разбивает текст на уровни. В этом и есть суть паттерна «Стратегия»: мы конфигурируем наш класс объектами-стратегиями, которые и делают реальную работу. Например, если бы мне было нужно, что при наступлении события вызывался какой-нибудь фильтр, я бы мог заменить событие EventType, передав в качестве стратегии другой класс, реализующий фильтры.

    Copy Source | Copy HTML
    1. TFiniteStateMachineManager & Process()
    2. {
    3.     _Begin = _Source.Begin();
    4.     _End = _Source.End();
    5.  
    6.     FiniteStateMachineType _Machine(_Descriptor.StartState(), _Descriptor.Proxy());
    7.  
    8.     for (_Iterator=_Begin; _Iterator<=_End; _Iterator++)
    9.     {
    10.         _Machine << EventType(_Source[_Iterator], _Iterator);
    11.     };
    12.  
    13.     _Machine << EventType(_Source.EndSign(), _End+1);
    14.  
    15. return *this;
    16. };



    В функции Process() всё просто. Создается объект конечного автомата _Machine, настраивается описателем (таблица переходов, начальное состояние), и запускается процесс распознавания в цикле. «Итератор», переданный в качестве второго параметра в класс EventType, обозначает индекс символа в тексте. Если событие вызвало, например, состояние «Начать слово», то индекс запишется в RangeItem как BeginIndex. И наоборот: если событие — это конец слова (предложения, абзаца), то индекс станет конечным для данного диапазона. Так мы и получаем список из RangeItem, соотнесенных с текстом.

    Почему слово «итератор» я взял в кавычки? Потому что это не настоящий итератор, а всего лишь целочисленная переменная. Но если бы нужно было сделать по-настоящему универсальный менеджер, то пришлось бы абстрагироваться от объектов-событий. Менеджер вообще не должно волновать, в каких списках, таблицах или массивах там хранятся данные, откуда берутся, сколько элементов, и в каком они порядке. А чтобы обеспечить проход по ним, можно было бы использовать паттерн «Итератор» (Iterator, [1], [2]). Великих изменений не потребовалось бы, чтобы заставить цикл работать с итераторами:

    Copy Source | Copy HTML
    1. // ......
    2. SourceType *_Source;
    3. // ......
    4.  
    5. SourceType::Iterator _Iterator = _Source->Begin();
    6.     for (; _Iterator != _Source->End(); ++_Iterator)
    7.     {
    8.         _Machine << EventType(*_Iterator);
    9.     };



    Результатом работы этого КА будут деревья разбиения текстов. Далее нужно из этих разбиений выбрать участки для сравнения. Алгоритм довольно прост.
    — Для каждого текста участки сортируются по возрастанию длины.
    — Составляется шаблон минимального соответствия. В нем прописывается, сколько участков одинаковой длины можно взять из всех текстов. Если у всех текстов есть 10 абзацев длиной 1000, а у одного текста таких абзацев всего 8, то минимальное соответствие — 8 участков. Так — для каждой длины.
    — В соответствии с шаблоном выбираются участки из текстов.
    — В алгоритме поочерёдно участвуют все уровни: абзацев, предложений и слов.

    Теперь у нас есть образцы, и можно приступить к сбору характеристик.

    Средняя зарплата в IT

    110 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 8 813 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 2

      +3
      года два назад написал небольшой скрипт на Python, который составляет 14 характеристик текста, в том числе сходимость текста, общий словарь, и тд.
      все это заняло дня 2 и 5КБ кода.

      Наверное потому что у меня не научный подход…

        0
        Что вы называете сходимостью текста?

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

      Самое читаемое