Tag Archives: python

Occurences of one string in another.

The string “ABC” occurs in “ABBC” twice, if you remove any characters you wish from “ABBC”. The following algorithm finds such occurences in O(n) time given any two strings. One assumption worth noting for the O(n) time bound is that … Continue reading

Posted in Coding, Misc | Tagged , | 1 Comment

Extract Longest Non-Decreasing Sequence From Any Sequence

I wrote some python code that extracts the longest non-decreasing subsequence from any given sequence. This runs in O(n log n) time, and uses O(n) memory. ”’ An item in the final sequence, used to form a linked list. ”’ … Continue reading

Posted in Coding, Misc | Tagged , | 10 Comments

2D CDF 9/7 Wavelet Transform in Python

As promised, here is an implementation of the Cohen-Daubechies-Feauveau 9 tap / 7 tap wavelet transform on a 2D signal in Python. This is the same transform used in the JPEG2000 codec. ”’ 2D CDF 9/7 Wavelet Forward and Inverse Transform (lifting implementation) … Continue reading

Posted in Coding | Tagged , , , , , , | 17 Comments