Работа с анаграммами, как можно оптимизировать скрипт?

Скрипт работает по такому алгоритму:
  1. Вводим слово
  2. Из введённого слова делаем анаграммы
  3. Полученные анаграммы сравниваем со словами из списка
  4. Если есть совпадения то выводим в консоль

В словаре 109581 слов. Самое длинное слово - antidisestablishmentarianism в котором количество букв - 28.
На данный момент если в ведённом слове больше 8 букв, то скрипт очень долго обрабатывает данные. Если ввести слово с большим количеством букв, выскакивает исключение OutOfMemory.

Нужно:
  1. Избавиться от OutOfMemory
  2. Ускорить работу скрипта

Функция возвращающая список анаграмм из заданного слова:
anagrams
def anagrams(s):
    n=len(s)
    if n == 1:
        return s
    sb=[]
    for i in range(n):
        sb.append(s[i])
        rval=anagrams(s[0:i]+s[i+1:n])
        if isinstance(rval,str):
            sb[i]=sb[i]+rval
        if isinstance(rval,list):
            c=sb[i]
            sb[i]=[c + rval[x] for x in range(len(rval))]
    if(n==2):
        return sb
    else:
        c=[sb[x][h] for x in range(len(sb)) for h in range(len(sb[x]))]
        return c


Функция сравнивающая два списка и возвращающая совпадения:
find_word
def find_word(list,source):
    L = []
    for item in list:
        if item in source and item not in L:
            L.append(item)
    if L:
        print('Matches found', len(L))
        print(L)
    else:
        print('No matches found')


Python 3.4.2
Подскажите, расскажите, объясните ибо своего опыта на это не хватает(
  • Вопрос задан
  • 4354 просмотра
Решения вопроса 1
@throughtheether
human after all
Функция возвращающая список анаграмм из заданного слова
Рекомендую присмотреться к модулю itertools, в частности, функции permutations. Примерный код:
import itertools
def anagrams(word):
	for permutation in itertools.permutations(word):
		yield ''.join(permutation)

for word in anagrams('car'):
    print(word)
car
cra
acr
arc
rca
rac

В случае повторения букв в слове анаграммы тоже будут содержать дубли:
>>> for word in anagrams('rar'):
	print word
rar
rra
arr
arr
rra
rar

Функция сравнивающая два списка и возвращающая совпадения
Если я правильно понял, вы держите в памяти списки анаграмм и словарных слов и ищете (линейным поиском) их пересечение. Это, на мой взгляд, не вполне эффективно. Я бы поступил так:
words=['car','arc','cat','map','toster']
wordset=set(words)
for word in anagrams('car'):
   if word in wordset:
        print ("word %s matched vocabulary" % word)

Если и этого не хватит, то можно будет, на мой взгляд, подумать об использовании фильтров Блума.
UPD: Как я понял, основная проблема в количестве анаграмм.
Вводим слово
Из введённого слова делаем анаграммы
Вы можете с самого начала для каждого слова из словаря запомнить его 'отсортированный' вариант:
words=['car','arc','cat','map','toster']
sortedwordset=set(''.join(sorted(w)) for w in words)
>>> sortedwordset
set(['acr', 'eorstt', 'amp', 'act'])
Тогда для каждого введенного слова можно проверить, имеет ли смысл составлять анаграммы:
if ''.join(sorted(word)) in sortedwordset:
    #continue with anagrams

UPD2: Можно, на мой взгляд, сделать так: для каждого слова из словаря формируется его 'отсортированная' форма. Эта форма будет ключом словаря, а значением - список словарных слов, являющихся анаграммами этой формы. Тогда за счет предварительных вычислений можно будет быстро искать словарные анаграммы:
def sorted_string(s):
	return ''.join(sorted(s))

words=['car','arc','cat','map','toster']
d={}
for word in words:
	sorted_word=sorted_string(word)
	if sorted_word in d:
		d[sorted_word].append(word)
	else:
	    d[sorted_word]=[word]
>>> d
{'acr': ['car', 'arc'], 'eorstt': ['toster'], 'amp': ['map'], 'act': ['cat']}
>>> d.get(sorted_string('car'),[])
['car', 'arc']
>>> d.get(sorted_string('cat'),[])
['cat']
>>> d.get(sorted_string('perkele'),[])
[]
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
adugin
@adugin Куратор тега Python
Расчёт анаграмм (permutations) здесь не требуется (пп. 2 и 3 - вводят в заблуждение).
Поэтому скорость выполнения представленного ниже кода не зависит от длины слова.
На базе в 20.000 слов выполняется мгновенно даже с 'antidisestablishmentarianism':
from collections import Counter
from itertools import ifilter

def criteria(dictword):
    return (
        wlen == len(dictword) and
        wset == set(dictword) and
        wcnt == Counter(dictword)
    )

while True:

    word = raw_input('\nEnter word: ')
    wlen, wset, wcnt = len(word), set(word), Counter(word)

    with open('thesaurus.txt') as f:
        thesaurus = (line.rstrip() for line in f)
        for dictword in ifilter(criteria, thesaurus):
            print dictword

    if word in {'exit', 'quit'}:
        break
Ответ написан
Lerg
@Lerg
Defold, Corona, Lua, GameDev
Можно не хранить все анаграммы в одном массиве: сделали перестановку, проверили в базе слов, затем следующую перестановку. Это избавит от OutOfMemory проблемы. Но прибавит немного времени, так как будут повторения.

Затем можно разбить базу слов на 28 отдельных баз, где хранятся слова только определённой длинны. Должно немного ускорить поиск.

А вот как сделать быстрее - я бы использовал другой язык программирования (Go, C, Java) и попытался бы распараллелить процесс на потоки.
Ответ написан
mannaro
@mannaro
Умею профессионально гуглить
Для начала подготовьте свой словарь.

1) Создайте новый хеш.
2) Перебираем весь словарь.
2.1) Разбиваем текущее слово на буквы, сортируем их, склеиваем.
2.2) Проверяем, есть ли в хеше такой ключ.
2.2.1) Если нет - то создаем hash[key] = [] (пустой массив)
2.2.2) Если да, то в массив добавляем текущее слово.
3) Подготовка окончена. Сохраняем текущий хеш и используем везде его.
4) Функция сравнения: берем слово, разбиваем по буквам, сортируем, склеиваем.
5) Проверяем наличие этого ключа в нашем словаре. Выводим результат.

Пример на JS: jsfiddle.net/6bz8g9gz
Пример на питоне:
dict = ['wolf','flow','hello','world','folw','jack','open','close','nepo','peno','kill'];

def prepare(d):
  hash = {};
  for v in d:
    v = v.lower()
    list = [c for c in v]
    list.sort()
    result = "".join(list)
    if hash.has_key(result):
      hash[result].append(v)
    else:
      hash[result] = [v]
  return hash

def test(word, d):
  word = word.lower()
  list = [c for c in word]
  list.sort()
  result = "".join(list)
  if d.has_key(result) and len(d[result]) != 0:
    return d[result]
  else:
    return False

d = prepare(dict)
print test("WolF", d)
Ответ написан
half-life
@half-life Автор вопроса
Всем спасибо. Решение найдено. Всё работает быстро и как задумывалось. Отдельная благодарность throughtheether и Sergey Lerg

Саша Вам тоже спасибо, хотя ваш пример у меня так и не запустился.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
01 авг. 2021, в 13:03
1000 руб./за проект
01 авг. 2021, в 12:46
4000 руб./за проект
01 авг. 2021, в 11:17
30000 руб./за проект