Abstract: An Efficient and Effective Longest Common Subsequence algorithm（EELCS） is proposed for video subsequence matching.Firstly，the Vector Quantization algorithm，which simplifies the calculation on the real distance among the elements to comparison operations，is employed on multi-dimensional longest common subsequence algorithm.Compared with the original longest common subsequence matching algorithm，it can not only be directly applied to the practical application of the multidimensional sequence matching，but also greatly reduces the matching complexity.Then the algorithm further distinguishes the difference caused by the concentration degree of both matched and unmatched sub-sequences among the sequences. Lastly，the algorithm is applied to video clips matching.The experimental results show that，compared with the respective algorithms Time-Warped Longest Common Subsequence（T-WLCS） and continuous longest common subsequence，the algorithm can be better applied to video sequence matching.

Key words: video retrieval, sequence matching, vector quantization, the longest common subsequence

摘要： 为视频序列匹配提出一个高效精确的最大公共子序列（Efficient and Effective Longest Common Subsequence，EELCS）算法。首先，利用矢量量化（Vector Quantization，VQ）将多维最大公共子序列算法（Multi-dimensional LCS，MLCS）中元素对匹配过程中的实际距离的计算简化成比较操作，较原始的最大公共子序列匹配算法（Original LCS，OLCS），该处理不仅可以继承MLCS的可应用到实际多维时序匹配问题中的优点，同时大大降低了匹配的复杂度；然后进一步区分待匹配序列中由于匹配子序列和未匹配子序列在时间轴上连续性而产生的差异；最后将该算法应用到视频片段的匹配中。实验结果表明，与具有代表性的基于时间规扭曲的最大公共子序列（Time-Warped LCS，T-WLCS）和连续最大公共子序列（Continuous LCS，CLCS）相比，该算法能较好地应用于视频序列的匹配。

关键词: 视频检索, 序列匹配, 矢量量化, 最大公共子序列