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

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%这个比例完全是随便定的。"最常见"或者"主要的"也可以用来描述。
对了，这段代码是用Python 2.7写的，双引号里的空格只是视觉上的效果。

Answer 1

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

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 ''

注意：因为这个解决方案在循环过程中没有提前退出和减少输入，所以它的效率比原来的代码要低。

这里有一个更高效的方法，我认为它仍然符合Python的风格，但比我第一个方法更难理解，也更长：

Answer 2

一种很好的方法来查找哪些东西有特定的前缀，就是使用一种叫做字典树的结构。我使用了一个叫做pytrie的实现，但它们的工作原理基本上是差不多的。唯一有趣的地方是，你仍然需要用其他方法生成所有的前缀，因为如果你问字典树“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_。

Answer 3

如果你知道想要的阈值频率，也就是常见前缀的频率：

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

这两个代码示例都假设有一个主要的前缀存在，也就是说，在每个位置上出现频率最高的字符属于这个最常见的前缀。