找到字符串的*最*公共前缀更好的方法？

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

我想听听一些建议。在

编辑。 附加背景和说明。
这些是其他开发人员在应用程序中用于翻译的密钥。 它们应该有一个共同的前缀，但人们忘记了，于是从其他代码中剪切粘贴。”_“作为前缀分隔符只是惯例。最好不要假设使用了分隔符。70%是一个完全任意的阈值。”“最流行”或“占主导地位”也能起作用。
是的，这是Python2.7，引号内的空格只是一个可视的艺术品。在

Answer 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_

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

^{pr2}$

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

Answer 2

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])

警告：由于此解决方案在循环过程中没有早期输出和输入缩减，因此它的效率低于原始代码。在

这里有一个更有效的方法，它仍然是Python式的，但比我的第一个方法更难理解，时间也更长：

^{pr2}$

Answer 3

找到有特定前缀的事物的一个好方法是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_。在