python - 找到*最*常见的字符串前缀 - 更好的方法？

Question

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

此处所有类似的解决方案都假定您的文本中没有 fnord。

我有这段代码可以完成这项工作:

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 现在还不够强大。

我很想听听一些建议。

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

Answer 1

如果您知道公共(public)前缀所需的阈值频率:

#!/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)]

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