Python - Code Optimization Help - Найти все действительные в словаре анаграммы слова - PullRequest
Новая
       16

Python - Code Optimization Help - Найти все действительные в словаре анаграммы слова

2 голосов
/ 21 мая 2011

Я решил проблему, используя этот (ужасно неэффективный метод): 

def createList(word, wordList):
    #Made a set, because for some reason permutations was returning duplicates.  
    #Returns all permutations if they're in the wordList

    return set([''.join(item) for item in itertools.permutations(word) if ''.join(item) in wordList])

def main():

    a = open('C:\\Python32\\megalist.txt', 'r+')
    wordList = [line.strip() for line in a]
    maximum = 0
    length = 0
    maxwords = ""

    for words in wordList:
        permList = createList(words, wordList)
        length = len(permList)
        if length > maximum:
            maximum = length
            maxwords = permList
    print (maximum, maxwords)

Потребовалось около 10 минут, чтобы найти пятибуквенное слово, содержащее большинство анаграмм, допустимых для словаря.Я хочу выполнить это на словах без ограничения буквы, но это заняло бы смехотворное количество времени.Есть ли способ оптимизировать это?

Ответы [ 3 ]

3 голосов
/ 21 мая 2011

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

Если вам нужно добавить ограничения на количество букв, использование итераторов - удобный способ отфильтровать некоторые слова. 

def wordIterator(dictionaryFilename):
    with open(dictionaryFilename,'r') as f:
        for line in f:
            word = line.strip()
            yield word

def largestAnagram(words):
    import collections
    d = collections.defaultdict(list)
    for word in words:
        sortedWord = str(sorted(word))
        d[ hash(sortedWord) ].append(word)
    maxKey = max( d.keys(), key = lambda k : len(d[k]) )
    return d[maxKey]

iter = wordIterator( 'C:\\Python32\\megalist.txt' )
#iter = ( word for word in iter if len(word) == 5 )
print largestAnagram(iter)

Edit:

В ответ на комментарий hash(sortedWord) - это оптимизация экономии места, возможно, преждевременная в этом случае, чтобы уменьшить sortedWord обратно до целого числа, потому что нам не важен ключ, пока мы можем всегда однозначно восстанавливайте все соответствующие анаграммы. Было бы одинаково правильно использовать просто sortedWord в качестве ключа.

Аргумент key для ключевого слова max позволяет найти максимальный элемент в коллекции на основе предиката. Таким образом, оператор maxKey = max( d.keys(), key = lambda k : len(d[k]) ) является кратким выражением Python для ответа на запрос, с учетом ключей в словаре, с каким ключом связано значение максимальной длины? . Этот вызов max в этом контексте мог бы быть записан (гораздо более многословно) как valueWithMaximumLength(d), где эта функция была определена как: 

def valueWithMaximumLength( dictionary ):
    maxKey = None
    for k, v in dictionary.items():
        if not maxKey or len(dictionary[maxKey]) < len(v):
            maxKey = k
    return maxKey
2 голосов
/ 21 мая 2011

wordList должно быть set.

Проверка членства в списке требует, чтобы вы просмотрели все элементы списка, проверяя, являются ли они словом, которое вы сгенерировали. Участие в тестировании набора (в среднем) не зависит от размера набора.

Следующая очевидная оптимизация заключается в том, что после того, как вы проверили слово, вы можете удалить все его перестановки из wordList, поскольку они будут давать точно такой же набор в createList. Это очень простая операция, если все сделано с set s - действительно, вы просто используете двоичный минус.

1 голос
/ 21 мая 2011

Нет необходимости делать ВСЕ перестановки, - это пустая трата памяти и процессора. Итак, прежде всего ваш словарь должен храниться в двоичном дереве, например: 

   e.g. Dict = ['alex', 'noise', 'mother', 'xeal', 'apple', 'google', 'question']

   Step 1: find the "middle" word for the dictionary, e.g. "mother", because "m" 
           is somewhere in the middle of the English alphabet 
           (this step is not necessary, but it helps to balance the tree a bit)

   Step 2: Build the binary tree:

               mother 
              /      \
             /        \
         alex          noise
           \            /  \
            \          /    \
           apple   question xeal
             \
              \
             google

  Step 3: start looking for an anagram by permutations:
  alex: 1. "a"... (going deeper into binary tree, we find a word 'apple')
        1.1 # of, course we should omit apple, because len('apple') != len('alex')
            #  but that's enough for an example:
        2. Check if we can build word "pple" from "lex": ("a" is already reserved!)
           -- there is no "p" in "lex", so skipping, GOTO 1            
        ... 
        1. "l"... - nothing begins with "l"...
        1. "l"... - nothing begins with "e"...
        1. "x" - going deeper, "xeal" found
        2. Check if "eal" could be built from "ale" ("x" is already reserved)
           for letter in "eal":
               if not letter in "ale":
                  return False
           return True

Вот и все :) Этот алгоритм должен работать намного быстрее.

EDIT:

Установите флажок bintrees , чтобы не тратить время на реализацию двоичного дерева.

...