データ構造

Question

例文を見つけてください：

(S1 (S (S (NP (NP (NP (NN Activation)) (PP (IN of) (NP (NN protein) (NN kinase) (NN C)))) (CC and) (NP (NP (NN elevation)) (PP (IN of) (NP (NN cAMP))))) (VP (VBP interact) (ADVP (RB synergistically)) (S (VP (TO to) (VP (VB raise) (NP (NP (NP (NP (NN c-Fos)) (CC and) (NP (NN AP-1))) (NN activity)) (PP (IN in) (NP (NN Jurkat) (NNS cells))))))))) (. .))) 

目的はこの文からツリーを作成することです。葉は単語であり、中間ノードは音声タグの一部であり、根はS1である。かっこは、文の中に含まれる語句のスパンを示す。それらはツリーに含める必要はありません。

上記の目的を達成するためのデータ構造の良い組み合わせと、提案をサポートする擬似コードを共有することができますか？

私はHashMapとArrayListを念頭に置いていますが、実際に実装を開始する方法は混乱しています。ただ、この時点で論理が直感的にわたしには届かないということです。あなたの提案は高く評価されます。

ありがとうございました。その後、

Answer 1

私は最近Pythonで同様のことをしました。

各品詞は、品詞のリスト（非終端記号）または単一の単語（端末）のいずれかです。これは比較的型なしではありません

enum Type { 
    Sentence, 
    NounPhrase, 
    VerbPhrase, 
    Conjunction, 
    ... 
}; 

interface PartOfSpeech { }; 

class NonTerminal implements PartOfSpeech { 
    Type type; 
    List<PartOfSpeech> subparts; 
}; 

class Terminal implements PartOfSpeech { 
    String word; 
}; 

：だからクラスにのようなものを作成することができ、あなたのプログラムは、これらの唯一の有効なstruturesを構築する必要があります（たとえば、何の文章のリストからなる動詞句を作る - あなたはそれを行うことができますが、それはです意味がない！）。

代替ルートは、より明示的な型システムを定義することです。したがって、品詞の各タイプに対してクラスを定義することができます。

class VerbPhrase { 
    Verb verb; 
    AdverbPhrase adverb; /* optional */ 
    ... 
}; 

動詞句を作るいくつかの方法があるので、あなたの代わりに、各タイプのためのクラスを持つことができます：ように

interface VerbPhrase { }; 

class IntransitiveVerbPhrase implements VerbPhrase { 
    Verb verb; 
    AdverbPhrase adverb; /* optional */ 
}; 

class TransitiveVerbPhrase implements VerbPhrase { 
    Verb verb; 
    AdverbPhrase adverb; /* optional */ 
    NounPhrase obj; 
}; 

とします。 Javaレベルでの最適なタイプのExploitnessの程度は、最初は明白ではないかもしれません。まず、簡単な文章を扱い、それがどのように感じられるかを見てみましょう。

私のケースでは、それぞれがターミナルまたは非ターミナルのいずれかから継承していますが、スピーチタイプの各部分のクラスを作成しました。それから、どのように各タイプを構築できるかについてのルールがあります。これは、それらのいくつかのために一種の混乱しました。

、言うためのコードです

add_rule(NounPhrase, [Noun]) 
add_rule(NounPhrase, [RelativeNounWord]) 
add_rule(NounPhrase, [Noun, AdjectiveClause]) 
add_rule(NounPhrase, [Article, Noun]) 
add_rule(NounPhrase, [Article, Adjectives, Noun]) 
add_rule(NounPhrase, [Article, Noun, AdjectiveClause]) 
add_rule(NounPhrase, [Article, Adjectives, Noun, AdjectiveClause]) 
add_rule(NounPhrase, [Adjectives, Noun]) 
add_rule(NounPhrase, [Adjectives, Noun, AdjectiveClause]) 
add_rule(NounPhrase, [Article, Adjectives, Noun]) 
... 

「名詞句が名詞である。あるいは、それはAdjectiveClause続く名詞だ、RelativeNoun。またはです。または、等」。ツリーを取得するまで、単語のリストにルールを適用しようとする一般的なパーサがあります。 （http://code.google.com/p/ejrh/source/browse/trunk/ircbot/nl.pyに乱雑で文書化されていないコードを見ることができます）

ここにはある程度の組み合わせの爆発があります。品詞/品詞/ AdjectiveClause /などのすべての可能な組み合わせに規則を持たせることで、新しい種類の品詞を導入するか、またはその一部をオプションにするだけで、多分改善する可能性があります。存在/欠席、あなたはそれらをオプションにすることができます。

Answer 2

この種のもののための基本的なアプローチはトークンのシーケンスにlexのに文字列であり、かつ抽象構文木と呼ばれるものの中にその文字列を解析します。これは大きな話題ですが、非常に簡単です：

レキシングは、文字列を別の論理トークンに分割することを意味します。あなたの場合、たぶん、シーケンスを開いたカッコと閉じたカッコとラベルに分割するだけです。したがって、あなたのトークンは、 "（"、 "）"、またはそれ以外の非空白文字のシーケンスの1つです。

構文解析は、その文字列を読み取り、その中からツリー構造を構築することを意味します。

まず、ツリー構造が必要です。おそらく、品詞タグと単語またはサブセントのいずれかになるオブジェクトのリストで構成されるSentenceで構成されるデータ構造になるでしょう。 （ここで興味深い構造はないと思っています。NNには単語しか入れることができないと知っていれば、NPにはサブセンスなどが含まれていて、ここではより豊かなツリー構造を作ることができます）。

次に解析する必要がありますあなたのトークンをこのツリーに入れます。これを行う最も簡単な方法は非常に簡単です：たとえば、最初のトークンがオープンカッコで、2番目のトークンがラベルで、次に再帰的になると期待する関数 `parse（List tokens）トークンを閉じる括弧のトークンが出現するまでシーケンスからトークンを消費します。

これらのトピックは、巨大な書籍や数多くの図書館の主題ですが、これにより、問題へのアプローチ方法を十分に理解できるようになります。

Answer 3

ここでは、いくつかのアイデアを始めるのに非常に素朴な実装です。それは、品詞に基づいてタイピングをしていないし、単一の例から推測できるものを超えて何らかの規則を強制するものでもない。

class Node { 
    String partOfSpeech; 

    Node(String partOfSpeech) { 
     this.partOfSpeech = partOfSpeech; 
    } 

    String toString() { 
     return "(" + partOfSpeech + " " + getInternalString() + ")"; 
    } 

    abstract String getInternalString(); // could use a better name 
    abstract String toSentence(); 
} 

class Word extends Node { 
    String word; 

    Word(String partOfSpeech, String word) { 
     super(partOfSpeech); 
     this.word = word; 
    } 

    String getInternalString() { 
     return word; 
    } 

    String toSentence() { 
     return word; 
    } 
} 

class Phrase extends Node { 
    List<Node> children; 

    Phrase(String partOfSpeech) { 
     super(partOfSpeech); 
     this.children = new ArrayList<Node>(); 
    } 

    add(Node child) { 
     children.add(child); 
    } 

    String getInternalString() { 
     return combineChildren(false); 
    } 

    String toSentence() { 
     return combineChildren(true); 
    } 

    private String combineChildren(boolean sentence) { 
     StringBuilder result = new StringBuilder(); 
     for (Node child : children) { 
      sentenct.append(sentence ? child.toSentence() : child.toString()).append(' '); 
     } 
     return result.substring(0, result.length() - 1); 
    } 
}