Pull to refresh

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

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

Структура статьи:
  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 участков. Так — для каждой длины.
— В соответствии с шаблоном выбираются участки из текстов.
— В алгоритме поочерёдно участвуют все уровни: абзацев, предложений и слов.

Теперь у нас есть образцы, и можно приступить к сбору характеристик.
Tags:
Hubs:
Total votes 45: ↑41 and ↓4 +37
Views 2K
Comments 2
Comments Comments 2

Posts