py-common-subseq 0.2

作者、许可证和条件

（c）A.Samuel Pottinger（http://gleap.org），2013年 根据[MIT许可证]（http://opensource.org/licenses/MIT）发布。不要 忘了做个了不起的人。

安装（PIP）

pip安装py_common_subseq

安装（手动/单文件）

这个mico库是一个单独的文件，工程师可能更喜欢包含 直接复制文件而不是使用pip py_common_subseq/py_common_subseq.py进入可访问的位置。这个 除了python之外，micro库没有任何其他依赖项 标准库。

快速启动

` >>> import py_common_subseq >>> test_seq_1 = 'qwer' >>> test_seq_2 = 'qewr' >>> py_common_subseq.count_common_subsequences(test_seq_1, test_seq_2) 12 >>> py_common_subseq.find_common_subsequences(test_seq_1, test_seq_2) set(['', 'qer', 'wr', 'qwr', 'er', 'qr', 'e', 'qw', 'q', 'r', 'qe', 'w']) >>> py_common_subseq.find_common_subsequences(test_seq_1, test_seq_2, sep=',')set(['', ',q,w,r', ',e,r', ',e', ',w,r', ',q,w', ',q,r', ',w', ',r', ',q', ',q,e', ',q,e,r']) `

完整的API

`count_common_subsequences(seq_1, seq_2)` 查找两个集合之间的公用子序列数。

此函数用于查找两个 但不返回这些子序列的实际列表。 这比查找公共子序列更节省空间。

• seq_1: Any integer indexable collection (list, tuple, etc.). The first collection to find subsequences in.
• seq_2: Any integer indexable collection (list, tuple, etc.). The second collection to find subsequences in.
• return: Integer. The number of common subsequences between seq_1 and seq_2.

`find_common_subsequences(seq_1, seq_2)` 查找两个集合之间的公用子序列数。

此函数用于查找两个集合和 返回这些子序列的实际列表。这地方太小了 有效（o（len（seq^1）^2））大于计数公共子序列。

• seq_1: Any integer indexable collection (list, tuple, etc.). The first collection to find subsequences in.
• seq_2: Any integer indexable collection (list, tuple, etc.). The second collection to find subsequences in.
• sep: Seperator to put between elements when constructing a subsequence. Keyword argument defaulting to ‘’.
• empty_val: The value to use to represent the empty set. Keyword argument defaulting to ‘’.
• return: Python standard lib set. Set of subsequences in common between seq_1 and seq_2.

动机/背景

虽然最长的公共子序列允许序列的比较， 一些问题域还受益于 第二、第三、第四等典型lcs忽略的最大公共子序列。 这个微库提供了动态编程的实现 找到所有公共子序列的解决方案 子序列（http://dl.acm.org/citation.cfm?id=1625377-calacs dp）由 王辉（http://www.ulster.ac.uk/staff/h.wang.html）。这个微型图书馆 添加一些空间效率改进和功能以列出常见的 子序列（下面的半形式证明）。

测试

在py_common_subseq文件夹中，运行：

python test_py_common_subseq.py

单元测试除了python标准库之外没有任何依赖关系。

该算法运行于〈cite〉o（a x b）`时间，其中〈cite〉a是第一个 提供的序列，b是第二个序列的长度。空间 复杂性如下：

计数公共子序列：2*min（len（seq_1），len（seq_2））或o（min（a，b）） 查找公共子序列：2*min（len（seq_1），len（seq_2））^2或o（min（a，b））^2

有关更多详细信息，请参见下面的讨论。

偏差和优化概述

类似于动态规划的文档化空间优化 最长公共子序列问题的解 计算公共子序列并查找公共子序列仅保持 “当前”和“以前”行，这是Hui Wang算法所要求的。 如下面所证明的，这减少了空间复杂度如下：

计数公共子序列：2*min（len（seq_1），len（seq_2））或o（min（a，b）） 查找公共子序列：2*min（len（seq_1），len（seq_2））^2或o（min（a，b））^2

此外，与王教授的原始论文不同，find_common_subsequences 修改算法表以包含在 算法的执行点，而不是它的基数 准备好了。

讨论/证明正确性

请参见readme.md

请参见readme.md

关于空间优化的讨论

见readme.md