在多层可迭代对象中查找匹配字符串（Python）

Question

假设我们有一个多层的可迭代对象，最里面的层级是一些字符串。没错，字符串是可以被迭代的，但我想你明白我的意思：

['something', 
('Diff',
('diff', 'udiff'),
('*.diff', '*.patch'),
('text/x-diff', 'text/x-patch')),

('Delphi',
('delphi', 'pas', 'pascal', 'objectpascal'),
('*.pas',),
('text/x-pascal',['lets', 'put one here'], )),

('JavaScript+Mako',
('js+mako', 'javascript+mako'),
('application/x-javascript+mako',
'text/x-javascript+mako',
'text/javascript+mako')),
...
]

有没有什么方便的方法可以让我实现一个搜索，找出匹配字符串的索引？我想要的效果类似于这样（上面的列表是 data）：

>>> grep('javascript', data)

然后它会返回 [ (2,1,1), (2,2,0), (2,2,1), (2,2,2) ] 之类的结果。也许我错过了某种类似的解决方案，它没有返回这样的结果，但能帮助我在一个多层的可迭代对象中找到一些字符串。

我写了一点代码，但感觉有些幼稚和不优雅，所以我想在这里问问。我想我可以像一开始那样继续嵌套异常，直到函数支持的层级数，但我希望能得到一些简洁、抽象、符合Python风格的东西。

import re

def rgrep(s, data):
    ''' given a iterable of strings or an iterable of iterables of strings,

    returns the index/indices of strings that contain the search string.

    Args::

        s - the string that you are searching for
        data - the iterable of strings or iterable of iterables of strings
    '''


    results = []
    expr = re.compile(s)
    for item in data:
        try:
            match = expr.search(item)
            if match != None:
                results.append( data.index(item) )

        except TypeError:
            for t in item:
                try:
                    m = expr.search(t)
                    if m != None:
                        results.append( (list.index(item), item.index(t)) )

                except TypeError:
                    ''' you can only go 2 deep! '''
                    pass

    return results

Answer 1

要获取位置，可以使用 enumerate()。

>>> data = [('foo', 'bar', 'frrr', 'baz'), ('foo/bar', 'baz/foo')]
>>> 
>>> for l1, v1 in enumerate(data):
...     for l2, v2 in enumerate(v1):
...             if 'f' in v2:
...                     print l1, l2, v2
... 
0 0 foo
1 0 foo/bar
1 1 baz/foo

在这个例子中，我使用了一个简单的匹配方式 'foo' in bar，不过你可能会用正则表达式来完成这个工作。

显然，enumerate() 可以支持超过两个层级，就像你编辑的帖子中提到的那样。

Answer 2

这里有一个使用递归来搜索数据结构的grep。

要注意，好的数据结构能让解决问题变得简单优雅。 而糟糕的数据结构则会让你费尽心思去适应它。 我觉得这就是一个糟糕的数据结构在阻碍你，而不是在帮助你。

使用一个更简单、结构更统一的数据结构 （而不是用这个grep）可能会更值得考虑。

#!/usr/bin/env python

data=['something', 
('Diff',
('diff', 'udiff'),
('*.diff', '*.patch'),
('text/x-diff', 'text/x-patch',['find','java deep','down'])),

('Delphi',
('delphi', 'pas', 'pascal', 'objectpascal'),
('*.pas',),
('text/x-pascal',['lets', 'put one here'], )),

('JavaScript+Mako',
('js+mako', 'javascript+mako'),
('application/x-javascript+mako',
'text/x-javascript+mako',
'text/javascript+mako')),
]

def grep(astr,data,prefix=[]):
    result=[]
    for idx,elt in enumerate(data):
        if isinstance(elt,basestring):
            if astr in elt:
                result.append(tuple(prefix+[idx]))
        else:
            result.extend(grep(astr,elt,prefix+[idx]))
    return result

def pick(data,idx):
    if idx:
        return pick(data[idx[0]],idx[1:])
    else:
        return data
idxs=grep('java',data)
print(idxs)
for idx in idxs:
    print('data[%s] = %s'%(idx,pick(data,idx)))

Answer 3

我建议把递归的枚举和查找分开：

def enumerate_recursive(iter, base=()):
    for index, item in enumerate(iter):
        if isinstance(item, basestring):
            yield (base + (index,)), item
        else:
            for pair in enumerate_recursive(item, (base + (index,))):
                yield pair

def grep_index(filt, iter):
    return (index for index, text in iter if filt in text)

这样你就可以同时进行非递归和递归的查找：

l = list(grep_index('opt1', enumerate(sys.argv)))   # non-recursive
r = list(grep_index('diff', enumerate_recursive(your_data)))  # recursive

另外要注意，我们在这里使用了迭代器，这样可以在需要的时候节省内存，特别是处理较长的序列时。

一个更通用的解决方案是给grep_index传递一个可调用的对象，而不是字符串。不过这对你来说可能不是必须的。