1.实验背景

最近毕业设计中，希望通过wifi数据计算人员轨迹的相似度。
人员轨迹数据按照时间顺序，以地点id的序列来表示。示例：

a = [180, 180, 141, 146, 141, 200, 235, 235, 173, 141, 141, 172, 180]
b = [165, 235, 180, 141, 240, 171, 173, 172]

LCSS算法则可以计算出两个序列之间的最长公共子序列。
值得一提的是，子序列是有序的，但不一定是连续，作用对象是序列。
例如：序列 X = <B, C, D, B> 是序列 Y = <A, B, C, B, D, A, B> 的子序列，对应的下标序列为 <2, 3, 5, 7>。

2.LCSS算法介绍

下面我们看一下，如何使用动态规划的思想来解决最大公共子序列问题。

首先考虑最大公共子序列问题是否满足动态规划问题的两个基本特性：

1. 最优子结构：

设输入序列是X [0 .. m-1] 和 Y [0 .. n-1]，长度分别为 m 和 n。和设序列 L(X [0 .. m-1]，Y[0 .. n-1]) 是这两个序列的 LCS 的长度，以下为 L(X [0 .. M-1]，Y [0 .. N-1]) 的递归定义：

1）如果两个序列的最后一个元素匹配（即X [M-1] == Y [N-1]）

则：L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）

2）如果两个序列的最后字符不匹配（即X [M-1] != Y [N-1]）
　　则：L(X [0 .. M-1]，Y [0 .. N-1]) = MAX(L(X [0 .. M-2]，Y [0 .. N-1])，L(X [0 .. M-1]，Y [0 .. N-2]))

通过如下具体实例来更好地理解一下：

1）考虑输入子序列 <AGGTAB> 和 <GXTXAYB>。最后一个字符匹配的字符串。这样的 LCS 的长度可以写成：

L(<AGGTAB>, <GXTXAYB>) = 1 + L(<AGGTA>, <GXTXAY>)

2）考虑输入字符串“ABCDGH”和“AEDFHR。最后字符不为字符串相匹配。这样的LCS的长度可以写成：

L(<ABCDGH>, <AEDFHR>) = MAX ( L(<ABCDG>, <AEDFHR>), L(<ABCDGH>, <AEDFH>) )

因此，LCS问题有最优子结构性质。

3.python代码实现LCSS算法

沿袭递归的思想，使用python进行最长公共子序列的挖掘

li =[]

def lcs(a, b):
    lena = len(a)
    lenb = len(b)
    c = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
    flag = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
    for i in range(lena):
        for j in range(lenb):
            if a[i] == b[j]:
                c[i + 1][j + 1] = c[i][j] + 1
                flag[i + 1][j + 1] = 'ok'
            elif c[i + 1][j] > c[i][j + 1]:
                c[i + 1][j + 1] = c[i + 1][j]
                flag[i + 1][j + 1] = 'left'
            else:
                c[i + 1][j + 1] = c[i][j + 1]
                flag[i + 1][j + 1] = 'up'
    return c, flag


def printLcs(flag, a, i, j):
    if i == 0 or j == 0:
        return
    if flag[i][j] == 'ok':
        printLcs(flag, a, i - 1, j - 1)
        # print a[i - 1]
        li.append(a[i-1])
    elif flag[i][j] == 'left':
        printLcs(flag, a, i, j - 1)
    else:
        printLcs(flag, a, i - 1, j)


# a = 'ARWQRQBCBDASFJIOAAB'
# b = 'BDREQWTRCWABQRQWRQWRTYKOEQPA'

a = [180, 180, 141, 146, 141, 200, 235, 235, 173, 141, 141, 172, 180]
b = [165, 235, 180, 141, 240, 171, 173, 172]
#a、b表示两个mac在某段时间内的轨迹id序列

c, flag = lcs(a, b)
printLcs(flag, a, len(a), len(b))

print li
print len(li)

实验结果输出：