Алгоритм генерации анаграмм

Большинство из этих ответов ужасно неэффективны и / или будут давать только однословные решения (без пробелов). Мое решение будет обрабатывать любое количество слов и очень эффективно.

То, что вы хотите, это структура данных trie. Вот полная реализация Python. Вам просто нужен список слов, сохраненный в файле с именем words.txt Вы можете попробовать список словарных слов Scrabble здесь:

http://www.isc.ro/lists/twl06.zip

 MIN_WORD_SIZE = 4 # min size of a word in the output class Node(object): def __init__(self, letter='', final=False, depth=0): self.letter = letter self.final = final self.depth = depth self.children = {} def add(self, letters): node = self for index, letter in enumerate(letters): if letter not in node.children: node.children[letter] = Node(letter, index==len(letters)-1, index+1) node = node.children[letter] def anagram(self, letters): tiles = {} for letter in letters: tiles[letter] = tiles.get(letter, 0) + 1 min_length = len(letters) return self._anagram(tiles, [], self, min_length) def _anagram(self, tiles, path, root, min_length): if self.final and self.depth >= MIN_WORD_SIZE: word = ''.join(path) length = len(word.replace(' ', '')) if length >= min_length: yield word path.append(' ') for word in root._anagram(tiles, path, root, min_length): yield word path.pop() for letter, node in self.children.iteritems(): count = tiles.get(letter, 0) if count == 0: continue tiles[letter] = count - 1 path.append(letter) for word in node._anagram(tiles, path, root, min_length): yield word path.pop() tiles[letter] = count def load_dictionary(path): result = Node() for line in open(path, 'r'): word = line.strip().lower() result.add(word) return result def main(): print 'Loading word list.' words = load_dictionary('words.txt') while True: letters = raw_input('Enter letters: ') letters = letters.lower() letters = letters.replace(' ', '') if not letters: break count = 0 for word in words.anagram(letters): print word count += 1 print '%d results.' % count if __name__ == '__main__': main() 

Когда вы запускаете программу, слова загружаются в trie в памяти. После этого просто введите буквы, которые хотите найти, и распечатает результаты. Он будет показывать только результаты, которые используют все входные буквы, ничто не короче.

Он фильтрует короткие слова из результата, в противном случае количество результатов огромно. Не стесняйтесь настраивать настройку MIN_WORD_SIZE . Имейте в виду, что только использование «астрономов» в качестве входных данных дает 233 549 результатов, если MIN_WORD_SIZE равно 1. Возможно, вы можете найти более короткий список слов, который содержит только более распространенные английские слова.

Кроме того, сокращение «Я» (из одного из ваших примеров) не будет отображаться в результатах, если вы не добавите «im» в словарь и не установите MIN_WORD_SIZE в 2.

Трюк для получения нескольких слов заключается в том, чтобы вернуться к корневому узлу в trie всякий раз, когда вы сталкиваетесь с полным словом в поиске. Затем вы продолжаете пересекать три, пока не будут использованы все буквы.

Для каждого слова в словаре сортируйте буквы в алфавитном порядке. Поэтому «foobar» становится «abfoor».

Затем, когда вводится входная анаграмма, соберите ее буквы, а затем посмотрите. Это так же быстро, как поиск в hash-таблице!

Для нескольких слов вы можете делать комбинации отсортированных букв, сортируя их по ходу. Все еще намного быстрее, чем генерация всех комбинаций.

(см. комментарии для большей оптимизации и деталей)

См. Это задание в отделе CSE Университета Вашингтона.

В принципе, у вас есть структура данных, которая имеет только количество каждой буквы в слове (массив работает для ascii, обновляется до карты, если вы хотите поддерживать unicode). Вы можете вычесть два из этих наборов букв; если число отрицательно, вы знаете, что одно слово не может быть анаграммой другого.

Предварительная обработка:

Постройте три с каждым листом как известное слово, введенное в алфавитном порядке.

Во время поиска:

Рассмотрим входную строку как мультимножество. Найдите первое подслово, пройдя по индексу trie, как при первом поиске. В каждой ветви вы можете спросить, есть ли буква x в оставшейся части моего ввода? Если у вас хорошее представление мультимножества, это должен быть постоянный запрос времени (в основном).

Когда у вас есть первое подслово, вы можете сохранить остаток мультимножества и рассматривать его как новый вход, чтобы найти остальную часть этой анаграммы (если таковая существует).

Увеличьте эту процедуру с помощью memoization для более быстрого поиска по общим остальным мультимножествам.

Это довольно быстро – каждый trie traversal гарантированно дает фактическое подслово, и каждый обход занимает линейное время в длине подслова (а подсловные слова обычно довольно мелкие, по стандартам кодирования). Однако, если вы действительно хотите что-то еще быстрее, вы можете включить все n-граммы в ваш предварительный процесс, где n-грамм – любая строка из n слов в строке. Конечно, если W = #words, то вы перейдете от индекса O (W) к O (W ^ n). Возможно, n = 2 реалистично, в зависимости от размера вашего словаря.

Одним из основных работ по программным анаграммам был Майкл Мортон (Mr. Machine Tool), используя инструмент Ars Magna. Вот легкая статья, основанная на его работе.

Итак, вот рабочее решение на Java, которое предложил Джейсон Коэн, и он работает несколько лучше, чем тот, который использует trie. Ниже приведены некоторые из основных моментов:

• Загрузите словарь со словами, которые являются подмножествами заданного набора слов
• Словарь будет хешем отсортированных слов в качестве ключа и набора фактических слов в качестве значений (как предложил Джейсон)
• Перебирайте каждое слово из словарного ключа и выполняйте рекурсивный прямой поиск, чтобы узнать, найден ли какой-либо действительный анаграмма для этого ключа
• Только переадресуйте поиск, потому что, анаграммы для всех слов, которые уже пройдены, должны были быть найдены
• Слейте все слова, связанные с ключами, например, если «зачисление» – это слово, для которого нужно найти анаграммы, и один из ключей для слияния – [ins] и [elt], а фактические слова для ключа [ins ] является [sin] и [ins], а для ключа [elt] является [let], тогда окончательный набор слов слияния будет [sin, let] и [ins, let], который будет частью нашего окончательного списка анаграмм
• Также следует отметить, что в этой логике будет отображаться только уникальный набор слов, т.е. «одиннадцать плюс два» и «два плюс одиннадцать» будут одинаковыми, и только один из них будет указан в выводе

Ниже приведен главный рекурсивный код, который находит набор ключей анаграммы:

 // recursive function to find all the anagrams for charInventory characters // starting with the word at dictionaryIndex in dictionary keyList private Set> findAnagrams(int dictionaryIndex, char[] charInventory, List keyList) { // terminating condition if no words are found if (dictionaryIndex >= keyList.size() || charInventory.length < minWordSize) { return null; } String searchWord = keyList.get(dictionaryIndex); char[] searchWordChars = searchWord.toCharArray(); // this is where you find the anagrams for whole word if (AnagramSolverHelper.isEquivalent(searchWordChars, charInventory)) { Set> anagramsSet = new HashSet>(); Set anagramSet = new HashSet(); anagramSet.add(searchWord); anagramsSet.add(anagramSet); return anagramsSet; } // this is where you find the anagrams with multiple words if (AnagramSolverHelper.isSubset(searchWordChars, charInventory)) { // update charInventory by removing the characters of the search // word as it is subset of characters for the anagram search word char[] newCharInventory = AnagramSolverHelper.setDifference(charInventory, searchWordChars); if (newCharInventory.length >= minWordSize) { Set> anagramsSet = new HashSet>(); for (int index = dictionaryIndex + 1; index < keyList.size(); index++) { Set> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList); if (searchWordAnagramsKeysSet != null) { Set> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet); anagramsSet.addAll(mergedSets); } } return anagramsSet.isEmpty() ? null : anagramsSet; } } // no anagrams found for current word return null; } слово для // recursive function to find all the anagrams for charInventory characters // starting with the word at dictionaryIndex in dictionary keyList private Set> findAnagrams(int dictionaryIndex, char[] charInventory, List keyList) { // terminating condition if no words are found if (dictionaryIndex >= keyList.size() || charInventory.length < minWordSize) { return null; } String searchWord = keyList.get(dictionaryIndex); char[] searchWordChars = searchWord.toCharArray(); // this is where you find the anagrams for whole word if (AnagramSolverHelper.isEquivalent(searchWordChars, charInventory)) { Set> anagramsSet = new HashSet>(); Set anagramSet = new HashSet(); anagramSet.add(searchWord); anagramsSet.add(anagramSet); return anagramsSet; } // this is where you find the anagrams with multiple words if (AnagramSolverHelper.isSubset(searchWordChars, charInventory)) { // update charInventory by removing the characters of the search // word as it is subset of characters for the anagram search word char[] newCharInventory = AnagramSolverHelper.setDifference(charInventory, searchWordChars); if (newCharInventory.length >= minWordSize) { Set> anagramsSet = new HashSet>(); for (int index = dictionaryIndex + 1; index < keyList.size(); index++) { Set> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList); if (searchWordAnagramsKeysSet != null) { Set> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet); anagramsSet.addAll(mergedSets); } } return anagramsSet.isEmpty() ? null : anagramsSet; } } // no anagrams found for current word return null; } 

Вы можете разблокировать репо и играть с ним. Есть много оптимизаций, которые я, возможно, пропустил. Но код работает и находит все анаграммы.

И вот мое новое решение.

Книга Джона Бентли «Программирование жемчуга» содержит проблему поиска анаграмм слов. Заявление:

Учитывая словарь английских слов, найдите все наборы анаграмм. Например, «горшки», «стоп» и «вершины» – это все анаграммы друг друга, потому что каждый из них может быть сформирован путем перестановки букв других.

Я немного подумал, и мне пришло в голову, что решение будет заключаться в получении подписи слова, которое вы ищете, и сравнения его со всеми словами в словаре. Все анаграммы слова должны иметь одну и ту же подпись. Но как этого добиться? Моя идея состояла в том, чтобы использовать основную теорему арифметики:

Основная теорема арифметики утверждает, что

каждое положительное целое число (кроме числа 1) может быть представлено в точности одним способом, кроме перегруппировки, как произведение одного или нескольких простых чисел

Поэтому идея состоит в том, чтобы использовать массив из первых 26 простых чисел. Тогда для каждой буквы слова мы получаем соответствующее простое число A = 2, B = 3, C = 5, D = 7 … и затем вычисляем произведение нашего входного слова. Затем мы делаем это для каждого слова в словаре, и если слово соответствует нашему входному слову, мы добавляем его в результирующий список.

Производительность более или менее приемлема. Для словаря из 479828 слов для получения всех анаграмм требуется 160 мс. Это примерно 0,0003 мс / слово или 0,3 микросекунд / слово. Сложность алгоритма представляется O (mn) или ~ O (m), где m – размер словаря, а n – длина входного слова.

Вот код:

 package com.vvirlan; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Date; import java.util.List; import java.util.Scanner; public class Words { private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 }; public static void main(String[] args) { Scanner s = new Scanner(System.in); String word = "hello"; System.out.println("Please type a word:"); if (s.hasNext()) { word = s.next(); } Words w = new Words(); w.start(word); } private void start(String word) { measureTime(); char[] letters = word.toUpperCase().toCharArray(); long searchProduct = calculateProduct(letters); System.out.println(searchProduct); try { findByProduct(searchProduct); } catch (Exception e) { e.printStackTrace(); } measureTime(); System.out.println(matchingWords); System.out.println("Total time: " + time); } private List matchingWords = new ArrayList<>(); private void findByProduct(long searchProduct) throws IOException { File f = new File("/usr/share/dict/words"); FileReader fr = new FileReader(f); BufferedReader br = new BufferedReader(fr); String line = null; while ((line = br.readLine()) != null) { char[] letters = line.toUpperCase().toCharArray(); long p = calculateProduct(letters); if (p == -1) { continue; } if (p == searchProduct) { matchingWords.add(line); } } br.close(); } private long calculateProduct(char[] letters) { long result = 1L; for (char c : letters) { if (c < 65) { return -1; } int pos = c - 65; result *= PRIMES[pos]; } return result; } private long time = 0L; private void measureTime() { long t = new Date().getTime(); if (time == 0L) { time = t; } else { time = t - time; } } } 

Книга « Программирование жемчуга » Джона Бентли довольно хорошо описывает этот материал. Обязательное чтение.

Как я вижу это:

вы хотите создать таблицу, которая отображает неупорядоченные наборы букв в списки слов, то есть через словарь, чтобы вы могли завершить, скажем,

 lettermap[set(a,e,d,f)] = { "deaf", "fade" } 

то из вашего стартового слова вы найдете набор букв:

  astronomers => (a,e,m,n,o,o,r,r,s,s,t) 

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

Редактировать: hmmm, это в значительной степени то, что написал Джейсон Коэн.

edit: кроме того, комментарии по вопросу упоминаются, генерируя «хорошие» анаграммы, например, примеры :). после того, как вы создадите список всех возможных анаграмм, запустите их через WordNet и найдите те, которые семантически близки к исходной фразе 🙂

Я использовал следующий способ вычисления анаграмм пару месяцев назад:

• Вычислите «код» для каждого слова в словаре: создайте таблицу поиска из букв в алфавите в простые числа, например, начиная с [‘a’, 2] и заканчивая на [‘z’, 101]. В качестве этапа предварительной обработки вычислите код для каждого слова в вашем словаре, просмотрев простое число для каждой буквы, оно состоит из таблицы поиска и умножает их вместе. Для последующего поиска создайте мультимап кодов для слов.

• Вычислите код вашего входного слова, как описано выше.

• Вычислить codeInDictionary% inputCode для каждого кода в multimap. Если результат равен 0, вы нашли анаграмму, и вы можете найти соответствующее слово. Это также работает для анаграмм 2 или более слов.

Надеюсь, это было полезно.

Некоторое время назад я написал сообщение в блоге о том, как быстро найти две текстовые анаграммы. Он работает очень быстро: поиск всех 44 двухсловных анаграмм для слова с текстовым файлом объемом более 300 000 слов (4 мегабайта) занимает всего 0,6 секунды в программе Ruby.

Два алгоритма поиска аналоговых слов (в Ruby)

Возможно сделать приложение быстрее, когда ему разрешено препроцессировать список слов в большое хеш-отображение из слов, отсортированных по буквам, в список слов, используя эти буквы. Эти предварительно обработанные данные могут быть сериализованы и использованы с этого момента.

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

Теперь, если нам нужно сгенерировать все допустимые анаграммы, нам нужно проверить, есть ли сгенерированная анаграмма в словаре, если она присутствует в словаре, ее действительная другая, которую мы должны игнорировать.

Я предполагаю, что может быть слово из 100 символов (или больше, но есть предел).

Поэтому любое слово, которое мы воспринимаем как последовательность индексов типа слова «привет», может быть представлено как «1234». Теперь анаграммы «1234» – «1243», «1242» ..etc

Единственное, что нам нужно сделать, это сохранить все такие комбинации индексов для определенного количества символов. Это одноразовая задача. И тогда слова могут быть сгенерированы из комбинаций, выбирая символы из индекса. Мы получаем анаграммы.

Чтобы проверить, являются ли анаграммы действительными или нет, просто проиндексируйте словарь и подтвердите его.

Единственное, что нужно обработать, это дубликаты. Это можно сделать легко. Как когда нам нужно сравнить с предыдущими, которые были найдены в словаре.

Решение подчеркивает производительность.

В верхней части моей головы решение, которое имеет наибольший смысл, заключалось бы в том, чтобы случайно выбрать букву из входной строки и отфильтровать словарь на основе слов, которые начинаются с этого. Затем выберите другую, отфильтруйте вторую букву и т. Д. Кроме того, отфильтруйте слова, которые не могут быть сделаны с остальным текстом. Затем, когда вы нажмете конец слова, вставьте пробел и начните его с оставшихся букв. Вы также можете ограничить слова на основе типа слова (например, у вас не было бы двух глаголов рядом друг с другом, у вас не было бы двух статей рядом друг с другом и т. Д.).

1. Как предложил Джейсон, подготовьте словарь, создающий hash-таблицу с ключевым словом, отсортированным в алфавитном порядке, и само слово значения (у вас может быть несколько значений на ключ).
2. Удалите пробелы и отсортируйте свой запрос, прежде чем искать его.

После этого вам нужно будет сделать какой-то рекурсивный, исчерпывающий поиск. Псевдокод очень грубо:

 function FindWords(solutionList, wordsSoFar, sortedQuery) // base case if sortedQuery is empty solutionList.Add(wordsSoFar) return // recursive case // InitialStrings("abc") is {"a","ab","abc"} foreach initialStr in InitalStrings(sortedQuery) // Remaining letters after initialStr sortedQueryRec := sortedQuery.Substring(initialStr.Length) words := words matching initialStr in the dictionary // Note that sometimes words list will be empty foreach word in words // Append should return a new list, not change wordSoFar wordsSoFarRec := Append(wordSoFar, word) FindWords(solutionList, wordSoFarRec, sortedQueryRec) 

В конце концов, вам нужно выполнить итерацию через список решений и напечатать слова в каждом подсписке с пробелами между ними. Возможно, вам придется распечатать все заказы для этих случаев (например, «Я Сэм» и «Сэм я» – оба решения).

Конечно, я не тестировал это, и это подход грубой силы.