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

Question

[Ник В]

Скрипт работает по такому алгоритму:

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
Подскажите, расскажите, объясните ибо своего опыта на это не хватает(

Answer 1

[throughtheether]

Функция возвращающая список анаграмм из заданного слова

Рекомендую присмотреться к модулю 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'),[])
[]

Comments

[Александр Вульф]

UPD2 я уже продожил (: За 6 минут до.

[Ник В]

def word_source():
    word_list = []
    sorted_words = {}
    sourse = open(PATH_TO_DICT, 'r')
    for line in sourse:
        line = line.strip("\n")
        word_list.append(line)

    for word in word_list:
        sorted_word = sorted_string(word)
        if sorted_word in sorted_words:
            sorted_words[sorted_word].append(word)
        else:
            sorted_words[sorted_word]=[word]
    return sorted_words

sorted_word_dictionary = word_source()

while True:
        wrd = input("Enter String: ").strip()
        if wrd == 'exit()':
            print('Script stopped')
            exit()
        if not ''.join(sorted(wrd)) in sorted_word_dictionary:
            print('No matches found')
        else:
            print('Matches found')

[throughtheether]

Саша: Вы молодец, а я буду почаще нажимать F5 перед ответом.

Answer 2

[Andrey Dugin]

Расчёт анаграмм (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

Answer 3

[Sergey Lerg]

Можно не хранить все анаграммы в одном массиве: сделали перестановку, проверили в базе слов, затем следующую перестановку. Это избавит от OutOfMemory проблемы. Но прибавит немного времени, так как будут повторения.

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

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

Comments

[Ник В]

Хорошая идея) Буду пробовать. Но надо на питоне сделать.

[Sergey Lerg]

@half-life: и для базы слов нужно использовать хэш массив (dict), чтобы слова искались по хэшу, а не перебором.

[Ник В]

Есть файл со словами. Там 109581 слово. Можете пример привести как это сделать.?

[Sergey Lerg]

@half-life: Если sourse типа List, то скрипт будет работать намного медленнее, чем если бы он был Dict. В вашем примере какой используется тип не понятно, поэтому убедитесь, что загружаете данные в Dict.
Кстати sourCe, а не sourSe.

source = {}
for line in file:
source[line] = true

[Ник В]

Спасибо, не заметил опечатку.

def word_source():
anagrams = []
word_list = open(PATH_TO_DICT, 'r')
for line in word_list:
line = line.strip("\n")
anagrams.append(line)
return anagrams

вот так было изначально. Получался список со словами из файла. Теперь, если я правильно вас понял, мне надо сделать не список, а словарь?

[Sergey Lerg]

@half-life: именно, сразу увидите большой прирост скорости и не нужно ничего параллелить.

[Ник В]

эм.. должен получаться словарь вида {'agronomies': True, 'abashing': True, 'ablutions': True, 'abominably': True} ?

[Sergey Lerg]

@half-life: Да.

[Ник В]

Спасибо. Итак, надо сделать что то типа такого:
получить словарь, (можно разбить его на несколько словарей в зависимости от количества символов в слове (допустим от 1 до 30)), не хранить все анаграммы в одном массиве, проверять сразу после перестановки букв в анаграмме.

[Sergey Lerg]

@half-life: Да. Ниже @throughtheether привёл хороший пример.

Answer 4

[Александр Вульф]

Для начала подготовьте свой словарь.

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)

Comments

[Ник В]

Что то вы намудрили
if hash.has_key(result):
AttributeError: 'dict' object has no attribute 'has_key'

[Александр Вульф]

@half-life: runnable.com/VFgNB-yfL7pbvhOZ/ana_python

[Илья]

Саша: шикарное решение. Только в prepare вместо dict писать d. Или принимающий аргумент сделать dict, а не d.

[Александр Вульф]

@FireGM: я не знаю питон =) Выучил, чтобы ответить на этот вопрос :D

[Александр Вульф]

@FireGM: a, все, понял =) Исправил.

Answer 5

[Ник В]

Всем спасибо. Решение найдено. Всё работает быстро и как задумывалось. Отдельная благодарность throughtheether и Sergey Lerg

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

Comments

[throughtheether]

рад был помочь