Структуры данных для разобранного предложения

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

Основной подход для такого рода вещей заключается в lex строке в последовательность токенов , а затем синтаксический анализ этой строки в так называемую абстрактное синтаксическое дерево . Это большая тема, но очень кратко:

Lexing означает разбиение вашей строки на разные логические токены. В вашем случае вы, вероятно, просто хотите, чтобы последовательность была разбита на открытые и закрытые скобки и метки. Таким образом, ваш токен является одним из "(", ")" или последовательностью непробельных символов, что не так.

Парсинг означает чтение этой последовательности символов и построение из нее древовидной структуры.

Сначала вам понадобится древовидная структура: в вашем случае это, вероятно, структура данных, состоящая из Sentence, который состоит из тега части речи и списка объектов, которые могут быть как словами, так и субстанциями. (Я предполагаю, что здесь нет интересной структуры: если вы знаете, что NN может содержать только слова, а NP может содержать только субстанции или что-то в этом роде, вы можете сделать здесь более богатую древовидную структуру.)

Далее вам нужно разобрать свои жетоны в это дерево. Простейшие способы сделать это довольно просты: например, похоже, что здесь вы можете просто написать функцию `parse (List tokens), которая ожидает, что первый токен будет открывающей скобкой, а второй - меткой, а затем рекурсивно потребляет токены из последовательности, пока не встретит токен с закрывающими скобками.

Эти темы являются предметом гигантских книг, множества библиотек и т. Д., Но, надеюсь, это поможет вам начать понимать, как решить проблему.

Answer 2

Вот очень наивная реализация, чтобы вы начали с некоторых идей. У него нет типизации, основанной на части речи, и при этом он не применяет никаких правил, кроме тех, которые я мог бы вывести из одного примера.

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);
    }
}

Answer 3

Я недавно сделал что-то подобное в Python. Я рассмотрю только часть о структурах данных:

Каждая часть речи является либо списком частей речи (нетерминалом), либо просто одним словом (терминалом). Таким образом, вы можете создавать классы что-то вроде:

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

interface PartOfSpeech { };

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

class Terminal implements PartOfSpeech {
    String word;
};

Это относительно нетипизированный: вашей программе нужно создавать только правильные их структуры (например, не делать VerbPhrase, состоящий из списка предложений - вы можете сделать это, но это бессмысленно!).

Альтернативный маршрут - определить более явную систему типов. Таким образом, вы можете определить классы для каждого типа части речи, например,

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 может быть неочевидной с самого начала. Начните с написания чего-то, что обрабатывает простые предложения, и посмотрите, как оно выглядит.

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

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. Или и т. Д.». Есть общий синтаксический анализатор, который пытается применить правила к списку слов, пока не получит дерево. (Вы можете увидеть грязный и недокументированный код на http://code.google.com/p/ejrh/source/browse/trunk/ircbot/nl.py.)

Здесь есть определенное количество комбинаторных взрывов. Возможно, его можно улучшить, введя новые типы частей речи или просто сделав некоторые его части необязательными: наличие правила для каждой возможной комбинации Article / Adjectives / AdjectiveClause / etc. присутствует / отсутствует, вы можете просто сделать их необязательными.