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

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，并且引号内的空格只是一个视觉效果。

- Alias_Knagg

---

期望的输出是什么？由于“''”是每个字符串的前缀，因此它始终是最常见的前缀；您是否接受“return ''”？ - user2357112

你是否正在寻找至少70％的输入字符串共享的最长前缀？ - user2357112

在Python 3.2.5中，该函数失败：Traceback（最近的调用最后）： File“<pyshell#11>”，第1行，在<module>中 detect_prefix（['foo_a'，'foo_b'，'foo_c'，'fnord']） File“<pyshell#7>”，第12行，在detect_prefix中 if cnt[max(cnt)] / float(l) >= PCT： ValueError：max（）arg是一个空序列 - Vroomfondel

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

- lvc

---

这很有趣，也是一种完全不同的方法。然而，我期望使用Pyinstaller打包我正在构建的工具，所以我不愿意依赖于标准库之外的东西。这可能不是问题，但还是有点犹豫。 - Alias_Knagg

Answer 2

如果您知道常见前缀的期望阈值频率：

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

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

- jfs

---

这个在 "strings = ['goo_a', 'fno_b','fox_c','foord']" 上失败了，输出为 "[('', 4), ('foo_', 3)]"，但是缺少有效的 'f' 前缀... - Vroomfondel

啊，抱歉，第一次看的时候我没有完全理解意思.. :D - Vroomfondel

基于简洁和速度，我接受这个答案。在我的应用程序中，第一个示例比我的稍微快一些，并且一旦移动导入，大小约为我的1/3。输入方面的假设在我的情况下似乎成立 :-) 感谢大家给我提供了一些不错的例子来思考。 - Alias_Knagg

Answer 3

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

- Vroomfondel

---

这可能并不像一些天真的时间表所显示的那样：detect_prefix函数花费了0.177毫秒，det_pref函数花费了0.543毫秒。否则，这正是我希望看到的 :) - Alias_Knagg

@Alias_Knagg：它必须失败。在Python 2.7中，5/7 == 0。 - jfs