2019-01-16

Viterbi

转载自：

作者：Kiwee
链接：https://www.zhihu.com/question/20136144/answer/239971177
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最高票的回答结果是正确的，但是并没有把viterbi算法讲明白，尤其是其中的dp思想。可以用相同的例子来解释：

1.题目背景：

从前有个村儿，村里的人的身体情况只有两种可能：健康或者发烧。
假设这个村儿的人没有体温计或者百度这种神奇东西，他唯一判断他身体情况的途径就是到村头我的偶像金正月的小诊所询问。
月儿通过询问村民的感觉，判断她的病情，再假设村民只会回答正常、头晕或冷。
有一天村里奥巴驴就去月儿那去询问了。
第一天她告诉月儿她感觉正常。
第二天她告诉月儿感觉有点冷。
第三天她告诉月儿感觉有点头晕。
那么问题来了，月儿如何根据阿驴的描述的情况，推断出这三天中阿驴的一个身体状态呢?
为此月儿上百度搜 google ，一番狂搜，发现维特比算法正好能解决这个问题。月儿乐了。

2.已知情况：

隐含的身体状态 = { 健康 , 发烧 }

可观察的感觉状态 = { 正常 , 冷 , 头晕 }

月儿预判的阿驴身体状态的概率分布 = { 健康：0.6 , 发烧： 0.4 }
这就是初始状态序列。

月儿认为的阿驴身体健康状态的转换概率分布 = {
健康->健康： 0.7 ,
健康->发烧： 0.3 ,
发烧->健康：0.4 ,
发烧->发烧： 0.6
}

这样就可以列出相应的状态转移矩阵。（人懒。。不想编辑公式了）

月儿认为的在相应健康状况条件下，阿驴的感觉的概率分布 = {
健康，正常：0.5 ，冷：0.4 ，头晕： 0.1 ；
发烧，正常：0.1 ，冷：0.3 ，头晕： 0.6
}

这样就可以列出相应的观测矩阵。

由上面我们可以发现，HMM的三要素都齐备了，下面就是解决问题了。
阿驴连续三天的身体感觉依次是：正常、冷、头晕。

3.题目：

已知如上，求：阿驴这三天的身体健康状态变化的过程是怎么样的？即已知观测序列和HMM模型的情况下，求状态序列。
4.过程：

初始化。第一天的时候，对每一个状态（健康或者发烧），分别求出第一天身体感觉正常的概率：P(第一天健康) = P(正常|健康)*P(健康|初始情况) = 0.5 * 0.6 = 0.3 P(第一天发烧) = P(正常|发烧)*P(发烧|初始情况) = 0.1 * 0.4 = 0.04
第二天的时候，对每个状态，分别求在第一天状态为健康或者发烧情况下观察到冷的最大概率。在维特比算法中，我们先要求得路径的单个路径的最大概率，然后再乘上观测概率。P(第二天健康) = max{0.30.7, 0.040.4}0.4=0.30.70.4=0.084 此时我们需要记录概率最大的路径的前一个状态，即0.084路径的前一个状态，我们在小本本上记下，第一天健康。 P(第二天发烧)=max{0.30.3, 0.04*0.6}*0.3=0.027, 同样的在0.027这个路径上，第一天也是健康的。
第三天的时候，跟第二天一样。P(第三天健康)=max{0.0840.7, 0.0270.4}0.1=0.00588，在这条路径上，第二天是健康的。P(第三天发烧)=max{0.0840.3, 0.027*0.6}*0.6=0.01512,在这条路径上，第二天是健康的。
最后一天的状态概率分布即为最优路径的概率，即P(最优)=0.01512，这样我们可以得到最优路径的终点，是发烧
由最优路径开始回溯。请看我们的小本本，在求得第三天发烧概率的时候，我们的小本本上面写的是第二天健康，好了，第二天就应该是健康的状态，然后在第二天健康的情况下，我们记录的第一天是健康的。这样，我们的状态序列逆推出来了。即为：健康，健康，发烧。
简略的画个图吧：

这儿的箭头指向就是一个回溯查询小本本的过程，我们在编写算法的时候，其实也得注意，每一个概率最大的单条路径上都要把前一个状态记录下来。

2018-12-21

使用—软件—Antlr4

Antlr4+python3-visitor使用（四则运算解析）

Antlr系列（配合Python3）文章：https://www.jianshu.com/nb/32570686

Visitor实现四则运算的计算

文法规则文件Expr.g4：

grammar Expr;		
prog:	expr NEWLINE            # printExpr;
expr:	left=expr op=('*'|'/') right=expr   # mulDiv    // 用来确定优先级，在上面的优先级高
    |	left=expr op=('+'|'-') right=expr   # addSub
    |	INT                     # int
    |	'(' expr ')'            # brackets
    ;
NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

MUL     : '*' ;  // 用来便于当作常量引用
DIV     : '/' ;
ADD     : '+' ;
SUB     : '-' ;

在执行antlr4的时候需要指明-no-listener和-visitor，因此执行antlr4 -no-listener -visitor -Dlanguage=Python3 Expr.g4

创建文件Expr.py：

import sys
from antlr4 import *
from ExprLexer import ExprLexer
from ExprParser import ExprParser
from ExprVisitor import ExprVisitor
 
class ExprCalculateVisitor(ExprVisitor):
    def visitPrintExpr(self, ctx):
        # 函数名enterR的R指的是非终结符r
        val = self.visit(ctx.expr())
        print(val)
        return val

    def visitBrackets(self, ctx):
        return self.visit(ctx.expr())
    
    def visitAddSub(self, ctx):
        if ctx.op.type == ExprParser.ADD:
            return self.visit(ctx.left) + self.visit(ctx.right)
        else:
            return self.visit(ctx.left) - self.visit(ctx.right)

    def visitMulDiv(self, ctx):
        if ctx.op.type == ExprParser.MUL:
            return self.visit(ctx.left) * self.visit(ctx.right)
        else:
            return self.visit(ctx.left) / self.visit(ctx.right)

    def visitInt(self, ctx):
        return int(ctx.getText())


def main():
    lexer = ExprLexer(StdinStream())
    stream = CommonTokenStream(lexer)
    parser = ExprParser(stream)
    tree = parser.prog()
    calculator = ExprCalculateVisitor()
    calculator.visitPrintExpr(tree)
 
if __name__ == '__main__':
    main()

这里的visitXXX的XXX部分都是上面#后的内容；如果不写#后的东西，就会是visitProg之类的

之后仍然是运行并且输入后回车输入EOF（Ctrl-D/Ctrl-Z）即可看到结果输出

2018-12-21

使用—软件—Antlr4

Antlr4+python3安装&示例程序

Antlr系列（配合Python3）文章：https://www.jianshu.com/nb/32570686

Ubuntu安装

安装方法：（来自官网首页，Quick Start）

$ cd /usr/local/lib
$ wget https://www.antlr.org/download/antlr-4.7.2-complete.jar
$ export CLASSPATH=".:/usr/local/lib/antlr-4.7.2-complete.jar:$CLASSPATH"
$ alias antlr4='java -jar /usr/local/lib/antlr-4.7.2-complete.jar'
$ alias grun='java org.antlr.v4.gui.TestRig'

直接运行antlr4和grun出现帮助信息就说明成功。

第二步下载的时候如果权限不够，就sudo下载并且之后sudo chmod 777 antlr-4.7.2-complete.jar

然后为方便使用，在.bashrc里面添加后三行：

1
2
3

export CLASSPATH=".:/usr/local/lib/antlr-4.7.2-complete.jar:$CLASSPATH"
alias antlr4='java -jar /usr/local/lib/antlr-4.7.2-complete.jar'
alias grun='java org.antlr.v4.gui.TestRig'

一定要注意这里的classpath里面要有.

Windows安装

添加下载的jar文件与.添加到CLASSPATH中，同时在Path内的路径里面建立两个bat文件：

antlr4.bat

1	java org.antlr.v4.Tool %*

grun.bat

1	java org.antlr.v4.gui.TestRig %*

要特别注意，.一定要添加到CLASSPATH中！！！！！！！

使用

（官方GetStarted：https://github.com/antlr/antlr4/blob/master/doc/getting-started.md

创建文件Hello.g4，如下：

grammar Hello;
r  : 'hello' ID ;         // match keyword hello followed by an identifier
ID : [a-z]+ ;             // match lower-case identifiers
WS : [ \t\r\n]+ -> skip ; // skip spaces, tabs, newlines

执行antlr4 Hello.g4和javac Hello*.java

之后grun Hello r -tree或者grun Hello r -gui，输入某一个输入串（如hello pjio）后回车并按下Ctrl-D（Windows下为Ctrl-Z），就可以看到解析结果。

这里的r表示的是第二行的起始符号r

python部分

（官方说明：https://github.com/antlr/antlr4/blob/master/doc/python-target.md

准备python库：

pip install antlr4-python3-runtime

执行antlr4，其中需要声明Dlanguage：antlr4 -Dlanguage=Python3 Hello.g4 （注意是Python3，P要大写！）

之后在那个执行antlr4的目录下，创建以下程序并运行：

import sys
from antlr4 import *
from HelloLexer import HelloLexer
from HelloParser import HelloParser
from HelloListener import HelloListener
 
class HelloPrintListener(HelloListener):
    def enterR(self, ctx):
        # 函数名enterR的R指的是非终结符r
        print("Hello: %s" % ctx.ID())


def main():
    lexer = HelloLexer(StdinStream())
    stream = CommonTokenStream(lexer)
    parser = HelloParser(stream)
    tree = parser.r()
    printer = HelloPrintListener()
    walker = ParseTreeWalker()
    walker.walk(printer, tree)
 
if __name__ == '__main__':
    main()

还是直接启动后输入hello wjgoiwejgoiw并且回车，输入Ctrl-D或者Ctrl-Z（Windows）

2018-12-03

领域—测试

Test分类与区别

https://blog.csdn.net/rickenwang/article/details/78033575

2018-11-09

使用—软件—Selenium

服务器selenium截图中文问题

https://blog.csdn.net/weixin_39792252/article/details/80415550

sudo apt-get install fonts-droid-fallback ttf-wqy-zenhei ttf-wqy-microhei fonts-arphic-ukai fonts-arphic-uming

2018-11-08

使用—服务器

apt-get-problem-with-merge-list

https://askubuntu.com/questions/30072/how-do-i-fix-a-problem-with-mergelist-or-status-file-could-not-be-parsed-err

sudo rm -vf /var/lib/apt/lists/*

sudo apt-get update

2018-10-23

语言—C++

printf不显示

需要缓冲区满或者scanf或者fflush(stdout);或者有\n才显示。

2018-10-17

使用—软件—其他

django-rander导致网址被转义

网址中具有的&符号可能被django转义。

解决：可以把改为

2018-10-16

使用—软件—其他

Pycharm-search-in-path-快捷键冲突

Ctrl-Alt-F快捷键在Win10自带中文输入法下是切换繁体简体的，但是该快捷键同时也是Pycharm等的search in path快捷键

2018-10-16

领域—Win32桌面程序

Win32-编程添加控件及监听

Win32编程系列文章：https://www.jianshu.com/nb/30332818

添加控件

在Hello World基础上，添加：

wWinMain内部创建变量，使用的是如下的方法：

//创建静态文本控件
HWND hStatic = CreateWindow(
	TEXT("static"),  //静态文本框的类名
	TEXT("hahaha"),  //控件的文本
	WS_CHILD /*子窗口*/ | WS_VISIBLE /*创建时显示*/ | WS_BORDER /*带边框*/,
	120 /*X坐标*/, 20/*Y坐标*/, 150/*宽度*/, 80/*高度*/, hwnd/*父窗口句柄*/,
	(HMENU)1,  //为控件指定一个唯一标识符
	hInstance,  //当前实例句柄
	NULL
);

类似可以创建按钮、输入框等，如下：

// 下面一行代码创建输入框
CreateWindow(L"EDIT", 0, WS_BORDER | WS_CHILD | WS_VISIBLE, 56, 10, 50, 18, hwnd, 0, hInstance, 0);

// 下面一行代码创建按钮
my_button = CreateWindow(L"BUTTON", L"一个按钮", WS_CHILD | WS_VISIBLE, 70, 70, 80, 25, hwnd, (HMENU)8, hInstance, 0);

创建下拉框的时候会比较麻烦，需要绑定数据，如下所示：

TCHAR Planets[9][10] =
{
	TEXT("Mercury"), TEXT("Venus"), TEXT("Terra"), TEXT("Mars"),
	TEXT("Jupiter"), TEXT("Saturn"), TEXT("Uranus"), TEXT("Neptune"),
	TEXT("Pluto??")
};

int xpos = 100;            // Horizontal position of the window.
int ypos = 100;            // Vertical position of the window.
int nwidth = 200;          // Width of the window
int nheight = 200;         // Height of the window
HWND hwndParent = hwnd; // Handle to the parent window

HWND hWndComboBox = CreateWindow(L"COMBOBOX", TEXT(""),
	CBS_DROPDOWN | CBS_HASSTRINGS | WS_CHILD | WS_OVERLAPPED | WS_VISIBLE,
	xpos, ypos, nwidth, nheight, hwndParent, NULL, hInstance,
	NULL);

TCHAR A[16];
int  k = 0;

memset(&A, 0, sizeof(A));
for (k = 0; k <= 8; k += 1)
{
	wcscpy_s(A, sizeof(A) / sizeof(TCHAR), (TCHAR*)Planets[k]);

	// Add string to combobox.
	SendMessage(hWndComboBox, (UINT)CB_ADDSTRING, (WPARAM)0, (LPARAM)A);
}

// Send the CB_SETCURSEL message to display an initial item 
//  in the selection field  
SendMessage(hWndComboBox, CB_SETCURSEL, (WPARAM)2, (LPARAM)0);

绑定事件

在WindowProc里面添加对应的switch-case，如下：

wchar_t a[6] = TEXT("Dian0");
int wmId = LOWORD(wParam);
int wmEvent = HIWORD(wParam);
switch (uMsg)
{
case WM_CLOSE:
	DestroyWindow(hwnd);
	break;
case WM_DESTROY:
	PostQuitMessage(0);
	break;
case WM_COMMAND:
	if (wmEvent == BN_CLICKED) {
		a[4] = L'0' + (a[4] - L'0' + 1) % 10;
		SetWindowText(my_button, a);
		break;
	}
	else if (wmEvent == CBN_SELCHANGE)
		// If the user makes a selection from the list:
		//   Send CB_GETCURSEL message to get the index of the selected list item.
		//   Send CB_GETLBTEXT message to get the item.
		//   Display the item in a messagebox.
	{
		int ItemIndex = SendMessage((HWND)lParam, (UINT)CB_GETCURSEL,
			(WPARAM)0, (LPARAM)0);
		TCHAR  ListItem[256];
		(TCHAR)SendMessage((HWND)lParam, (UINT)CB_GETLBTEXT,
			(WPARAM)ItemIndex, (LPARAM)ListItem);
		MessageBox(hwnd, (LPCWSTR)ListItem, TEXT("Item Selected"), MB_OK);
	}
	// Here don't write break on purpose!
default:
	return DefWindowProc(hwnd, msg, wParam, lParam);
}
// 还是得要去处理default的事件