端末の所定の数の文法から文を生成します

StackOverflow https://stackoverflow.com/questions/966576

質問

の

（出力がより自然に見えるように更新）：

のようにあなたは、おもちゃの文法を持っていると言います 

S -> ${NP} ${VP} | ${S} and ${S} | ${S}, after which ${S}

NP -> the ${N} | the ${A} ${N} | the ${A} ${A} ${N}

VP -> ${V} ${NP}

N -> dog | fish | bird | wizard

V -> kicks | meets | marries

A -> red | striped | spotted

例えば、「犬は赤ウィザードを蹴る」、「鳥は、斑点の魚を満たしているか、ウィザードはストライプ犬と結婚する」

どのようにそれが N の対+として+ Nsとの合計を含んでいなければならないという制約に応じて、この文法から文を生成することができます。文は、その多くの端末が含まれている必要があり整数を指定します。 （可能な最小この文法におけるコースのメモ N のである3）。

役に立ちましたか？

解決

次のPythonコードは、端末の所定の数のランダムな文を生成します。 これは、所与の長さの文を生成する方法の数を数える大きな乱数を生成し、指示文を計算することによって動作します。 カウントはメモ化して、再帰的に行われています。 nは0,0文そうでない場合は、空の右側は、1文を生成します。 空でない右辺によって生成される文の数、Iにわたる和、右辺の最初のシンボルで使用される端末の数をカウントします。 各iについて、最初のシンボルの可能性の数で右側の残りの可能性の数を掛けます。 最初のシンボルが端末である場合、私はそれ以外の場合は1と0である場合、1つの可能性があります。 最初のシンボルが非終端である場合、各選択肢を超える可能性をまとめます。 無限ループを回避するために、我々は、数量が0であるとき、再帰呼び出しを剪定して注意する必要があります。 これは無限ループまだ文法は一つの文章の無限に多くの派生を持っている場合があります。 例えば、文法内の

S -> S S
S ->
S =>、S => S S =>、S => S S => S S S =>など

空の文の無限に多くの派生が存在します 特定の文を見つけるためのコードは、それらをカウントするためのコードの簡単な変更です。 このコードは、1秒未満で100の端子各100文を生成し、合理的に効率的である。

import collections
import random

class Grammar:
    def __init__(self):
        self.prods = collections.defaultdict(list)
        self.numsent = {}
        self.weight = {}

    def prod(self, lhs, *rhs):
        self.prods[lhs].append(rhs)
        self.numsent.clear()

    def countsent(self, rhs, n):
        if n < 0:
            return 0
        elif not rhs:
            return 1 if n == 0 else 0
        args = (rhs, n)
        if args not in self.numsent:
            sym = rhs[0]
            rest = rhs[1:]
            total = 0
            if sym in self.prods:
                for i in xrange(1, n + 1):
                    numrest = self.countsent(rest, n - i)
                    if numrest > 0:
                        for rhs1 in self.prods[sym]:
                            total += self.countsent(rhs1, i) * numrest
            else:
                total += self.countsent(rest, n - self.weight.get(sym, 1))
            self.numsent[args] = total
        return self.numsent[args]

    def getsent(self, rhs, n, j):
        assert 0 <= j < self.countsent(rhs, n)
        if not rhs:
            return ()
        sym = rhs[0]
        rest = rhs[1:]
        if sym in self.prods:
            for i in xrange(1, n + 1):
                numrest = self.countsent(rest, n - i)
                if numrest > 0:
                    for rhs1 in self.prods[sym]:
                        dj = self.countsent(rhs1, i) * numrest
                        if dj > j:
                            j1, j2 = divmod(j, numrest)
                            return self.getsent(rhs1, i, j1) + self.getsent(rest, n - i, j2)
                        j -= dj
            assert False
        else:
            return (sym,) + self.getsent(rest, n - self.weight.get(sym, 1), j)

    def randsent(self, sym, n):
        return self.getsent((sym,), n, random.randrange(self.countsent((sym,), n)))

if __name__ == '__main__':
    g = Grammar()
    g.prod('S', 'NP', 'VP')
    g.prod('S', 'S', 'and', 'S')
    g.prod('S', 'S', 'after', 'which', 'S')
    g.prod('NP', 'the', 'N')
    g.prod('NP', 'the', 'A', 'N')
    g.prod('NP', 'the', 'A', 'A', 'N')
    g.prod('VP', 'V', 'NP')
    g.prod('N', 'dog')
    g.prod('N', 'fish')
    g.prod('N', 'bird')
    g.prod('N', 'wizard')
    g.prod('V', 'kicks')
    g.prod('V', 'meets')
    g.prod('V', 'marries')
    g.prod('A', 'red')
    g.prod('A', 'striped')
    g.prod('A', 'spotted')
    g.weight.update({'and': 0, 'after': 0, 'which': 0, 'the': 0})
    for i in xrange(100):
        print ' '.join(g.randsent('S', 3))

他のヒント

おそらくない最良の解決策が、私は戻ってポップや文法に沿って別のパスを探るそして、制約を超えましたまで、私は、再帰的な文法の各ルールを通じて自分の道を働くと思います。制約を満たすすべての文章をキープしていないすべての文章を捨てます。

例えば、n = 3：

S - >（$ {NP} $ {VP}） - >（（$ {N}）$ {VP}） - >（（（犬）$ {VP}） - > ... - >（（（犬）（（キック）（$ {NP}）））） - >（（（犬）（（キック）（（イヌ）））））

そして

バックポップ

（（（犬）（（キック）（$ {N}）））） - >（（（犬）（（キック）（（FISH）））））

としばらく後に...

（（（犬）（$ {V} $ {N}））） - >（（（犬）（（満たす）$ {N}））） - >（（（犬）（（満たしている）（犬））））

など。

本質的に深さ優先グラフ探索、自分だけがそれを検索しているのようにしてグラフを作成している（あなたが制約を超えて部品を構築停止）。

この質問はカテゴリのエラーが含まれています。あなたが指定した文法は文脈自由文法の外観を持っていますが、ターミナルノードの特定の数があることが要件は帰納的可算文法を必要とします。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top