Cookie 中的 Path

问题

最近在将 PlayTask 的服务器用 Spring 重写. 这两天准备将实现了的登录和退出登录的功能先上线. 由于涉及到两套系统并且两套系统用的 Session 的框架不一样, 所以这其中会有 Session 的同步的问题, 即 Spring 版本中登录之后需要设置 Python 版本中服务器的 Session 的值.

开始想了一个方案是用户登录之后, Spring 服务器去请求 Python 的服务器来设置下 Session, 然后返回的 Header 添加 Set-Cookie 字段来同步 Session. 但是上线之后发现用户第一次登录总是会出现同步失败的情况. 一开始以为是 Python 的 Session 没有持久化, 最后发现是 Cookie 没有设置成功. 为什么呢?

Path 作用

Cookie 中有一个字段是 Path, 这个 Path 有什么用呢? 客户端 (比如浏览器), 在请求服务器的时候, 只会将 Path 和当前请求的的链接匹配的 Cookie 添加到请求的 Header 中, 即 Path 是用来限制 Cookie 的作用域的.

Path 设置的优先级

如果当前客户端中有一个 Cookie 的 Path 已经设置成了 /, 那么即使服务器返回的响应中的 Header 中有 Set-Cookie, 并且将 Path 设置成 /<sub>, Cookie 的 Path 字段也不会更新, 因为 / 是 /<sub> 的父目录. 反之会更新成父目录.

Servlet 中 Cookie Path 的设置

默认 Cookie 的 Path 是 程序在容器中的地址 (包括 Context Path). 可以通过如下代码更改 Path:

HttpServletResponse response;
Cookie cookie = new Cookie("name", "value");
cookie.setPath("/");
response.addCookie(cookie);

总结

这 Bug 困扰了两天, 今天终于查出来了. 匆匆忙忙的记录下.

字符串查找算法

字符串查找是很常见的功能, 但是实现一个高效的查找算法还是挺不容易的. 这两天花了点时间理解了几种常见的算法 (KMP, BM, BMH a.k.a Horspool), 这里记录一下, 方便以后查找.

约定

Pat: 模式字符串, Str: 待搜索的字符串.

Brute-force

先介绍最容易理解的暴力破解法. 这算法比较直观, 就是将 Pat 与 Str 的字符一个个比较, 如果匹配失败就将 Pat 向右移动一位再进行比较, 直到匹配完成.

直接上算法

public int bruteForce(String str, String pat) {
    int m = pat.length();
    int n = str.length();
    int i = 0, j = 0;

    while (j < m && i < n) {
        if (str.charAt(i) == pat.charAt(j)) {
            i++;
            j++;
            continue;
        }
        i = i - j + 1;
        j = 0;
    }

    if (j == m) {
        return i - j;
    }
    return -1;
}

Knuth–Morris–Pratt

Brute-force 算法之所以不够高效是因为, 当匹配失败时, 部分匹配的字符会在 Pat 右移一位后再次比较, 这就带来了不必要的开销. KMP 算法就是在此基础上改进的.

Knuth DFA 版本

Knuth 最开始的算法实现是基于 DFA (有限状态机) 的, 假如 Pat 的长度为 M, 那么 DFA 的状态共有 M + 1

Pat: abc
DFA: (0) --a--> (1) --b--> (2) --c--> (3)

我们顺序读取 Str 的每个字符, 每读取一个就会改变 DFA 的状态, 当 DFA 处于 (3) 状态时就表示字符串匹配完成.

假如 DFA 构造完成了, 那么我们该如何利用改造出来的 DFA 来搜索呢?

class KMP {
    publiv int[][] initDfa(String pat) {
        // TODO
    }

    public int search(String pat, String str) {
        int[][] dfa = this.initDfa(pat);
        int j = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            j = dfa[c - 'a'][j];
            if (j == pat.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }
}

有了 DFA 搜索就很简单了, 只用依次读取字符, 再从 DFA 里获取下一个状态就行了.

如何构造 DFA

KMP 算法最核心的问题就在于构造 DFA. 我们用一个矩阵来表示 DFA, 矩阵的行数为所有的可输入字符, 列数为 DFA 的状态数

以 aba 为例 (假设我们需要匹配的字符串只可能由 abc 组成), 我们会得到下面的 DFA

假如 Str 为 acaba, 那么依次读取字符, DFA 的状态变化为

DFA[0][0]: 1
DFA[1][2]: 0
DFA[0][0]: 1
DFA[1][1]: 2
DFA[2][0]: 3

我们先考虑 DFA 的第一列 (状态 0), 只有当输入字符和 Pat 的第一个字符相同, DFA 才会进入 (1) 状态 (即匹配了一个字符), 其它任何字符都不会匹配, 所以 DFA 会停留在 (0) 状态 (即没有字符匹配)

下面我们考虑第二列 (状态 1), 只有当输入字符合 Pat 的第二个字符相同时, DFA 才会进入 (2) 状态, 那其它不匹配的字符呢? 可以这样思考, 当输入字符不匹配时, Pat 如果按照暴力破解法会右移一位, 此时 DFA 会进入 (0) 状态, 那么 (2) 状态在不匹配的时候的跳转情况和 (0) 状态是一样的.

最后考虑第三列 (状态 2), 同上, 只有匹配的时候才会进入 (3) 状态. 不匹配的时候, Pat 会右移一位, 此时 DFA 进入 (0), 但是此时我们知道, 即将和 Pat 匹配的字符是 Pat 的第二个字符 (因为刚才匹配了), 所以 DFA 会进入 DFA[0][Pat[1]] 状态, 用上面的例子来说明就是, DFA[0][1] (b 在 Pat 中的 index 是 1), 即状态 (0), 所以第三列不匹配的情况和状态里 (0) 是一样的.

总结下就是, 当在某个状态不匹配时, DFA 会进入 (0) 状态 (右移一位), 这时我们可以根据已经匹配的字符 (除去第一个字符, 因为 Pat 右移了一位) 来推断当匹配到当前字符时 DFA 会处于哪个状态. 本质也是一种递归的思想, 我们可以根据之前状态的跳转规则来计算出当前状态的跳转规则.

最后构造 DFA 的算法实现如下:

class KMP {
    private static final String ALPHABETS = "abc";

    private int[][] initDfa(String pat) {
        int m = pat.length();
        int r = KMP.ALPHABETS.length();
        int[][] dfa = new int[r][m]; // init with 0
        dfa[pat.charAt(0) - 'a'][0] = 1; // init first column
        int x = 0; // previous state
        for (int i = 1; i < pat.length(); i++) {
            for (int j = 0; j < r; j++) { // copy x state to current
                dfa[j][i] = dfa[j][x];
            }
            int ci = pat.charAt(i) - 'a';
            dfa[ci][i] = i + 1; // mached
            x = dfa[ci][x]; // update x
        }
        return dfa;
    }

    public int search(String pat, String str) {
        int[][] dfa = this.initDfa(pat);
        int j = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            j = dfa[c - 'a'][j];
            if (j == pat.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

}

算法里的 x 是比较重要的, 按照之前的描述我们是需要每次都回溯的, 但是因为 Pat 的字符串是不变的, 也就是说, 每次回溯时前面的部分都是一样的, 所以用 x 记录一下省得每次都回溯.

这个就是 Knuth DFA 版的 KMP 算法, 我觉得这个版本是比较好理解的. 但这个版本有一个缺点就是, 需要使用 MR (Pat 的长度乘以可输入字符的长度) 的额外空间. Pratt 在 Knuth 的 DFA 版本上改进了下, 只需要额外使用 M 的空间 (即和可输入字符长度无关, 当然效率会低点), 于是就有了现在通常所说的 KMP 算法. (Morris 在 KMP 算法里做了什么? 呃, Wiki 的说法是, 他是独立完成这个算法的. 总结就是, Knuth 完成了 DFA 版本的, Pratt 改进了, Morris 独立完成了)

Pratt 改进版

发现用 Java 写算法不利于表现算法的本质, 所以之后还是用 Python 写算法吧.

在暴力破解算法中我们用指针 i 指向 Str 中待匹配的字符, j 指向 Pat 中待匹配的字符. 现在回过头来看暴力破解法, 当 i 和 j 指向的字符不匹配时, i 移动到 i - j + 1 位置, j 重置为 0, 然后继续匹配. 仔细想想我们可以发现, Str 中 i - j + 1 到 i 之间的字符我们是知道的, 所以当暴力破解法中 i 再次走到现在这个位置时, j 所处的位置我们是可以提前算出来了.

跳转表

假如我们现在有张跳转表 jump, jump[j] 表示当 Pat[j] != Str[i] 时 j 的下一个值应该是多少. 那么我们便可以利用 jump 来完成搜索算法

jump = []

def pratt(pat, s):
    m = len(pat)
    if m == 0:
        return 0
    j = 0
    i = 0
    for c in s:
        while j > 0 and c != pat[j]:
            j = jump[j]
        if c == pat[j]:
            i += 1
            j += 1
        else:  # j == 0 and c != pat[j]
            i += 1
        if j == m:
            return i - j
    return -1

构造跳转表

下面我们来构造跳转表, 我们先考虑 jump 的前两项, 当 j 等于 0, 1 时, 显然 j 需要重置为 0. 那么当 j 大于 1 时呢? 等于用 Pat 去匹配 Pat[1:], 看匹配到当前位置时 j 等于多少.

def initJump(pat):
    m = len(pat)
    jump = [0, 0]
    if m < 3:
        return jump

    j = 0
    for c in pat[1:-1]:
        while j > 0 and c != pat[j]:
            j = jump[j]
        if c == pat[j]:
            j += 1
        jump.append(j)
    return jump

Boyer-Moore

KMP 可以说是 Brute-Force 的改进版. BM 算法也差不多, 不过是基于反向的 Brute-Force 的算法:

def bruteForceRev(s, pat):
    m = len(pat)
    n = len(s)
    i = m - 1
    j = m - 1
    while i < n and j > -1:
        if s[i] == pat[j]:
            i -= 1
            j -= 1
        else:
            i += m - j
            j = m - 1
    return i + 1 if j == -1 else -1

Boyer-Moore-Horspool

完整的 BM 算法实现起来比较麻烦, BMH 是它的简化版本, 不过匹配起来依旧很快. BMH 是根据当前不匹配的字符来决定pat 的位移的. 比如说, 我们从右向左的匹配, 匹配第一个字符就失败了, 同时这个字符也没有在 pat 中出现过, 那么我们可以放心大胆的将 pat 直接向右位移 len(pat) 个距离. 可以看到决定位移的距离的关键在于当前不匹配的那个字符是否在 pat 中出现过, 出现的位置是多少. 这就是所谓的坏字符表.

坏字符表

我们用一个字典来表示坏字符表, 每一个在 pat 中出现的字符都在这个字典里, 对应的值为这个字符在 pat 中最后一次出现的位置. 比如 pat = 'aba' 那么坏字符表就等于 {'a': 2, 'b': 1}

我们先看假如我们现在有了坏字符表, 我们应该怎么匹配呢?

bad = {}

def BMH(s, pat):
    m = len(pat)
    n = len(s)
    i = m - 1
    j = m - 1
    while i < n and j >= 0:
        b = s[i]
        if b != pat[j]:
            if b in bad:
                inc = m - 1 - bad[b]
                inc = m - j if inc < m - j else inc  # 在反向 BF 中 i 至少会增加 m - j
            else:
                inc = m
            i += inc
            j = m - 1
        else:
            i -= 1
            j -= 1
    return i + 1 if j == -1 else -1

需要注意的地方已经在代码中注释了. 剩下的就是构造坏字符表了, 根据定义我们很容易就可以实现如下的代码:

def initBad(pat):
    bad = {}
    for i, v in enumerate(pat):
        bad[v] = i 
    return bad

完整 BM 算法

完整的 BM 算法不单单利用了不匹配的字符的信息还利用了已经匹配的字符的信息来决定位移的距离. 也就是所谓的好字符表. 乍看下觉得好字符表的构造应该和 KMP 的差不多, 然而, 因为匹配的顺序 (从右向左) 和位移的方向 (从左向右) 不一样, 导致好字符表的构造的远比 KMP 的跳转表的构造复杂. Algorithm 一书中作者 Robert Sedgewick 直接一句:

In general, the pattern at the end might appear elsewhere, so we need an array of restart positions as for Knuth-Morris-Pratt. We will not explore this approach in further detail because it is quite similar to our implementation of the Knuth-Morris-Pratt method.

就这么一笔带过了! 果然境界不一样啊.

这里我也不打算详细的叙述 (这文章已经断断续续的写了好多天了), 我就贴个代码好了:

def BM(s, pat):
    n = len(s)
    m = len(pat)
    jump = self.initJump(self.initBorder(pat))
    i = m - 1
    j = m - 1
    while i < n and j >= 0:
        if s[i] != pat[j]:
            i += jump[j]
            j = m - 1
        else:
            i -= 1
            j -= 1
    return i + 1 if j == -1 else -1

def initBorder(pat):
    m = len(pat)
    border = [m] * m  # last one will always equal to `m`
    for j in range(m - 1)[::-1]:
        prev = border[j + 1]
        while prev != m:
            if pat[j] == pat[prev - 1]:
                border[j] = prev - 1
                break
            prev = border[prev]
        else:
            border[j] = m - 1 if pat[j] == pat[m - 1] else m
    return border

def initJump(border):
    m = len(border)
    if m == 0:
        return []
    jump = [0] * m
    jump[m - 1] = 1
    j = border[0]
    for i in range(m):
        b = border[i]
        if b != m:
            jump[b - 1] = m - i
        if jump[i] != 0:
            continue
        while i >= j:
            j = border[j]
        jump[i] = j + m - i - 1
    return jump

总结

不管 KMP 还是 BM 都是在 Brute-Force (不管是从左往右还是从右往左比较) 的基础上, 利用已经匹配的和当前不匹配的字符来优化位移移动的距离.

将近一个礼拜断断续续的把这篇文章写完了, 并且把文中的算法都自己实现了一遍. 实现的过程中各种 +1 -1 搞的头都大了. 写算法的过程中感觉 大局观 很重要, 不能一开始就陷入细枝末节中. 比如, 可以先假设跳转表实现了, 先利用跳转表实现搜索算法.

ps. 在 LeetCode 上分别跑了下 KMP, BM, BF 算法, 最后发现, KMP 最慢, BF 最快. 没错, Brute-Force 算法最快!

Android - Multitouch 记录

今天看 Android Developer 上的 Handling Multi-Touch Gestures 这篇文章, 感觉有几个地方写的不是很好, 费了好大劲才理解. 把几个不是太好理解的点记录下.

Index vs ID

Index: A MotionEvent effectively stores information about each pointer in an array. The index of a pointer is its position within this array. Most of the MotionEvent methods you use to interact with pointers take the pointer index as a parameter, not the pointer ID.

ID: Each pointer also has an ID mapping that stays persistent across touch events to allow tracking an individual pointer across the entire gesture.

这里需要注意的就是对于每一个 Pointer (也就是你的手指), Index 是会变化的. 比如说你食指先触摸屏幕, 然后中指, 无名指也依次触摸屏幕, 那么这三个手指的 Index 分别是 0, 1, 2. 这时候如果你将食指抬起, 中指, 无名指的 Index 就会分别变成 0, 1. 食指 (换小拇指也行…) 再次触摸屏幕, 食指 (或者是小拇指…), 中指, 无名指的 Index 就又分别变成了 0, 1, 2. 一开始我以为会变成 2, 0, 1 的, 本来想看下源码里的实现, 然后发现代码里调用的是 native 的方法, 只好算了, 大概和数据结构有关吧.

对于 ID 来说, 只要你的手指不离开屏幕, 对应的 ID 就不会变化.

Touch events

When multiple pointers touch the screen at the same time, the system generates the following touch events:

ACTION_DOWN—For the first pointer that touches the screen. This starts the gesture. The pointer data for this pointer is always at index 0 in the MotionEvent.

ACTION_POINTER_DOWN—For extra pointers that enter the screen beyond the first. The pointer data for this pointer is at the index returned by getActionIndex().

ACTION_MOVE—A change has happened during a press gesture.

ACTION_POINTER_UP—Sent when a non-primary pointer goes up.

ACTION_UP—Sent when the last pointer leaves the screen.

1. ACTION_MOVE

   当你多个手指在屏幕上移动的时候, 只有 Index 为 0 的那个 Pointer 会触发 ACTION_MOVE 的事件.

2. ACTION_POINTER_UP

   文档里说, 当 non-primary 的 Pointer 离开时会触发该事件, 那么什么叫 non-primary? 我一开始认为非第一个触摸的手指就是 non-primary 的, 后来看到 Android 官方博客里的 Making Sense of Multitouch 这篇文章, 里面写到:

   If there is already a pointer on the screen and a new one goes down, you will receive ACTION_POINTER_DOWN instead of ACTION_DOWN. If a pointer goes up but there is still at least one touching the screen, you will receive ACTION_POINTER_UP instead of ACTION_UP.

   所以对于 ACTION_POINTER_UP 来说, 一个 Pointer 只要不是最后一个离开屏幕的, 那么它就是 non-primary 的.

getX(), getY()

getX()

getX(int) for the first pointer index (may be an arbitrary pointer identifier).

getY()

getY(int) for the first pointer index (may be an arbitrary pointer identifier).

直接调用 getX(), getY() 得到的竟然不是触发该事件的 Pointer 的坐标, 还非要获取 Index 之后再去调用 getX(int pointerIndex) 和 getY(int pointerIndex) 来获取当前的 Pointer 的坐标.

Android - 微信 SDK 应用签名

在微信开放平台里创建移动应用的时候, 最重要的就是填写应用签名了.

签名有很多用处, 比如软件升级的时候, 系统会对签名进行验证, 如果签名不一致的话就会拒绝升级.

Android 要求所有安装的应用都是被签名过的, 但是我们开发的时候好像没有对应用进行签名呀! 这是因为在 debug 模式下, 编译的过程中会自动对 APK 进行签名. 签名需要用到 keystore 文件, 可以通过 JDK 自带的 keytool 工具生成. Android SDK 会默认帮我们创建一个 keystore 文件, 文件名是 debug.keystore.

debug.keystore 在不同的操作系统下的默认地址是:

• Linux, Unix: ~/.android/
• Windows XP: C:\Documents and Settings<user>.android\
• Windows 7: C:\Users<user>.android\

debug.keystore 的默认属性是:

• Keystore name: “debug.keystore”
• Keystore password: “android”
• Key alias: “androiddebugkey”
• Key password: “android”
• CN: “CN=Android Debug,O=Android,C=US”

更多的关于签名的介绍可以看 Android Developers 上的 Signing Your Applications 这篇文章.

下面介绍我们如何获取微信开放平台所要求的应用签名, 更准确的来说应该是 keystore 的 MD5 fingerprint.

有三种方式:

1. 使用微信官方提供的签名生成工具, 可以到微信开放平台的 资源中心 - 移动应用开发 - 资源下载 - Android资源下载 里下载.

   直接下载

   但是, 这个工具很奇葩的地方是, 获取到的签名你没法复制, 只能一个个的手输.

2. 打开 eclipse, Window - Preferences - Android - Build, MD5 fingerprint 的值就是了, 记得把冒号去掉. 这个是默认的 debug.keystore 的 MD5 fingerprint, 如果你要获取你自己的 keystore 的 MD5 fingerprint 需要通过下面一种方法.

3. 根据微信官方提供的 Signature的生成方法 文档, 我们可以使用下面的命令来获取应用签名:

    keytool -exportcert -keystore debug.keystore  -storepass android -alias androiddebugkey | md5sum
   

   如果是你自己的 keystore, 修改命令里对应的部分就可以了.

Ps. 应用签名在审核通过之后随时可以更改, 且不用再次审核!

UDP Fragmentation

我们知道, UDP 是不可靠的, 比如你无法知道数据包是否发送成功, 你也无法知道数据包到达的先后顺序.

那么问题就来了, 当使用 sendto 时, 协议能否保证传给 sendto 的数据被打包成一个 UDP 数据包呢? 还是像 TCP 一样, 根据 MSS 对数据进行分割后再打包? 直觉上来说应该是有保证的, 否则的话, UDP 真心鸡肋啊!

最终在 UNIX Network Programming Vol 1 中找到了答案.

This time, we show the socket send buffer as a dashed box because it doesn’t really exist. A UDP socket has a send buffer size (which we can change with the SO_SNDBUF socket option, Section 7.5), but this is simply an upper limit on the maximum-sized UDP datagram that can be written to the socket. If an application writes a datagram larger than the socket send buffer size, EMSGSIZE is returned.