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

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

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

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

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

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

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

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

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

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

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

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

edit: хммм, это в значительной степени то, что опубликовал Джейсон Коэн.

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

1. Как предложил Джейсон, подготовьте словарь, создающий хеш-таблицу с ключевым словом, отсортированным по алфавиту, и само слово значения (у вас может быть несколько значений для каждого ключа).
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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Книга Жемчуг программирования Джона Бентли довольно хорошо освещает этот вопрос. Обязательно к прочтению.

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

Алгоритм поиска анаграмм из двух слов (на Ruby)

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

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

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

Вам нужна структура данных 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()

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

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

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

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

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

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

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

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

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

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

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

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

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

• Загружать словарь только со словами, которые являются подмножествами данного набора слов
• Словарь будет представлять собой хеш отсортированных слов в качестве ключа и набор фактических слов в качестве значений (как предложил Джейсон)
• Перебирайте каждое слово из словарного ключа и выполняйте рекурсивный прямой поиск, чтобы увидеть, найдена ли какая-либо допустимая анаграмма для этого ключа.
• Выполняйте только прямой поиск, потому что анаграммы для всех слов, которые уже были пройдены, уже должны были быть найдены
• Объедините все слова, связанные с ключами, например, если «enlist» - это слово, для которого должны быть найдены анаграммы, и один из наборов ключей для слияния - это [ins] и [elt], а фактические слова для key [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;
}

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

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

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

Given a dictionary of english words, find all sets of anagrams. For instance, “pots”, “stop” and “tops” are all anagrams of one another because each can be formed by permuting the letters of the others.

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

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

every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes

Итак, идея состоит в том, чтобы использовать массив из первых 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;
        }
    }
}