Python-ideas

Download

python-ideas@python.org

September 2007

26 participants
22 discussions

Re: [Python-ideas] FInd first tuple argument for str.find and str.index
by Terry Jones Sept. 5, 2007

Sept. 5, 2007

>>>>> "Guido" == Guido van Rossum <guido(a)python.org> writes: Guido> I was surprised to find that startswith and endswith support this, Guido> but it does make sense. Adding a patch to 2.6 would cause it to be Guido> merged into 3.0 soon enough. Guido> On 9/4/07, Ron Adam <rrr(a)ronadam.com> wrote: >> Could we add the ability of str.index and str.find to accept a tuple as the >> first argument and return the index of the first item found in it. Hi If someone is going to head down this path, it might be better to implement a more general algorithm and provide the above as a special case via an argument. There's a fast and beautiful algorithm due to Aho & Corasick (CACM, 1975) that finds _all_ matches of a set of patterns. It runs in time that's linear in max(sum of the lengths of the patterns to be matched, length of to-be-matched text). The algorithm was the basis of fgrep. To provide the above, a special case could have it return as soon as it found a first match (i.e., of any pattern). One general way to write it would be to have it return a dict of patterns and result indices in the case that the pattern argument is a tuple. So "Hey, look, look, look at these patterns".find(('look', 'for', 'these', 'patterns')) might return { 'look' : [ 5, 11, 17 ], 'for' : [ ], # or arguably [ -1 ], 'these' : [ 25 ], 'patterns' : [ 31 ], } OK, that's a bit of a departure from the normal behavior of find, but so is passing a tuple of patterns. Alternately, you could also get back a tuple of (tuples of) matching indices. The ideal calling interface and result depends on what you need to do - check if a specific string matched? Just know the first match offset, etc. I don't know the best solution, but the algorithm rocks. Raymond - you'll love it :-) Terry

2 1

Re: [Python-ideas] FInd first tuple argument for str.find and str.index
by Terry Jones Sept. 5, 2007

Sept. 5, 2007

>>>>> "Terry" == Terry Jones <terry(a)jon.es> writes: >>>>> "Guido" == Guido van Rossum <guido(a)python.org> writes: Guido> I was surprised to find that startswith and endswith support this, Guido> but it does make sense. Adding a patch to 2.6 would cause it to be Guido> merged into 3.0 soon enough. Guido> On 9/4/07, Ron Adam <rrr(a)ronadam.com> wrote: >>> Could we add the ability of str.index and str.find to accept a tuple as the >>> first argument and return the index of the first item found in it. I should have added a few more comments. If you're going to implement the original desired functionality and make it run quickly, you're probably going to dream up something along the lines of what Aho & Corasick did so beautifully. It's tricky to get it right. As you walk the text string, several patterns may be currently matching. But the next char you consider might cause one or more of the current matches to fail, or a currently non-matching pattern to begin to match. The A&C algorithm builds a trie with failure arcs, so the matching is linear (both linear time to build the trie and the failure arcs, and then linear to walk the trie with the text). It has accepting states, so you know as soon as something matches, and can quit early. If this is going to be implemented you may as well do it right the first time. You could also return a dict in which (pattern) keys are absent if they didn't match at all. Then it would be fast to tell which, if any, patterns matched - no need to step through all passed patterns, just use result.keys() to get them. Terry

1 0