基本原則

このテキストは、Strutext C ++テキスト処理ライブラリに関する投稿の続きです。ここでは、言語表現の字句レベルの実装、特に形態学の実装について説明します。

著者によると、言語表現の字句レベルのプログラムモデルを実装する際に解決しなければならない主なタスクは次のとおりです。

意味のある文字のチェーンのソーステキストからの分離。テキストを一連の単語として提示します。
字句タイプの要素として選択されたチェーンの識別。
その字句属性の選択されたチェーンの定義（詳細については以下を参照）。

字句タイプは、通常、言語の文で同じ意味を持つ文字の有限セットとして表されます。字句クラスの要素は通常、単語形式と呼ばれ、単語形式のセットはパラダイムと呼ばれ、字句タイプは単語または補題と呼ばれます。たとえば、字句タイプ「mom」は単語形式{mom、mom、mom、...、mom、mom、...}で構成されます。

字句タイプは、構文カテゴリー（品詞）に分類されます。スピーチの一部は、言語の文で単語が果たす役割を定義します。この役割は、文中の単語の正しい場所を決定するために重要であり、したがって、文の意味を決定する上で重要です。ロシア語のスピーチの有名な部分：名詞、形容詞、動詞、副詞など

字句タイプの単語形式にはプロパティがあります。このようなプロパティは、字句属性または字句属性とも呼ばれます。これらのプロパティのタイプは、指定された字句タイプが属する構文カテゴリに依存します。たとえば、ケースフォームは名詞にとって重要な役割を果たしますが、この属性は動詞には使用できません。

字句タイプをグループ化するために使用される特定の構文カテゴリとそれらが持つ字句属性は、実装される言語と実装される字句解析の具体的なモデルの両方に依存します。以下では、 AOTの字句モデルについて検討します。

語彙のあいまいさ

ソーステキストから単語を抽出するプロセスで、あいまいさが発生することがあります。ここでは、2つの属のあいまいさを考慮します。

第1種のあいまいさは、テキストから選択された字句タイプの文字列を割り当てるプロセスで発生します。「ママがフレームを洗った」という例を考えてみましょう。ここで、文字列「soap」は動詞「wash」になり、名詞「soap」にもなります。このようなあいまいな場合は、字句同音異義語とも呼ばれます。
第2種のあいまいさは、ソーステキストを単語のチェーンにカットするプロセスで発生します。ほとんどの自然言語では、単語はスペースで区切られていますが、この原則に違反することもあります（例として、ドイツ語の複合語）。しかし、プログラミング言語には興味深い例があります。たとえば、C ++で「a >> b」という形式の式を考えてみましょう。古典的なCでは、この式は明確に解釈されます：識別子「a」、右シフト演算子「>>」、識別子「b」。しかし、C ++の最近のバージョンでは、テンプレートがリストの最後のパラメーターとしても機能する場合、この式はテンプレートパラメーターのリストの最後を意味する場合があります。この場合、単語のシーケンスは次のようになります：識別子「a」、テンプレートパラメータのリストの終わり「>」、テンプレートパラメータのリストの終わり「>」、識別子「b」。

このテキストでは、第1種の語彙のあいまいさのみを考慮します。

AOT辞書の形態モデル

Strutextライブラリは、 AOTからの形態学的モデルを実装しています。したがって、その説明に特定の場所を与えます。

AOT辞書では、各字句タイプは2つのパラメーターによって定義されます。

接尾辞を追加して単語形式を形成するベース文字列（単語のルート）。
偏角パラダイムの番号。これはペアのリスト（接尾辞、一連の字句属性）です。

字句的特徴のセットの組み合わせは比較的少なく、それらは特別なファイルにリストされており、そのような組み合わせはそれぞれ2文字のコードでエンコードされています。例：

 A  ,,  A  ,,  A  ,,,2 ...  Y  ,,,,,  Y  ,,,,, ...  a  ,,1,  a  ,,1,  a  ,,2, ...

ここでは、各行の最初の要素はセットの2文字のコードであり、3番目の要素は品詞のコード（Cは名詞、Pは形容詞、Gは動詞など）であり、文法記号のコードはコンマでリストされています。

辞書記述ファイルは5つのセクションで構成されており、そのうち2つのセクションが最も重要です。赤緯のパラダイムの説明のこのセクションと、基本のセクション（字句タイプ）。このセクションの各行は、偏角のパラダイムを表しています。語彙タイプの説明のセクションでは、基礎とともに、赤緯パラダイムの行番号が設定されます。

たとえば、緑という言葉を考えてみましょう。 AOT辞書内のこの単語の字句タイプは、次の形式の文字列で与えられます

  15 12 1  -

ここで、番号15は、パラダイムセクションの赤緯パラダイム番号です。このパラダイムの行は次のようになります。

 %*%*%*%*%*%*%*%*%*%*%*%*%*

パラダイム内の各ペアは、シンボル「％」によって互いに分離され、ペアの要素はシンボル「*」によって互いに分離されます。最初のペア（KA、ha）は、green + ka = zelenkaという単語を定義し、字句属性のセットがあります：ha = G C zr、ed、im =名詞、女性、単数、主格。他のパラダイムペアはそれに応じて解読できます。

AOTで使用される単語エンコード方式には、長所と短所があります。ここではそれらについては説明しません。興味深い事実のみに注意してください。辞書には、空のベースを持つ字句タイプが含まれています。たとえば、複数形の「person」という単語は、「people」という単語形式で表されますが、「person」という形式とは共通の基礎がありません。したがって、この単語は、単語形式の単純な列挙によって設定する必要があります。

 %*%*%*%*%*%*%*%*%*%*%*%*%*%*%*%*

このパラダイムは、ゴッドマンやモンキーマンなどの他の単語（空でないルートを持つ）で使用できます。

構文カテゴリのセットと、AOT辞書の対応する字句属性をさらに詳しく考えてみましょう。

AOT構文のカテゴリ

前述のとおり、AOTディクショナリの構文カテゴリは別のファイルで定義され、2文字のコードに品詞と字句属性のセットが与えられた文字列のセットです。 Strutextライブラリでは、品詞とその属性はC ++のクラスの階層として表されます。この実装をより詳細に検討してください。

AOT辞書の構文カテゴリのモデルは、morpho / modelsディレクトリに定義されています。ロシア語と英語のモデルが表示されます。 morpho / models / rus_model.hファイルの一部のフラグメントを考えてみてください。これはロシア語モデルの説明を示しています。

すべてのモデルの基本クラスはPartOfSpeech抽象クラスで、列挙子として言語ラベルが含まれ、このラベルを返すための仮想メソッドも設定します。

 class PartOfSpeech : private boost::noncopyable { public: /// Type of smart pointer to the class object. typedef boost::shared_ptr<PartOfSpeech> Ptr; /// Language tag definitions. enum LanguageTag { UNKNOWN_LANG = 0 ///< Unknown language. , RUSSIAN_LANG = 1 ///< Russian language. , ENGLISH_LANG = 2 ///< English language. }; /// Language tag. virtual LanguageTag GetLangTag() const = 0; /// Virtual destruction for abstract class. virtual ~PartOfSpeech() {} };

ロシア語のすべての構文カテゴリの基本クラスは、このクラスから継承されます。

 struct RussianPos : public PartOfSpeech { /// Type of smart pointer to the class object. typedef boost::shared_ptr<RussianPos> Ptr; /// Possible parts of speech. enum PosTag { UNKNOWN_PS = 0 ///< Unknown part of speech. , NOUN_PS = 1 ///<  , ADJECTIVE_PS = 2 ///<  , PRONOUN_NOUN_PS = 3 ///< - , VERB_PS = 4 ///<     , PARTICIPLE_PS = 5 ///<  , ADVERB_PARTICIPLE_PS = 6 ///<  , PRONOUN_PREDICATIVE_PS = 7 ///< - , PRONOUN_ADJECTIVE_PS = 8 ///<   , NUMERAL_QUANTITATIVE_PS = 9 ///<  () , NUMERAL_ORDINAL_PS = 10 ///<   , ADVERB_PS = 11 ///<  , PREDICATE_PS = 12 ///<  , PREPOSITION_PS = 13 ///<  , CONJUCTION_PS = 14 ///<  , INTERJECTION_PS = 15 ///<  , PARTICLE_PS = 16 ///<  , INTRODUCTORY_WORD_PS = 17 ///<   , UP_BOUND_PS }; /// Number. enum Number { UNKNOUN_NUMBER = 0 ///< Unknown number. , SINGULAR_NUMBER = 0x01 ///< . , PLURAL_NUMBER = 0x02 ///< . }; /// Language. enum Lang { NORMAL_LANG = 0 // Normal language. , SLANG_LANG = 1 , ARCHAIZM_LANG = 2 , INFORMAL_LANG = 3 }; /// Gender definitions. enum Gender { UNKNOWN_GENDER = 0 ///< Unknown gender value. , MASCULINE_GENDER = 0x01 ///<  , FEMININE_GENDER = 0x02 ///<  , NEUTER_GENDER = 0x04 ///<  }; /// Case definition. enum Case { UNKNOWN_CASE = 0 ///< Unknown case. , NOMINATIVE_CASE = 1 ///<  , GENITIVE_CASE = 2 ///<  , GENITIVE2_CASE = 3 ///<   , DATIVE_CASE = 4 ///<  , ACCUSATIVE_CASE = 5 ///<  , INSTRUMENTAL_CASE = 6 ///<  , PREPOSITIONAL_CASE = 7 ///<  , PREPOSITIONAL2_CASE = 8 ///<   , VOCATIVE_CASE = 9 ///<  }; /// Time. enum Time { UNKNOWN_TIME = 0 ///< Unknown time. , PRESENT_TIME = 0x01 ///<  , FUTURE_TIME = 0x02 ///<  , PAST_TIME = 0x04 ///<  }; /// Person. enum Person { UNKNOWN_PERSON = 0 ///< Unknown person. , FIRST_PERSON = 0x01 ///<  , SECOND_PERSON = 0x02 ///<  , THIRD_PERSON = 0x04 ///<  }; /// Entity kind. enum Entity { UNKNOWN_ENTITY = 0 ///< Unknown entity, for ordinal words. , ABBREVIATION_ENTITY = 1 ///< . , FIRST_NAME_ENTITY = 2 ///< . , MIDDLE_NAME_ENTITY = 3 ///< . , FAMILY_NAME_ENTITY = 4 ///< . }; /// Animation. enum Animation { UNKNOWN_ANIMATION = 0 , ANIMATE_ANIMATION = 0x01 ///< . , INANIMATE_ANIMATION = 0x02 ///< . }; /// Voice defintion. enum Voice { UNKNOWN_VOICE = 0 ///< Unknown voice. , ACTIVE_VOICE = 0x01 ///<  . , PASSIVE_VOICE = 0x02 ///<  . }; /// Language tag. LanguageTag GetLangTag() const { return RUSSIAN_LANG; } /// Class is absract one -- virtual destruction. virtual ~RussianPos() {} /// Get part of speech tag. virtual PosTag GetPosTag() const = 0; /// Serialization implementaion. virtual void Serialize(uint32_t& out) const = 0; /// Desirialization implementation. virtual void Deserialize(const uint32_t& in) = 0; /// Write POS signature. static void WritePosSign(PosTag pos, uint32_t& out) { // Write to lower 5 bits. out |= static_cast<uint32_t>(pos); } /// Read POS signature. static PosTag ReadPosSign(const uint32_t& in) { return PosTag(in & 0x1f); } };

このクラスには、PosTag列挙子の形式で構文カテゴリのラベルが含まれており、字句属性が定義されています。文法コンポーネントに加えて、このクラスは、バイナリ形式との間で変換を行うためのSerializeおよびDeserializeメソッドを定義します。構文タイプごとに、uint32_tタイプで表される4バイトの変換が定義されています。

RussianPosクラスは抽象的であり、特定の構文カテゴリを表すクラスはそれから継承されます。たとえば、クラスNounは名詞を定義します。

 struct Noun : public RussianPos { Noun() : number_(UNKNOUN_NUMBER) , lang_(NORMAL_LANG) , gender_(UNKNOWN_GENDER) , case_(UNKNOWN_CASE) , entity_(UNKNOWN_ENTITY) {} /// Get part of speech tag. PosTag GetPosTag() const { return NOUN_PS; } /** * \brief Serialization implementaion. * * Binary map of the object: * 13 3 4 3 2 2 5 * ----------------------------------------------------------- * Unused | Entity | Case | Gender | Lang | Number | POS tag | * ----------------------------------------------------------- * * \param[out] ob The buffer to write to. */ void Serialize(uint32_t& ob) const { ob |= static_cast<uint32_t>(number_) << 5; ob |= static_cast<uint32_t>(lang_) << 7; ob |= static_cast<uint32_t>(gender_) << 9; ob |= static_cast<uint32_t>(case_) << 12; ob |= static_cast<uint32_t>(entity_) << 16; } /** * \brief Desirialization implementaion. * * Binary map of the object: * 13 3 4 3 2 2 5 * ----------------------------------------------------------- * Unused | Entity | Case | Gender | Lang | Number | POS tag | * ----------------------------------------------------------- * * \param ib The buffer to write to. */ void Deserialize(const uint32_t& ib) { number_ = static_cast<Number>((ib & 0x0060) >> 5); lang_ = static_cast<Lang>((ib & 0x0180) >> 7); gender_ = static_cast<Gender>((ib & 0x0e00) >> 9); case_ = static_cast<Case>((ib & 0xf000) >> 12); entity_ = static_cast<Entity>((ib & 0x070000) >> 16); } Number number_; Lang lang_; Gender gender_; Case case_; Entity entity_; };

名詞クラスには、数、言語の種類（通常、時代錯誤、口語など）、性別、大文字小文字、名前または略語の記号などの字句属性が格納されます。

辞書をコーディングするためのステートマシン

辞書を保存し、辞書から単語を効率的に抽出するために、Strutextライブラリはステートマシンを使用します。有限状態マシンは、オートマトンディレクトリ内の対応するC ++タイプによって定義されます。

有限状態マシンは、ある状態（シンボル、シンボル）を特定の状態に関連付ける遷移関数によって定義されることを思い出してください。デルタ：Q x V-> Q.状態マシンが作業を開始する1つの初期状態と、一定数の「許可」状態があります。マシンは文字ごとに入力行を読み取ります。現在の状態と読み取られた文字について、遷移関数が特定の状態に一致する場合、マシンはこの新しい状態に「移行」し、その後新しい文字の読み取りサイクルが再び開始されます。オートマトンは2つの場合に停止できます：ペアに遷移がない場合（現在の状態、文字の読み取り）、および文字チェーン全体が最後まで読み取られる場合。最初のケースでは、入力チェーンはマシンによって許可されていないと見なされます。2番目のケースでは、停止後にマシンが許容状態のいずれかにある場合、チェーンが許可されます。

したがって、入力チェーンの新しい文字が読み取られるたびに、オートマトンは新しい状態のペア（状態、シンボル）を見つけるタスクに直面します。 Strutextライブラリでは、この検索関数の実装はTransitionと呼ばれる別のクラスで強調表示されます。オートマトンは、各状態（オートマトン/ fsm.h）に対して定義された遷移クラスのオブジェクトの配列です。

 template <typename TransImpl> struct FiniteStateMachine { /// Type of transition table. typedef TransImpl Transitions; ... /// State definition. struct State { Transitions trans_; ///< Move table. bool is_accepted_; ///< Is the state accepptable. /// Default initialization. explicit State(bool is_accepted = false) : is_accepted_(is_accepted) {} }; /// Type of states' list. typedef std::vector<State> StateTable ... StateTable states_; ///< The table of states. };

ここで、TransImplテンプレートパラメーターは遷移関数を表します。

Strutextライブラリには、遷移関数を実装するための2つのメソッドがあります。 1つの方法は、通常のstd :: map（automata / flex_transitions.h）に基づいています。ここで、キーは文字コードであり、ステータス番号は値です。別の方法（automata / flat_transitions.h）は、配列が可能な文字コードに対応して割り当てられるときの疎配列に基づいています。配列の各要素にはステータスコードが含まれています。値ゼロは無効な状態のために予約されています。移行なしを意味します。値がゼロ以外の場合、このペア（配列インデックス=シンボルコード、配列セルの状態番号）が遷移を設定します。

FiniteStateMachineクラスは、このチェーンが許可されていることを除いて、入力チェーンについて何も言うことができません。許可されたチェーンに関する追加情報を保存するには、許可された状態に属性を追加する必要があります。これは、AttributeFsmテンプレートクラスで行われます。このクラスは、テンプレートのパラメーターとして、遷移関数の実装と有効化状態の属性タイプを受け取ります。属性は許可状態にアタッチできるだけでなく（これが理にかなっているかどうかは不明ですが）、状態に複数の属性をアタッチできることにも注意してください。それらはすべてベクトルに格納されます。

ディクショナリをステートマシンに保存すると、このディクショナリのステートマシンの遷移関数のツリー構造が定義されます。このような構造の場合、D。クヌートによって導入されたトライという用語も使用されます。 Strutextライブラリには、オートマタ/ trie.hファイルにこのようなステートマシンの実装があります。

 template <class Trans, typename Attribute> struct Trie : public AttributeFsm<Trans, Attribute> { /// Chain identifier type. typedef Attribute ChainId; /// Attribute FSM type. typedef AttributeFsm<Trans, Attribute> AttributeFsmImpl; /// Default initialization. explicit Trie(size_t rsize = AttributeFsmImpl::kReservedStateTableSize) : AttributeFsmImpl(rsize) {} /// It may be base class. virtual ~Trie() {} /** * \brief Adding chain of symbols. * * \param begin Iterator of the chain's begin. * \param end Iterator of the chain's end. * \param id Chain identifier. * * \return The number of last state of the chain. */ template <typename SymbolIterator> StateId AddChain(SymbolIterator begin, SymbolIterator end, const ChainId& id); /** * \brief Adding chain of symbols. * * \param begin Iterator of the chain's begin. * \param end Iterator of the chain's end. * * \return The number of last state of the chain. */ template <typename SymbolIterator> StateId AddChain(SymbolIterator begin, SymbolIterator end); /** * \brief Search of the passed chain in the trie * * \param begin Iterator of the chain's begin. * \param end Iterator of the chain's end. * \result The reference to the list of attributes of the chain if any. */ template <typename SymbolIterator> const typename AttributeFsmImpl::AttributeList& Search(SymbolIterator begin, SymbolIterator end) const; };

コードから、AddChainとSearchの2つの主要なメソッドがあることがわかります。後者の方法は、属性ベクトルへの参照を返すという点で注目に値します。検索時に、状態属性はコピーされません。入力文字列が見つからない場合、属性ベクトルは空になります。

Strutextライブラリは、テキスト内の辞書要素を効率的に検索するために、Aho-Korasikサブマシンガンも実装しています。実装は、automata / aho_corasick.hに示されています。その実装の原理と方法の提示は、このテキストの範囲を超えています。インターフェイスの使い方は非常に簡単であり、テキストにあるチェーンに沿ってイテレータもあります。

また、すべてのオートマトンはstd :: streamでシリアライズ/デシリアライズできることに注意してください。これにより、マシンをディスク上のファイルに保存できます。バイナリ形式の辞書のストレージとして使用します。

形態分析装置

モルフォロジーアナライザーは、morpho / morpholibディレクトリにあるライブラリです。メインインターフェースクラスMorphologistは、morpho / morpholib / morpho.hファイルにあります。

クラスのインターフェースと実装について説明する前に、まず、この実装の基礎となる基本原則について説明します。

まず、Trieクラスのオブジェクトに実装されている基本の辞書があります。

次に、偏角パラダイムが許容可能な状態で各ベースに割り当てられます（以前と同様、これはペアのベクトル（接尾辞、字句属性のセット）。属性セットはPartOfSpeechから継承されたクラスのインスタンスによって表されます）。

第三に、各字句タイプには一意の数値識別子、辞書の基底番号が与えられます。

したがって、転送された単語形式を単語として認識するためには、マシンの基底を検索する必要があり（この基底に対応する字句タイプの識別子が検索されます）、最後に対応する属性を検索します。これはすべて、基本を検索するときと、語尾を決定するときの両方で、あいまいさを考慮して実行する必要があります。検索のコードは次のとおりです。

 /** * \brief Implementation of morphological analysis of passed form. * * \param text Input text in UTF-8 encoding. * \param[out] lem_list List of lemmas within morphological attributes. */ void Analize(const std::string& text, LemList& lem_list) const { // The first phase. Go throw the passed word text, encode symbol // and remember symbol codes in the string. If found word base on // some position, remember attribute and position for an each // attribute. // Try starts with empty bases typedef std::list<std::pair<Attribute, size_t> > BaseList; BaseList base_list; strutext::automata::StateId state = strutext::automata::kStartState; if (bases_trie_.IsAcceptable(state)) { const typename Trie::AttributeList& attrs = bases_trie_.GetStateAttributes(state); for (size_t i = 0; i < attrs.size(); ++i) { base_list.push_back(std::make_pair(attrs[i], 0)); } } // Permorm the first phase. std::string code_str; typedef strutext::encode::Utf8Iterator<std::string::const_iterator> Utf8Iterator; for (Utf8Iterator sym_it(text.begin(), text.end()); sym_it != Utf8Iterator(); ++sym_it) { Code c = alphabet_.Encode(*sym_it); code_str += c; if (state != strutext::automata::kInvalidState) { state = bases_trie_.Go(state, c); if (bases_trie_.IsAcceptable(state)) { const typename Trie::AttributeList& attrs = bases_trie_.GetStateAttributes(state); for (size_t i = 0; i < attrs.size(); ++i) { base_list.push_back(std::make_pair(attrs[i], code_str.size())); } } } } // The second phase. Go throuth the found base list and find suffixes for them. // If suffixes have been found then add them to the lemma list. lem_list.clear(); for (BaseList::iterator base_it = base_list.begin(); base_it != base_list.end(); ++base_it) { AttrMap attr; attr.auto_attr_ = base_it->first; SuffixStorage::AttrList att_list; std::string suffix = code_str.substr(base_it->second); // If suffix is empty (empty suffix passed), add zero symbol to it. if (suffix.empty()) { suffix.push_back('\0'); } if (const SuffixStorage::AttrList* att_list = suff_store_.SearchAttrs(attr.line_id_, suffix)) { for (size_t i = 0; i < att_list->size(); ++i) { lem_list.push_back(Lemma(attr.lem_id_, (*att_list)[i])); } } } }

ご覧のとおり、決定アルゴリズムは2つの段階に分かれています。最初に、基本事項が強調表示されます（ここでは、空の基本事項の存在を検討する必要があります）。各ベースについて、入力チェーン内の位置が記憶されているため、終了を選択できます。第2段階では、選択した基本に対応するエンディングの検索が実行されます。語尾が指定された基底に対応する曲用パラダイムで見つかった場合、この語尾の語彙属性が単語の識別子とともに返されます。

Morphologistクラスは、ベース番号と送信された字句属性によって単語形式を生成するサービスも提供します。 Generateメソッドはこれを行います：

 /** * \brief Generate form. * * \param lem_id The lemma identifier. * \param attrs The attributes of the form. * \return Generated text in UTF-8 encoding. */ std::string Generate(uint32_t lem_id, uint32_t attrs) const;

指定された単語のすべての形式を生成するGenAllFormsメソッドと、単語のメイン形式を返すGenMainFormメソッドもあります。名詞の場合、これは明らかに主格の単数形です。

main.cppファイルのmorpho / aotディレクトリは、元の形式のAOT辞書表現のパーサーを実装します。これにより、結果として、形態ライブラリと互換性のあるバイナリ表現が返されます。結果のバイナリ辞書は、Morphologistクラスで使用できます。バイナリ辞書自体はリポジトリに保存されませんが、必要に応じてユーザーが生成できます。ロシア語辞書を実装するには、次のコマンドを使用できます。

 ./Release/bin/aot-parser -t ../morpho/aot/rus_tabs.txt -d ../morpho/aot/rus_morphs.txt -m rus -b aot-rus.bin

バイナリ形式では、辞書の辞書サイズは20 MB未満です。

ソーステキストから単語フォームを分離するには、utility / word_iterator.hで定義されているWordIteratorクラスを使用できます。このクラスは、文字の単語シーケンス（シンボル:: IsLetter）を考慮します。イテレータは、単語をユニコード文字列として返します。 encode :: utf8_generator.hで定義されているGetUtf8Sequence関数を使用して、この文字列をUTF-8にトランスコードできます。

あとがき

テキストはかなりボリュームがあり、おそらく読みにくいことが判明しました。著者はプレゼンテーションを単純化することを試みましたが、それは可能な限りでしたが、資料の複雑さを考えると、明らかにテキストには多くの場所がありませんでした。

それでも、著者は、テキストで説明されているStrutextライブラリが有用であり、その実装に関する作業が無駄にならないことを期待しています。

C ++でのワードプロセッシングのStrutextライブラリ-字句レベルの実装