Нахождение анагарам (ов) словарных слов

Question

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

Имеет ли java класс словаря английского языка (список слов), который я могу использовать, или есть реализации с открытым исходным кодом этого?

Как я могу оптимизировать мой код, если это нужно делать повторно?

Answer 1

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

Answer 2

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

Проверка на анаграмму заключается в сортировке букв обоих слов и проверке на равенство:

sort_letters(word1) == sort_letters(word2)

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

Если нам придется делать это многократно, лучше выполнить некоторую предварительную обработку . Мы можем построить что-то вроде HashMap, где мы могли бы сопоставить string с набором strings, которые являются анаграммами. Что-то вроде:

Bad ==> Dab
Cat ==> Act, Tac
.....

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

Answer 3

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

   if(hashFunc(word1) == hashFunc(word2)) -> word2 is anagram of word1     

Имеет ли java класс словаря английского языка (список слов), который я могу использовать, или есть реализации с открытым исходным кодом этого?

В системах Unix вы можете начать с файла слов

Как я могу оптимизировать мой код, если это нужно делать повторно?

Превратить словарь в хеш-таблицу, используя предварительно вычисленный hashFunc.

Answer 4

Как упомянуто unicornaddict , вы можете довольно легко определить, являются ли два слова анаграммами путем сортировки, однако это неэффективно, особенно если вы делаете это неоднократно.

Подготовленная хеш-таблица, вероятно, будет лучшим решением, загрузив в нее свой словарь в начале программы. Довольно простой для написания алгоритм хеширования / сравнения будет

uint HashSomeWord(string someWord)
{
   uint hashVal = 0;
   //foreach letter in someword
   {
      //hashVal += letter.ValueAsInteger
   }
   return hashVal;
}

затем

bool IsAnagram(string inputWord, string compareTo)
{
    if(inputWord == null
       || compareTo == null
       || inputWord.Length != compareTo.Length
       || HashSomeWord(inputWord) != HashSomeSome(compareTo))
    {
       return false;
    }
    if(sort_letters(inputWord) == sort_letters(compareTo))
    {
        return true;
    }
}

Моя Java довольно ржавая, но я думаю, что это сделает.

Answer 5

Вы можете использовать Пример Anagrams2 с сайта Sun в качестве отправной точки

Для повышения производительности вы можете иметь кеш анаграмм для часто используемых / недавно использованных слов. Рассмотрите использование WeakHashMap для этой цели