Text analyzer: recognition of authorship (continued)

This article is about the authorship recognition algorithm implemented in the Text Analyzer project. In the continuation of the article we will consider a finite state machine for splitting text into levels. ( Begin and end ).

Article structure:

1. Authorship analysis
2. Introducing the code
3. TAuthoringAnalyser internals and text storage
4. Leveling by state machine on strategies
5. Collection of frequency characteristics
6. Hamming neural network and authorship analysis

Additional materials:

• Sources of the Text Analyzer Project (Borland C ++ Builder 6.0)
• Testing the Hamming Neural System in Excel ( [xls] )
• Conversion table for the spacecraft splitting the text into levels ( [xls] )
• Calculation of the sound of individual letters ( [xls] )
• Presentation of the graduation project "Text Analyzer" ( [ppt] )
• Presentation of the “Euphony Card” project ( [ppt] )
• All these materials are compressed ( [zip] , [7z] , [rar] )

4. Leveling by the state machine on strategies

Need to:

• Break the text into words, sentences and paragraphs.
• Address these levels uniformly, without knowing anything about internal realization.
• Do not store these levels in their natural form, otherwise the texts would be copied a huge number of times.

')

Findings:

• Levels will be stored as lists with indexes. Logically, the concept of ranges fits here (Range, [1] , [2] , [3] ); and although at that time I still did not know anything about the Range, or about Alexandrescu ( [1] ), I got the primitive ranges. The ranges have a starting index and an ending index: RangeItem (BeginIndex, EndIndex), or a starting index and quantity (offset): Range (BeginIndex, Count). The indices correspond exactly to the positions of the characters in the text. If we want to mark all the text, it will be a RangeItem (1, Length (Text)). If we need a paragraph in the middle, we will get a RangeItem (312031, 312355). The list of ranges will be pieces of text without copying them directly.
• Ranges must be hidden behind the abstraction. So, referring to the list of ranges representing the first and last paragraphs, we should only see the text that is hidden in them. We should not care how many there are these Range and where they point. May we turn to a higher level, and he will give us what we want.
• Defining words is not a problem. Know yourself to separate all the letters between other characters ... Paragraphs are also easily identified. Unless, of course, to forget that in different OS the end of a paragraph is denoted differently ( [1] ). But sentences ... How many, you would think, we have "legal" signs that complete the sentence? Three?! Point, question and exclamation? .. Where there! .. They can still be combined !!! ( [1] ). But even that is not all; I have met constructions where in one sentence there are actually two or more. And if you count wrong, instead of the seven previous sentences, you can count more than fifteen. The conclusion, in principle, is obvious: we need a finite automaton.

KA is a state machine ( [1] , [2] , [3] ). One of its applications is that it recognizes certain constructions in a chain of incoming characters: words, compound punctuation marks, functions, structures, whole classes with their methods and fields. This is how spell checkers, source code analyzers, compilers, syntax highlighting tools work, so does your computer, and so on and so forth. The applicability of the spacecraft is huge. For example, I asked my students to generate a fairy tale using non-deterministic spacecraft, and this is possible. Here the spacecraft is used on strategies ( [1] ), written by Sergei Satsky ( [1] ) already in 2003.

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

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

Satskii state machine ( [h] ) is implemented on the Strategy pattern. (Strategy, [1] , [2] , [3] ). The strategies come in the types SState, SEvent (event, state), SFunctor (functor of transition from one state to another) and SUnknownEventStrategy (behavior of the SC, if the event is not recognized). Here is the function that recognizes the event and translates the spacecraft into a new state:

Copy Source | Copy HTML

1. inline void ProcessEvent ( const EventType & tEvent)
2. {
3. int EventIndex (GetEventIndex (tEvent));
4. if (EventIndex == - 1 ) return ;
6. StateType OldState (_CurrentState); // Save the old state.
8. _CurrentState = (_Transitions [EventIndex]) [_ CurrentStateIndex]; // Define a new state.
9. _CurrentStateIndex = GetStateIndex (_CurrentState);
11. _Functor (OldState, tEvent, _CurrentState); // Perform the action associated with the new state.
12. }

Let somewhere in the external environment, we iterate the text character by character. We take the next character and pass it to the ProcessEvent () function. The state machine for this symbol selects a cell in the transition table, also based on the current state. The cell says what state should come and what to do next. I slightly changed the spacecraft so that he understood the “symbol” as an event. I also redefined the “Status” strategy by slipping my state class. Thus, the transition table consisted of certain events and states by me.

And it was very difficult to develop. She grew by leaps and bounds. If the state was “Empty”, and the letter “A” came, then we should start recognizing the word, sentence and paragraph by going to the corresponding state. If a point has arrived, then we have to go into a special state and wait, but is this a composite punctuation mark? Could be “B”, “C”, “b”, “c”, “!”, “1”, “2” ... All the letters of the alphabet, all the punctuation marks, in general, all the signs of the ASCII table. And because they need to somehow react! Imagine a table with ~ 255 lines (one line - one event, one character) and about 20 columns of spacecraft states. It's a broom how many cells with transition teams to fill! 20 * 255 = 5100 cells. I found a simpler approach. All single-type characters are placed in character sets ( [CCharsSet.h] ; [UConstants.h] ), and the entire character set is already considered an event if its character has arrived. Of course, the sets may intersect. For example, the letter “B” is the elements of the following sets: “All symbols”, “Letter”, “Uppercase letter”, “Russian letter”, “Russian capital letter”. The “dot” sign is included in the “All symbols”, “Punctuation mark”, “Paragraph end” sets. And so on. The sets came out decently, however, this is less than all the characters. The transition table ( [xls] ) has decreased tenfold. Another important advantage is that the sets can be changed without affecting the conversion table. Well, we have forgotten the letter "E", well, inserted into the appropriate sets, and business! ..

How does this even work? After all, passing the text through the state machine, we have to build a tree of levels. If in words, then the state machine, executing the instruction upon the occurrence of an event, calls the function associated with the event. There are several such functions ( [UParSentWordFSM.h] ), and they all build a common tree, receiving a pointer to it as input. Let's take a closer look at how the configuration of the spacecraft is described.

Copy Source | Copy HTML

1. class TState ;
2. typedef TCharsSetEvent TEvent ;
4. typedef TCFDivisionTreeItem < TCFLevelDataType , TUnitType > TCFCustomUnitDivisionTreeItem;
5. typedef TCFTreeLevel < TCFLevelDataType , TUnitType > TCFCustomUnitTreeLevel;
7. typedef void (* TFuncPtr) (TCFCustomUnitDivisionTreeItem *, const TEvent &);
8. typedef TStateMachineDescriptor < TState , TEvent > TParSenWordDescriptor;
10. / * Class of used state. * /
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. };
22. TState ( const TTextString & tName, TFuncPtr tFunc, TCFCustomUnitDivisionTreeItem * tTargetTree)
23. : TFunctionalState < TEvent , TTextString > (tName, sat_None), _Function (tFunc), _TargetTree (tTargetTree) {};
24. };

The TState class, as its name implies, is a state of the spacecraft. Inside it is a pointer to a function for building a tree, and a pointer to the tree itself. The function is called when the OnEnter () method is requested from TState. The class that this tree represents (TCFCustomUnitDivisionTreeItem) is quite complicated: this is the definition of some more abstract template class ( [h] ). We will not focus on it now. Let's look further at the functions of building a tree.

Copy Source | Copy HTML

1. void FEmpty (TCFCustomUnitDivisionTreeItem * tItem, const TEvent & tEvent)
2. {
3. return ;
4. };
6. void FOpenParagraph (TCFCustomUnitDivisionTreeItem * tTree, const TEvent & tEvent)
7. {
8. TCFCustomUnitDivisionTreeItem NewItem ( 0 , TRangeItem (tEvent.Iterator (), tEvent.Iterator ()));
9. tTree-> AddItem ( 0 , NewItem);
10. };
12. void FOpenSentence (TCFCustomUnitDivisionTreeItem * tTree, const TEvent & tEvent)
13. {
14. TCFCustomUnitDivisionTreeItem NewItem ( 1 , TRangeItem (tEvent.Iterator (), tEvent.Iterator ()));
15. tTree-> AddItem ( 1 , NewItem);
16. };
18. // .......
20. void FCloseAll (TCFCustomUnitDivisionTreeItem * tTree, const TEvent & tEvent)
21. {
22. FCloseWord (tTree, tEvent);
23. FCloseSentence (tTree, tEvent);
24. FCloseParagraph (tTree, tEvent);
25. };
27. // ... and some more functions ...

They all have the same type. We can replace these functions in the TState class with each other, - thus, we have here an overload and polymorphism of functions ( [1] , [2] ).

But these are all definitions and preparation for the main thing. We should get a specific object that contains settings for the spacecraft, right? Here is the function that returns this object:

Copy Source | Copy HTML

1. TParSenWordDescriptor Descriptor (TCFCustomUnitDivisionTreeItem * tTree)
2. {
3. // The initial state is q0, the function is FEmpty, the transition table is called "Paragraphs, sentences, words".
4. TParSenWordDescriptor D (TState ( "q0" , FEmpty, tTree), "Paragraphs, Sentences, Words" );
6. // Set the state, and each has its own name: q0, q1, ... q14.
7. // Each state is passed a function (FEmpty, FOpenAll ...), which should be called if the state occurs.
8. // Also, we pass a pointer to the tree that we are building - 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);
25. // Set events, each one has its own name ("WinParagraph", "SentenceEnd" ...).
26. // cWinParagraph, cSentenceEnd are the character sets described in 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" ;
40. return D;
41. };

It is very clearly seen how events and states are entered in the AC table, but the table itself in these "<<" signs is difficult to see. Just believe, here it is recorded all.

One could also look into the TEvent class, which, in fact, is TCharsSetEvent ( [cpp] , [h] ). Curious - welcome, and we move on to the manager of the CA - TFiniteStateMachineManager ( [h] ). The task of this class is as follows: using unified interfaces, perform an analysis using an abstract spacecraft over an abstract source of events. Also in the manager, you can pass a function that will somewhere display the progress of recognition. The code of this class is very rich, and I will give only the most interesting sites.

Copy Source | Copy HTML

1. template < class EventType , class FiniteStateMachineType , class StateMachineDescriptorType , class SourceType >
2. class TFiniteStateMachineManager
3. {
4. private :
6. StateMachineDescriptorType _Descriptor;
7. SourceType _Source;
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. // <......>

Again we deal with patterns. To be precise, the “Strategy” pattern is also presented here. Not only do we have a finite state machine itself on strategies, but also some kind of manager! I don’t hide it, I’ll say that the same manager is used to create a map of euphony, it only works with another special state machine. He, in fact, in general, all the same, that the KA slipped, if only the interface was the same. The manager takes this "slipped" spacecraft, and redirects all the work to him. One KA handles the rules of sound, the other - breaks the text into levels. This is the essence of the “Strategy” pattern: we configure our class with strategy objects that do the real work. For example, if it were necessary for me that when an event occurred, a filter was called, I could replace the EventType event, passing another class as a strategy that implements filters.

Copy Source | Copy HTML

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

In the Process () function, everything is simple. An _Machine state machine object is created, set up with a descriptor (transition table, initial state), and the recognition process starts in a loop. The “iterator” passed as the second parameter to the EventType class denotes the index of the character in the text. If the event caused, for example, the “Start word” status, then the index will be written into the RangeItem as BeginIndex. And vice versa: if the event is the end of a word (sentence, paragraph), then the index will be the end for the given range. So we get a list of RangeItem, correlated with the text.

Why did I put the word “iterator” in quotes? Because it is not a real iterator, but only an integer variable. But if it were necessary to make a truly universal manager, then we would have to abstract away from the event objects. The manager should not worry at all in which lists, tables or arrays the data is stored there, where they come from, how many elements, and in what order they are. And to ensure passage through them, one could use the Iterator pattern (Iterator, [1] , [2] ). Great changes would not be necessary to make the loop work with iterators:

Copy Source | Copy HTML

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

The result of this spacecraft will be split trees. Next you need to select areas for comparison from these partitions. The algorithm is pretty simple.
- For each text, plots are sorted in increasing length.
- A pattern of minimum compliance is compiled. It registers how many sections of the same length can be taken from all texts. If all texts have 10 paragraphs 1000 in length, and one text of such paragraphs is only 8, then the minimum correspondence is 8 sections. So - for every length.
- In accordance with the template selected sections of the texts.
- The algorithm alternately involves all levels: paragraphs, sentences and words.

Now we have samples, and we can begin to collect characteristics.