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

Ответ 1

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

То, что вы хотите, это структура данных 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.

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

Ответ 2

Для каждого слова в словаре сортируйте буквы в алфавитном порядке. Таким образом, "foobar" становится "abfoor".

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

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

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

Ответ 3

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

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

Ответ 4

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

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

В момент поиска:

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

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

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

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

Ответ 5

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

Ответ 6

И здесь - мое новое решение.

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

С учетом словаря английских слов найдите все наборы анаграмм. Для например, "горшки", "стоп" и "вершины" - это все анаграммы друг друга потому что каждый может быть сформирован путем перестановки букв других.

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

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

каждое положительное целое число (кроме числа 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<String> 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;
        }
    }
}

Ответ 7

Книга "Программирование жемчуга" Джона Бентли прекрасно описывает этот материал. Обязательно прочитайте.

Ответ 8

Итак вот рабочее решение на 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<Set<String>> findAnagrams(int dictionaryIndex, char[] charInventory, List<String> 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<Set<String>> anagramsSet = new HashSet<Set<String>>();
        Set<String> anagramSet = new HashSet<String>();
        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<Set<String>> anagramsSet = new HashSet<Set<String>>();
            for (int index = dictionaryIndex + 1; index < keyList.size(); index++) {
                Set<Set<String>> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList);
                if (searchWordAnagramsKeysSet != null) {
                    Set<Set<String>> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet);
                    anagramsSet.addAll(mergedSets);
                }
            }
            return anagramsSet.isEmpty() ? null : anagramsSet;
        }
    }

    // no anagrams found for current word
    return null;
}

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

Ответ 9

Как я его вижу:

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

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

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

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

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

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

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

Ответ 10

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

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

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

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

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

Ответ 11

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

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

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

Ответ 12

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

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

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

Таким образом, любое слово, которое мы воспринимаем как последовательность индексов, таких как слово "привет", может быть представлено как "1234". Теперь анаграммы "1234" - "1243", "1242"..etc

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

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

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

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

Ответ 13

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

Ответ 14

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

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

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)

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

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