Поиск анаграмм для данного слова

Ответ 1

Пример алгоритма:

Open dictionary
Create empty hashmap H
For each word in dictionary:
  Create a key that is the word letters sorted alphabetically (and forced to one case)
  Add the word to the list of words accessed by the hash key in H

Чтобы проверить все анаграммы данного слова:

Create a key that is the letters of the word, sorted (and forced to one case)
Look up that key in H
You now have a list of all anagrams

Относительно быстро, чтобы строить, невероятно быстро в поиске.

Ответ 2

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

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

Вот код. Я конвертирую слово в UPPERCASE, а 65 - это позиция A, которая соответствует моему первому простому числу:

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 };

Это метод:

 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;
}

Ответ 3

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

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

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

Например, скажем 'A' = 65, 'B' = 66, затем length("AB") = sqrt(65*65 + 66*66). Очевидно, length("AB") = length("BA").

Ясно, что если два слова являются анаграммами, то их векторы имеют одинаковую длину. Следующий вопрос: если два слова (одинакового числа букв) векторов имеют одинаковую длину, являются ли они анаграммами? Интуитивно я бы сказал "нет", поскольку все векторы с этой длиной образуют сферу, их много. Не уверен, поскольку в этом случае мы находимся в целочисленном пространстве, сколько есть.

Но, по крайней мере, это позволяет вам разбить ваш словарь еще дальше. Для каждого слова в вашем словаре вычислите векторное расстояние: for(each letter c) { distance += c*c }; distance = sqrt(distance);

Затем создайте карту для всех слов длины n и введите ее с расстоянием, а значение - список слов длины n, которые дают это конкретное расстояние.

Вы создадите карту для каждого расстояния.

Затем ваш поиск станет следующим алгоритмом:

• Используйте правильную карту словаря в зависимости от длины слова
• Вычислить длину словарного вектора
• Поиск списка слов, соответствующих этой длине
• Пройдите список и выберите анаграммы с помощью наивного алгоритма, теперь список кандидатов значительно сокращен.

Ответ 4

Well Tries упростит проверку наличия слова. Поэтому, если вы поместили весь словарь в trie:

http://en.wikipedia.org/wiki/Trie

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

Trie помогает, потому что его хорошее условие остановки: Мы можем проверить, является ли часть строки, например "Anag", допустимым путем в trie, если мы не можем сломать эту ветвь рекурсивной ветки. Это означает, что нам не нужно проверять каждую перестановку символов.

В псевдокоде

checkAllChars(currentPositionInTrie, currentlyUsedChars, restOfWord)
    if (restOfWord == 0)
    {
         AddWord(currentlyUsedChar)
    }
    else 
    {
        foreach (char in restOfWord)
        {
            nextPositionInTrie = Trie.Walk(currentPositionInTrie, char)
            if (nextPositionInTrie != Positions.NOT_POSSIBLE)
            {
                checkAllChars(nextPositionInTrie, currentlyUsedChars.With(char), restOfWord.Without(char))
            }
        }   
    }

Очевидно, вам нужна хорошая структура данных Trie, которая позволяет вам постепенно "ходить" по дереву и проверять каждый node, если есть путь с данным char к любому следующему node...

Ответ 5

static void Main(string[] args)
{

    string str1 = "Tom Marvolo Riddle";
    string str2 = "I am Lord Voldemort";

    str2=  str2.Replace(" ", string.Empty);
    str1 = str1.Replace(" ", string.Empty);
    if (str1.Length != str2.Length)
        Console.WriteLine("Strings are not anagram");
    else
    {
        str1 = str1.ToUpper();
        str2 = str2.ToUpper();
        int countStr1 = 0;
        int countStr2 = 0;
        for (int i = 0; i < str1.Length; i++)
        {
            countStr1 += str1[i];
            countStr2 += str2[i];

        }
        if(countStr2!=countStr1)
            Console.WriteLine("Strings are not anagram");
        else Console.WriteLine("Strings are  anagram");

    }
    Console.Read();
}

Ответ 6

• Уменьшите слова до - скажем - в нижнем регистре (clojure.string/lower-case).
• Классифицируйте их (group-by) по буквенной частотной карте (frequencies).
• Отбросьте карты частот,
• ... оставляя коллекции анаграмм.

(These) - соответствующие функции на диалекте Lisp Clojure.

Вся функция может быть выражена так:

(defn anagrams [dict]
  (->> dict
       (map clojure.string/lower-case)
       (group-by frequencies)
       vals))

Например,

(anagrams ["Salt" "last" "one" "eon" "plod"])
;(["salt" "last"] ["one" "eon"] ["plod"])

Функция индексирования, которая отображает каждую вещь в ее коллекцию,

(defn index [xss]
  (into {} (for [xs xss, x xs] [x xs])))

Итак, чтобы, например,

((comp index anagrams) ["Salt" "last" "one" "eon" "plod"])
;{"salt" ["salt" "last"], "last" ["salt" "last"], "one" ["one" "eon"], "eon" ["one" "eon"], "plod" ["plod"]}

... где comp - оператор функциональной композиции.

Ответ 7

Создание всех перестановок легко, я думаю, вы обеспокоены тем, что проверка их существования в словаре - это "очень неэффективная" часть. Но это зависит от того, какую структуру данных вы используете для словаря: конечно, список слов будет неэффективным для вашего варианта использования. Говоря о Tries, они, вероятно, были бы идеальным представлением и довольно эффективным.

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

Ответ 8

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

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

• Обозначить словарь как D, текущий префикс как S. S = 0;
• Вы создаете частотную карту для своего слова. Обозначим его через F.
• Используя двоичный поиск, найдите указатели для начала каждой буквы в словаре. Обозначим этот массив указателей через P.
• Для каждого char c из A в Z, если F [c] == 0, пропустите его, иначе
  • S + = c;
  • F [c] -;
  • P < - для каждого символа я P [i] = указатель на первое слово, начинающееся с S + i.
  • Рекурсивно вызовите шаг 4, пока не найдете совпадение для вашего слова или пока не найдете, что такого совпадения не существует.

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

Ответ 9

попытался реализовать решение hashmap

public class Dictionary {

    public static void main(String[] args){

    String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};

    HashMap<String,String> h=new HashMap<String, String>();

    QuickSort q=new QuickSort();

    for(int i=0;i<Dictionary.length;i++){

        String temp =new String();

        temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog

        if(!h.containsKey(temp)){
           h.put(temp,Dictionary[i]);
        }

        else
        {
           String s=h.get(temp);
           h.put(temp,s + " , "+ Dictionary[i]);
        }
    }

    String word=new String(){"tolo"};

    String sortedword = q.quickSort(word);

    if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive

        System.out.println("anagrams from Dictionary   :  " + h.get(sortedword.toLowerCase()));
    }

}

Ответ 10

• Вычислить вектор счета частоты для каждого слова в словаре, вектор длины списка алфавита.
• генерирует случайный гауссовский вектор длины алфавитного списка

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

• С учетом нового тестового слова проецируйте его в том же случайном направлении, что и словарные слова.

• Сделайте двоичный поиск, чтобы найти список слов, которые сопоставляются с одним и тем же значением.
• Убедитесь, что каждое слово, полученное как указано выше, действительно является настоящей анаграммой. Если нет, удалите его из списка.
• Возвращает остальные элементы списка.

PS: Вышеприведенная процедура представляет собой обобщение процедуры простого числа, которая может потенциально привести к большим числам (и, следовательно, к проблемам с вычислительной точностью)

Ответ 11

Одно из решений - Перечислите простые числа в символы алфавита и умножьте простое число

For ex - 

    a -> 2
    b -> 3
    ......
    .......
    ......
    z -> 101

So

'ab' -> 6
'ba' -> 6
'bab' -> 18
'abba' -> 36
'baba' -> 36

Получить MUL_number для данного слова. верните все слова из словаря, которые имеют одинаковый MUL_number как заданное слово

Ответ 12

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