デコードアルゴリズム

8922 ワード
ダイナミック？プログラム アルゴリズム
音声認識機能は,有向図$G=(V,E)$において動的に計画されたアルゴリズムを用いることによって実現できる.各エッジ$(u,v)in E$に、有限音セット$sum$からの音声ラベル$sigma(u,v)$を付けます.図中の特定の頂点から$v_0 in V$から始まる各パスは、モデルに対応して可能な音声シーケンスを生成する.方向性のあるパスの場合、パス内のエッジのラベルの単純な連結としてラベルを定義します.
特定の音のシーケンスを探します
指定されたラベル付き図$G$、特定の頂点$v_0$および$sum$の音声シーケンス$sigma=$は、$G$から$V_を返す0$から始まるパスです.$s$はパスのラベルです(このようなパスがある場合).そうでなければ、NO-SUCH-PATHを返します
viterbi_graph.h 
#include 
#include 
#include 
#include "stdlib.h"
#include 
using namespace std;

#define MAXVEX 100

enum color{WHITE,GRAY,BLACK};
enum which_edge{NONE,TREE,BACK,FORWARD,CROSS};

typedef int status;
typedef string VertexType;
typedef int EdgeType;

typedef struct EdgeNode
{
    int Edgestart;
    int Edgeend;  //    ，          
    EdgeType weight;  //      

    int type;
    struct EdgeNode *next;  //      
}EdgeNode;

typedef struct VertexNode  //     
{
    VertexType data;  //   ，      

    int color;
    int touch,finish;   //           
    EdgeNode* FirstEdge;  //     
    int parent; //        
}VertexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList; //     
    int numNodes,numEdges;
}GraphAdjList;

void CreateALGraph(GraphAdjList *G)
{
    EdgeNode *e;
    cout<>G->numNodes>>G->numEdges;

    //        
    for(int i=0;inumNodes;i++)
    {
        cout<>G->adjList[i].data;
        G->adjList[i].FirstEdge=NULL;
        G->adjList[i].parent=-1;

        G->adjList[i].color=WHITE;
        G->adjList[i].touch=G->adjList[i].finish=-1;
    }

    int beg,end;
    for(int k=0;knumEdges;k++)
    {
        cout<>beg;

        cout<>end;

        e=(EdgeNode *)malloc(sizeof(EdgeNode));
        e->Edgeend=end;
        e->Edgestart=beg;
        e->weight=0;
        e->type=NONE;
        e->next=G->adjList[beg].FirstEdge;
        G->adjList[beg].FirstEdge=e;
    }
}

graph_algorithm.h 
#include "viterbi_graph.h"

int path_time=0;
int path_exist=0;
int path_print_signal=0;

void print_graph(GraphAdjList *G)
{
    EdgeNode *cur_edge;
    for(int i=0;inumNodes;i++)
    {
        cout<adjList[i].data<adjList[i].data;
        if(G->adjList[i].FirstEdge)
            cout<adjList[i].FirstEdge;cur_edge;cur_edge=cur_edge->next)
        {
            cout<Edgeend<adjList[start].color=GRAY;
    path_time++;
    G->adjList[start].touch=path_time;

    for(EdgeNode *cur_e=G->adjList[start].FirstEdge;cur_e;cur_e=cur_e->next)
    {
        if(cur_e->Edgeend==end)
        {
            path_exist=1;
        }
        if(path_exist==1)
            return;
        int cur_end=cur_e->Edgeend;
        if(G->adjList[cur_end].color==WHITE)
        {
            G->adjList->parent=start;
            DFS_visit(G,cur_end,end);
            cur_e->type=TREE;
        }
        else if(G->adjList[cur_end].color==GRAY)
        {
            cur_e->type=BACK;
        }
        else if(G->adjList[cur_end].color==BLACK)
        {
            if(G->adjList[start].touchadjList[end].touch)
                cur_e->type=FORWARD;
            else
                cur_e->type=CROSS;
        }
    }

    //G->adjList[start] has finished
    G->adjList[start].color=BLACK;
    path_time++;
    G->adjList[start].finish=path_time;
}

void DFS(GraphAdjList *G,int start,int end)
{
    for(int u=0;unumNodes;u++)
    {
        G->adjList[u].color=WHITE;
        G->adjList[u].parent=-1;
    }
    path_time=0;
    if(G->adjList[start].color==WHITE)
        DFS_visit(G,start,end);
}

void path_print(GraphAdjList *G,int start,int end)
{
    if(path_exist==1)
    {
        cout<adjList[start].FirstEdge;e_ptr;e_ptr=e_ptr->next)
        {
            if(e_ptr->Edgeend==end)
            {
                cout<adjList[start].FirstEdge;e_ptr;e_ptr=e_ptr->next)
            {
                if(e_ptr->type==TREE)
                    path_print(G,e_ptr->Edgeend,end);
            }
        }
    }
    else
    {
        cout<

viterbi_algorithm.cpp 
#include "graph_algorithm.h"

int main()
{
    GraphAdjList G;
    CreateALGraph(&G);

    print_graph(&G);

    int start,end;
    cout<>start;
    cout<>end;
    DFS(&G,start,end);
    cout<

アルゴリズム実行結果
ランダムウォーク
各エッジ$(u,v)/in E$は、頂点$u$から始まり、エッジ$(u,v)$を経て、対応する音を生成する確率を表す非負の確率$p(u,v)$に関連付けられると仮定する.いずれの頂点から射出される確率の和も1である.
1つのパス上の確率は、パス上のすべてのエッジの確率の積として定義されます.
じょうたいてんいかんすう
$v_から1$から$v_4$で、最大確率値は$0.8 times 1=0.8$です.
動的計画で実現できる状態遷移関数は次のとおりです.
answer=e->probability*DFS_compute(G,e->e_end,end);
//   G->adjlist[beg]       ，     
if(answer>G->adjlist[beg].res)
{
    G->adjlist[beg].res=answer;
    G->adjlist[beg].direction=e->e_end;
}

probability_graph.h 
#include 
#include 
#include "stdlib.h"

using namespace std;

#define MAXVEX 100

typedef int status;
typedef string VertexType;
typedef double EdgeType;

typedef struct Edge
{
    int e_start;
    int e_end;  //    
    EdgeType probability;  //      ，     

    struct Edge *next;
}Edge;

typedef struct Vertex
{
    VertexType data;
    Edge* head; //     

    int direction;  //              
    double res;  //         ，    -1
    //direction res   
}Vertex,adjvertex[MAXVEX];

typedef struct
{

    adjvertex adjlist; //     
    int numNodes,numEdges;
}GraphAdj;

void CreateGraph(GraphAdj *G)
{
    Edge *e;
    cout<>G->numNodes>>G->numEdges;

    //       
    for(int i=0;inumNodes;i++)
    {
        cout<>G->adjlist[i].data;
        G->adjlist[i].head=NULL;
        G->adjlist[i].direction=-1;
        G->adjlist[i].res=-1;
    }

    int beg,end;
    double prob;

    for(int k=0;knumEdges;k++)
    {
        cout<>beg;

        cout<>end;

        cout<>prob;

        e=(Edge *)malloc(sizeof(Edge));
        e->e_start=beg;
        e->e_end=end;
        e->probability=prob;

        e->next=G->adjlist[beg].head;
        G->adjlist[beg].head=e;

    }
}

viterbi_probability.h 
#include "probability_graph.h"

double answer=1;
double maxpath=0;
int path_exist=0;

int path_print_signal=0;
int has_founded[MAXVEX];

double DFS_compute(GraphAdj *G,int beg,int end);

double max(double a,double b)
{
    return a>b?a:b;
}

double DFSTraverse(GraphAdj *G,int beg,int end)
{
    for(int i=0;inumNodes;i++)
        has_founded[i]=0;

    maxpath=DFS_compute(G,beg,end);
    return maxpath;
}

double DFS_compute(GraphAdj *G,int beg,int end)
{
    if(beg==end)
    {
        answer=1;
        return 1;
    }
    for(Edge *e=G->adjlist[beg].head;e;e=e->next)
    {
        if(has_founded[beg]==1)
        {
            answer=G->adjlist[e->e_start].res;
            return G->adjlist[e->e_start].res;
        }
        if(has_founded[beg]==0)
        {
            if(e->e_end==end)
            {
                path_exist=1;
                answer=e->probability;
                if(answer>G->adjlist[e->e_start].res)
                {
                    G->adjlist[e->e_start].res=answer;
                    G->adjlist[e->e_start].direction=e->e_end;
                }
                return G->adjlist[e->e_start].res;
            }

            answer=e->probability*DFS_compute(G,e->e_end,end);
            //   G->adjlist[beg]       ，     
            if(answer>G->adjlist[beg].res)
            {
                G->adjlist[beg].res=answer;
                G->adjlist[beg].direction=e->e_end;
            }
        }        
    }
    //beg   answer        

    has_founded[beg]=1;
    return G->adjlist[beg].res;
}

void print_graph(GraphAdj *G)
{
    Edge *cur_edge;
    for(int i=0;inumNodes;i++)
    {
        cout<adjlist[i].data<adjlist[i].data;
        if(G->adjlist[i].head)
            cout<adjlist[i].head;cur_edge;cur_edge=cur_edge->next)
        {
            cout<e_end<

viterbi_probability.cpp 
#include "viterbi_probability.h"

int main()
{
    GraphAdj G;
    CreateGraph(&G);

    print_graph(&G);

    int start,end;
    cout<>start;
    cout<>end;

    double result=DFSTraverse(&G,start,end);
    cout<

アルゴリズム実行結果
素数判定アルゴリズムの実現
PythonがSSHクライアントを実現