5 ms·

String overlap detection in Python

glenjamin 16y ago
As I understand this, the KMP function uses an optimal algorithm, while the indexOf version uses a suboptimal algorithm but takes advantage of a native (C) implementation found in the standard library. It follows that the fastest approach should be to implement the KMP algorithm natively, using Pyrex rather than C should make this fairly trivial.
- cracki 16y ago
  besides Pyrex, there's also Cython (I don't know if one superseeded the other or what exactly their relationship is)
  - wisty 16y ago
    Pyrex is the original. Cython is the fork by people who wanted to add more features. I think their relationship is reasonable, but not reasonable enough for the two projects to link to each-other.
- endtime 16y ago
  >It follows that the fastest approach should be to implement the KMP algorithm natively Not exactly - well, depends what you mean by "fastest". The KMP algorithm is optimal in the worst case, not necessarily in the average case. If you implemented KMP in C and then fed it typical rather than pathological strings, you might still do better with the indexOf algorithm.
endtime 16y ago
>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. Once you start engineering things of course you have to take practical considerations into account (such as the classes of strings your algorithm is likely to be fed as input), but that doesn't invalidate (or devalue) proofs which make no claims about practical usage.
- btilly 16y ago
  >The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios. This is absolutely not true. Big-O is a notation to describe the growth of functions. The functions themselves can describe anything you want, including either the average OR the worst case. The usage you complain about is therefore correct. See http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation for verification. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. It is actually a very unoriginal quip. I've been repeating it for years. Furthermore it is a quip with a lot of truth. Sciences are fields of study that use experiments to test hypotheses and refine theories. As you point out, CS is a lot like math, and unlike science, in that it is a field of knowledge which is in a large part based on our ability to construct ideas on top of each other and prove things about them rather than being built on experiment. In short "not science" is descriptive, not pejorative.
  - endtime 16y ago
    >I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios... I appreciate what you're saying here, but I think this part of the Wikipedia page is relevant: >A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. Upper bound implies worst case. I was going to say that big Theta is average case, but after some brief research I actually think I was mistaken on that.
    - deleted 16y ago
      [deleted]
    - plinkplonk 16y ago
btilly 16y ago
His implementation of the KMP algorithm starts by constructing a table for the whole of one string, to use in matching the other. But the full table is seldom needed. I wonder how much of the performance is taken in that construction, and how much of a difference only constructing part of that would make.
drallison 16y ago
The problem statement: "How does one detect when two strings overlap?" is inadequate. If "overlap" means "at least one substring in common", a trivial test for overlap would be to determine whether they have a character in common.
- drallison 16y ago
  I do not understand why this comment was down voted. When analyzing algorithms, a clear and correct statement of the problem is necessary and the one made here is clearly inadequate. For example, while the problem calls for an algorithm to "detect" overlap, while the algorithms described produce a list the overlapped strings. Moreover, there is no definition (other than the programs listed) for what is meant by "overlap". Consider "abc" and "abcd". The overlapping strings might be "a", "ab", "abc", "bc" , and "c" under one definition, or simply "abc" under another.
- endtime 16y ago
  >If "overlap" means "at least one substring in common" Why would it mean that? Is it not obvious that the common substring must be the beginning of one string and the end of the other?

As I understand this, the KMP function uses an optimal algorithm, while the indexOf version uses a suboptimal algorithm but takes advantage of a native (C) implementation found in the standard library. It follows that the fastest approach should be to implement the KMP algorithm natively, using Pyrex rather than C should make this fairly trivial.

cracki 16y ago
besides Pyrex, there's also Cython (I don't know if one superseeded the other or what exactly their relationship is)
- wisty 16y ago
  Pyrex is the original. Cython is the fork by people who wanted to add more features. I think their relationship is reasonable, but not reasonable enough for the two projects to link to each-other.
endtime 16y ago
>It follows that the fastest approach should be to implement the KMP algorithm natively Not exactly - well, depends what you mean by "fastest". The KMP algorithm is optimal in the worst case, not necessarily in the average case. If you implemented KMP in C and then fed it typical rather than pathological strings, you might still do better with the indexOf algorithm.

endtime 16y ago

>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. Once you start engineering things of course you have to take practical considerations into account (such as the classes of strings your algorithm is likely to be fed as input), but that doesn't invalidate (or devalue) proofs which make no claims about practical usage.

btilly 16y ago
>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios. This is absolutely not true. Big-O is a notation to describe the growth of functions. The functions themselves can describe anything you want, including either the average OR the worst case. The usage you complain about is therefore correct. See http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation for verification. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. It is actually a very unoriginal quip. I've been repeating it for years. Furthermore it is a quip with a lot of truth. Sciences are fields of study that use experiments to test hypotheses and refine theories. As you point out, CS is a lot like math, and unlike science, in that it is a field of knowledge which is in a large part based on our ability to construct ideas on top of each other and prove things about them rather than being built on experiment. In short "not science" is descriptive, not pejorative.
- endtime 16y ago
  >I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios... I appreciate what you're saying here, but I think this part of the Wikipedia page is relevant: >A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. Upper bound implies worst case. I was going to say that big Theta is average case, but after some brief research I actually think I was mistaken on that.
  - deleted 16y ago
    [deleted]
  - plinkplonk 16y ago

btilly 16y ago

His implementation of the KMP algorithm starts by constructing a table for the whole of one string, to use in matching the other. But the full table is seldom needed. I wonder how much of the performance is taken in that construction, and how much of a difference only constructing part of that would make.

drallison 16y ago

The problem statement: "How does one detect when two strings overlap?" is inadequate. If "overlap" means "at least one substring in common", a trivial test for overlap would be to determine whether they have a character in common.

drallison 16y ago
I do not understand why this comment was down voted. When analyzing algorithms, a clear and correct statement of the problem is necessary and the one made here is clearly inadequate. For example, while the problem calls for an algorithm to "detect" overlap, while the algorithms described produce a list the overlapped strings. Moreover, there is no definition (other than the programs listed) for what is meant by "overlap". Consider "abc" and "abcd". The overlapping strings might be "a", "ab", "abc", "bc" , and "c" under one definition, or simply "abc" under another.
endtime 16y ago
>If "overlap" means "at least one substring in common" Why would it mean that? Is it not obvious that the common substring must be the beginning of one string and the end of the other?