Наиболее практичная структура данных для последовательных уровней фильтрации. ⇐ Python

[Anonymous]

Я пишу программу для поиска шифров замены test_phrase, которые сами по себе являются допустимыми английскими фразами.

Пример: test_phrase = 'x отмечает точку' → ['все небо заканчивается', 'Я инсценирую наше эхо', ...]
Мой подход
Я фильтрую список слов, чтобы найти кандидатов (правильная структура) для каждого слова во фразе.

Пример: кандидатов['x'] = {'a', 'i', кандидатов['marks'] = {'adopt', 'angle', 'begin', ...
Но кандидаты на слово зависят от того, какой кандидат мы используем для другого слова.

Пример: For 'x отмечает точку', если мы заменим 'x' на 'a', в оставшихся словах не может быть 'a'.
Поэтому я сохраняю правила для каждого слова, определяющие, в какой позиции каждая из его букв должна первой появляться в каждом другом слове.

Пример: Rules['x'][0]['marks'] = -1 (где -1 означает буквы нет).
Затем при проверке кандидата я фильтрую других кандидатов на наличие слов, которые соответствуют его правилам.

Пример: (cand for cand в кандидатах['marks'] if Rules['x'][0]['marks'] == cand.find('a'))
В настоящее время я создаю действительные фразы по одному слову, проверяя, что следующее слово удовлетворяет всем правилам предыдущих слов.

Код: Выделить всё

phrases=((),)
for i,word in enumerate(test_words):                       #[(0,'x'), (1,'marks'), (2,'the'), (3,'spot')]
phrases = tuple(phrase + (cand,)
for phrase in phrases
for cand in candidates[word]
if all( rules[test_words[j]][k][word]  #word j, kth letter's position in word
== cand.find(phrase[j][k] )     #cand j, kth letter's position in cand
for j in range(i)               #previous words
for k in rules[test_words[j]])) #position of each unique letter in word j
print( sorted(' '.join(phrase) for phrase in phrases) )

Проблема
Это слишком медленно.

Пример: «x отмечает точку» заняло 4 часа.
Поскольку во многих словах используется одна и та же буква, они могут не соответствовать одному и тому же правилу. Вместо того, чтобы повторно перечислять действительных кандидатов, я бы хотел сохранить наборы слов, например, с «t» в качестве второй буквы. Моя первая мысль — использовать вложенный словарь.

Пример: cands['marks']['t'][1] — это слова с той же структурой, что и «marks», с буквой «t» в позиции 1.
Чтобы удовлетворить правилу, код проверит, есть ли уже соответствующий правилу набор в этом словаре, и если нет, создаст и сохранит его. Он будет использовать пересечение наборов, чтобы определить, какие кандидаты удовлетворяют правилам для каждой буквы.

Пример: фраза=('a', 'begin') → (cands['the']['a'][-1]) & (cands['the']['b'][-1] & cands['the']['e'][-1] & cands['the']['g'][-1] & cands['the']['i'][-1] & cands['the']['n'][-1])
Мне пришло в голову построить набор слов с 't', поскольку вторая буква могла бы быть быстрее, если бы мы уже сгенерировали набор слов с 't' в них.
Итак, если моя цель - получить доступ к набору слов, содержащих 't', и каким-то образом сохранить слова с 't' на более глубоком уровне во второй позиции (и в других позициях, если возникнет необходимость), существует ли структура, которая более подходит для такой последовательной фильтрации, чем отдельные вложенные словари?

Подробнее здесь: https://stackoverflow.com/questions/798 ... -filtering