Получить строку с наибольшим количеством префиксов

Question

У меня есть список строк, например:

py
python
co
comp
computer

Я просто хочу получить строку, которая содержит максимально возможное количество префиксов. Результат должен быть 'computer', потому что его префиксы - 'co' и 'comp' (2 префикса).

У меня есть этот код (список слов - словарь):

for i in wordlist:
    word = str(i)
    for j in wordlist:
        if word.startswith(j):
            wordlist[i] += 1
result = max(wordlist, key=wordlist.get)

Есть ли лучший, более быстрый способ сделать это?

Answer 1

Структура данных, которую вы ищете, называется Trie. Статья в Википедии об этом дереве поиска, безусловно, стоит прочитать. Ключевое свойство дерева, которое здесь пригодится, таково:

Все потомки узла имеют общий префикс строки, связанной с этим узлом, а корень связан с пустой строкой.

Код может выглядеть следующим образом:

words = """py
python
co
comp
computer""".split()

def make_trie(ws):
    """Build trie from word list `ws`."""
    r = {}  # trie root
    for w in ws:
        d = r
        for c in w:
            d = d.setdefault(c, {})  # get c, set to {} if missing
        d['$'] = '$' # end marker
    return r

def num_pref(t, ws):
    """Use trie `t` to find word with max num of prefixes in `ws`."""
    b, m = -1, ''  # max prefixes, corresp. word
    for w in ws:
        d, p = t, 1
        for c in w:
            if '$' in d: p += 1
            d = d[c]  # navigate down one level
        if p > b: b, m = p, w
    return b, m

t = make_trie(words)
print(num_pref(t, words))

make_trie строит дерево, num_pref использует его для определения слова с максимальным количеством префиксов. Это печатает (3, 'computer'),

Очевидно, что эти два метода могут быть объединены. Я держал их отдельно, чтобы сделать процесс построения дерева более понятным.

Answer 2

Для большого количества слов вы могли бы построить три.

Затем вы можете перебрать все листья и посчитать количество узлов (конечных узлов) со значением между корнем и листом.

Для n слов это должно потребовать O(n) шаги по сравнению с вашим O(n**2) решение.

Этот пакет выглядит хорошо, и вот связанная тема.

Answer 3

"Правильный" способ заключается в использовании некоторой структуры данных Trie или аналогичной. Однако, если ваши слова уже отсортированы, вы можете получить практическое ускорение с помощью некоторого довольно простого кода, который использует префиксный стек вместо поиска методом грубой силы. Это работает, поскольку в отсортированном порядке все префиксы предшествуют их префиксному слову (что облегчает получение результата с помощью простого линейного сканирования). Думайте об этом как о разумном компромиссе между простым кодом и эффективным кодом:

prefixes = []   # Stack of all applicable prefixes up to this point (normally very small)
max_prefixes = [None]
for w in sorted(wordlist):
    while prefixes and not w.startswith(prefixes[-1]):
        prefixes.pop()
    prefixes.append(w)
    if len(prefixes) >= len(max_prefixes):
        max_prefixes = list(prefixes)
result = max_prefixes[-1]

Работая над всеми словарными словами на моем компьютере с Linux (из них 479828), приведенный выше код занимает всего 0,68 секунды (оригинальный код не завершается за разумное время). На первых 10000 слов мой код занимает 0,02 секунды вместо 19,5 секунды исходного кода.

Если вам нужен действительно эффективный код (скажем, вы имеете дело с гигабайтами данных), вам лучше использовать правильные структуры данных, кодированные в кэш-памяти в Си, но для правильной записи может потребоваться несколько недель!