Frases Randomicas

Programação Java
#1

Olá!

Alguém tem alguma idéia de algoritmo para realizar o seguinte problema.

Preciso gerar frases randômicas a partir de uma lista de regras de uma linguagem livre de contexto.
S -> NP VP

Ou seja, uma regra S vira uma regra NP e uma regra VP, porém estas regras possuem probabilidades, pois são construídas assim:
S -> NP VP 0.4
S -> PP VP 0.6

Ou seja a primeira regra S tem 40% de chance de acontecer e a segunda 60%, preciso de um algoritmo para escolher a melhor e continuar derivando as regras até chegarem no fim.

A gramática é a seguinte:
[ S ] > [ PES ] [ OBJ ] ;1
[ PES ] > [ SUJ ] [ VER ] ;0.3
[ PES ] > [ SUJ ] [ COMP ] ;0.4
[ PES ] > [ PES ] [ VER ] ;0.3
[ OBJ ] > [ PREP ] [ SUJ ] ;0.3
[ OBJ ] > [ NOM ] [ QUANT ] ;0.1
[ OBJ ] > [ PRON ] [ NOM ] ;0.1
[ OBJ ] > [ NOM ] [ ADV ] ;0.4
[ OBJ ] > [ PREP ] [ NOM ] ;0.1
[ LIG ] > [ VER ] [ ART ] ;1
[ NOM ] > [ ART ] [ NOM ] ;0.2
[ COMP ] > [ CON ] [ SUJ ] ;1
[ VER ] > [ NEG ] [ VER ] ;0.14

Só para exemplificar. As regras são vetores, [0] equivale ao primeiro valor, [1] e [2] ao segundo e terceiro respectivamente o [4] possui o valor da probabilidade.

Se alguém puder ajudar obrigado!
Se precisarem que eu esclareça mais, por favor.

#2

Vou dar um exemplo. Digamos que você tenha 3 resultados possíveis, um (A) com probabillidade de 0.2, outro (B) com probabilidade de 0.7 e o terceiro © com probabilidade de 0.1. (O total é 1.0, conforme você deve ter entendido).

Gere um número aleatório de 0.0 até 1.0. Se ele estiver entre 0 e 0.2, então escolha A; se ele estiver entre 0.2 e 0.9 (note que 0.9 = 0.2 + 0.7) então escolha B; e se ele estiver entre 0.9 e 1.0 (note que 1.0 = 0.2 + 0.7 + 0.1) escolha C.

A partir disso, você que é bem esperto pode gerar suas frases aleatórias. (A palavra em português é “aleatório”, embora eu ache que a palavra “randômico” possa ser encontrada no Aurélio - não tenho o dicionário aqui comigo para conferir.)

#3

[quote=entanglement]Vou dar um exemplo. Digamos que você tenha 3 resultados possíveis, um (A) com probabillidade de 0.2, outro (B) com probabilidade de 0.7 e o terceiro © com probabilidade de 0.1. (O total é 1.0, conforme você deve ter entendido).

Gere um número aleatório de 0.0 até 1.0. Se ele estiver entre 0 e 0.2, então escolha A; se ele estiver entre 0.2 e 0.9 (note que 0.9 = 0.2 + 0.7) então escolha B; e se ele estiver entre 0.9 e 1.0 (note que 1.0 = 0.2 + 0.7 + 0.1) escolha C.

A partir disso, você que é bem esperto pode gerar suas frases aleatórias. (A palavra em português é “aleatório”, embora eu ache que a palavra “randômico” possa ser encontrada no Aurélio - não tenho o dicionário aqui comigo para conferir.)

[/quote]
Sim sim, essa parte já tenho montada na minha cabeça, só preciso montar a estrutura toda, acho que uma árvore binária é o que eu preciso já que todas produções das regras são de 2 ou 1 resultado.

Alguma outra idéia?

Obrigado!

#4

Alguém?
Algum exemplo de montagem de árvore binária baseada em probabilidades?

Obrigado!

#5

Até agora consegui isto:

[code]package parser;

import java.util.ArrayList;

class no extends Parseador {

no noEsq;
no noDir;
String valor;
String[][] regras;

public void setRegras(String[][] regras) {
    this.regras = regras;
}

public no(String regra, String[][] regrasPai) {
    setRegras(regrasPai);
    valor = regra;
    System.out.println("Nó " + valor + " criado.");
    ArrayList<Integer> regrasUtilizadas = new ArrayList<Integer>();
    for (int i = 0; i < regras.length; i++) {
        if (regras[i][0].equalsIgnoreCase(valor)) {
            regrasUtilizadas.add(i);
        }
    }
    if (regrasUtilizadas == null)
    {
        System.out.println(valor);
    }
    else {
        constroiProbabilidades(regrasUtilizadas);
    }
}

public void constroiProbabilidades(ArrayList<Integer> regrasUtilizadas) {
    ArrayList<Double> prob = new ArrayList<Double>();
    double aux = 0;
    for (int i = regrasUtilizadas.get(0); i <= regrasUtilizadas.size(); i++) {
        aux = aux + Double.parseDouble(regras[i][3]);
        prob.add(aux);
    }
    double random = Math.random();
    System.out.println(random);
    int regraEscolhida = regrasUtilizadas.get(0);
    for (int j = 0; j < regrasUtilizadas.size(); j++) {
        if (j == 0 && random <= prob.get(0)) {
            geraNos(regraEscolhida, regrasUtilizadas);
        } else if (random > prob.get(j) && random <= prob.get(j + 1)) {
            regraEscolhida = regrasUtilizadas.get(j);
            geraNos(regraEscolhida, regrasUtilizadas);
        }
    }
}

public void ImprimeValor() {
    if (noDir == null) {
        System.out.println(valor);
    } else {
        noEsq.ImprimeValor();
        noDir.ImprimeValor();
    }
}

public void geraNos(int regraEscolhida, ArrayList<Integer> regrasUtilizadas) {
    String esq = regras[regrasUtilizadas.get(regraEscolhida)][1];
    String dir = regras[regrasUtilizadas.get(regraEscolhida)][2];
    System.out.println(esq);
    System.out.println(dir);

    
        noEsq = new no(esq, regras);
        if (regras[regrasUtilizadas.get(regraEscolhida)][2].equals("")) {
            System.out.println("teste");
            noDir = null;
        } else {
            System.out.println("teste");
            noDir = new no(dir, regras);
        }
    

}

}
[/code]

Mas a árvore fica criando nós recursivamente a esquerda :\

#6