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

Question

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

py 
python 
co 
comp 
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.

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

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

Этот package выглядит хорошо, и вот thread.

Answer 2

Структура данных, которую вы ищите, называется 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 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.68s секунд (исходный код Безразлично» t в течение разумного промежутка времени). На первых 10000 словах мой код принимает 0.02s вместо 19.5s взято по оригинальному коду.

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