3

我有一个钥匙列表['foo_a','foo_b','foo_c','fnord']

这里所有类似的解决方案都假定fnord您的文本中没有 's。

我有这个代码可以完成这项工作：

def detect_prefix(keys):
    PCT = 0.70 # cutof 
    pre = ''
    l = len(keys)
    for i in range(0, len(max(keys, key=len))):
        keys = filter(lambda k: k.startswith(pre), keys)
        cnt = dict()
        for k in map(lambda k: k[i], keys):
            cnt.setdefault(k,0)
            cnt[k] +=1
        if cnt[max(cnt)] / float(l) >= PCT:
            pre += max(cnt)
        else:
            break
    return pre

我强烈怀疑这可以做得更优雅，但我的 python-fu 现在还不够强大。

我很想听听一些建议。

编辑. 附加背景和说明。
这些是其他开发人员放入应用程序中用于翻译的键。他们应该有一个共同的前缀，但人们忘记了，他们从其他代码中剪切和粘贴。“_”作为前缀分隔符只是一个约定。最好不要假设甚至使用了分隔符。70% 是一个完全任意的阈值。“最普遍”或“主要”也会起作用。
是的，这是 python 2.7，引号内的空格只是一个视觉伪影。

4

3 回答 3

1

查找具有特定前缀的事物的一种好方法是trie。我使用了一个名为pytrie的实现，但它们的工作方式几乎相同。唯一有趣的一点是您仍然需要以另一种方式生成所有前缀，因为向 trie 询问“foo_a 的所有前缀”只会给您“foo_a”以及它的所有前缀字符串，它们是您的数据的一部分，但是您似乎关心“foo_”，即使它不是自己的键。但是，它可以反过来做，告诉你所有以给定前缀开头的键，即使它没有显式存储。

除此之外，这一切都相当简单。包括导入在内，它有五行：

from pytrie import StringTrie as trie

data = trie.fromkeys(['foo_a','foo_b','foo_c','fnord'])
PCT = 0.70 
prefixes = (k[:i] for k in data for i,_ in enumerate(k, start=1))
print(max(filter(lambda x: len(data.keys(x)) >= PCT * len(data), prefixes), key=len))

打印foo_。

于 2014-03-25T09:21:38.227 回答
1

如果您知道公共前缀的所需阈值频率：

#!/usr/bin/env python
from collections import Counter
from itertools import izip_longest

strings = ['foo_a','foo_b','foo_c','fnord']
threshold = .7 * len(strings)
prefix = []
for chars in izip_longest(*strings, fillvalue=''):
    char, count = Counter(chars).most_common(1)[0]
    if count < threshold:
        break
    prefix.append(char)
print(''.join(prefix))
# -> foo_

或者您可以收集所有常见前缀及其频率，然后再决定：

#!/usr/bin/env python
from collections import Counter
from itertools import izip_longest

strings = ['foo_a', 'foo_b','foo_c','fnord']
assert len(strings) > 1
threshold = len(strings)
prefix = []
prefixes = []
for chars in izip_longest(*strings, fillvalue=''):
    char, count = Counter(chars).most_common(1)[0]
    if count == 1:
        break
    elif count < threshold:
        if prefix:
            prefixes.append((''.join(prefix), threshold))
        threshold = count
    prefix.append(char)
if prefix:
    prefixes.append((''.join(prefix), threshold))
print(prefixes)
# -> [('f', 4), ('foo_', 3)]

两个代码示例都假设存在主要前缀，即每个位置最常见的字符属于最常见的前缀。

于 2014-03-26T09:33:13.837 回答
0 
def det_pref(words):
    cnt =  {'':len(words)}
    for w_pfx in itertools.chain.from_iterable([[w[:i] for i in range(1,len(w)+1)] for  w in words]):
         cnt[w_pfx] = 1 + cnt.get(w_pfx,0)
    return max([w_pfx for (w_pfx,n) in cnt.items() if n/len(words)>0.7])

警告：由于此解决方案在循环期间没有提前退出和减少输入，因此效率低于原始代码。

这是一种更有效的方法，恕我直言，它仍然是 pythonic，但比我的第一个更难理解且更长：

def det_pref(words):
    cnt = dict()
    pfx_len = [len(w) for w in words]
    while any(pfx_len):
        for i,w_pfx in [(i,words[i][:l]) for i,l in enumerate(pfx_len)]:
            pfx_len[i] -= pfx_len[i] and 1 or 0
            n = 1 + cnt.get(w_pfx,0)
            if n/len(words)> 0.7:
                return w_pfx
            cnt[w_pfx] = n
    return ''
于 2014-03-25T10:23:42.253 回答