Array-search algorithm for identical sequences and character distances

Here is Python code written to perform the following operations:

1. Find each occurrence of a three-letter sequence in a character array (e.g. a sequence such as ('a','b','c')), including overlapping sequences of up to 2 shared characters.
2. Count the characters between the start of each sequence and the start of all identical sequences following it.
3. Every time the same number of characters results from #2, increment a counter for that specific number of characters (regardless of which character sequence caused it).
4. Return a dictionary containing all accumulated counters for character distances.

counts = {}
# repeating groups of three identical chars in a row
for i in range(len(array)-2):
for j in range(i+1,len(array)-2):
if ((array[i] == array[j]) & (array[i+1] == array[j+1]) & (array[i+2] == array[j+2])):
if counts.has_key(j-i) == False:
counts[j-i] = 1
else:
counts[j-i] += 1

This code was originally written in another programming language, but I would like to apply any optimizations or improvements available in Python.

1. Improving the code

Here are some ways in which you could improve your code, while leaving the algorithm unchanged:

1. You can avoid the need to check counts.has_key(j-i) if you use collections.Counter.

2. You are looping over all pairs of distinct indexes between 0 and len(array)-2. The function itertools.combinations provides a way to cleanly express your intention.

3. Instead of comparing three pairs of array elements, you can compare one pair of array slices.

4. Organize the code into a function with a docstring.

5. Generalize it from 3 to $k$.

6. Python doesn't have an "array" type, but it does have sequences. So your variables could be better named.

Here's the revised code after making the above improvements:

from collections import Counter
from itertools import combinations

def subseq_distance_counts(seq, k=3):
"""Return a dictionary whose keys are distances and whose values
are the number of identical pairs of k-length subsequences
of seq separated by that distance. k defaults to 3.

"""
counts = Counter()
for i, j in combinations(range(len(seq) - k + 1), 2):
if seq[i:i + k] == seq[j:j + k]:
counts[j - i] += 1
return counts

It's possible to rewrite the body of this function as a single expression:

return Counter(j - i
for i, j in combinations(range(len(seq) - k + 1), 2)
if seq[i:i + k] == seq[j:j + k])

Some people prefer this style of coding, and others prefer the explicitness of the first version. It doesn't make much difference to the performance, so comes down to personal taste.

2. Improving the algorithm

Here's an alternative approach (that you could use if the subsequences are hashable). Your original algorithm is $O(n^2)$, where $n$ is the length of the sequence. The algorithm below is $O(n + m)$, where $m$ is the number of repeated triples. This won't make any different in the worst case, where $m = Θ(n^2)$, but in cases where $m = ο(n^2)$ it should be an improvement.

def subseq_distance_counts(seq, k=3):
"""Return a dictionary whose keys are distances and whose values
are the number of identical pairs of k-length subsequences
of seq separated by that distance. k defaults to 3.

>>> subseq_distance_counts('abcabcabc')
Counter({3: 4, 6: 1})
>>> subseq_distance_counts('aaaaaa', 1)
Counter({1: 5, 2: 4, 3: 3, 4: 2, 5: 1})

"""
positions = defaultdict(list) # List of positions where each subsequence appears.
for i in range(len(seq) - k + 1):
positions[seq[i:i + k]].append(i)
return Counter(j - i
for p in positions.itervalues()
for i, j in combinations(p, 2))

The first way to improve the code that I can see is: make it more readable, more expressive. In one word: refactoring.

Try to avoid so many one-letter variables and long lines as they obstruct the meaning of the code. Also, you're using two nested loops and two nested if statements with a pretty long condition.

Try assigning those to more meaningful variables.

Your code sample is also incomplete, not showing what the "array" really is. Python doesn't have "arrays" so I guess you're using a standard list type. Something that can speed up this kind of lookup could be "dynamic programming", i.e. caching of some re-occuring computations. But this would require to refactor into more readable blocks first.

• thank you for tips. but the variables which I am using for the for loops (i and j) are only iterating variables, so I think, they should be ok there. the nested fors and ifs are exactly what I have talked about. it seems to me also "not good". – Peter Dec 9 '12 at 15:07
• Actually it does matter. I recommend you try starting with a simpler question first regarding how to refactor code so it becomes "beautiful". Deflecting on a possible solution won't help. – Theuni Dec 9 '12 at 15:43

Instead of taking three elements at a time and comparing them to every other three elements, which takes O(n2) comparisons, you can use the following, which only requires traversing the array once:

from collections import defaultdict

counts = defaultdict(int)
for i in xrange(len(string) - 2):
counts[tuple(string[i:i+3])] += 1

Using this answer about a Python equivalent to Ruby's each_cons, you can make this even nicer, though I don't know about the performance.

As the array contains characters, you may as well call it a string.

• This doesn't do the same thing as the OP's code: in his counts dictionary the keys are the distance between the repetitions, whereas in yours the keys are the repeated triples. – Gareth Rees Dec 10 '12 at 12:57

You can use simple python dictionary and list comprehensions to achieve your goal:

import re
string = "test test test test test"
aTuplePositions = {string[y:y+3]:[m.start() for m in re.finditer(''.join([string[y],'(?=',string[y+1:y+3],')']), string)] for y in range(len(string)-2) }
aTupleDistances = [t-u for z in aTuplePositions for a,u in enumerate(aTuplePositions[z]) for t in aTuplePositions[z][a+1:]]
counts = {y:aTupleDistances.count(y) for y in aTupleDistances if y >= 0}
counts # returns {10: 12, 20: 2, 5: 17, 15: 7}
• This doesn't do the same thing as the OP's code: in his counts dictionary the keys are the distance between the repetitions, whereas in yours the keys are the repeated triples. – Gareth Rees Dec 10 '12 at 12:58
• The OP failed to phrase the question correctly, so downvote the question rather than my answer. – Barbarrosa Dec 11 '12 at 3:14
• @GarethRees I fixed the difference between my answer and the answer the OP wanted (but failed to correctly request). – Barbarrosa Dec 11 '12 at 5:09
• @Barbarrosa sorry for misunderstanding, now I know that I have to formulate the questions more clearly, so I hope there will be no such problems. your answer is also very interesting, and I take valuable information from both of you. – Peter Dec 13 '12 at 19:46