py_common_subseq
A re-usable Python micro-library that finds all of the subsequences shared between two sequences (like strings or lists) in polynomial time.
Author, License, and Conditions
(c) A. Samuel Pottinger (http://gleap.org), 2013
Released under the MIT license. Don't forget to be awesome.
Installation (pip)
pip install py_common_subseq
Installation (manual / single file)
This mico-library is a single file and engineers that may prefer to include the file directly instead of using pip can simply copy py_common_subseq/py_common_subseq.py into an accessible location. This micro-library does not have any additional dependencies beyond the Python standard library.
Quickstart
>>> 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'])
Full API
count_common_subsequences(seq_1, seq_2)
Find the number of common subsequences between two collections.
This function finds the number of common subsequences between two collections but does not return an actual listing of those subsequences. This is more space efficient O(len(seq_1)) than find_common_subsequences.
- 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, sep='', empty_val='')
Find the number of common subsequences between two collections.
This function finds the common subsequences between two collections and returns an actual listing of those subsequences. This is less space efficient (O(len(seq_1)^2)) than count_common_subsequences.
- 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.
Motivation / Background
While the longest common subsequence allows for the comparison of sequences, some problem domains also benefit from the additional information hiding in the second, third, fourth, etc. largest common subsequences ignored by typical LCS. This micro-library provides an implementation of the dynamic programming solution for finding all common subsequences as presented in All Common Subsequences (calACS-DP) by Hui Wang. This micro-library also adds some space efficiency improvements and functionality to list common subsequences (semi-formal proof below).
Testing
Within the py_common_subseq folder, run:
python test_py_common_subseq.py
Unit tests do not have any dependencies beyond the Python standard library.
Overview of Space and Time complexity
The algorithm runs in O(|A|x|B|) time where |A| is the length of the first sequence provided and |B| is the length of the second sequence. Space complexity is as follows:
count_common_subsequences: 2 * min(len(seq_1), len(seq_2)) or O(min(|A|, |B|))
find_common_subsequences: 2 * min(len(seq_1), len(seq_2))^2 or O(min(|A|, |B|))^2
See the discussion below for additional detail.
Overview of Deviations and Optimizations
Similar to the well-documented space optimization for the dynamic programming solution to the Longest Common Subsequence problem, both count_common_subsequences and find_common_subsequences only maintains the "current" and "previous" rows of the table that Hui Wang's algorithm requires. As proven below, this reduces the space complexity to the following:
count_common_subsequences: 2 * min(len(seq_1), len(seq_2)) or O(min(|A|, |B|))
find_common_subsequences: 2 * min(len(seq_1), len(seq_2))^2 or O(min(|A|, |B|))^2
Additionally, unlike Professor Wang's original paper, find_common_subsequences modifies the algorithm's table to contain the set of subsequences achieved at the point of the algorithm's execution as opposed to the cardinality of that set.
Discussion / proof of correctness
Note: This section will only discusses the modifications made to create find_common_subsequences and why they maintain the algorithm's correctness. For the original algorithm's (more formal) proof of correctness / space complexity / time complexity, see the original paper. This also only attempts to provide an informal proof.
Claim
find_common_subsequences returns the set of all common subsequences between a sequence A and a sequence B.
Assumptions / Definitions
- Define a subsequence of sequence A as an ordered set of elements where all elements in the subsequence appear in A and are relatively ordered to each other as they are in A. All pairs of sequences share the empty sequence as a common subsequence by this definition.
- Define the set of common subsequences between sequence A and sequence B as the intersection of the set of all subsequences of A and the set of all subsequences of B.
- Define A' as the subsequence from A_{0} through A_{i} and B' as the subsequence from B_{0} through B_{j}.
- A_{1} is the first element in A and B_{1} is the first element in B.
- A'' = A_{1} to A_{i-1} A'' and B'' = B_{1} to B_{j-1}.
Lemma 1
C_{i j} = C_{i-1 j-1} âˆª (A_{i} appended to S âˆ€ S âˆˆ C_{i-1 j-1}) if A_{i} = B_{j}.
- If A_{i} = B_{j}, appending A_{i} to A'' will yield A' and appending A_{i} to B'' will yield B'. Both A' and B' would then have a final element of A_{i}.
- A' and B' would thus share common subsequences ending in A_{i}.
- Thus, appending A_{i} to all of the common subsequences between A'' and B'' would yield common subsequences between A' and B'. This includes adding A_{i} to the empty set.
- Since the elements of a common subsequence must be in order relative to the ordering of the elements in the original sequences, all new common subsequences introduced by adding A_{i} to A'' and B'' must be able to be constructed by adding this an instance of A_{i} after the elements in the prior common subsequences between A'' and B''.
- Thus, the set of common subsequences (C_{i j}) can be constructed by C_{i-1 j-1} âˆª (A_{i} appended to S âˆ€ S âˆˆ C_{i-1 j-1}).
Lemma 2
C_{i j} = C_{i j-1} âˆª C_{i-1 j} if A_{i} â‰ B_{j}.
- Since A_{i} â‰ B_{j}, all common subsequences between A' and B' (C_{i j}) must already occur in the set of common subsequences between B'' and A' (C_{i j-1}) or B' and A'' (C_{i-1 j}) since A' and B' do not share the same final element.
- Thus, all common subsequences between A' and B' (C_{i j}) equals the union of C_{i j-1} and C_{i-1 j}.
Informal proof
- C_{i j} contains the subsets between A' and B' if i>=0 âˆ§ i<=|A|âˆ§ j>=0 âˆ§ j<=|B|.
- C_{00} through C_{0j} = the set of an empty sequence by definition.
- C_{00} through C_{i0} = the set of an empty sequence by definition.
- Therefore, C contains all the common subsets between A' and B' if i=0 or j=0.
- C_{i j} =
- C_{i-1 j-1} âˆª (A_{i} appended to S âˆ€ S âˆˆ C_{i-1 j-1}) by lemma 1 if A_{i} = B_{j}. C_{i-1 j-1} is available by memoization or recursion until reaching the base case of C_{00} through C_{0j} or C_{00} through C_{i0}.
- C_{i j-1} âˆª C_{i-1 j} by lemma 2 if A_{i} â‰ B_{j}. C_{i j-1} and C_{i-1 j} are available by memoization or recursion until reaching the base case of C_{00} through C_{0j} or C_{00} through C_{i0}.
- C_{|A| |B|} contains the set of all common subsequences between A and B.
- find_common_subsequences yields C_{|A| |B|} and, thus, yields the set of all common subsequences between A and B.
Discussion of time complexity
The original paper demonstrates a running time of O(|A| Ã— |B|) for count_common_subsequences. To achieve C_{|A| |B|}, the algorithm computes C_{i j} âˆ€ i âˆˆ range(0, |A|) âˆ§ j âˆˆ range(0, |B|) with memoization of each result indexed by i and j. Thus, find_common_subsequences also achieves O(|A| Ã— |B|) time complexity.
Discussion of space optimization
Note: This section will only discusses the space saving modifications in depth. For the original algorithm's proof of correctness / space complexity / time complexity, see the original paper.
As implemented in this micro-library, this algorithm manipulates its table (T) by working through a nested loop, manipulating all of row's elements before moving to the next. The result of the algorithm rests in T[|A|][|B|] or T[len(seq_1)][len(seq_2]). Since the algorithm never returns to previously visited rows, only the "current" and "previous" rows need to be maintained in memory. Both count_common_subsequences and find_common_subsequences take advantage of this to remove all rows before the "previous" row during iteration but do not otherwise change the behavior of the algorithm's operation. Moreover the algorithm will choose the number of rows and elements per row such that it will iterate max(|A|,|B|) times over rows of min(|A|,|B|) elements. This reduces the space required for the algorithm from O(|A||B|) to O(min(|A|,|B|)).
Of course, for find_common_subsequences, the sets themselves take up memory and if two identitical subsequences are compared, O(2^n * n) sets will be created.